Kurs:Genetische Algorithmen/Kapitel 6

Dieses Kapitel gehoert zum Kurs Genetische Algorithmen des Fachbereichs Informatik.

Übersicht

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

• 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!

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.

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

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?