Information Technology Reference
In-Depth Information
4
3
2
1
0
0
1
2
3
4
Abbildung 10.3: Ein Lösungskandidat des 5-Damen-Problems. Er enthält zwei Kolli-
sionen. Seine Fitness beträgt somit
2.
3
1
4
0
3
1
4
3
2
0
3
1
4
2
0
1
4
3
0
3
4
3
2
1
Fitness:
-2
-3
0
-3
Abbildung 10.4: Ein-Punkt-Crossover zweier Individuen an der zweiten Trennstelle.
Lösungskandidats (einer Platzierung von
n
Damen) sei ganz einfach die negierte
Anzahl der Spalten und Diagonalen mit mehr als einer Dame. Mit der Negation er-
halten wir eine zu maximierende Fitnessfunktion.
Bei mehr als zwei Damen in einer Spalte oder Diagonale zählen wir jedes Paar
(siehe Abbildung 10.3). Dies ist einfacher zu implementieren. Aus dieser Fitnessfunk-
tion ergibt sich unmittelbar das Abbruchkriterium: Eine Lösung hat die (maximal
mögliche) Fitness 0. Desweiteren sollte man eine maximale Generationenzahl wäh-
len, um die Terminierung des EA zu garantieren. Bei einer endlichen Generationen-
zahl kann nicht sichergestellt werden, dass eine Lösung gefunden wird.
Für den wichtigen Operator der Selektion könnten wir z. B. eine
Tu r n i e r a u swa h l
wählen. Wir erwähnen den Ablauf dieses Selektionsverfahrens hier nur kurz: Wir
lassen
µ
tm
zufällig bestimmte Individuen „in einem Turnier“ gegeneinander antre-
ten. Das Beste dieser Individuen „gewinnt“ das Turnier und wird in die Zwischen-
population gewählt. Je höher die Fitness des Individuums ist, umso größer ist die
Chance ausgewählt zu werden. Eventuell übernehmen wir das beste Individuum
(unverändert) in die Zwischenpopulation. Wir betrachten dieses und weitere Selek-
tionsverfahren noch genauer im Abschnitt 11.2.
Abschließend müssen wir genetische Operatoren für Rekombination und Varia-
tion auswählen. Als Crossover, also der Austausch eines Chromosomenstücks (oder
auch einer in anderer Weise ausgewählter Teilmenge der Gene) zwischen zwei In-
dividuen, könnten wir z. B. das sogenannte Ein-Punkt-Crossover benutzen. Hierbei
wird zufällig eine Trennstelle zwischen zwei Genen gewählt. Die Gensequenzen auf
der einen Seite dieser Trennstelle wird abschließend aus. In Abbildung 10.4 ist die
Wah l de r 2 . Trenns t e l l e geze i g t .
