Genetischer Algorithmus

Was ist das?

Die natürliche Evolution kann als ein Spiel modelliert werden, in dem die Belohnung für einen Organismus, der ein gutes Spiel des Lebens spielt, die Weitergabe seines genetischen Materials an seine Nachfolger und sein weiteres Überleben sind. ^[2] In der natürlichen Evolution hängt die Leistung eines Individuums davon ab, mit wem es arbeitet und mit wem es konkurriert, sowie von seiner Umwelt. Genetische Algorithmen sind eine Simulation der natürlichen Selektion auf einer Population von Kandidaten für die Lösung eines Optimierungsproblems (Chromosomen, Individuen, Lebewesen oder Phänotypen).

Die Kandidaten werden bewertet und gekreuzt, um gute Lösungen zu finden. Solche Lösungen können viel Zeit in Anspruch nehmen und sind für einen Menschen nicht offensichtlich. Eine evolutionäre Phase wird mit einer Population zufällig generierter Wesen begonnen. In jeder Generation wird die Tauglichkeit jedes einzelnen Individuums in der Population bewertet. Einige werden zufällig aus der aktuellen Population ausgewählt (auf der Grundlage ihrer Fitness) und modifiziert (rekombiniert und möglicherweise zufällig mutiert), um eine neue Population zu bilden. Der Zyklus wiederholt sich mit dieser neuen Population. Der Algorithmus endet entweder nach einer bestimmten Anzahl von Generationen oder nachdem ein guter Fitness-Level für die Population erreicht wurde. Wenn der Algorithmus aufgrund des Erreichens einer maximalen Anzahl von Generationen beendet wurde, bedeutet dies nicht unbedingt, dass ein guter Fitness-Level erreicht wurde.

Programmierung auf einem Computer

Der Pseudocode ist:

1. Initialisierung: Einige mögliche Lösungen werden erstellt; sehr oft werden diese zufällige Werte haben
2. Auswertung: Eine Fitnessfunktion bewertet jede Lösung; die Bewertung ist eine Zahl, die angibt, wie gut diese Lösung das Problem löst.
3. Die folgenden Schritte werden so lange durchgeführt, bis die Anforderung zum Anhalten erfüllt ist:
1. Auswahl: Wählen Sie die Lösungen/Einzelpersonen für die nächste Iteration
2. Rekombination: Kombinieren der gewählten Lösungen
3. Mutation: Zufällige Änderung der neu geschaffenen Lösungen
4. Auswertung: Wenden Sie die Fitnessfunktion an, siehe Schritt 2.
5. Wenn die Anforderung zum Anhalten nicht erfüllt ist, beginnen Sie erneut mit dem Auswahlschritt.

Beispiel

Die obige Beschreibung ist abstrakt. Ein konkretes Beispiel hilft.

Bewerbungen

Allgemeines

Genetische Algorithmen sind gut in der Lage, Probleme zu lösen, die die Zeit- und Ablaufplanung einschließen. Sie wurden auch in der Technik angewandt. Sie werden oft verwendet, um globale Optimierungsprobleme zu lösen.

Als allgemeine Faustregel gilt, dass genetische Algorithmen in Problembereichen mit einer komplexen Fitnesslandschaft nützlich sein könnten, da das Mischen darauf abzielt, die Bevölkerung von lokalen Optima wegzubewegen, in denen ein traditioneller Bergsteigeralgorithmus stecken bleiben könnte. Häufig verwendete Crossover-Operatoren können keine einheitliche Population verändern. Mutation allein kann die Ergodizität des gesamten genetischen Algorithmusprozesses (als Markov-Kette betrachtet) gewährleisten.

Beispiele für Probleme, die durch genetische Algorithmen gelöst werden, sind: Spiegel, die so konstruiert sind, dass sie das Sonnenlicht zu einem Sonnenkollektor leiten, Antennen, die so konstruiert sind, dass sie Funksignale im Weltraum empfangen, Laufmethoden für Computerfiguren, optimales Design von aerodynamischen Körpern in komplexen Strömungsfeldern

In seinem Algorithm Design Manual rät Skiena von genetischen Algorithmen für jede Aufgabe ab: "Es ist ziemlich unnatürlich, Anwendungen im Hinblick auf genetische Operatoren wie Mutation und Crossover auf Bit-Strings zu modellieren. Die Pseudobiologie fügt eine weitere Ebene der Komplexität zwischen Ihnen und Ihrem Problem hinzu. Zweitens benötigen genetische Algorithmen bei nicht-trivialen Problemen sehr viel Zeit. [...] Die Analogie zur Evolution - wo bedeutende Fortschritte Millionen von Jahren erfordern - kann durchaus angemessen sein. Ich bin noch nie auf ein Problem gestoßen, bei dem mir genetische Algorithmen der richtige Weg schienen, es zu lösen. Außerdem habe ich noch nie Rechenergebnisse gesehen, bei denen genetische Algorithmen verwendet wurden, die mich positiv beeindruckt haben. Halten Sie sich an simuliertes Glühen für Ihre heuristischen Such-Voodoo-Bedürfnisse".

Brettspiele

Brettspiele sind ein sehr relevanter Teil des Bereichs der genetischen Algorithmen in der Anwendung auf spieltheoretische Probleme. Ein großer Teil der frühen Arbeiten über Computerintelligenz und Spiele richtete sich auf klassische Brettspiele, wie z.B. Tic-Tac-Toe,^[3] Schach und Dame. ^[4] Brettspiele können heute in den meisten Fällen von einem Computer auf einem höheren Niveau gespielt werden als die besten Menschen, selbst mit blinden, erschöpfenden Suchtechniken. Go ist eine bekannte Ausnahme von dieser Tendenz und hat bisher Maschinenangriffen widerstanden. Die besten Go-Computerspieler spielen jetzt auf dem Niveau eines guten Neulings. ^[5][6] Die Go-Strategie soll sich stark auf die Mustererkennung stützen und nicht nur auf die logische Analyse wie beim Schach und anderen eher Figuren-unabhängigen Partien. Der enorme effektive Verzweigungsfaktor, der erforderlich ist, um qualitativ hochwertige Lösungen zu finden, schränkt die Vorausschau, die innerhalb einer Zugfolge-Suche verwendet werden kann, stark ein.

Computerspiele

Der genetische Algorithmus kann in Computerspielen verwendet werden, um künstliche Intelligenz zu schaffen (der Computer spielt gegen Sie). Dies ermöglicht ein realistischeres Spielerlebnis; wenn ein menschlicher Spieler eine Abfolge von Schritten finden kann, die auch bei der Wiederholung in verschiedenen Spielen immer zum Erfolg führen, kann es keine Herausforderung mehr geben. Umgekehrt, wenn eine Lerntechnik wie ein genetischer Algorithmus für einen Strategen die Wiederholung früherer Fehler vermeiden kann, wird das Spiel spielbarer.

Genetische Algorithmen erfordern die folgenden Teile:

• Eine Methode zur Darstellung der Herausforderung im Hinblick auf die Lösung (z.B. die Führung von Soldaten bei einem Angriff in einem Strategiespiel)
• Eine Fitness- oder Bewertungsfunktion, um die Qualität einer Instanz zu bestimmen (z.B. eine Messung des Schadens, der einem Gegner bei einem solchen Angriff zugefügt wurde).

Die Fitnessfunktion akzeptiert eine mutierte Instanziierung einer Entität und misst ihre Qualität. Diese Funktion wird an die Problemdomäne angepasst. In vielen Fällen, insbesondere bei der Code-Optimierung, kann die Fitnessfunktion einfach eine System-Timing-Funktion sein. Sobald eine genetische Repräsentations- und Fitnessfunktion definiert ist, instanziiert ein genetischer Algorithmus erste Kandidaten wie zuvor beschrieben und verbessert sie dann durch wiederholte Anwendung von Mutations-, Kreuzungs-, Inversions- und Selektionsoperatoren (wie entsprechend der Problemdomäne definiert).

Einschränkungen

Es gibt Einschränkungen bei der Verwendung eines genetischen Algorithmus im Vergleich zu alternativen Optimierungsalgorithmen:

• Die wiederholte Bewertung von Fitnessfunktionen für komplexe Probleme ist oft das einschränkendste Segment künstlicher evolutionärer Algorithmen. Das Finden der optimalen Lösung für komplexe Probleme erfordert oft sehr teure Fitnessfunktionsbewertungen. Bei Problemen der realen Welt, wie z.B. Strukturoptimierungsproblemen, kann eine einzelne Funktionsauswertung mehrere Stunden bis mehrere Tage einer vollständigen Simulation erfordern. Typische Optimierungsmethoden können mit solchen Arten von Problemen nicht umgehen. Oft ist es notwendig, eine Approximation zu verwenden, da die Berechnung der genauen Lösung zu lange dauert. Genetische Algorithmen kombinieren manchmal verschiedene Approximationsmodelle, um komplexe Probleme aus dem wirklichen Leben zu lösen.
• Genetische Algorithmen lassen sich nicht gut skalieren. Das heißt, wenn die Anzahl der Elemente, die einer Mutation ausgesetzt sind, groß ist, nimmt die Größe des Suchraums oft exponentiell zu. Das macht es extrem schwierig, die Technik bei Problemen wie dem Entwurf eines Motors, eines Hauses oder eines Flugzeugs anzuwenden. Um genetische Algorithmen bei solchen Problemen einzusetzen, müssen sie in eine möglichst einfache Darstellung zerlegt werden. Aus diesem Grund sehen wir evolutionäre Algorithmen, die Entwürfe für Fanschaufeln anstelle von Triebwerken, Gebäudeformen anstelle von detaillierten Konstruktionsplänen und Tragflächen anstelle ganzer Flugzeugkonstruktionen kodieren. Das zweite Problem der Komplexität ist die Frage, wie Teile, die sich so entwickelt haben, dass sie gute Lösungen darstellen, vor weiterer zerstörerischer Mutation geschützt werden können, insbesondere wenn ihre Tauglichkeitsbeurteilung erfordert, dass sie sich gut mit anderen Teilen kombinieren lassen.
• Die "bessere" Lösung ist nur im Vergleich zu anderen Lösungen. Folglich ist das Stoppkriterium nicht bei jedem Problem klar.
• Bei vielen Problemen neigen genetische Algorithmen dazu, eher in Richtung lokaler Optima oder sogar willkürlicher Punkte zu konvergieren als in Richtung des globalen Optimums des Problems. Das bedeutet, dass der Algorithmus nicht "weiß, wie" er kurzfristige Fitness opfern muss, um längerfristige Fitness zu erlangen. Die Wahrscheinlichkeit, dass dies eintritt, hängt von der Form der Fitnessfunktion ab: Bestimmte Probleme machen es leicht, das globale Optimum zu finden, andere wiederum können es der Funktion erleichtern, das lokale Optima zu finden. Dieses Problem kann durch die Verwendung einer anderen Fitnessfunktion, die Erhöhung der Mutationsrate oder durch den Einsatz von Selektionstechniken, die eine vielfältige Population von Lösungen aufrechterhalten, gemildert werden. Eine gängige Technik zur Erhaltung der Vielfalt ist die Verwendung einer "Nischenstrafe": Jeder Gruppe von Individuen mit ausreichender Ähnlichkeit (Nischenradius) wird eine Strafe hinzugefügt, die die Repräsentation dieser Gruppe in den folgenden Generationen verringert und es ermöglicht, andere (weniger ähnliche) Individuen in der Population zu behalten. Dieser Trick ist jedoch je nach der Landschaft des Problems möglicherweise nicht wirksam. Eine andere mögliche Technik wäre, einfach einen Teil der Bevölkerung durch zufällig generierte Individuen zu ersetzen, wenn der größte Teil der Bevölkerung einander zu ähnlich ist. Diversität ist bei genetischen Algorithmen (und genetischer Programmierung) wichtig, da die Kreuzung über eine homogene Population keine neuen Lösungen liefert. Bei Evolutionsstrategien und evolutionärer Programmierung ist Diversität nicht wesentlich, weil man sich stärker auf Mutation verlässt.
• Das Arbeiten mit dynamischen Datensätzen ist schwierig, da die Genome schon früh beginnen, sich auf Lösungen zuzubewegen, die für spätere Daten möglicherweise nicht mehr gültig sind. Es wurden mehrere Methoden vorgeschlagen, um dies zu beheben, indem die genetische Vielfalt irgendwie erhöht und eine frühe Konvergenz verhindert wird, entweder durch Erhöhung der Mutationswahrscheinlichkeit bei abnehmender Lösungsqualität (als ausgelöste Hypermutation bezeichnet) oder durch gelegentliche Einführung völlig neuer, zufällig generierter Elemente in den Genpool (als zufällige Einwanderer bezeichnet). Auch hier können Evolutionsstrategien und evolutionäre Programmierung mit einer sogenannten "Komma-Strategie" umgesetzt werden, bei der die Eltern nicht beibehalten und neue Eltern nur aus den Nachkommen ausgewählt werden. Dies kann bei dynamischen Problemen wirksamer sein.
• Genetische Algorithmen können Probleme, bei denen das einzige Fitnessmass ein einziges Richtig/Falsch-Mass ist (wie bei Entscheidungsproblemen), nicht effektiv lösen, da es keine Möglichkeit gibt, sich der Lösung anzunähern (kein Hügel zu erklimmen). In diesen Fällen kann eine Zufallssuche so schnell eine Lösung finden wie ein GA. Wenn die Situation jedoch eine Wiederholung des Erfolgs-/Misserfolgsversuchs mit (möglicherweise) unterschiedlichen Ergebnissen zulässt, dann stellt das Verhältnis von Erfolgen und Misserfolgen ein geeignetes Fitnessmass dar.
• Bei spezifischen Optimierungsproblemen und Probleminstanzen können andere Optimierungsalgorithmen hinsichtlich der Konvergenzgeschwindigkeit effizienter sein als genetische Algorithmen. Zu den alternativen und komplementären Algorithmen gehören Evolutionsstrategien, evolutionäre Programmierung, simuliertes Ausglühen, Gauß'sche Anpassung, Bergsteigen und Schwarmintelligenz (z.B.: Ameisenkolonie-Optimierung, Partikelschwarm-Optimierung) sowie Methoden, die auf ganzzahliger linearer Programmierung basieren. Die Eignung genetischer Algorithmen hängt von der Menge an Wissen über das Problem ab; bekannte Probleme haben oft bessere, spezialisiertere Ansätze.

Geschichte

1950 schlug Alan Turing eine "Lernmaschine" vor, die parallel zu den Prinzipien der Evolution arbeiten sollte. Die Computersimulation der Evolution begann bereits 1954 mit der Arbeit von Nils Aall Barricelli, der den Computer am Institute for Advanced Study in Princeton, New Jersey, benutzte. Seine Publikation von 1954 fand keine große Beachtung. Ab 1957 veröffentlichte der australische Quantitative Genetiker Alex Fraser eine Reihe von Arbeiten über die Simulation der künstlichen Selektion von Organismen mit mehreren Loci, die ein messbares Merkmal kontrollieren. Von diesen Anfängen an wurde die Computersimulation der Evolution durch Biologen in den frühen 1960er Jahren immer üblicher, und die Methoden wurden in Büchern von Fraser und Burnell (1970) und Crosby (1973) beschrieben. Frasers Simulationen beinhalteten alle wesentlichen Elemente der modernen genetischen Algorithmen. Darüber hinaus veröffentlichte Hans-Joachim Bremermann in den 1960er Jahren eine Reihe von Arbeiten, die ebenfalls eine Population von Lösungen für Optimierungsprobleme enthielten, die Rekombination, Mutation und Selektion durchliefen. Bremermanns Forschung umfasste auch die Elemente moderner genetischer Algorithmen. Zu den weiteren bemerkenswerten frühen Pionieren gehören Richard Friedberg, George Friedman und Michael Conrad. Viele frühe Arbeiten werden von Fogel (1998) nachgedruckt.

Obwohl Barricelli in seiner Arbeit, über die er 1963 berichtete, die Entwicklung der Fähigkeit, ein einfaches Spiel zu spielen, simuliert hatte, wurde die künstliche Evolution als Ergebnis der Arbeit von Ingo Rechenberg und Hans-Paul Schwefel in den 1960er und frühen 1970er Jahren zu einer weithin anerkannten Optimierungsmethode - Rechenbergs Gruppe war in der Lage, komplexe technische Probleme durch Evolutionsstrategien zu lösen. Ein weiterer Ansatz war die evolutionäre Programmiertechnik von Lawrence J. Fogel, die zur Erzeugung künstlicher Intelligenz vorgeschlagen wurde. Die evolutionäre Programmierung verwendete ursprünglich endliche Zustandsautomaten zur Vorhersage von Umgebungen und nutzte Variation und Selektion zur Optimierung der Vorhersagelogik. Genetische Algorithmen wurden insbesondere durch die Arbeit von John Holland in den frühen 1970er Jahren populär, insbesondere durch sein Buch Adaptation in Natural and Artificial Systems (1975). Seine Arbeit hat ihren Ursprung in Studien über zelluläre Automaten, die von Holland und seinen Studenten an der Universität von Michigan durchgeführt wurden. Holland führte einen formalisierten Rahmen für die Vorhersage der Qualität der nächsten Generation ein, das so genannte HollandscheSchematheorem. Die Forschung auf dem Gebiet der Genetischen Algorithmen blieb bis Mitte der 1980er Jahre weitgehend theoretisch, als die Erste Internationale Konferenz über Genetische Algorithmen in Pittsburgh, Pennsylvania, stattfand.