Information Technology Reference
In-Depth Information
Allel Nachbarn Wah l : 6
5
2
7
4
3
1
1
3, 4, 5, 6
3, 4, 5
3, 4
3, 4
3, 4
3
5
,7
5
,7
7
7
2
— — — —
3
1, 4, 6, 7
1, 4, 7
1, 4, 7
1, 4, 7
1, 4
1
1
—
4
1, 3, 6, 7
1, 3, 7
1, 3, 7
1, 3, 7
1, 3
1, 3
— —
1, 2
,6
1, 2
1, 2
5
—
— — — —
6
1, 3, 4, 5
1, 3, 4, 5
—
—
— — — —
2
,3,4
2
,3,4
2
,3,4 3, 4
7
3, 4
— — —
Tabelle 11.5: Aufbau eines Nachkommen durch Kantenrekombination
den Nachbarn der 6 (lies 1, 3, 4, 5) die 5 die kürzeste Liste hat, wählen wir die 5
für das zweite Gen. Dann folgt die 2, die 7 usw. Der so entstandene Nachkomme ist
demnach
652743 1
wobei uns auffällt, dass die gewünschte Nachbarschaftsinformation von der 5, 2 und
7erhaltengebliebenist.
Abschließend erwähnen wir zur Kantenrekombination Folgendes: Der Nachkom-
me hat meist eine neue Kante, nämlich vom letzten zum ersten Gen. Man kann die
Kantenrekombination auch dann anwenden, wenn man das erste und das letzte Gen
eines Chromosoms nicht als benachbart ansieht: Man nimmt dann die entsprechen-
den Kanten eben nicht in die Kantentabelle auf. Sieht man allerdings das erste und
das letzte Gen als benachbart an, so kann man das Startallel beliebig aus den Chro-
mosomen wählen. Wenn man sie dagegen nicht als benachbart ansieht, muss es ein
amAnfang stehendes Allel sein, das ausgewählt wird. BeimAufbau eines Nachkom-
men kann es vorkommen, dass die Nachbarschaftsliste des gerade ausgewählten Al-
lels leer ist. Die Prioritätsregeln dienen dazu, die Wahrscheinlichkeit dafür gering
zu halten; sie sind aber nicht perfekt. In diesem Fall setzt man die Konstruktion mit
einem Allel fort, das man zufällig aus den noch übrigen Allelen wählt.
11.3.3 Genetische Drei- und Mehr-Elter-Operatoren
Das
Diagonal-Crossover
arbeitet ähnlich wie das Ein-, Zwei- oder
n
-Punkt-Crossover.
Es wurde aber für mehr als zwei Eltern entwickelt. Bei drei Eltern wählt man zwei
Crossover-Punkte. An den Schnittstellen verschiebt man die Gensequenzen diagonal
und zyklisch über die Chromosomen (siehe Abbildung 11.16). Eine Verallgemeine-
rung auf mehr als drei Eltern ist naheliegend. Für
k
Elternwählt man
k
1Crossover-
Punkte. Dieses Verfahren führt zu einer sehr guten Erforschung des Suchraums, be-
sonders bei einer großen Zahl an Eltern (ca. 10-15).
11.3.4 Charakterisierung von Crossover-Operatoren
Man kann Crossover-Operatoren anhand bestimmter Eigenschaften charakterisie-
ren, sodass bei der Konzipierung eines evolutionären Algorithmus gewisse Rekom-
binationsoperatoren eher begründet berücksichtigt werden können als andere. Man
