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