Kurs:Genetische Algorithmen/Kapitel 7

Dieses Kapitel gehoert zum Kurs Genetische Algorithmen des Fachbereichs Informatik.

Übersicht

Wir lernen verschiedene Anwendungen von genetischen Algorithmen in der Praxis kennen. Es werden Vor- und Nachteile der Verwendung von genetischen Algorithmen diskutiert. Zusammenfassend wird erklärt, wann es sich lohnt, einen genetischen Algorithmus anzuwenden und wann nicht.

Lernziele

• Sie kennen einige Beispiele aus der Praxis, wo genetische Algorithmen zur Anwendung kommen.
• Sie kennen die Vor- und Nachteile genetischer Algorithmen.
• Sie wissen, wann es sich lohnt, einen genetischen Algorithmus für ein Optimierungsproblem anzuwenden.

Wann soll man einen genetischen Algorithmus verwenden?

In der Praxis sind genetische Algorithmen weit verbreitet. Sie werden zur Lösung einer Vielzahl unterschiedlicher Probleme benutzt:

• Phantombilder: In England werden Phantombilder am Computer mit einem genetischen Algorithmus erzeugt. Anhand ein paar wenigen Daten, zum Beispiel Geschlecht, Haarfarbe, Gesichtsbehaarung und Kopfform, werden ein Satz zufälliger Phantombilder erzeugt. Aus diesen Bildern wählt der Zeuge das, welches dem Täter am ähnlichsten sieht. Aus diesem und den letzten paar Bildern werden neue Bilder erzeugt, aus denen der Zeuge wieder das dem Täter am ähnlichsten wählen soll. Dieser Vorgang wird wiederholt, bis keine der Vorschläge dem Täter ähnlicher sehen. Dieser Vorgang ist nicht nur schneller und billiger als ein Zeichner -- die Resultate haben sich in Tests als genauer erwiesen.
• Computerspiele: Um einen Gegner mit eigener Strategie vorzutäuschen, werden in vielen Computerspielen genetische Algorithmen verwendet, die vom Benutzer "lernen". Auf diese Art und Weise kann vielfältiges und vorallem unvorhersehbares Verhalten entstehen.
• Flugzeugbau: Um ein optimales Flügelprofil oder eine optimale Rumpfform zu bekommen, verwendet man heute genetische Algorithmen. Die Lösungen (sprich: die verschiedenen Profile) werden mit Simulationen ausgewertet, so dass keine teuren Modelle gebaut werden müssen.
• Logistik: Eine Transportfirma muss Ware von Stadt $A$ nach Stadt $B$ transportieren. Dann wieder von Stadt $A$ nach Stadt $C$ und von Stadt $C$ nach Stadt $B$. Sie hat aber nur einen Lastwagen und es gilt, Liefertermine einzuhalten. Die optimale Verwaltung von Lastwagen und Ware ist ein sehr komplexes Problem und war eines der ersten Anwendungsgebiete für genetische Algorithmen.

Genetische Algorithmen haben folgende Vorteile:

• Vorwissen: Wir müssen über das Optimierungsproblem nichts wissen. Es reicht, wenn wir die Parameter kennen und eine Zielfunktion haben, mit der wir die Lösungen auswerten können. Ob es dann um Handelsreisende oder Damen geht, ist eigentlich egal.

Beispiel:

Wir haben im Laufe der letzten Kapitel gesehen, wie wir die verschiedenen Operatoren auf unsere parametrisierten Hasen anwenden können. Wir können nun statt Hasen Wölfe parametrisieren und genau gleich vorgehen wie beim parametrisierten Hasen. Obwohl es sich um ganz andere Lebewesen und eine ganz andere Zielfunktion handelt, gehen wir genau gleich vor, also unabhängig vom darunterliegenden Problem. Wir brauchen eigentlich gar nicht zu wissen, um was für ein Problem es sich handelt.

• Einfachheit: Verglichen mit mathematischen Verfahren sind genetische Algorithmen sehr einfach zu implementieren und effizient auszuführen.

Aufgabe:

Beschreiben Sie in Worten, wie man einen genetischen Algorithmus ausführt. Beschreiben Sie auch, wie man das Problem $\sin x-x^{2}=0$ löst. Welche Beschreibung ist kürzer und/oder einfacher?

• Lösungsmenge: Wir erhalten nicht - im Gegensatz zu anderen Verfahren - eine einzige Lösung, sondern eine Menge von Lösungen. Dies ist von Vorteil, wenn wir aus irgendwelchen Gründen nicht mit der optimalen Lösung zufrieden sind oder einfach andere Varianten zur Auswahl haben wollen.

Beispiel:

Sie haben mittels eines genetischen Algorithmus' die Struktur einer Brücke optimiert. Ihr Chef findet die optimale Lösung scheusslich. Die Optimierung müssen Sie aber nicht nochmals laufen lassen, denn sie haben eine Bevölkerung von Brücken, die alle etwa gleich gut sind, aber nicht alle gleich aussehen.

Genetische Algorithmen haben aber nicht nur Vorteile. Einige der wichtigsten Nachteile oder Probleme sind:

• Direktlösungen schneller: Kennen wir für ein Optimierungsproblem eine direkte Lösung, wie zum Beispiel bei vielen mathematischen Problemen, dann ist diese direkte Lösung meistens um Grössenordnungen schneller als ein genetischer Algorithmus.

Beispiel:

Bei einer quadratischen Gleichung

$ax^{2}+bx+c=0$

mit der Unbekannten $x$ wissen wir, dass die Lösungen

$x_{1,2}={\frac {b\pm {\sqrt {b^{2}-4ac}}}{2a}}$

sind. Dies ist bedeutend einfacher und effizienter direkt zu berechnen als mit einem genetischen Algorithmus.

• Nicht zusammenhängende Lösungen: Wir sind bis jetzt immer davon ausgegangen, dass gute Lösungen sich ähnlich sind und dass man daher durch Mutation und Rekombination schrittweise zu besseren Lösungen gelangen kann. Es gibt aber ganze Klassen von Problemen wo dies nicht der Fall ist. Ein genetischer Algorithmus verkommt dann zu einer zufälligen Suche nach einer Nadel im Heuhaufen.

Beispiel:

Wir versuchen eine Zahl zwischen 1 und 100 zu erraten, dabei sagt unser Gegenspieler nicht "grösser" oder "kleiner", sondern nur "wahr" oder "falsch". Wir können somit Lösungen, die näher bei einer "guten" Lösung sind, nicht von denen unterscheiden, die weiter weg sind. Der Selektionsoperator würde die unterschiedlichen Lösungen alle gleich behandeln und keine eigentliche Selektion vornehmen. Die optimale Lösung könnte dann nur zufällig gefunden werden.

• Optimalität: Auch wenn der genetische Algorithmus zu einer Lösung -- oder Satz von Lösungen -- gelangt, die er nicht weiter optimieren kann, haben wir keine Garantie, dass wir wirklich das Optimum gefunden haben. Dieses ist eher ein generelles Problem vieler Optimierungsverfahren, welches eben auch von den genetischen Algortihmen geteilt wird.

Beispiel:

Wir erinnern uns an unsere Funktion aus Kapitel~\ref{kap:selektion} mit den zwei Minima. Wenn wir bei $x=1$ sind und unser Algorithmus dort eine Zeit lang hängen bleibt, wissen wir vom anderen Minimum bei $x=3$ nichts.

Zusammenfassend kann man sagen, dass genetische Algorithmen dann sinnvoll sind, wenn:

• wir über das Problem zu wenig wissen, um es direkt zu lösen,
• die Menge aller Lösungen zu gross ist, um sie direkt zu durchsuchen oder
• wenn wir von der zu optimierenden Zielfunktion nichts wissen - wir können sie nur auswerten.

Lernkontrolle

• Welche dieser Optimierungsprobleme sind für genetische Algorithmen geeignet, welche nicht? Begründen Sie Ihre Antwort.
  • Wir wollen das Minimum einer mathematischen Funktion finden, von der wir die Ableitungen analytisch berechnen können.
  • Wir wollen eine neue Tomate züchten, welche sich möglichst gut in viereckigen Schachteln verpacken lässt.
  • Wir wollen die Noten der letzten Prüfung mit unlauteren Mitteln ein bisschen verbessern. Um an diese zu gelangen, müssen wir ein achtstelliges Passwort des Lehrers im Computersystem der Schule, bestehend aus Buchstaben und Zahlen, erraten.
  • Wir wollen ein Computerprogramm schreiben, welches das Maximum einer beliebigen Funktion errechnet. Von der Funktion weiss das Programm nichts, es darf es aber an beliebigen Stellen auswerten.

Kapiteltest

Welche dieser Optimierungsprobleme sind für genetische Algorithmen geeignet, welche nicht?

1. Ein Schäfer mit drei Wölfen und drei Schafen will einen Fluss mit nur einem Boot überqueren. Da im Boot nur Platz für zwei Personen ist und weder die Wölfe noch die Schafe rudern können, muss der Schäfer jedes Tier einzeln rüberrudern. Zudem muss er darauf achten, dass in seiner Abwesenheit die Schafe nicht die Wölfe fressen, sobald sie in der Überzahl sind (es handelt sich hierbei um buddhistische Wölfe und hyperagressive Schafe). Wie bringt der Schäfer alle Tiere und sich selbst ohne Blutvergiessen über den Fluss?
2. Ein Werkteil muss zwei Maschinenteile zusammenhalten. Nebst einer gewissen Belastung, welche das Teil aushalten muss, soll es auch möglichst leicht sein. Die Stabilität, bzw.~die Tauglichkeit des Werkteils kann mittels einer Simulation ohne grossen Aufwand errechnet werden.

Lösungen

Lernkontrolle

1. Wenn wir von einer mathematischen Funktion die Ableitungen analytisch berechnen können, so können wir auch viel leichter die Minima und Maxima bestimmen, als mit genetischen Algorithmen. Dieses Problem wäre daher nicht geeignet.
2. Das gezielte Züchten von Pflanzen mit bestimmten Eigenschaften ist ein genetischer Algorithmus. Die Tomaten mutieren und rekombinieren unter sich und produzieren neue Individuen, die wir anhand einer Zielfunktion auswählen oder eliminieren können.
3. Die Zielfunktion, ob ein Passwort funktioniert oder nicht, liefert nur einen binären Wert, nämlich wahr oder falsch. Da alle falschen Lösungen das gleiche Resultat ergeben, liefern sie keine Information, die wir als Güte der Lösung interpretieren können. Somit sind die Lösungen nicht korreliert und das Problem eignet sich nicht für einen genetischen Algorithmus.
4. Da wir von der zu maximierenden Funktion rein gar nichts wissen, ist hier der Einsatz eines genetischen Algorithmus' angebracht.

Kapiteltest

1. Da die Zielfunktion nur binäre Resultate liefert -- sprich: richtig oder falsch -- und die Lösungen nicht endlich lang sind, eignet sich dieses Problem nicht zur Lösung mit einem genetischen Algorithmus.
2. Die Form des Werkteils bildet eine Lösung, die sich mit einer Simulation auswerten lässt. Kleine Änderungen an der Form können das Werkteil stabiler und/oder leichter machen. Dieses Problem ist daher gut geeignet zur Lösung mit einem genetischen Algorithmus.