Kurs:Genetische Algorithmen/Kapitel 6

Aus Wikiversity
Zur Navigation springen Zur Suche springen

Dieses Kapitel gehoert zum Kurs Genetische Algorithmen des Fachbereichs Informatik.

Übersicht[Bearbeiten]

In diesem Kapitel werden die theoretischen Kenntnisse über genetische Algorithmen in die Praxis umgesetzt. Die verschiedenen Komponenten werden zusammengesetzt und angewedet, um ein konkretes Problem zu lösen. Es ist auch möglich, grössere Probleme ohne grossen Aufwand mit dem gleichen Verfahren zu optimieren.

Lernziele[Bearbeiten]

  • Sie können alle Komponenten eines genetischen Algorithmus zusammenfügen und anwenden.
  • Durch die Anwendung kennen und verstehen Sie die Details der Ausführung der einzelnen Komponenten besser.
  • Die Ausführung eines genetischen Algorithmus' wird Ihnen vertraut.

Jetzt gehts los![Bearbeiten]

Nun wollen wir unser Wissen in die Tat umsetzen! Wir kennen alle Komponenten eines genetischen Algorithmus', nun müssen wir sie nur noch zusammensetzen, um eines unserer Beispielprobleme zu optimieren.

Wir gehen dabei nach folgendem Schema vor. Sie können in kleineren Gruppen zusammenarbeiten.


Diagramm GA.png
Schreiben Sie für das ausgewählte Optimierungsproblem die 6 ersten Lösungen auf. Wählen Sie drei aus und wenden Sie einen Mutationsoperator darauf an. Wählen sie dann drei zufällige Paare und rekombinieren Sie diese. Wenden Sie schliesslich den Selektionsoperator darauf an und schreiben sie die neuen 6 Lösungen darunter. Fahren Sie nach dem gleichen Schema weiter.


  1. Wählen Sie eines der drei im Text vorgestellten Optimierungsprobleme aus.
  2. Wählen Sie dazu einen Mutationsoperator und einen Rekombinationsoperator aus.
  3. Führen sie einige Durchläufe unseres genetischen Algorithmus durch. Sie können dabei nach dem Schema in Abbildung~\ref{fig:algo} vorgehen.
    1. Wir wählen eine Anfangsbevölkerung bestehend aus sechs identischen Kopien einer einzigen Lösung.
    2. Wir wählen aus der Bevölkerung zufällig drei Lösungen heraus. Wir verwenden hierfür einen Würfel. Von diesen drei Lösungen machen wir je eine Kopie und wenden auf jede einen Mutationsoperator an.
    3. Aus der ursprünglichen Bevölkerung wählen wir nochmals mithilfe eines Würfels jeweils zwei Lösungen und erzeugen mittels eines Rekombinationsoperators eine neue Lösung. Dies führen wir dreimal aus.
    4. Wir müssen nun unsere Bevölkerung von 12 Lösungen wieder auf 6 Lösungen reduzieren. Dazu verwenden wir einfachheitshalber den Turnier-Selektionsoperator. Um die Lösungen zufällig auszuwählen schreiben wir die Zahlen 1 bis 12 auf Zettelchen, die wir in einen Hut legen. Wir wählen zufällig zwei Zettel und vergleichen die dazugehörenden Lösungen und verwerfen die schlechtere der beiden. Ergeben beide Lösungen den gleichen Wert der Zielfunktion, so entscheidet ein Münzenwurf, welche davon ausscheidet.

Bei allen vorgestellten Mutations- und Rekombinationsoperatoren werden nur Zufallszahlen von 1 bis 6 benötigt. Diese erzeugen wir mit einem Würfel.

Die ersten zwei Optimierungsprobleme -- nämlich das Problem des Handelsreisenden und das Damenproblem -- bewegen sich in einer Grössenordnung, die noch von Hand lösbar ist. Bei 12 Städten (19'958'400 unterschiedliche Lösungen, vgl.~Tabelle~\ref{tab:staedte2}) oder 12 Damen (2'229'025'112'064 mögliche Aufstellungen) sind die Probleme aber nicht mehr so einfach.


Distanztabelle für 12 Schweizer Städte Aarau, Bern, Chur, Dübendorf, Emmen, Fribourg, Genf, Herisau, Ittigen, Jona, Kreuzlingen und Lausanne.
von/nach A B C D E F G H I J K L
A 0 65 127 43 38 94 195 94 63 61 88 145
B 65 0 157 100 62 29 130 146 2 107 149 80
C 127 157 0 92 98 181 268 62 156 67 92 225
D 43 100 92 0 31 117 229 51 98 24 6 180
E 38 62 98 31 0 90 188 85 61 45 92 140
F 94 29 181 117 90 0 100 175 31 135 179 51
G 195 130 268 229 188 100 0 273 132 233 279 53
H 94 146 62 51 85 175 273 0 145 39 29 225
I 63 2 156 98 61 31 132 145 0 106 148 82
J 61 107 67 24 45 135 233 39 106 0 53 185
K 88 149 92 6 92 179 279 29 148 53 0 230
L 145 80 225 180 140 51 53 225 82 185 230 0


Wählen Sie eines dieser zwei Probleme aus und verwenden sie unseren genetischen Algorithmus darauf. Um schneller zu guten Lösungen zu kommen, wenden Sie zwei Mutationsoperatoren je viermal und einen Rekombinationsoperator viermal an, um 12 neue Lösungen zu erzeugen. Sie müssen dann bei der Selektion von 18 auf 6 Lösungen reduzieren. Dies machen sie am besten wieder mit dem Hut und 18 Zettelchen.

Lernkontrolle[Bearbeiten]

  1. Funktioniert der Algorithmus bzw. werden die Lösungen von Generation zu Generation besser?
  2. Sind die Lösungen des zweiten, grösseren Optimierungsproblems, die Sie nach 5 Generationen erhalten, besser als die, die Sie von Hand finden können?
  3. Vergleichen Sie Ihre Lösungen mit denen anderer Gruppen. Gab es zwischen den verschiedenen Operatoren bedeutende Unterschiede?
  4. Wieviel mussten Sie über das eigentliche Optimierungsproblem wissen, um den Algorithmus durchzuführen?