Database Reference
In-Depth Information
The next algorithm shows the structure of a basic GGA.
P(t)
denotes the
population at generation
t
:
Generational Genetic Algorithm
Begin
t
=0;
Initialize
P(t)
;
Evaluate
P(t)
;
While (Not termination-condition) do
Begin
t
=
t
+1;
Select
P(t)
from
P(t-1)
;
Recombine
P(t)
;
Evaluate
P(t)
;
End;
End;
The selection mechanism produces a new population,
P(t)
, with copies of
chromosomes in
P(t
-
1).
The number of copies received for each chromosome
depends on its fitness; chromosomes with higher fitness usually have a greater
chance of contributing copies to
P(t).
Then the crossover and mutation operators
are applied on
P(t).
Crossover takes two individuals called parents and produces two new
individuals called the offspring by swapping parts of the parents. In its simplest
form, the operator works by exchanging substrings after a randomly selected
crossover point. The crossover operator is not usually applied to all pairs of
chromosomes in the new population. A random choice is made, where the
likelihood of crossover being applied depends on the probability defined by a
crossover rate
.
Mutation serves to prevent premature loss of population diversity by randomly
sampling new points in the search space. Mutation rates are kept small however,
otherwise the process degenerates into a random search. To bit strings, mutation is
applied by flipping one or more random bits in a string with a probability equal to
the
mutation rate
.
Termination may be triggered by reaching a maximum number of generations
or by finding an acceptable solution by some criterion.
5.4.2 Steady-State Genetic Algorithm (SGA) [36]
In SGAs usually only one or two offspring are produced in each generation.
Parents are selected to produce offspring and then a replacement/deletion strategy
defines which member of the population will be replaced by the new offspring.
The basic algorithm steps of SGA are the following:
Search WWH ::
Custom Search