Warum Genetische Algorithmen ?


An erster Stelle sollte bei der Betrachtung von Algorithmen die Frage stehen ...

Warum überhaupt ...?

Der wesentliche Grund ist, dass es Probleme gibt, die auf anderem Wege nicht oder nicht effektiv genug gelöst werden können. Wie kann das sein, wo doch die Leistung von Computern in den letzten Jahren so immens zugenommen hat? Die Antwort ist sehr einfach: Es gibt Probleme, die so groß sind, dass selbst mit den schnellsten denkbaren Computern eine Lösung innerhalb der Lebensdauer des Weltalls nicht möglich ist. Insbesondere die np-vollständigen Probleme haben (bisher?) einer vollständigen Lösung standhaft getrotzt. Viele von ihnen haben neben dieser vertrackten Eigenschaft aber gleichzeitig die Möglichkeit, prinzipiell mögliche Zustände des Systems nicht nur anzugeben, sondern sie auch schnell zu bewerten.

[np-vollständige Probleme -bitte für genauere Definitionen nachlesen- sind Probleme, deren Größe des Lösungsraumes exponentiell von der Zahl der Knoten abhängt, bei denen aber eine Bewertung mit polynomialem Aufwand zu bestimmen ist.]

Welche Bedingungen müssen also vorgegeben sein?

  1. Das Problem ist ein Suchproblem, da es kein direktes Lösungsverfahren gibt.
  2. Der Lösungsraum ist so groß, z.B. nicht endlich, dass eine vollständige Suche versagen muss.
  3. Es gibt eine relativ schnelle Bewertungsfunktion für Zustände im Lösungsraum (fitness).
  4. Keines der optimierten Suchverfahren, auch nicht greedy wie z.B. beim minimal spanning tree, liefert eine Lösung.

Wie kommt man auf eine solche Idee?

Gott würfelt eben doch, und das sehr wirkungsvoll, wie die belebte Natur zeigt. (Übrigens tritt Selbstorganisation auch in der nicht belebten Natur auf.) Inzwischen ist es in der Technik und Informatik ein vielfach gegangener Weg nachzumachen, was uns die Natur vorgemacht hat. Für diesen an vielen Stellen schon sehr erfolgreichen Gedanken hat sich inzwischen der Name Bionik festgesetzt. Der Grundgedanke bei den Genetischen Algorithmen ist:

Wenn die Natur bei der Entwicklung optimaler Systeme so erfolgreich ist, dann versuchen wir ihre Prozesse zu verstehen und nachzubauen.

Vieles an dieser Kurzformulierung stimmt natürlich nicht oder nur bedingt. Sie ist -hoffentlich- im selben Sinne optimal wie die Natur: Sie ist nicht die beste, aber erfolgreich!

Evolution ist ein sehr effektiver Optimierungsprozess! Wir werden bei den Genetischen Algorithmen also in vielen Fällen nicht die oder eine von gleichwertigen besten Lösungen finden, aber eine gute, die meistens besser ist als eine auf einem anderen Wege zu findende Lösung. Wenn nicht, nehme man den anderen Weg!

Welche sind die wesentlichen modellierten Prozesse?

Es sind vor allem die drei Prozesse

die bei Genetische Algorithmen eingesetzt werden.

Alle drei Prozesse treten dabei nicht gesteuert auf, sondern zufällig. Ich gehe davon aus, dass jedem von Ihnen klar ist, was das konkret bei Berechnungen mit Computern bedeutet. Der Grundgedanke ist: Schaffe dir einen Pool von möglichen Zuständen des Systems, und lasse es nun mehrere oder viele Schleifen durchlaufen, bei denen alle Individuen des Pools nacheinander immer wieder möglicher Mutation, möglichem Kreuzen mit anderen Individuen des Pools und einem Ausleseprozess ( die guten ins Töpfchen, die schlechten ins Kröpfchen ) unter allen Individuen des Pools ausgesetzt werden.

Wozu macht man sich überhaupt den Aufwand?

Man könnte doch einfach einen ähnlichen Zustand suchen, der besser ist als der gegenwärtige und dann immer so weiter machen bis zur Lösung! Das geht tatsächlich so bei einigen Problemen, die dann sehr schnell und erfolgreich mit dieser Strategie gelöst werden können. Das setzt allerdings zwei Eigenschaften voraus:

  1. Ich muss wissen, in welcher Richtung die Zustände besser werden, also eine lokale Bewertungsfunktion besitzen.
  2. Der Lösungsraum muss so beschaffen sein, dass er keine lokalen Maxima enthält. Bin ich in einem lokalen Maximum angekommen, dann kommt das beschriebene Verfahren nicht weiter, da es einen Endzustand erreicht hat: Alle benachbarten Zustände sind schlechter.

Wie schaffen es Genetische Algorithmen, das zu vermeiden?

Der Gedanke lässt sich sehr einfach beschreiben: Man muss das System aus einem solchen lokalen Maximum herausbringen, energetisch würde man sagen, man muss es aufheizen, damit es seinen teilgeordneten Zustand wieder verlässt und zunächst einen stärker ungeordneten, schlechteren Zwischenzustand einnimt, von dem aus es von ihm aus dann einem besseren als dem vorher erreichten zustreben kann. Obwohl prinzipiell sowohl die Mutation als auch das Kreuzen von zwei Individuen dazu führen kann, kann man sagen, dass das Kreuzen eher den konvergierenden Effekt hat und das Mutieren den divergierenden, aber das ist abhängig vom Problem.

Die grundlegenden Verfahren

Die wesentlichen Verfahren sind

Es gibt Probleme, bei denen ein Kreuzen nicht oder nicht sinnvoll modellierbar ist, trotzdem aber eine Mutation. Dann können evolutionäre Prozesse dennoch nachgebildet werden und aus bestehenden Zuständen bessere generiert werden, solange eine Bewertungsfunktion (fitness) zur Verfügung steht.

Eigentlich hätte das Thema Evolutionäre Algorithmen (Oberbegriff) heißen müssen. Mit Genetische Algorithmen bezeichnet man speziell die Verfahren, die alle drei Prozesse nutzen. Die Zustände lassen sich in der Regel mit einer linearen Datenstruktur ( Vektor oder Liste ) beschreiben.

Warum Genetische Algorithmen im Unterricht?

Dafür sprechen aus meiner Sicht zwei wesentliche Aspekte:

  1. np-vollständige Probleme sind noch aktueller Forschungsbereich. Für viele Probleme liegen Artikel aus der neueren Literatur vor. Ich selbst bin durch Informationen über Arbeiten an der FH Wedel auf dieses Problem gestoßen: Container - Ladeproblem.
  2. Genetische Algorithmen eignen sich hervorragend für eine Gruppenarbeit insbesondere im Leistungskurs. Das Problem ist einerseits umfangreich genug, um interessant zu sein, bleibt aber durch gute Modularisierbarkeit überschaubar.

Warum mit tsp?

Das tsp ( travelling salesperson problem ) hat zwei wichtige Vorteile für den Unterricht.

  1. Man kann sehr einfach zeigen, dass der Suchaufwand exponentiell mit der Zahl der Orte ansteigt.
  2. Die Zustände des Systems lassen sich gut bildlich darstellen. Die Schülerinnen und Schüler können also auf dem Bildschirm sehen, wie das Verfahren arbeitet.

Und was kommt heraus?

Nicht immer, aber manchmal eben doch: