Heuristics: Genetic Algorithm 2: Unterschied zwischen den Versionen

Version vom 25. Juni 2013, 09:34 Uhr

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

Example

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, ot 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:

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

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

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

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

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

${\displaystyle 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).

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

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

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

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

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

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

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

Crossover-points: 2 and 5

Before crossover:

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

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

After crossover:

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

${\displaystyle 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

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

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

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

After applying mutation (random) with updated fitness-values:

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

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

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

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

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

${\displaystyle 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

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)