Elemente evolutionärer Algorithmen - Computational Intelligence - page 168

netische Operatoren zu verwenden. Sollte man den Lösungsraum dennoch einmal
verlassen, so kann man Mechanismen nutzen, die Chromosomen reparieren und so-
mit wieder in den Lösungsraum zurückführen. Alternativ kann man auch einen
Strafterm einführen, der die Fitness von Chromosomen außerhalb des Suchraums
(deutlich) verringert.
Als ein Beispiel zum Verlassen des Suchraums betrachten wir nachfolgend zwei
verschiedene Kodierungen des n -Damen-Problems. Das n -Damen-Problem haben
wir bereits im Abschnitt 10.3 besprochen. Die beiden evolutionären Algorithmen,
die wir hier benutzen, seien wie folgt zusammengesetzt.
1. Ein Chromosom der Länge n speichert die Spaltenpositionen der Damen je
Zeile. Mögliche Allele sind demnach 0, . . . , n 1(sieheAbschnitt10.3.1).Als
Operatoren verwenden wir Ein-Punkt-Crossover und Standardmutation. So-
mit entstehen stets wieder gültige Vektoren von Spaltenpositionen. Der Such-
raum kann nicht verlassen werden.
2. Ein Chromosom der Länge n , das die Nummern der Felder angibt, auf denen
Damen stehen. Mögliche Allele sind also 0, . . . , n 2 1. Wir wollen dieselben
Operatoren wie oben verwenden. Es könnten also Chromosomen entstehen,
die mehrere Damen auf das gleiche Feld setzen. Somit kann der Suchraum
verlassen werden.
Sollte man die zweite Kodierung benutzen wollen, so gibt es mehrere mögliche
Lösungsansätze, die verwendet werden können.
• Benutzen einer anderen Kodierung: Da die erste Kodierung das Problem des Ver-
lassens des Suchraums vermeidet und außerdem der Suchraum deutlich klei-
ner ist, ist sie vorzuziehen. Dieser Ansatz ist, wenn durchführbar, die mit Ab-
stand beste Variante.
• Kodierungsspezifische genetische Operatoren: Z. B. könnte eine Mutation bereits
vorhandene Allele bei der zufälligen Wahl ausschließen. Eine Alternative zum
Ein-Punkt-Crossover wäre u. U. folgender Ansatz. Stelle zunächst die Feld-
nummern je Chromosom zusammen, die im jeweils anderen Chromosom nicht
vorkommen, und wende auf die so verkürzten Chromosomen das Ein-Punkt-
Crossover an.
• Reparaturmechanismus: Finde und ersetze doppelt bzw. mehrfach auftretende
Feldnummern, sodass alle Feldnummern verschieden werden.
• Strafterm: Ve r r i nge r e d i e F i t ne s s um d i e Anz ah l de r Doppe l t - ode r Meh r f a c h -
belegungen von Feldern, gegebenenfalls multipliziert mit einem Gewichtungs-
faktor.
Als weiteres Beispiel zum Verlassen des Suchraums besprechen wir nachfolgend
auch das Problem des Handlungsreisenden. Wir nehmen an, dass eine Rundreise
durch eine Permutation der Städte dargestellt wird. D. h., die Stadt an k -ter Positi-
on wird im k -ten Schritt besucht. Offensichtlich kann der Raum der Permutationen
durch Anwendung eines Ein-Punkt-Crossover verlassen werden (siehe Abbildung
11.1).