5.3 Genetische Algorithmen, Evolutionsstrategie

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):

• Ein Lebensraum besteht zu jedem Zeitpunkt aus einer bestimmten Anzahl von Lebewesen; die Anzahl kann variabel sein, ist aber in der Regel begrenzt (auch wenn dies nicht immer eingesehen wird).
• Gelegentlich entstehen neue Lebewesen.
• Ebenso sterben vorhandene und nehmen am weiteren Geschehen nicht mehr teil (es sei denn als Proteinlieferant für begrenzte Zeit).
• Jedes Lebewesen hat einen gewissen Satz Erbinformationen (Gene), die quasi ein Bauplan dieses Wesens sind. Einzelne Gene oder Gruppen davon (Allele) bewirken die Haarfarbe, die Anzahl der Beine, Nasen, Gesichtszüge, Bau der Organe, chemische Vorgänge und so weiter.
• Jedes der Lebewesen ist individuell und wird sich in der Regel von anderen mehr oder weniger unterscheiden. Als Ausprägung seiner Geninformationen nennt man ein solches Individuum auch Phänotyp.
• die Fähigkeiten eines Lebewesens ergeben sich teilweise aus seinen Erbinformationen (zwei Augen sehen mehr als 10 Ohren, mit vier Beinen kann man besser laufen als mit zweien, aber mit zwei Händen kann man besser den Kühlschrank öffnen als mit vier Hufen), teilweise aber auch aus den Einwirkungen seiner Umgebung auf das Lebewesen (Erziehung, Ernährung, Einnahme von Drogen, schwere Kindheit, Training etc.)
• jedes Lebewesen erhält seine Erbinformationen von zwei Elternteilen (die ungeschlechtliche Vermehrung durch Zellteilung, die teilweise bei Bakterien oder vielen Pflanzen (Vermehrung durch Ableger) beliebt ist, soll hier nicht weiter interessieren, weil sie hinsichtlich der Optimierung nicht so erfolgreich und auch aus Sicht der Informatik langweilig ist). Die Gene beider Elternteile werden mehr oder weniger willkürlich so kombiniert, daß sich einer oder mehrere neue Sätze von Erbinformationen ergeben, die jeweils zum Teile Gene von Vater und zum anderen Teil Gene der Mutter enthalten (Rekombination, crossing over). Bei der üblicherweise praktizierten Vermehrung wird von diesen beiden rekombinierten Genen nur eines verwendet, das andere verworfen und als Eiweiß entsorgt.
• Gelegentlich verändern sich Gene auch spontan (etwa durch Radioaktivität, Vorgänge in der Zelle durch Unzuverlässigkeit der beteiligten Reaktionen, Alkoholeinfluß, Medikamente, Alter...), sodaß weitere Rekombinationen mit einem veränderten Satz von Erbinformationen ausgeführt werden (Mutation).
• neben dem erfreulichen Thema Vermehrung sterben leider auch Lebewesen, und zwar umso leichter je schlechter sie an ihre Umgebung angepaßt sind. Früher oder später sterben sie alle, aber: Es gibt Lebewesen, die eine gute Anpassung an ihre Umgebung besitzen; diese überleben länger (weil sie rechtzeitig das Richtige essen (und zwar mindestens so schnell wie ihre Geschwister), sich schnell genug einen guten Platz suchen wenn die Wölfe kommen, und nicht Samstag abend besoffen aus der Disco heimfahren), und haben mehr Chancen sich zu vermehren (eine Rekombination der Gene ist nur möglich, wenn die Eltern noch leben und dazu willens und in der Lage sind; beispielweise sind in der Natur meist zwei Individuen verschiedener Geschlechter nötig, die sich zumindest kurzzeitig einig sein müssen). Die weniger tauglichen Individuen sterben leichter als die besseren (weil sie zu schnell Motorrad fahren, bekifft vor die Straßenbahn laufen, oder sich auf einen Kampf mit Keule und Tritt in den Unterleib einlassen), oder sind nicht in der Lage sich zu vermehren, bevor sie irgendwann eines mehr oder weniger natürlichen Todes sterben (durch biologische Defekte nicht attraktiv genug oder vermehrungsfähig, homosexuell, gucken lieber Sportschau, oder sind einfach zu dusselig). Je nach den Fähigkeiten eines Lebewesens gibt es also höhere oder niedrigere Chancen, die eigenen Gene in neue Lebewesen einzubringen, die wiederum gut oder schlecht mit ihrer Umwelt zurechtkommen (natürliche Selektion, ,,survival of the fittest``).
• Neben dem Sterben durch Untauglichkeit (oder eremitischen Lebensstil, was evolutionsmäßig auf dasselbe hinausläuft) kommt es auch vor, daß durch irgendwelche zufälligen Vorgänge ein hoffnungsvolles Leben ausgelöscht wird, obwohl es eigentlich recht tauglich war (Meteoriteneinschlag, ein anderer Idiot fährt ein taugliches Wesen versehentlich oder absichtlich um), oder andererseits ein gar nicht so taugliches Wesen auch die Gelegenheit zur Vermehrung bekommt (ein blindes Huhn...). Je nach Weltanschauung nennt man so etwas Schicksal, Vorsehung, Gottes Wille etc.; oder einfach ,,dumm gelaufen``.
• Die eigentliche Evolution besteht jetzt darin, daß sich der Lebensraum mit der Bevölkerung so entwickelt, daß die Lebewesen von Generation zu Generation ,,besser`` werden, indem sich Gene, die in Anbetracht der Umwelt zu einer hohen Tauglichkeit führen, mit der Zeit die unbrauchbaren Gene verdrängen.

  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.

• eine ganz wichtige Eigenheit der Evolution ist die Konkurrenz: In einem frühen Stadium können sich noch Lebewesen behaupten, die vom Optimum weit entfernt sind (,,unter Blinden ist der Einäugige König``). Je weiter sich die Evolution entwickelt, desto besser muß ein Lebewesen angepaßt sein, um nicht von besseren verdrängt zu werden. Dieser steigende Konkurrenzdruck ist also natürlich, und beschleunigt die Evolution deutlich.

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 Tauglichkeitsfunktion wird vorgegeben, und entspricht der Zielfunktion des zu optimierenden Problems.
• Der Satz an Erbinformationen (die Gene) drückt eine Kombination der variablen Eingangsgrößen des gegebenen Problems aus.
• Die Tauglichkeitsfunktion verwendet nur fest vorgegebene Größen sowie die Erbinformationen eines Lebewesens, nicht Umstände wie Aufenthaltsort im Lebensraum, Sozialverhalten, angesammeltes Wissen in Gemeinschaften oder ähnliches. (Will man solche Informationen auswerten, baut man sie in die Gene mit ein und behandelt sie fortan ebenso.)
• Dementsprechend wirkt sich die Umwelt nicht mehr auf die Lebewesen aus; neben Rekombination und Mutation werden sie nicht weiter beeinflußt (abgesehen von ihrem willkürlichen Tod). Insbesondere können sie ihre Chancen auf Fortpflanzung nicht durch Lernen, Training im Sportstudio oder Schminken verbessern (also keine Rückkopplung der Umwelt auf die Fähigkeiten innerhalb eines Lebens).
• Die Anzahl der Lebewesen ist (meistens) konstant; der Lebensraum ist damit einfach ein Feld von Genen.
• Der Einfachheit halber werden untaugliche Lebewesen üblicherweise (rückstandsfrei) entsorgt, indem sie durch Produkte aus der Rekombination überschrieben werden.
• Die einzelnen Lebewesen haben in der Regel keine Beziehungen untereinander. Sie existieren unabhängig voneinander und werden nur verglichen und gelegentlich entsorgt. Die einzige Stelle, an der sie in Beziehung treten, ist bei der Rekombination: ein erbarmungsloser Algorithmus wählt zwei Lebewesen aus, um ihre Gene neu zu kombinieren. Die ausgewählten Lebewesen verbleiben dabei im Lebensraum; ihre Nachkommen werden zusätzlich abgelegt (möglicherweise als Ersatz für andere ausgeschiedene Wesen).

• Die Umgebung ist meist konstant; es ändern sich also nicht laufend die Bedingungen für die Lebewesen. Dies würde sich in einer laufenden Anpassung der Zielfunktion ausdrücken. Da die Zielfunktion aber dem zu optimierenden Problem entspricht, soll sie sich ja eben nicht laufend ändern. (Es gibt gelegentlich den Fall, daß man eine Optimierung in mehreren Schritten erreichen will; dann kann eine Anpassung der Zielfunktion und eine Weiterverwendung der existierenden Lebewesen durchaus sinnvoll sein. Beispielsweise könnte man bei einer aufwendig zu berechnenden Zielfunktion eine erste Teilevolution veranstalten, die mit einer vereinfachten Zielfunktion relativ schnell eine Ausgangslage für einen zweiten, genaueren Teil liefert.)

  Die Fähigkeit der natürlichen Evolution, auf eine Veränderung der Lebensbedingungen durch Anpassung zu reagieren, wird damit üblicherweise nicht genutzt.

• Es wird meist keine Unterscheidung der Geschlechter gemacht; dies führt schon im realen Leben zu viel Ärger und hat offensichtlich kaum Vorteile (zumindest nicht in der rechnerischen Umsetzung; im realen Leben, wo sich auch Gebräuche einbürgern wie Arbeitsteilung im näheren Umfeld beispielsweise, und die Zöglinge einer gewissen Pflege bedürfen, scheint es in den letzten Jahrmillionen Vorteile geboten zu haben, sonst hätte es sich wohl nicht so entwickelt).

• Die Evolution läuft nicht in Echtzeit ab, sondern deutlich schneller (wenn man nicht gerade in Java oder Basic programmiert).

• Die Evolution wird nicht endlos fortgeführt, sondern irgendwann beendet.

  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.

Abbildung 5.1: Prinzipieller Ablauf eines genetischen Algorithmus

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:

• Die eigentlichen Evolutionsstrategien verwenden keine genetischen Vorgänge. Vielmehr wird jedes Individuum als Satz numerischer Werte (entsprechend der Allele) betrachtet; die Optimierung findet statt durch Ändern dieser Werte und Neubewerten der Lösung. Die Änderungen werden nicht auf Bitebene durchgeführt, sondern wirklich als Änderung der numerischen Werte um bestimmte Beträge aufgefaßt. Das klassische Beispiel hierfür ist die Optimierung einer Überschalldüse durch Rechenberg und Schwefel, indem eine Folge von Ringen variablen Durchmessers einen Strömungskanal ergibt; die einzelnen Durchmesser werden nun reihum so variiert, daß der Wirkungsgrad der Düse optimal wird.

  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).

• Bei einer zusätzlichen Verwendung der genetischen Vorgänge spricht man von genetischen Algorithmen. Nur hier tritt eine Rekombination vorhandener Erbinformationen und willkürliche Mutation auf Bitebene auf. Dies ist die von Holland vorgeschlagene Vorgehensweise. Weil die Erbinformation hier nicht nur als ein Satz numerischer Werte entsprechend ihrer Bedeutung aus der Aufgabenstellung aufgefaßt, sondern auch auf Bitebene betrachtet wird, bezeichnet man die Erbinformation hier auch als digitalen Code.

  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.

Allerdings sind die Grenzen zwischen diesen beiden Gruppen fließend. Beispielweise kann man Mutation bei genetischen Algorithmen durchaus anhand der numerischen Entsprechung der Gene durchführen; ebenso ist bei Evolutionsstrategien eine Rekombination vorhandener Individuen denkbar, indem die numerischen Werte der Allele gemittelt werden (sogenannte intermediäre Vererbung). In der Praxis wird eine Mischung der beiden Reinformen meist günstiger sein als eine Form alleine; die Natur kennt keine Ideologie.

Sowohl die beiden Reinformen als auch vermischte (hybride) Verfahren führen zu folgenden charakteristischen Eigenschaften:

• Man erhält in der Regel vermutlich nicht die beste Lösung, sondern (mit Glück oder Geschick) eine gute Näherung.
• Die Zielfunktion muß nicht differenzierbar sein, sondern nur berechenbar.
• Eine Implementation ist gut vektorisierbar und parallelisierbar, und damit auch auf entsprechender Hardware effektiv zu nutzen.
• Es ist kein tiefes Verständnis der Lösung nötig; allerdings erhält man aus der gelieferten Lösung auch kein Verständnis, sondern nur numerische Ergebnisse in Form guter Gene. Insofern ist das Verfahren nicht hilfreicher als ein ,,gut geraten``.
• Besonders geeignet ist das Verfahren für komplexe Optimierungsprobleme, für die keine geschlossene Lösung gefunden werden kann: aerodynamische Auslegung von Flugzeugen, Tragflügeln, Verdichtern und Turbinen, Festigkeits- oder Schwingungsoptimierung und viele andere technische Aufgabenstellungen, für die zwar eine gegebene Lösung bewertet werden kann, aber kein vernünftiger Weg existiert, zu bewertende Lösungen sinnvoll zu erzeugen; weiterhin rechnerisch schwer zu handhabende Probleme aus der gesamten Informatik wie NP-vollständige Probleme (Travelling Salesman Problem), falls auf die exakte Lösung verzichtet werden kann und eine gute Lösung genügt.

Weitere Anmerkungen:

• Die Zielfunktion wird häufig aufgerufen, und sollte deshalb möglichst schnell berechenbar sein
• Die Zielfunktion sollte auch sehr schlechte Lebewesen möglichst differenziert bewerten, um der Evolution beim Verbessern zu helfen.

  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.

• Der Rechenaufwand steigt mit dem Umfang der Gene jedes Lebewesens; deshalb sollte die Information in den Genen so gepackt wie möglich sein. Unnötige Redundanz kostet hier echte Rechenzeit durch überflüssige Variationen und effektive Verkleinerung des Genpools.

  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ß.

• Generell gehen Details des Verfahrens (Wahrscheinlichkeiten für Mutation und Rekombination, welche Elemente sollen dafür ausgewählt werden, welche sollen sterben, wieviele Lebewesen soll es geben...) stark in die Geschwindigkeit und Qualität der Lösung ein; es gibt aber keine allgemein gültigen Regeln dafür. Vielmehr muß der Anwender sie geschickt wählen beziehungsweise etwas probieren.

  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:

  • Wenn man zu Beginn der Evolution viele schlechte Wesen hat, kann man mit fleißiger Mutation schnell eine Verbesserung erreichen (egal, was man ändert: viel schlimmer kann es kaum werden, eigentlich nur besser!). Hat man dagegen etwas später bereits viele gute Lebewesen erschaffen, dann werden diese durch zu starke Mutation auch leicht wesentlich schlechter (viel besser können sie ja nicht mehr werden!). Deshalb macht es Sinn, anfangs stärker mutieren zu lassen, und später etwas weniger. In den meisten Fällen ist es auch sinnvoll, spätestens nach einigen Evolutionsschritten nur noch die schlechten Wesen stark zu mutieren, und die besseren etwas weniger.

    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.

  • Analog ist es meist es günstig, sich nach einigen Generationen mehr auf Rekombination und gegebenenfalls intermediäre Vererbung zu stützen.

    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.