Information Technology Reference
In-Depth Information
352 8 176 4
123 4 567 8
3
8
1
4
Abbildung 11.1: Ein-Punkt-Crossover einer Permutation
35
24
56
7
8
1
Abbildung 11.2: Reparaturmechanismus für Permutationen
Für das Problem des Handlungsreisenden kommen folgende kodierungsspezifi-
schen genetischen Operatoren in Betracht. Als Mutationsoperator können wir z. B.
aus dem Zweiertausch, dem Verschieben eines Teilstücks oder der Inversion wählen
(siehe Abschnitt 11.3.1). Als Crossover-Operator können wir z. B. die Kantenrekom-
bination nutzen (siehe Abschnitt 11.3.2). Ein simpler Reparaturmechanismus würde
man z. B. doppelt auftretende Städte entfernen und die fehlenden Städte an das En-
de anfügen. Dies ist in Abbildung 11.2 verdeutlicht. Für den Ansatz eines Strafterms
könnte man beispielsweise die Fitness um eine Konstante für jede fehlende Stadt
verringern.
Falls der Suchraum nicht zusammenhängend sein sollte, so können uns Repara-
turmechanismen die Suche erschweren, da Lösungskandidaten in den „verbotenen“
Bereichen sofort wieder in den erlaubten Bereich zurückgeführt werden. Dies ist in
Abbildung 11.3 verdeutlicht. In diesen Fällen empfehlen wir, einen Strafterm einzu-
führen, durch den Lösungskandidaten im „verbotenen“ Bereich zwar bestraft, aber
nicht entfernt werden. Dieser Strafterm sollte im Laufe der Zeit wachsen, um Lö-
sungskandidaten in den „verbotenen“ Bereichen in späteren Generationen zu unter-
drücken.
11.2 Fitness und Selektion
Das grundlegende Prinzip der Selektion besagt, dass bessere Individuen (Individu-
en mit einer bessere Fitness) größere Chancen haben sollen, Nachkommen zu haben
„verbotener“ Bereich
Optimum
(Lösung des Opti-
mierungsproblems)
Individuen der An-
fangspopulation
Abbildung 11.3: Nicht zusammenhängende Bereiche eines Suchraums erschweren
einem EA die Suche, besonders bei Verwendung von Reparaturmechanismen.
