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.

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

       select fitter individuals for reproduction

recombine between individuals

mutate individuals

       evaluate the fitness of the modified individuals

       generate a new population
  
  End while

use of GA

if alternate solutions take too much time or become too complicated

if there is a need for new approaches

if the problem is similar to one, that was alreadey solved by GA

if you want to get hybrid approaches

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