Genetische Algorithmen

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche

Allgemein

Die Genetischen Algorithmen basieren auf der synthetischen Evolutionstheorie welche auf kombinatorische Optimierungsprobleme angewendet werden.


Phasen

Im Allgemeinen bestehen genetische Algorithmen aus 4 sich wiederholenden Phasen:

  • Evaluation: Bewerten der Individuen in der Population durch Bestimmung der Fitness
  • Rekombination / Crossover: Entspricht der Paarung, also das Kreuzen zweier Individuen
  • Reproduktion / Klonen: Vervielfältigung einer bestehenden Lösung
  • Mutation: Veränderung von Individuen durch Außeneinflüsse um genetische Vielfalt sicher zu stellen


Problemrepräsentationen

Es gibt verschiedene Möglichkeiten ein Individuum darzustellen


Adjazenz-Repräsentation

Hierbei wird eine Tour der Länge n durch eine Liste von natürlichen Zahlen dargestellt. Die Zahl (Stadt) j ist an i-ter Stelle, falls die Tour von i nach j führt.

Beispiel

n=7 ; Repräsentant (6 1 5 3 2 7 4)

6 => Die Stadt 6 steht an 1. Stelle, also führt die Tour von 1 nach 6

1 => Die Stadt 1 steht an 2. Stelle, also führt die Tour von 2 nach 1

5 => Die Stadt 5 steht an 3. Stelle, also führt die Tour von 3 nach 5

3 => Die Stadt 3 steht an 4. Stelle, also führt die Tour von 4 nach 3

2 => Die Stadt 3 steht an 5. Stelle, also führt die Tour von 5 nach 2

7 => Die Stadt 7 steht an 6. Stelle, also führt die Tour von 6 nach 7

4 => Die Stadt 4 steht an 7. Stelle, also führt die Tour von 7 nach 4

Dies ergibt folgende Route: 1-6-7-4-3-5-2-1


Ordinale Repräsentation

Auch in dieser Darstellung ist eine Tour eine Liste von n Städten, wobei das i-te Element der Liste zwischen 1 und n-i+1 liegen muss. Diese Liste repräsentiert eine Tour unter Zunahme einer sortierten Referenzliste C.

Beispiel

n=7, C=(1 2 3 4 5 6 7), Repräsentant (2 3 1 4 1 2 1)

2=> Nimm 2. Element aus C und lösche es aus der Referenzliste

=> Tour: 2 und C=(1 3 4 5 6 7)

3=> Nimm 3. Element aus C und lösche es aus der Referenzliste

=> Tour: 2-4 und C=(1 3 5 6 7)

1 => Nimm 1. Element aus C und lösche es aus der Referenzliste

=> Tour: 2-4-1 und C=(3 5 6 7)

4 => Nimm 4. Element aus C und lösche es aus der Referenzliste

=> Tour: 2-4-1-7 und C=(3 5 6)

1 => Nimm 1. Element aus C und lösche es aus der Referenzliste

=> Tour: 2-4-1-7-3 und C=(5 6)

2=> Nimm 2. Element aus C und lösche es aus der Referenzliste

=> Tour: 2-4-1-7-3-6 und C=(5)

1 => Nimm 1. Element aus C und lösche es aus der Referenzliste

=> Tour: 2-4-1-7-3-6-5 und C=()

Dies ergibt die Tour 2-4-1-7-3-6-5


Pfad-Repräsentation

Die Pfad-Repräsentation ist die Einfachste Art eine Tour darzustellen. Die Reihenfolge der Elemente in der Liste gibt direkt den Weg an.

Beispiel

Repräsentant (3 4 7 6 1 2 5) ergibt die Tour 3-4-7-6-1-2-5

Crossover-Operatoren

Für jede Repräsentation Form gibt es verschiedene Crossover-Operatoren. In diesem Falle sollen die Crossover-Operatoren für die Pfad-Repräsentation näher gezeigt werden


Partially-Matched Crossover (PMX)

Es wird eine Teiltour aus einem Elternteil übernommen und versucht die Reihenfolge und Position möglichst vieler Städte aus dem anderen Elternteil zu erhalten. Dies geschieht, indem zwei zufällige Crossoverpunkte gewählt werden, zwischen denen dann die Werte vertauscht werden. Dann werden die Städte links und rechts der Crossoverpunkte wieder an ihrer Orginalposition eingefügt, sofern sie die Gültigkeit der Darstellung nicht verletzen. Sollte dies aber der Fall sein, wird stattdessen der Wert eingefügt der vor der Crossover Operation an der Stelle stand, an der nun der gleiche Wert steht wie der, der eingetragen werden soll.

Beispiel

n=7

p1 = (1 4 |6 7 5 3| 2) und

p2 = (5 2 |7 6 4 3| 1)

Erzeuge durch Vertauschung zuerst folgende Nachkommen

o1 = (x x |7 6 4 3| x)

o2 = (x x |6 7 5 3| x)

folgende Werte können ohne Konflikt an ihre Originalposition

o1 = (1 x |7 6 4 3| 2)

o2 = (x 2 |6 7 5 3| 1)

In o1 konnte die 4 nicht eingefügt werden, da sie schon an Stelle 5 steht. Daher wird sie du4rch das Element, welches zuvor an Stelle 5 stand, ersetzt (die 5). Analog wird bei o2 verfahren. Damit ergeben sich folgende Nachkommen:

o1 = (1 5 7 6 4 3 2) und

o2 = (4 2 6 7 5 3 1)


Order Crossover (OX)

Prinzipiell arbeitet OX ähnlich wie PMX, es gibt aber signifikante Änderungen bei der Erhaltung der Gültigkeit. Die Elternteile werden wieder durch je zwei Crossoverpunkte unterteilt, aber hier nicht vertauscht. Die Lücken links und rechts (zuerst rechts) werden dann in der Folge gefüllt, in der die Werte im anderen Elternteil startend vom rechten Crossoverpunkt vorkommen. Werte, die schon zwischen den Crossoverpunkten vorkommen, werden hierbei übersprungen.

Beispiel

n=7

p1 = (1 4 |6 7 5 3| 2) und

p2 = (5 2 |7 6 4 3| 1)

vorläufige Nachkommen

o1 = (x x |6 7 5 3| x)

o2 = (x x |7 6 4 3| x)

Nun werden die Werte aus o2 in der Reihenfolge wie sie nach dem zweiten Crossoverpunkt vorkommen in o1 nach dem zweiten Crossoverpunkt eingefügt.

Die Werte sind zunächst (5 2 7 6 4 3 1). Hierbei werden aber die Werte 6 7 5 3 übersprungen, da sie bereits in o1 vorkommen. Somit bleiben die Werte (2 4 1), welche von rechts nach links eingefügt werden. Analog o2.

o1 = (2 4 6 7 5 3 1)

o2 = (1 5 7 6 4 3 2)


Cyclic Crossover (CX)

Beim Cycle Crossover wird der Wert an einer zufälligen Position in einem Elternteil an die selbe Stelle im Nachkommen übernommen. Dann wird ausgehend von der Stelle, an der dieser Wert im anderen Elternteil steht, dieser Vorgang so lange wiederholt, bis sich ein Kreis bildet (man an einem Wert ankommt, den man schon übernommen hat). Die verbleibenden Stellen werden dann in der Reihenfolge aufgefüllt, in der die übrigen Werte im anderen Elternteil vorkommen.

Beispiel

n=7 und Startposition 2:

p1 = (1 4 6 7 5 3 2)

p2 = (5 2 7 6 4 3 1)

Als erstes wird die 4 aus p1 an Stelle 2 in o1 übernommen.

o1 = (x 4 x x x x x)

Die 4 steht in p2 an Position 5, also wird nun Positin 5 von p1 (5) an die selbe Position in o1 übernommen.

o1 = (x 4 x x 5 x x)

Die 5 steht in p2 an Position 1, also wird nun Position 1 von p1 (1) an die selbe Position in o1 übernommen.

o1 = (1 4 x x 5 x x)

Die 1 steht in p2 an Position 7, also wird nun Position 7 von p1 (2) an die selbe Position in o1 übernommen

o1 = (1 4 x x 5 x 2)

Die 2 steht in p2 an Position 2, somit würde jetzt aös Position 2 (4) an Position 2 in o1 übernommen werden. Dies ist jedoch schon geschehen und der Kreis ist geschlossen.

Analog dazu o2:

o2 = (5 2 x x 4 x 1)

Nun werden die unbelegten Werte mit den noch übrigen aus dem anderen Elternteil ersetzt. Bei o1 ist das (7 6 3) und bei o2 (6 7 3).

o1 = (1 4 7 6 5 3 2)

o2 = (5 2 6 7 4 3 1)


Weitere Crossover-Operatoren

Weiter Crossover-Operatoren für die Pfad-Repräsentation sind das Edge Recombination Crossover (ERX) und das Greedy Crossover (GX)