Transcript Genetic Algorithms

Genetic Algorithms
The Basic Genetic Algorithm
1.
2.
3.
4.
5.
6.
[Start] Generate random population of n chromosomes (suitable
solutions for the problem)
[Fitness] Evaluate the fitness f(x) of each chromosome x in the
population
[New population] Create a new population by repeating following steps
until the new population is complete
1.
[Selection] Select two parent chromosomes from a population
according to their fitness (the better fitness, the bigger chance to be
selected)
2.
[Crossover] With a crossover probability cross over the parents to
form new offspring (children). If no crossover was performed,
offspring is the exact copy of parents.
3.
[Mutation] With a mutation probability mutate new offspring at each
locus (position in chromosome).
4.
[Accepting] Place new offspring in the new population
[Replace] Use new generated population for a further run of the
algorithm
[Test] If the end condition is satisfied, stop, and return the best solution in
current population
[Loop] Go to step 2
Basic principles 1
• Coding or Representation
– String with all parameters
• Fitness function
– Parent selection
• Reproduction
– Crossover
– Mutation
• Convergence
– When to stop
Basic principles 2
• An individual is characterized by a set of parameters:
Genes
• The genes are joined into a string: Chromosome
• The chromosome forms the genotype
• The genotype contains all information to construct an
organism: the phenotype
• Reproduction is a “dumb” process on the chromosome of
the genotype
• Fitness is measured in the real world (‘struggle for life’)
of the phenotype
Conceptual Algorithm
Genetic Algorithm
• Encoding
• Fitness Evaluation
• Reproduction
• Survivor Selection
Reproduction
• Crossover
– Two parents produce two offspring
– There is a chance that the chromosomes of the two parents
are copied unmodified as offspring
– There is a chance that the chromosomes of the two parents
are randomly recombined (crossover) to form offspring
– Generally the chance of crossover is between 0.6 and 1.0
• Mutation
– There is a chance that a gene of a child is changed
randomly
– Generally the chance of mutation is low (e.g. 0.001)
One-point crossover
• Randomly one position in the chromosomes is chosen
• Child 1 is head of chromosome of parent 1 with tail of
chromosome of parent 2
• Child 2 is head of 2 with tail of 1
Randomly chosen position
Parents:
1010001110
0011010010
Offspring: 0101010010
0011001110
Crossover
•
•
•
•
Choose a random point on the two parents
Split parents at this crossover point
Create children by exchanging tails
Pc typically in range (0.6, 0.9)
Mutation
• Alter each gene independently with a
probability pm
• pm is called the mutation rate
– Typically between 1/pop_size and 1/
chromosome_length
Algorithm
BEGIN
Generate initial population;
Compute fitness of each individual;
REPEAT /* New generation /*
FOR population_size / DO
Select two parents from old generation;
/* biased to the fitter ones */
Recombine parents for two offspring;
Compute fitness of offspring;
Insert offspring in new generation
END FOR
UNTIL population has converged
END
Parent/Survivor Selection
• Strategies:Survivor selection
• Always keep the best one
• Elitist: deletion of the K worst
Worked Example
Parent 1
Parent 2
Neck: long 11000001
Neck : short 11000000
leggs : short 00110000
leggs : long 00110001
adaptation : middle
adaptation : middle
After many random crossover-combination, we get the following generation:
Sohn 1
Sohn 2
Sohn 3
Neck: short 11000000
Neck : short 11000000
Neck : long 11 000001
Leggs: short 00110000
Leggs: long 00110001
Leggs: long 00110001
Adaptation : Bad
Adaptation : Middle
Adaptation :Good
In a long terme process only sohn three will survive. Sohn 1 and 2 will be eliminate
from the existence because of the nature conditions(fitness function)
Conclusion
• The genetic algorithms are very good
techniques however the main obstacle is
to encode problem, to define a good
fitness function!
• Demo TSM
• AISteroid