Heuristics: Genetic Algorithm 2

Introduction

Genetic Algorithm are good at taking large, potentially huge search spaces and navigating them, looking for optimal combinations of things, solutions you might otherwise find in a lifetime (Salvatore Mangano, Computer Design, May 1995)

The solution that you get from a genetic algorithm is the result of the iteratively application of different stochastic operators.

individual =a strucuture, that represents a solution, consisting of genes

chromosome =equal to individuals

gene =a bit of the binary representation of a solution

population =quantity of individuals, that became considered by an GA

parents =two chosen individuals of a population

crossing =combination of two genes from two chromosomes

mutation =modification of a chromosome

fitness =qualtity of a solution

generation =one iteration in the duration of the optimation

genotype =coded solution of a problem

phenotype =decoded solution of a problem

Basically the strucure of Genetic Algorithm is always the same presented below

1. produce an initial population of indivuals
2. evaluate the fitness of all individuals
3. WHILE termination condition not met DO
   1. select fitter individuals for reproduction
   2. recombine between individuals
   3. mutate individuals
   4. evaluate the fitness of the modified individuals
   5. generate a new population
4. END WHILE

Example

We toss a fair coin 60 times and get the following initial population:

$s_{1}=1111010101\qquad \color {red}f(s_{1})=7$

$s_{2}=0111000101\qquad \color {red}f(s_{2})=5$

$s_{3}=1110110101\qquad \color {red}f(s_{3})=7$

$s_{4}=0100010011\qquad \color {red}f(s_{4})=4$

$s_{5}=1110111101\qquad \color {red}f(s_{5})=8$

$s_{6}=0100110000\qquad \color {red}f(s_{6})=3$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \color{red}\sum_{i=1}^{6}f(s_i)=34

The new population after performing selection:

$s_{1}'=1111010101\quad (s_{1})$

$s_{2}'=1110110101\quad (s_{3})$

$s_{3}'=1110111101\quad (s_{5})$

$s_{4}'=0111000101\quad (s_{2})$

$s_{5}'=0100010011\quad (s_{4})$

$s_{6}'=1110111101\quad (s_{5})$

We only perform a crossover for the pairs $(s_{1}',s_{2}')$ and $(s_{5}',s_{6}')$

Crossover-points: 2 and 5

Before crossover:

$s_{1}'=11\color {green}11010101\color {black}\qquad s_{5}'=01000\color {green}10011$

$s_{2}'=11\color {red}10110101\color {black}\qquad s_{6}'=11101\color {red}11101$

After crossover:

$s_{1}''=11\color {red}10110101\color {black}\qquad s_{5}''=01000\color {red}11101$

$s_{2}''=11\color {green}11010101\color {black}\qquad s_{6}''=11101\color {green}10011$

Before applying mutation:

$s_{1}''=11101\color {red}1\color {black}0101\qquad s_{2}''=1111\color {red}0\color {black}1010\color {red}1$

$s_{3}''=11101\color {red}1\color {black}11\color {red}0\color {black}1\qquad s_{4}''=0111000101$

$s_{5}''=0100011101\qquad s_{6}''=11101100\color {red}1\color {black}1$

After applying mutation with updated fitness-values:

$s_{1}'''=11101\color {red}0\color {black}0101\qquad f(s_{1}''')=6$

$s_{2}'''=1111\color {red}1\color {black}1010\color {red}0\color {black}\qquad f(s_{2}''')=7$

$s_{3}'''=11101\color {red}0\color {black}11\color {red}1\color {black}1\qquad f(s_{3}''')=8$

$s_{4}'''=0111000101\qquad f(s_{4}''')=5$

$s_{5}'''=0100011101\qquad f(s_{5}''')=5$

$s_{6}'''=11101100\color {red}0\color {black}1\qquad f(s_{6}''')=6$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i=1}^{6}f(s_i''')=37

Improvement of 9 percent