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.

For understanding GA and how they work, we have to introduce some new vacabulary:

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

chromosome =equal to individual

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

Examples

We want to visit 6 cities and every city just once.

The distances between the cities are given in the following tableau.

We want to minimize the distance.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \begin{array}{|c||c|c|c|c|c|c|} \hline & 1 & 2 & 3 & 4 & 5 & 6\\ \hline \hline 1 & - & 4 & 2 & 10 & 8 & 7\\ \hline 2 & & - & 5 & 7 & 9 & 2\\ \hline 3 & & & - & 3 & 5 & 9\\ \hline 4 & & & & - & 1 & 5\\ \hline 5 & & & & & - & 4\\ \hline 6 & & & & & & -\\ \hline \end{array}

We have an initial parents generation given by the following three route alternatives:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (1) \ \ 3-4-1-5-2-6

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (2) \ \ 2-6-3-1-4-5

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (3) \ \ 1-5-2-3-6-4

The reproduction rate of the parents´pool is 1/3. The reproduction rate of the children´s pool is 2/3.

The recombination takes place in the following (chosen randomly) order:

(1)->(2), (1)->(3), (3)->(2)

The algorithm stops after the second generation.

a) Partially-Matched Crossover (PMX)

The length of the sequence is given by 2.

(1)->(2)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (1) \ \ 3-4-1-\color{red}5\color{black}-\color{red}2\color{black}-6

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (2) \ \ 2-6-3-\color{green}1\color{black}-\color{green}4\color{black}-5

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (4) \ \ \color{green}4\color{black}-6-3-\color{red}5\color{black}-\color{red}2\color{black}-\color{green}1

The first recombination process [(1)->(2)] starts at gene 4 (randomly chosed). This means we cut out gene 4 and 5 of parent 1 (red marked).

So 5 becomes the 4th gene and 2 the 5h element of the child (red marked).

Now we have to take gene 4 and 5 of parent 2 (green marked).

The green marked 1 of parent 2 has to be placed under 5 of parent 2, because the green marked 1 of parent 2 stands below the 5 of parent 1.

The green marked 4 of parent 2 has to be placed under 2 of parent 2, because the green marked 4 of parent 2 stands below the 2 of parent 1.

At the end we have to fill up gene 2 and 3 of the child with gene 2 and 3 of parent 2 to get an new individual without a number twice.

(1)->(3)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (1) \ \ \color{red}3\color{black}-\color{red}4\color{black}-1-5-2-6

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (3) \ \ \color{green}1\color{black}-\color{green}5\color{black}-2-3-6-4

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (5) \ \ \color{red}3\color{black}-\color{red}4\color{black}-2-\color{green}1\color{black}-6-\color{green}5

The second recombination process [(1)->(3)] starts at gene 1 (randomly chosed). This means we cut out gene 1 and 2 of parent 1.

(3)->(2)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (3) \ \ 1-\color{red}5\color{black}-\color{red}2\color{black}-3-6-4

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (2) \ \ 2-\color{green}6\color{black}-\color{green}3\color{black}-1-4-5

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (6) \ \ \color{green}3\color{black}-\color{red}5\color{black}-\color{red}2\color{black}-1-4-\color{green}6

The third recombination process [(3)->(2)] starts at gene 2. This means we cut out gene 2 and 3 of parent 3.

Now we have to calculate the fitness of the parents and children.

Parent (1) : $f_{1}=3+10+8+9+2=32$

Parent (2) : $f_{2}=2+9+2+10+1=24$

Parent (3) : $f_{3}=8+9+5+9+5=36$

Child (4)  : $f_{4}=5+9+5+9+4=32$

Child (5)  : $f_{5}=3+9+4+7+4=27$

Child (6)  : $f_{6}=5+9+4+10+5=33$

The reproduction rate of the parents´ pool is 1/3. So we pick out parent 2, because we want to minimize the distance.

The reproduction rate of the childrens´ pool is 2/3. So we pick out Child 4 and 5.

So the second generation consists of parent 2 and child 4 and 5.

The Maxone problem:

We want to maximize the number of ones in a string of L binary bits.

This may seem to trivial, cause we know already the answer, but however, we can think of it as maximazing the number of correct answers, each encoded by 1, to difficult questions:

Suppose l=10, n=6

Cause everey individual is encoded as a string of l binary bit, we can write for one

1=0000000001 (10 bits)

To get the initial population, we toss a fair coin 60 times:

$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

while f(s) is the fitness function

The new population after performing selection (suppose we apply a random generator and get this 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})$

You can determine the probability for a crossover, for instance 0,6.

Thus 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 random mutation:

For each bit, that we are to copy to the new population, we allow a small probability of error, for instance 0,1.

$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 (random) 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 (fitness from 34 to 37)

You could repeat the algorithm, until a stopping criterion is met.

References

Nobal Niraula, Genetic Algorithm: http://de.slideshare.net/kancho/genetic-algorithm-by-example (download: 24.06.13)

Alfred Hermes, Heuristik: Genetischer Algorithmus am Beispiel des 0/1-Rucksackproblems: http://learntech.rwth-aachen.de/lehre/ss05/fdi/folien/VS11HTML/GenAlg.pdf (download: 24.06.13)