Information Technology Reference
In-Depth Information
Mutation Chromosom Liste noch zu besuchender Städte Rundreise
1,
2,
3,
4,
5
, 6
5
3
3
2
2
1
5
3
4
2
6
1
davor
1,
2,
3
, , 6
1,
2,
4
, 6
1,
2
, 6
1,
6
1
1
, , , , , 6
2,
1
3
3
2
2
1
1
4
5
3
6
2
danach
3,
4
, , 6
2,
3,
5
, 6
2,
3
, 6
2,
6
2
Tabe l l e 11 . 2 : Er l äut e rungen zur zwe i t en Kod i e rung anhand de r Wi rkung e i ne r Mu-
tation beim Problem des Handlungsreisenden
drückt führen in solch einem Fall Mutation und Crossover zu fast zufälligen Fitness-
änderungen. Finden wir eine Kodierung mit andererseits sehr geringer Epistasie, so
sind andere Verfahren oft besser geeignet (z. B. lokale Suchverfahren wie wir sie spä-
ter im Abschnitt 12.2 besprechen).
Man hat bereits versucht, mit dem Begriff der Epistasie Optimierungsprobleme
als „durch einen evolutionären Algorithmus leicht oder schwer lösbar“ zu kenn-
zeichnen [Davidor 1990]. Dies gelingt jedoch nicht, da Epistasie eine Eigenschaft der
Kodierung und somit
nicht des Problems
ist. Wie auch das vorangehende Beispiel des
Problems des Handlungsreisenden zeigt, kann man für ein Problem Kodierungen
mit hoher und niedriger Epistasie angeben. Nichtsdestoweniger gibt es Probleme,
die man mit geringer Epistasie kodieren kann und dennoch durch einen evolutio-
nären Algorithmus schwer zu lösen sind.
11.1.3 Verlassen des Suchraums
Der Suchraum
(die Menge der kodierten Lösungskandidaten) sollte, soweit möglich, unter
den verwendeten genetischen Operatoren abgeschlossen sein.
Wa s a l s Ve r l a s s en de s Suchr aums g i l t , i s t u . U. e i ne Defin i t i ons f r age . Al l geme i n
gilt, dass der Suchraum verlassen wird, wenn
• das neue Chromosom nicht sinnvoll interpretiert bzw. dekodiert werden kann,
• der Lösungskandidat bestimmte prinzipielle Anforderungen nicht erfüllt,
• der Lösungskandidat durch die Fitnessfunktion falsch bewertet wird.
Für gewöhnlich hat man es nicht einfach, eine Abstimmung von Kodierung und
genetischen Operatoren zu finden. Wir empfehlen daher, kodierungsspezifische ge-
