An erster Stelle sollte bei der Betrachtung von Algorithmen die Frage stehen ...
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.]
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!
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.
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:
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 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.
Dafür sprechen aus meiner Sicht zwei wesentliche Aspekte:
Das tsp ( travelling salesperson problem ) hat zwei wichtige Vorteile für den Unterricht.
Nicht immer, aber manchmal eben doch: