Wie man der Bezeichnung bereits ansehen kann, ist der folgende Abschnitt stark an die natürliche Evolution (wie sie von Charles Darwin begründet wurde) und teilweise an die Genetik angelehnt.
Dazu werden folgende Begriffe aus der Biologie entlehnt (entgegenstehende religiöse Ansichten ignoriere ich hier im Hinblick auf die Zielsetzung dieses Skripts und ohne größere Böswilligkeit):
Zudem verbessern sich neben den Genen auch noch andere Umstände, die das Überleben und die Vermehrung stark beeinflussen. Beispielweise ist das Wissen, wann Getreide ausgesät werden muß, nicht in den Genen begründet, sondern wird von Individuum zu Individuum irgendwie weitergegeben; es bilden sich Sitten und Gebräuche heraus, die den Bestand günstig beeinflussen (in Grönland die Sitte, Iglus zu bauen; in warmen Gegenden der rituelle Verzicht auf bakteriell verseuchtes Schweinefleisch, dafür der wurmhemmende Genuß von Chillie; in den meisten Gesellschaften der weitgehende Verzicht auf Mord; und so weiter). Solche Effekte sind eng mit dem obigen Punkt ,,Fähigkeiten`` durch ,,Einwirkungen seiner Umgebung`` verknüpft, in der Soziologie sicher ein unerschöpfliches Thema, tun aber hier in der Regel nichts zur Sache (auch wenn Effekte aus diesem Gebiet durchaus auch algorithmisch interessant sein können).
Auch wenn beispielsweise von den Eltern an die Nachkommen überlieferte Sitten und Gebräuche, Wissen und so weiter nicht direkt in den Genen begründet liegt, so ist doch zumindest die Fähigkeit, Wissen zu sammeln und weiterzugeben, von den Genen abhängig.
Evolution ist demnach nicht eine Optimierung, die irgendwie rechnet, und dann schlagartig ein Ergebnis liefert, sondern ist vielmehr ein kontinuierlicher Prozeß, der eine anfangs schlechte Lösung Schritt für Schritt verbessert.
Was hat das alles mit Informatik zu tun (außer daß sogar Informatiker gelegentlich versuchen, sich fortzupflanzen)?
Wenn man sich den oben geschilderten Vorgang von Werden und Vergehen etwas aus der Entfernung betrachtet, dann ist die natürliche Evolution ein ständig fortgeführtes Experiment, in dem die Erbinformation kontinuierlich optimiert wird. Denn durch Mutation und Rekombination entstehen laufend neue Erbinformationen, welche durch die Selektion einer Prüfung unterworfen werden. Nur die Erbinformationen, die sich für die aktuelle Umgebung als günstig herausstellen, werden wiederum für Mutation und Rekombination verwendet und führen zu weiter variierten Sätzen von Information. Die schlechten Lösungen vergehen recht schnell und meist ohne viel Aufhebens, während gute Lösungen gepflegt und im weiteren sogar noch verbessert werden.
Selbst nach einer recht langen Rechenzeit in der Größenordnung einiger Millionen Jahre kann allerdings noch lange nicht von einem Optimum gesprochen werden angesichts weit verbreiteter Blödheit, Krieg, abstrusen Sekten einschließlich der katholischen Kirche, AIDS und der Bildzeitung; und das bei einem riesigen Platzverbrauch für das Experiment.
Bedenkt man aber den Ausgangszustand in Form von primitiven Einzellern, ist ein enormer Fortschritt zu bekunden, sodaß in den Sechziger Jahren ein findiger Mensch namens John M. Holland auf die Idee kam, ein solches Experiment im Rechner zu simulieren: Die Gene lassen sich als Binärinformation deuten, die Menge der Lebewesen besteht aus einem Feld von Elementen, die im wesentlichen die Gene beinhalten, und die Fähigkeit zu überleben und sich zu vermehren, wird mit einer Tauglichkeitsfunktion (fitness function) ausgedrückt. Die Rekombination und Mutation vorhandener Gene läßt sich leicht bewerkstelligen. Selektion ist das Löschen unbrauchbarer Elemente (also solche, für die sich ein schlechter Wert der Tauglichkeitsfunktion ergibt). Eher schwierig ist die Simulation der Umgebung auf die Tauglichkeit (Erziehung etc.). Außerdem ist zur Simulation realer Lebewesen das Wissen um die Bedeutung der Gene vonnöten, was in absehbarer Zukunft nicht erreicht sein wird.
Aber auch wenn man nicht die Welt simulieren kann (und das eigentlich auch nicht unbedingt muß), kann man das Verfahren zur Optimierung anderer Vorgänge verwenden. Die Anwendung eines solchen Verfahrens auf reale Problemstellungen heißt Evolutionsstrategie.
Um das Ganze praktisch nutzbar zu machen, weicht man also sinnvollerweise von der tatsächlichen Evolution etwas ab:
Die Fähigkeit der natürlichen Evolution, auf eine Veränderung der Lebensbedingungen durch Anpassung zu reagieren, wird damit üblicherweise nicht genutzt.
Das Ergebnis der Optimierung besteht dann aus den Genen des besten Lebewesens des letzten Evolutionsschrittes. In diesen Genen drückt sich die beste erreichte Annäherung an das unbekannte Optimum aus.
Wenn man entweder alle möglichen Gene probiert hat, oder zufällig die richtige Kombination getroffen hat, wird man auch die wirklich optimale Lösung haben (wenn man sie nicht versehentlich durch Mutation wieder zerstört). Normalerweise wird man aber bei komplexen Problemen nicht so lange warten können, sondern nach einer bestimmten Rechenzeit abbrechen, oder wenn die Verbesserung des/der besten Elemente von Evolutionsschritt zu Evolutionsschritt sich nicht mehr nennenswert verbessert. Dadurch erhält man typischerweise nicht die bestmögliche, sondern nur eine gute Lösung. Wenn man die beste Lösung braucht, und genug Zeit hat, mit einem genetischer Algorithmus darauf zu warten, kann man auch gleich alle Varianten der Eingabeparameter durchprobieren, und kommt damit sicherer zum Ziel.
Der grundsätzliche Ablauf hat damit das Aussehen von Bild 5.1.
Zu den einzelnen Schritten in Abbildung 5.1:
: Wenn man kein Wissen über eine sinnvolle Vorbelegung hat, initialisiert man die Gene aller Lebewesen einfach mit zufälligen Zahlen. Es muß nur sichergestellt sein, daß die folgenden Schritte damit auch klarkommen; beispielsweise können zufällig initialisierte Gleitkommazahlen gemäß dem üblicherweise verwendeten Standard IEEE754 einen ungültigen Wert haben (positive infinity, negative infinity, verschiedene NAN = not a number), der bei der weiteren Rechnung je nach System zu Laufzeitfehlern oder unsinnigen Ergebnissen führen kann, wenn nicht gezielt mit geeigneten Prüfungen dieser Fall abgefangen wird (wie im Blechdosenbeispiel Lösung mithilfe eines genetischen Algorithmus mit der Funktion isnan() in der Zielfunktion). Ebenso unsinnig sind natürlich zufällige Werte für Zeigervariablen in C- oder C++-Programmen.
Hat man dagegen bereits ein Vorwissen, wie eine vernünftige Lösung aussehen könnte oder welche Kombinationen sinnvoll sind und welche nicht, dann kann man die ersten Lebewesen natürlich gleich entsprechend initialisieren und dadurch die ersten Evolutionsschritte etwas beschleunigen.
Auf jeden Fall sollte man aber vermeiden, Lebewesen unnötigerweise identisch zu initialisieren; dadurch muß die genetische Vielfalt erst rechenaufwendig durch Mutation erzeugt werden; und: ohne Vielfalt kein Leben! Welchen Sinn hat die Rekombination, wenn alle möglichen Partner gleich sind?
Die Wahl von N ist etwas Glückssache: zuwenige Wesen bedeuten eine genetische Armut (wie in dem einen oder anderen Adelsgeschlecht), zuviele erhöhen den Rechenaufwand pro Evolutionsschritt. In jedem Fall ist es sinnvoll, N wesentlich kleiner zu machen als die Anzahl der Kombinationsmöglichkeiten der Eingangsparameter der Optimierung (also wesentlich kleiner als die Mächtigkeit der Definitionsmenge der Zielfunktion). Dies ergibt sich aber meist von selbst, weil die Vorgehensweise sinnvollerweise für relativ komplexe Probleme mit vielen Kombinationsmöglichkeiten angewendet wird, sodaß die Anzahl der im Arbeitsspeicher darstellbaren Wesen ohnehin klein ist im Vergleich zu allen möglichen Wesen.
entspricht der Selektion und ist meist einfach gelöst, indem die Gesamtzahl der Lebewesen konstant ist und beim Erzeugen neuer Wesen durch Rekombination alte überschrieben werden. Die Auswahl, welche Wesen entfallen sollen, kann unterschiedlich erfolgen. Zumindest sollten vorwiegend schlechte Lebewesen aussortiert werden, um ,,gute`` Gene bevorzugt zu erhalten, und ,,schlechte`` mit der Zeit aussterben zu lassen. Häufig wird immer das schlechteste Wesen gelöscht, oft wird auch aus den schlechteren eines willkürlich ausgewählt.
lehnt sich sehr eng an die natürliche Genetik an (Rekombination, crossing over): es werden jeweils zwei Elternteile gewählt (sinnvollerweise bevorzugt aus den tauglicheren Lebewesen), daraus werden ein oder zwei neue generiert. Bei einem erzeugten Lebewesen erfolgt dies dadurch, daß jedes Gen des neuen Wesens zufällig vom ersten oder vom zweiten Elternteil kopiert wird. Bei zwei neuen Wesen erhält das zweite genau die Gene der Eltern, die für das erste nicht verwendet wurden. Das neue Wesen (oder die beiden neuen) werden dem Lebensraum (Genpool) hinzugefügt, oder überschreiben zu löschende Elemente (siehe oben).
Man sollte nicht nur die beiden besten Lebewesen neu kombinieren, weil auch in den bisher nicht besten Wesen gute Anlagen schlummern können, die sich durch Rekombination oder Mutation vielleicht erst noch entfalten. Ebensowenig sollte man soviel rekombinieren, daß alle nicht so guten Elemente zu schnell verdrängt werden.
Geschickter ist, es einige wenige relativ gute zu rekombinieren, und dadurch einige wenige nicht so gute hinauszuwerfen. Das ganze Spiel lebt wie gesagt von einer gewissen Vielfalt!
: durch Mutation von einem oder wenigen Genen einiger Lebewesen bringt man etwas Vielfalt in den Genpool, der erst zu wirklich neuen Lösungen führen kann.
Aber auch hier ist Augenmaß angebracht: zuviel Mutation zerstört vorhandenes brauchbares Material; zuwenig verlangsamt die Evolution weil keine neuen Ideen in das System eingebracht werden.
: Die Genauigkeit der erreichten Lösung ist über die Laufzeit steuerbar.
Je nach Anforderungen führt man die Evolution fort, bis eine gewünschte Genauigkeit erreicht ist, oder bis eine zugebilligte Rechenzeit verbraucht ist. Das Erreichen einer bestimmten Genauigkeit ist allerdings nicht exakt zu erkennen, weil man das genaue (optimale) Ergebnis ja meistens nicht weiß.
Ersatzweise kann man die Genauigkeit anhand der Verbesserung des besten oder einiger der besten Lebewesen im letzten Schritt (oder besser über einige Schritte gemittelt) abschätzen. Wenn der Wert der Zielfunktion des jeweils besten Lebewesens in den ersten Generationen deutlich steigt, und dann im Verlauf weiterer Generationen offensichtlich gegen einen Höchstwert konvergiert, ist man vom Optimum nicht mehr weit entfernt.
: Die Information, welche Kombination der Eingangsparameter des Problems zur besten Lösung führen, steckt in den Erbinformationen des besten Lebewesens.
(Will man die erreichte Lösung erst bewerten, und dann entscheiden, ob noch weiter optimiert werden soll -eventuell mit anderen Parametern für Mutation etc.-, dann kann es sinnvoll sein, alle Lebewesen des letzten Schrittes zu speichern, um sie gegebenenfalls wieder für die nächste Iteration einlesen zu können.)
Je nachdem, ob man die Genetik mit ins Spiel bringt, oder nicht, teilen sich die Verfahren in zwei Gruppen auf:
Der Schwerpunkt liegt hier mehr auf Seite der Mutation, Rekombination kommt eher selten vor. Änderungen der Erbinformation werden in beliebig feinen Schritten durchgeführt (unbeschadet der Tatsache, daß eine reale Implementation natürlich nicht beliebig kleine Differenzen darstellen kann).
Durch die digitale Sichtweise wird die Erbinformation nicht beliebig fein, sondern ausschließlich in Schritten bestimmter Mindestgröße geändert.
Der Schwerpunkt der Evolution liegt hier eher bei der Rekombination, weniger bei der Mutation.
Sowohl die beiden Reinformen als auch vermischte (hybride) Verfahren führen zu folgenden charakteristischen Eigenschaften:
Weitere Anmerkungen:
Beispielweise ist es bei einer harten Bedingung (ein einzuhaltender Abgasgrenzwert etwa) ungeschickt, alle Lebewesen, die die Grenze überschreiten, mit dem kleinstmöglichen Wert der Zielfunktion abzustrafen. Besser wäre es, das Maß der Überschreitung mit einfließen zu lassen. Dann kann die Optimierung wesentlich zielgerichteter in Richtung besserer Lösungen gehen, die den Grenzwert einhalten.
Für numerische Aufgabenstellungen kann man deshalb durchaus ein eigenes Zahlenformat verwenden, das nur den in Frage kommenden Zahlenbereich in der nötigen Genauigkeit mit möglichst wenigen Bit kodiert (vielleicht Verwendung von Ganzzahlen/Festkommazahlen statt Gleitkommazahlen?), oder man verwendet Gleitkommazahlen mit der kleinsten sinnvollen Genauigkeit, falls man einen relativ großen Wertebereich abdecken muß.
Dabei ist es hilfreich, die Entwicklung des Lebewesen verfolgen zu können (beziehungsweise ihre Tauglichkeit).
Erschwerend kommt hinzu, daß sich das Ausmaß der einzelnen Operationen im Verlauf der Optimierung ändern sollte:
Starke Mutation hat also eine sehr enge Verwandtschaft zu den Monte-Carlo-Methoden, und ist zu Anfang besonders hilfreich um überhaupt erst im gesamten Definitionsraum Gebiete mit guten Verbesserungschancen zu finden.
Dadurch wird eine bereits erreichte Qualität erhalten und sukzessive verbessert; dies entspricht etwa dem Suchen eines lokalen Optimums ausgehend von einer nahe gelegenen Näherung.
Es wäre also günstig, nicht nur für die Häufigkeiten von Rekombination und Mutation gute Werte zu finden, sondern für diese auch noch einen guten Verlauf über die Generationen. Dies ist in sich wieder eine Optimierungsaufgabe, die man recht einfach nebenbei erledigen kann: für die zu variierenden Wahrscheinlichkeiten baut man in die Erbinformationen noch sogenannte Regulatorgene ein, die der üblichen Evolution zeitgleich mit den eigentlichen Erbinformationen aus der Aufgabenstellung unterworfen werden (eine Gengruppe gibt in wenigen Bit an, mit welcher Wahrscheinlichkeit das Lebewesen mutiert wird, ein weiteres entsprechend die Dringlichkeit einer Rekombination). Dadurch werden sich neben der eigentlichen Lösung auch gute Werte für die Steuerung des Algorithmus herausbilden. (Diese müssen natürlich vom Algorithmus auch verwendet werden, indem sie zur Entscheidung herangezogen werden, ob mutiert oder rekombiniert werden soll.) Neben der automatischen Anpassung hat man hier auch gleich den Effekt, daß die bereits guten Individuen schwächer mutieren, weil sich das Regulatorgen auf einem niedrigen Wert einpendelt, während die schlechten Individuen einen höheren Wert im Schnitt behalten (bis sie sich verbessern). Die Werte sind also nicht nur in jeder Generation für den gesamten Genpool konstant, sondern auch noch von der Güte der einzelnen Wesen abhängig.
In solchen Regulatorgenen bildet sich der erwähnte Konkurrenzdruck ab, der im Laufe der Entwicklung steigt.
www.wachtler.de