Heuristics: Genetic Algorithm 2

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