Evolutionäre Basisalgorithmen - Computational Intelligence - page 192

wobei p c die Wahrscheinlichkeit eines Crossover ist, p loss die Wahrscheinlichkeit ist,
dass durch ein Ein-Punkt-Crossover die Passung eines Chromosoms zum Schema h
verlorengeht, A der Erwartungswert der Anzahl Chromosomen ist, die zum Schema
h passen und nicht am Crossover teilnehmen, B der Erwartungswert der Anzahl
Chromosomen ist, die am Crossover teilnehmen und deren Passung zum Schema h
dadurch nicht verlorengeht, C die Gewinne an Chromosomen ist, die zum Schema h
passen, durch günstige Rekombinationen von Chromosomen.
Einige Betrachtungen zur Wahrscheinlichkeit p loss im Folgenden sollen uns hel-
fen, zu verstehen, wie sich p loss annähern lässt. Als Beispiel führen wir folgende
Rechnung an:

h = ** 0 * | 1 * 1 *

** 0 * 1 * 1 * = h

00000000 = c h c 1 = 0000 | 1111

h

1

11111111 = c

h

c 2 = 1111 | 0000 h

2

h = ** 0 * | 1 * 1 *

** 0 * 1 * 1 * = h

00001010 = c

h c 1 = 0000 | 1111

1 h

11011111 = c

h c 2 = 1101 | 1010

2 h

So kann es vorkommen, dass zwei Chromosomen, die nicht zu h passen, es nach der
Rekombination sind. Genauso kann es auch sein, dass zwei Chromosomen, die zu h
passen, es auch noch nach dem Ein-Punkt-Crossover sind. Folglich gilt, dass

dl ( h )
L 1

1 N ( h , t + t s )
| pop |

p loss

·

,

A = p

x ( h )

B

wobei A dieWahrscheinlichkeit ist, dass der Schnittpunkt zwischen festgelegte Gene
fällt und B die Wahrscheinlichkeit ist, dass das zweite Chromosom zum Schema h
passt. Dem geneigten Leser bleibt es überlassen selbst zu ergründen, warum p loss
nur anhand einer oberen Schranke und nicht exakt angegeben werden kann.
Setzenwir nun der gerade erhaltene Ausdrucks für p loss ein, so entsteht folgender
Zusammenhang:

N ( h , t + t s + t x )
( 1 p x ) · N ( h , t + t s )

1 dl ( h )
L 1

1 N ( h , t + t s )
|pop|

+ p x · N ( h , t + t s ) · ·

1 dl ( h )
L 1

1 N ( h , t + t s )
| pop |

= N ( h , t + t s )

1 p x + p x ·

·

1 p x dl( h )
L 1

1 N ( h , t + t s )
| pop |

= N ( h , t + t s ) · ·

dl( h )
L 1

( = N ( h , t ) ·

f rel ( h ) ·|pop|· 1 p x · (1 N ( h , t ) · f rel ( h ))