Geography Reference
In-Depth Information
logistic distribution; Park et al. (
1999
) and Ceylan and Bell (
2004
) propose applying
GA to the problem of traffic signal optimization; and Pattnaik et al. (
1998
)alsouse
genetic algorithm to minimize the overall cost in urban bus route design.
13.3.1
Principles of Genetic Algorithm
The basic principle underlying genetic algorithm is the evolutionary ideas of natural
selection and genetics as described by Charles Darwin's theory of “survival of the
fittest”. Every organism has a set of rules, describing how that organism is built
up from cell, the smallest unit of life. These rules are encoded in the genes of cell
nucleus, which in turn are connected together into long strings called chromosomes.
Each gene has its unique position in the chromosome. The complete set of genetic
material (all chromosomes) is known as genome. Particular set of genes in genome
is called genotype, which can develop to a phenotype after birth, representing its
physical and mental characteristics such as eye color, intelligence, etc. (Holland
1992
).
In a genetic algorithm, a set of chromosomes called population (genome)
encode candidate solutions (called individuals) to an optimization problem. Each
chromosome in this population consists of several genes that carry the information
representing particular functions. Traditionally, these chromosomes are coded in
binary as strings of 0 and 1, other encodings like integer, floating type or character
etc. are also widely used (Forrest
1993
). The algorithm usually begins with a group
of individuals which are randomly created as potential solutions to a problem.
Performances of these individuals are measured by a predefined fitness function.
The ones with higher fitness value are likely to be selected and modified randomly
through crossover and/or mutation to generate a new population. This evolutionary
iteration will continue until the stop condition such as when a satisfactory fitness
level or a maximum number of generations or a number of generations without
improvement has been reached (Holland
1992
).
The success of GA depends on not only how the initial solutions (or chromo-
somes) are defined and formed, but also the evaluation mechanism (i.e. the fitness
function) and the genetic operations including crossover and mutation (Nicolas and
Hao
2001
). The fitness function determines the chance of survival for each individ-
ual, whilst the genetic operations increase the population diversity while avoiding
or at least reducing the chance of getting trapped from local maximum. Crossover
operator exchanges the piece(s) of genes between chromosomes. Chromosomes
selected as parents through crossover probability swap segments of their genes
with each other to create new chromosomes as children and then their positions
in the population would be replaced. During this process, new individuals can be
generated to the population, which brings possibility to have fitter chromosome
(Holland
1992
). In the same way, mutation operator alters the chromosome selected
by a predefined probability by modifying one or several of its gene(s) randomly
within a certain range. The new population is then used in the next iteration of
Search WWH ::
Custom Search