Encoding
{0,1}L
(representation)
010001001
011101001 Decoding (inverse representation)
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Genetic Algorithms
Holland’s original GA is now known as the simple genetic algorithm (SGA)
Other GAs use different:
– Representations – Mutations – Crossovers – Selection mechanisms
probability pc , otherwise copy parents 4. For each offspring apply mutation (bit-flip with
probability pm independently for each bit) 5. Replace the whole population with the resulting
Main idea: better individuals get higher chance
– Chances proportional to fitness
– Implementation: roulette wheel technique
– many variants, e.g., reproduction models, operators
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Genetic Algorithms
Genetic algorithms
– discrete optimization
Attributed features:
– not too fast – good heuristic for combinห้องสมุดไป่ตู้torial problems
Special Features:
– Traditionally emphasizes combining information from good parents (crossover)
offspring
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Genetic Algorithms
SGA operators: 1-point 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)
Genetic Algorithms
Chapter 3
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Genetic Algorithms
GA Quick Overview
Developed: USA in the 1970’s Early names: J. Holland, K. DeJong, D. Goldberg Typically applied to:
Parent selection Survivor selection Speciality
Binary strings
N-point or uniform
Bitwise bit-flipping with fixed probability Fitness-Proportionate
All children replace parents
SGA reproduction cycle
1. Select parents for the mating pool (size of mating pool = population size)
2. Shuffle the mating pool 3. For each consecutive pair apply crossover with
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Genetic Algorithms
SGA technical summary tableau
Representation Recombination Mutation
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Genetic Algorithms
SGA operators: mutation
Alter each gene independently with a probability pm pm is called the mutation rate
Emphasis on crossover
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Genetic Algorithms
Representation
Phenotype space
Genotype space =
– Typically between 1/pop_size and 1/ chromosome_length
A.E. Eiben and J.E. Smith, Introduction to Evolutionary Computing Genetic Algorithms
SGA operators: Selection