Heuristics: Genetic Algorithm 2: Unterschied zwischen den Versionen

Version vom 24. Juni 2013, 21:49 Uhr

Example

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

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

The new population after performing 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 mutation:

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