Information Technology Reference
In-Depth Information
4
3
1
4
0
3
3
Lösungskandidat
( n = 5 )
Phänotyp
Chromosom
Genotyp
2
1
0
0
1
2
3
4
Abbildung 10.2: Evolutionärer Algorithmus zur Lösung des n -Damen-Problems
Aufgrund der Existenz einer direkten Berechnung ist es eigentlich nicht zweck-
mäßig, einen evolutionären Algorithmus zu verwenden, um das n -Damen-Problem
zu lösen. Allerdings lassen sich an diesem Problem einige Aspekte evolutionärer Al-
gorithmen gut verdeutlichen.
10.3.1 Lösung durch einen evolutionären Algorithmus
Wir stellen einen Lösungskandidaten des n -Damen-Problems durch ein Chromosom
mit n Genen dar. Jedes Gen beschreibt eine Zeile des Schachbrettes und hat n mögli-
che Allele. Die Genausprägung gibt die Position der Dame in der zugehörigen Zeile
an. Eine beispielhafte Kodierung ist in Abbildung 10.2 phänotypisch und genoty-
pisch illustriert. Man muss beachten, dass bereits durch die Kodierung etwaige Lö-
sungskandidaten mit mehr als einer Dame je Zeile ausgeschlossen werden. Dadurch
wird der Suchraum verkleinert, was dem evolutionären Algorithmus bei der Er-
forschung von helfen wird.
Der Algorithmus 1 zeigt die Grundform eines evolutionären Algorithmus. Er
wird deswegen auch generischer evolutionärer Algorithmus genannt [Weicker 2007].
Algorithmus 1 EA-S CHEMA
Eingabe: Optimierungsproblem ( , f , )
1: t 0
2: pop ( t ) erzeuge Population der Größe µ
3: bewerte pop ( t )
4: while Terminierungsbedingung nicht erfüllt do
5: pop 1 selektiere Eltern für Nachkommen aus pop ( t )
6: pop 2 erzeuge Nachkommen durch Rekombination aus pop 1
7: pop 3 mutiere die Individuen in pop 2
8: bewerte pop 3
9: t t + 1
10: pop( t ) selektiere µ Individuen aus pop 3 pop( t 1)
11: end while
12: return bestes Individuum aus pop( t )
Zur Initialisierung der Population wird jedes der µ Individuen durch eine zufäl-
lige Folge von n Zahlen aus { 0, 1, . . . , n 1 } erzeugt. Die Güte oder Fitness eines
Search WWH ::




Custom Search