International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B2. Istanbul 2004
And finally, GA is a general search method (Goldberg, 1989).
It uses analogs of genetic operators on a population of states in
a search space to find those states that have high fitness values.
In optimization problems, genetic operators and coding
methods are designed in advance so that the individuals may
satisfy the constraints. In contrast, the objective of constraint
satisfaction problems (CSPs) is to find an individual that
satisfied constraints as the fitness value. Search in usual GA,
based on neo-Darwinian evolutionary theory is conducted by
crossover and mutation. Crossover is generally considered a
robust search means. Offspring may inherit partial solutions
without conflict from their parents, but no information to decide
which genes are partial solutions is available. From a search-
strategic point of view this means that variables are randomly
selected and then values which will be assigned to them are
also randomly selected from genes contained within a
population. Therefore search by crossover in GA can not be
considered efficient. Furthermore, mutation is a random search
method itself. When we think about efficiency of global search
that is the most important characteristic of GA; we must admit
that the rate of search is low, because GA stresses random
search rather than directional search. It can be considered that
the above problem is directly inherited from problems of the
neo-Darwinian evolutionary theory.
In the following sections, we first explain our basic strategies.
Next, we describe the fitness function, genetic operators.
Finally, we show the experimental results using an actual road
map.
3. STRATEGIES
Due to the advantages and disadvantage we mentioned in the
previous section, we plan to improve the rate of search by
giving direction to evolution that is search using crossover and
virus theory of evolution (Nakahara et al., 1986).
Domain specific knowledge, as partial solutions of problems, is
usually introduced into an initial population. Partial solutions
are considered to be viruses, and a population of viruses is
created as well as a population of individuals.
Our solution using the GA is based on the following basic
strategies:
e Any segment of an arterial road is regarded as a
main virus. We generate a population of viruses
in addition to a population of routes.
e Only routes that include viruses are generated as
the initial population. If two of the same routes
are produced in the population, one is removed.
e Minimal generation gap (MGG) model (Satoh et
al., 1996; Ono et al., 1999) for alternation of
generations. Mutation does not occur in the
proposed method.
3.1. Problem constraints
GA has been successfully applied to many NP-hard problems.
When the problem has hard constraints, some candidate
solutions are infeasible. This problem is generally addressed in
three ways:
e Avoiding infeasible solutions during the search
process.
e Penalizing infeasible solutions.
e Extracting feasible solutions after carrying out
the search using populations that may contain
infeasible candidate solutions.
The constraints on this particular problem can be grouped into
the following two categories:
* Fixed constraints: are always enforced,
irrespective of the composition of the current
solution. For example to select arterial and/or
wide roads to decrease the number of turns and
so on.
e Dynamic constraints: are enforced based on the
composition of the current solution. For
example, to select the roads where the traffic
restrictions are not imposed and to select the
roads not congested with traffic and so on.
In this stage of the development, our algorithm uses a directed
graph representation that embeds some static constraints.
4. PROPOSED METHOD
4.1. Algorithm
Figure.] shows the general steps of the algorithm. Details are
given in the following sections.
input map and map database
input origin and destination
initialize a population of viruses
initialize a population of individuals (routes). Set Generation= |
for generation = 1 to Number of Generation (repeat until
meeting deadline) {
calculate fitness values of individuals
select two individuals at random
single-point crossover
MGG
j
Figure 1. Algorithm of the proposed method
4.2. Coding and fitness
Repairing infeasible candidate solutions may incur significant
computational expense, but omitting them from the search
process may leave the search space disconnected, preventing
satisfactory optima from being reached. Computationally
cfficient search can be carried out by choosing a representation
that implicitly excludes infeasible candidate solutions, without
hindering the search process from visiting different parts of the
search space.
Variable-length chromosomes (routes) and their genes
(intersections) have been used for encoding the problem. A
chromosome of the proposed GA consists of sequences of
positive integers that represent the IDs of nodes through which
a routing path passes. In the other hand, we regard each route
from an origin to a destination as an individual for the GA and
express it as a sequence of intersections with directions.
The fitness of a route is evaluated using the length of the route,
the time required for a car to travel along it and the ease of
driving.
Internat
Penaltk
amenity
constrai
We rege
best one
4.3. Pop
In gener
initialize
procedu
It was
exponen
length o
Recent «
can be
summari
EXCESSIV
1989: H
populati
Secondly
heuristic
In this n
map wit
and wen
To gener
from the
origin to
Here are t
In this r
replacing
individual
random ir
