Evolutionärer Algorithmus

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Evolutionsstrategie)
Wechseln zu: Navigation, Suche
Die Antenne der Space Technology 5 Satelliten wurde mit einem EA entwickelt.[1]

Evolutionäre Algorithmen (EA) sind eine Klasse von stochastischen, metaheuristischen Optimierungsverfahren, deren Funktionsweise von der Evolution natürlicher Lebewesen inspiriert ist. In Anlehnung an die Natur werden Lösungskandidaten für ein bestimmtes Problem künstlich evolviert, EA sind also naturanaloge Optimierungsverfahren. Die Zuordnung zu den stochastischen und metaheuristischen Algorithmen bedeutet vor allem, dass EA meist nicht die beste Lösung für ein Problem finden, aber bei Erfolg eine hinreichend gute, was in der Praxis vor allem bei NP-vollständigen Problemen bereits wünschenswert ist. Die Verfahren verschiedener EA unterscheiden sich untereinander in erster Linie durch die genutzten Selektions-, Rekombinations- und Mutationsoperatoren, das Genotyp-Phänotyp-Mapping, sowie die Problemrepräsentation.

Die ersten praktischen Implementierungen evolutionärer Algorithmen wurden Ende der 1950er Jahre veröffentlicht[2], allerdings äußerten sich bereits in den vorigen Jahrzehnten Wissenschaftler zum Potenzial der Evolution für maschinelles Lernen[3]. Es gibt vier Hauptströmungen, deren Konzepte zumindest historisch voneinander zu unterscheiden sind: genetische Algorithmen, evolutionäre Algorithmen, genetische Programmierung und evolutionäre Programmierung. Heute verschwimmen diese Abgrenzungen zunehmend. Für eine bestimmte Anwendung wird ein EA geeignet entworfen, wobei in den letzten Jahrzehnten viele verschiedene Algorithmen und einzelne Operatoren entwickelt wurden, die heute benutzt werden können.

Die Anwendungen von EA gehen über Optimierung und Suche hinaus und finden sich auch in Kunst, Modellierung und Simulation, insbesondere auch bei der Untersuchung evolutionsbiologischer Fragestellungen.

Einführung[Bearbeiten]

Evolutionäre Algorithmen werden vorrangig zur Optimierung oder Suche eingesetzt. Konkrete Probleme, die mit EA gelöst werden, sind äußerst divers: z. B. Die Entwicklung von Sensornetzen, Aktienmarktanalyse oder RNA-Strukturvorhersage.[4] Auch bei Problemen, über deren Beschaffenheit nur wenig Wissen vorliegt, können sie zufrieden stellende Lösungen finden. Dies ist auf die Eigenschaften ihres natürlichen Vorbildes zurückzuführen.

Natürliches Vorbild Evolutionärer Algorithmus Beispiel
Organismus Lösungskandidat Autotür
Fortpflanzungserfolg Wert der Fitnessfunktion Strömungswiderstand
Natürliche Mutation Mutation Änderung der Form

In der biologischen Evolution sind die Gene von Organismen natürlich vorkommender Mutation ausgesetzt, wodurch genetische Variabilität entsteht. Diese Mutation können sich positiv, negativ oder gar nicht auf Erben auswirken. Da es zwischen erfolgreichen Individuen zur Fortpflanzung (Rekombination) kommt, können sich Arten über lange Zeiträume an einen vorliegenden Selektionsdruck anpassen (z. B. Klimaveränderungen oder die Erschließung einer ökologischen Nische). Diese vereinfachte Vorstellung wird in der Informatik idealisiert und künstlich im Computer nachgebildet. Dabei wird die Güte eines Lösungskandidaten explizit mit einer Fitnessfunktion berechnet, sodass verschiedene Kandidaten vergleichbar sind.

In der Praxis könnte z. B. die Form einer Autotür so optimiert werden, dass der aerodynamische Widerstand minimal wird. Die Eigenschaften einer potenziellen Lösung werden dabei im Rechner als Genom gespeichert. Häufige Problemrepräsentationen sind Genome aus binären oder reellen Zahlen oder eine Reihenfolge bekannter Elemente (bei kombinatorischen Problemen, z. B. Travelling Salesman).

Die starken Vereinfachungen, die im Vergleich zur Evolution getroffen werden, stellen ein Problem in Bezug auf die Erforschung evolutionsbiologischer Fragestellungen mit EA dar. Ergebnisse können nicht einfach auf die komplexere Natur übertragen werden.

Ablauf[Bearbeiten]

Das grobe Verfahren evolutionärer Algorithmen besteht meist aus einer Initialisierung und einer Schleife, die solange durchlaufen wird, bis ein Abbruchkriterium erfüllt ist:[5]

  1. Initialisierung: Die erste Generation von Lösungskandidaten wird (meist zufällig) erzeugt.
  2. Evaluation: Jedem Lösungskandidaten der Generation wird entsprechend seiner Güte ein Wert der Fitnessfunktion zugewiesen.
  3. Durchlaufe die folgenden Schritte, bis ein Abbruchkriterium erfüllt ist:
    1. Selektion: Auswahl von Individuen für die Rekombination
    2. Rekombination: Kombination der ausgewählten Individuen
    3. Mutation: Zufällige Veränderung der Nachfahren
    4. Evaluation: s. o.
    5. Selektion: Bestimmung einer neuen Generation

Die verschiedenen EA weichen in der Auswahl der Operatoren (Rekombination, Selektion, …) voneinander ab. Sie unterscheiden sich außerdem in verschiedenen Problemrepräsentationen, der entsprechenden Fitnessfunktion oder zusätzlichen Schritten. Rekombination muss dabei nicht zwangsläufig stattfinden, da die Individuen sich auch asexuell fortpflanzen können. EA werden oft mit künstlichen neuronalen Netzen oder lokaler Suche kombiniert. Je nach vorliegender Anwendung ergeben sich Vor- und Nachteile in Bezug auf spezielle Operatoren oder Konzepte.

Bestandteile[Bearbeiten]

Evolutionäre Algorithmen unterscheiden sich untereinander vor allem in der jeweiligen genetischen Repräsentation, der Fitnessfunktion und den genutzten genetischen Operatoren: Mutation, Rekombination und Selektion.

Die Rastrigin-Funktion ist eine multimodale Funktion, da sie viele lokale Extrema aufweist. Dies stellt einen Nachteil für den Rekombinationsoperator dar.

Mutation und Rekombination sind die Suchoperatoren evolutionärer Algorithmen, mit denen der Suchraum erkundet wird. Ihre Anwendung auf Lösungskandidaten kann keine Verbesserung garantieren[6], allerdings erhält der Suchprozess durch die Selektion eine Richtung, die bei erfolgreicher Konzeption zum globalen Optimum führt. Während mit dem Mutationsoperator völlig neue Bereiche des Suchraums erschlossen werden können, ermöglicht die Rekombination vor allem die Zusammenführung erfolgreicher Schemata (Building-Block-Hypothese). Eine erfolgreiche Suche basiert also auf der Kombination beider Eigenschaften. Der Erfolg eines Rekombinationsoperators hängt von der Beschaffenheit der Fitnesslandschaft ab. Je mehr lokale Optima die Fitnesslandschaft aufweist, desto wahrscheinlicher erzeugt die Rekombination aus zwei Individuen, die sich auf einem lokalen Optimum befinden, einen Nachfahren im Tal dazwischen. Mutation ist von dieser Eigenschaft der Fitnesslandschaft nahezu unabhängig[7].

Der Entwurf der verschiedenen Komponenten bestimmt, wie sich der evolutionäre Algorithmus bei der Optimierung des gegebenen Problems in Bezug auf Konvergenzverhalten, benötigte Rechenzeit und die Erschließung des Problemraums [8] verhält. Insbesondere müssen die genetischen Operatoren sorgfältig auf die zugrunde liegende Repräsentation abgestimmt sein, sodass sowohl die bekannten, guten Regionen des Problemraums genutzt, als auch die unbekannten Regionen erkundet werden können[9]. Dabei spielen die Beziehungen zwischen Such- und Problemraum eine Rolle. Im einfachsten Fall entspricht der Suchraum dem Problemraum (direkte Problemrepräsentation).

Theoretische Grundlagen[Bearbeiten]

No-free-Lunch-Theorem[Bearbeiten]

Hauptartikel: No-free-Lunch-Theoreme

Das No-free-Lunch-Theorem der Optimierung besagt, dass alle Optimierungsstrategien gleich effektiv sind, wenn die Menge aller Optimierungsprobleme betrachtet wird. Unter der gleichen Voraussetzung ist auch kein evolutionärer Algorithmus grundsätzlich besser als ein anderer. Dies kann nur dann der Fall sein, wenn die Menge aller Probleme eingeschränkt wird. Genau das wird in der Praxis auch zwangsläufig getan. Ein EA muss also Problemwissen ausnutzen (z. B. durch die Wahl einer bestimmten Mutationsstärke). Werden also zwei EA verglichen, dann wird diese Einschränkung impliziert.

Schemasatz[Bearbeiten]

Hauptartikel: Schemasatz

Der Schemasatz von John H. Holland wird allgemein als Erklärung des Erfolgs von genetischen Algorithmen gesehen. Er besagt vereinfacht, dass sich kurze Bitmuster mit überdurchschnittlicher Fitness schnell in einer Generation ausbreiten, die durch einen genetischen Algorithmus evolviert wird. So können Aussagen über den langfristigen Erfolg eines genetischen Algorithmus getroffen werden.

Virtuelle Alphabete[Bearbeiten]

Mit der Theorie der virtuellen Alphabete zeigte David E. Goldberg 1990, dass durch eine Repräsentation mit reellen Zahlen ein EA, der klassische Rekombinationsoperatoren (z. B. uniformes oder n-Punkt Crossover) nutzt, bestimmte Bereiche des Suchraums nicht erreichen kann[10], im Gegensatz zu einer Repräsentation mit binären Zahlen. Daraus ergibt sich, dass EA mit reeller Repräsentation arithmetische Operatoren zur Rekombination nutzen müssen (z. B. arithmetisches Mittel). Mit geeigneten Operatoren sind reellwertige Repräsentation entgegen der früheren Meinung effektiver als binäre[10].

Anwendungsgebiete[Bearbeiten]

Die Bereiche, in denen evolutionäre Algorithmen praktisch eingesetzt werden, sind nahezu unbegrenzt[4] und reichen von der Industrie, über Forschung bis zur Kunst (evolutionäre Kunst).

Wirtschaft[Bearbeiten]

EA werden zur Verifikation und Optimierung von Prototypen eingesetzt. Zum Beispiel werden die Geschwindigkeit von Mikroprozessoren, der Stromverbrauch von Mobiltelefonen oder die Wiederverwendbarkeit von Produkten (Recycling) optimiert[11]. Auch bei dem Entwurf von Telekommunikationsnetzen, Infrastruktur allgemein oder Sensornetzen. In der Finanzwelt werden mit EA Aktienmärkte analysiert, spieltheoretische Analysen oder agentenbasierte Simulationen entworfen[12] und Portfolios für maximalen Gewinn und minimales Risiko optimiert.[13] Sogar zur Optimierung von landwirtschaftlichen Betrieben werden sie genutzt, um langjährige Auswirkungen zu testen, Managementstrategien zu entwickeln oder praktisch nicht ausführbare Experimente zu simulieren[14].

Forschung[Bearbeiten]

Vor allem in der Molekularbiologie, wo enorme Datenmengen (Big Data) anfallen und Zusammenhänge nicht ohne Computerunterstützung erkannt werden können, werden mit evolutionären Algorithmen Sequenzanalyse, Sequenzalignment, die Erstellung phylogenetischer Bäume, Proteinstrukturvorhersage, Suche nach codierenden Bereichen oder die Visualisierung umfangreicher Daten[15] betrieben.

EA werden benutzt, um künstliche neuronale Netze aufzubauen, ein populärer Algorithmus ist NEAT. Robert Axelrods Versuch, mittels genetischer Algorithmen geeignete Strategien für das iterierte Gefangenendilemma zu finden, gab den Anstoß zur Entwicklung des Konzepts der evolutionären Spieltheorie.[16] Aufgrund ihrer Populationsbasiertheit können Evolutionäre Algorithmen auch in der agentenbasierten Modellierung sozialer oder ökonomischer Systeme eingesetzt werden.

Kunst und Musik[Bearbeiten]

Hauptartikel: Evolutionäre Kunst

Mit der Hilfe evolutionärer Algorithmen können komplexe Strukturen oder Tonfolgen entworfen werden, die auf Menschen ästhetisch wirken. Dies geschieht teils automatisiert und oft mit menschlicher Interaktion, wobei Menschen dem EA die Entscheidung abnehmen, was sie als schön empfinden.

Geschichte[Bearbeiten]

George Friedman entwarf 1956 für seine Masterarbeit an der University of California, Los Angeles eine Maschine, die mit dem Prinzip der natürlichen Selektion Schaltkreise entwickeln sollte, allerdings wurde diese Maschine nie gebaut[2]. Auch künstliches Leben wurde früh mit EA erforscht. Der Italiener Barricelli entwickelte 1954 ein Konzept, bei dem durch Zahlen repräsentierte Wesen auf einem zweidimensionalen Gitter "leben" und durch Mutation und Reproduktion zu neuen Generation geformt werden. Er zeigte, dass sich selbstreplikative Strukturen bilden, also Strukturen, die sich selbst in die nächste Generation kopieren. Bezüglich maschinellen Lernens schrieb der britische Informatiker Alan Turing schon 1950:

„Man muss mit dem Unterrichten einer Maschine herumexperimentieren und schauen, wie gut sie lernt. [...] Es gibt einen offensichtlichen Zusammenhang zwischen diesem Prozess und Evolution [...] Man darf allerdings hoffen, dass dieser Prozess schneller abläuft.“

Alan Turing: Computing Machinery and Intelligence[17]

Anfang der 1950er schlug der britische Statistiker George Box vor, die Produktion in Chemiefabriken zu optimieren, indem mit massivem Trial and Error Parameter wie Temperatur oder chemische Zusammensetzungen variiert und die potenziellen Verbesserungen per Hand ausgewertet werden, um danach mit den gefundenen Verbesserungen wieder zu variieren. Obwohl die Entscheidungsträger zuerst nicht davon begeistert waren, an einer laufenden Produktion zu experimentieren, wurde das Konzept, das Box Evolutionary Operation taufte, bis Anfang der 1960er in mehreren Chemiefabriken zur Steigerung der Produktivität genutzt [3]. Viele praktische Probleme ging man in der Folge mit evolutionären Algorithmen an, es bildeten sich vor allem die Evolutionsstrategie in Europa (Ingo Rechenberg[18] und Hans-Paul Schwefel) und der genetische Algorithmus (John H. Holland[19]) in den USA heraus, wobei Letzterer der bis heute populärste Ansatz ist und der Begriff genetischer Algorithmus oft pauschalisierend für alle EA genutzt wird. Dies hat aber keine praktische Bedeutung für die Auswahl eines konkreten Konzeptes[2]. Spätestens mit der rasant steigenden Verfügbarkeit von Rechenkraft fanden sich evolutionäre Algorithmen in allen erdenklichen Bereichen wieder, wo sie zur Optimierung und Suche eingesetzt wurden. Insbesondere auch in der Kunst und Musik, sowie in der Erforschung von künstlichem Leben (Avida).

Heute sind nicht nur die ursprünglichen Konzepte stark miteinander verwachsen, sondern auch viele andere Ansätze und Mischkonzepte entstanden. EA stellen wichtige Werkzeuge für Industrie und Forschung dar.

Typen Evolutionärer Algorithmen[Bearbeiten]

Durch die Problemstellung des Optimierungsproblems sind eine Zielfunktion sowie ein Problemraum, der potenzielle Lösungen enthält, gegeben. Der Unterschied zwischen dem Problemraum der Anwendung und dem Suchraum des Algorithmus besteht darin, dass ein EA eine Lösung anders darstellen kann, um sie besser zu verarbeiten und später wieder in ursprünglicher Form auszugeben (Genotyp-Phänotyp-Mapping, künstliche Embryogenese). Dies bietet sich vor allem dann an, wenn die Darstellung einer möglichen Lösung deutlich vereinfacht werden kann und nicht in ihrer Komplexität im Speicher verarbeitet werden muss. Verschiedene Evolutionäre Algorithmen unterscheiden sich vornehmlich in den folgenden Eigenschaften (vergleiche auch das einleitende Ablaufschema):

  • Suchraum (z. B. Binärzahlen, reelle Zahlen, Baumstrukturen)
  • Suchoperatoren (z. B. Mutation und Rekombination)
  • Fitnesszuweisung und Selektion auf Basis der Zielfunktion
  • Art und Weise, in der vorherige Generationen in die Selektion mit einbezogen werden (Elterngeneration ein-/ausschließen)
  • Beziehung zwischen dem Suchraum und dem Problemraum (Genotyp-Phänotyp-Mapping)

Klassische Varianten[Bearbeiten]

Die vier historisch zuerst entstandenen Verfahren sind heute in der Form nicht mehr zu unterscheiden, insbesondere werden oft die Namen einzelner Typen als Synonym für das gesamte Gebiet der evolutionären Algorithmen genutzt. Dazu kommt, dass es heute eine Fülle weiterer Verfahren und unüberschaubar viele Kombinationen gibt, für die keine einheitliche Benennung existiert. In der folgenden Darstellung werden die klassischen Konzepte in der historischen Form beschrieben.

Genetische Algorithmen (GA)[Bearbeiten]

Ausprägung des Genotyps in einer Zelle

Genetische Algorithmen wurden vor allem durch die Arbeiten John H. Hollands berühmt. Sie nutzen binäre Problemrepräsentation und benötigen deshalb meist ein Genotyp-Phänotyp-Mapping. Das bedeutet, dass binär repräsentierte Lösungskandidaten zuerst umgewandelt werden müssen, um mit der Fitnessfunktion evaluiert werden zu können. Wegen dieser Eigenschaft sind sie dem biologischen Vorbild von allen evolutionären Algorithmen am nächsten. Das Erbgut natürlicher Organismen ist ähnlich zu binären Zahlen in vier Nukleinsäuren codiert. Auf dieser Basis geschehen natürliche Mutation und Rekombination. Das Erscheinungsbild (Phänotyp) ist aber nicht das Erbgut selbst, sondern entsteht aus diesem durch einen vielschrittigen Prozess. Das Prinzip Genotyp-Phänotyp-Mapping verläuft in vereinfachter Form analog. Die binäre Repräsentation eignet sich zur schnellen Verarbeitung in Computern. Im Laufe der Forschung im Gebiet der EA hat sich dies aber nicht als klarer Vorteil gegenüber anderen Verfahren erwiesen.[20]

Die Auswahl der sich fortpflanzenden Individuen erfolgt bei GA mit fitnessproportionaler Selektion, die Fortpflanzung selbst durch n-Punkt-Crossover. Auch die Rekombination von mehr als zwei Elterngenomen ist möglich und führt in manchen Fällen zu besseren Ergebnissen. [21] Die Mutation bei GA kann man sich anschaulich gut vorstellen, da die Genome aus einzelnen Bits bestehen, die invertiert, dupliziert oder gelöscht werden können (auch ganze Sequenzen). Eine theoretische Untersuchung des Konvergenzverhaltens Genetischer Algorithmen liefert der Schemasatz von John H. Holland.

Evolutionsstrategien (ES)[Bearbeiten]

Evolutionsstrategien nutzen direkte Problemrepräsentationen (z. B. reelle Zahlen). Problem- und Suchraum sind also identisch. Das hat bei komplexen Problemen zur Folge, dass die Evolutionsstrategie nicht den gesamten Problemraum erkunden kann, wenn klassische Crossoveroperatoren benutzt werden (virtuelle Alphabete). ES nutzen vorrangig Mutation als Suchoperator und in manchen Fällen gar keine Rekombination. Die Mutation stellt eine Addition eines normalverteilten Wertes dar, wobei die Varianz (Mutationsstärke) nicht konstant ist. Da der Algorithmus mit zunehmender Lösungsqualität konvergiert (Schemasatz) ist es vorteilhaft, die Varianz anzupassen. So kann gewährleistet werden, dass die ES in immer feineren Schritten ihr Ziel sucht. Für die Anpassung haben sich zwei Methoden etabliert.

  • Adaptive Anpassung (1/5-Erfolgsregel [22]): Die 1/5-Erfolgsregel besagt, dass der Quotient aus den erfolgreichen Mutationen (also Mutationen, die eine Verbesserung der Anpassung bewirken) zu allen Mutationen etwa ein Fünftel betragen sollte. Ist der Quotient größer, so sollte die Varianz der Mutationen erhöht werden, bei einem kleineren Quotienten sollte sie verringert werden.
  • Selbstadaptivität: Jedes Individuum hat ein zusätzliches Gen für die Mutationsstärke selbst. Dies ist zwar nicht in der Biologie möglich, aber die Evolution im Rechner findet eine geeignete Varianz auf diese Weise ohne Einschränkung des Menschen.

Genetische Programmierung (GP)[Bearbeiten]

Darstellung einer Funktion als Baumstruktur. Teilbäume können umgehängt, geändert oder gelöscht (Mutation) und komplette Bäume kombiniert (Rekombination) werden.

Das Ziel der genetischen Programmierung ist die Erzeugung von Strukturen, die eine bestimmte Eingabe in eine festgelegte Ausgabe umwandeln sollen (Computerprogramme, Schaltkreise oder mathematische Funktionen). Die Lösungskandidaten werden durch Bäume repräsentiert.

Beim Problem der symbolischen Regression wird eine bestimmte Funktion X \to Y gesucht (z. B. ein Polynom wie 4x^4-3x^2+17). Gegeben sind Paare mit je einem Wert aus X und dem zugehörigen Wert aus Y. Es ist also bekannt, wie die gesuchte Funktion Werte abbildet. Mit GP werden Baumstrukturen evolviert, die die symbolische Funktion meist exakt nachbilden[23].

Eine grundlegende Arbeit zur Genetischen Programmierung verfasste John Koza. Er erkannte auch die Möglichkeit, symbolische Regression mit GP zu lösen. In der Erforschung von GP wurde dieses Problem oft als Benchmarktest genutzt.

Evolutionäre Programmierung (EP)[Bearbeiten]

Ähnlich zur GP werden Strukturen wie Computerprogramme gesucht, die aber nicht durch Bäume, sondern durch endliche Automaten repräsentiert werden. Nur die numerischen Eigenschaften der Automaten werden variiert, ihre Struktur ist fest. Gesucht wird ausschließlich über Mutation, Rekombination findet nicht statt. Einzelne Individuen werden sozusagen als verschiedene Spezies betrachtet. Evolutionäre Programmierung wurde nach ihrer Entstehung wenig weiterentwickelt.

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

Evolutionäre Algorithmen allgemein[Bearbeiten]

Genetische Algorithmen[Bearbeiten]

Evolutionsstrategien[Bearbeiten]

  • Ingo Rechenberg: Cybernetic Solution Path of an Experimental Problem (1965)., In: D.B. Fogel (Hrsg.): Evolutionary Computation - The Fossil Record. IEEE Press 1998, ISBN 0-7803-3481-7.
  • Ingo Rechenberg: Evolutionsstrategie. Optimierung technischer Systeme nach Prinzipien der biologischen Evolution., Frommann Holzboog 1973, ISBN 3-7728-0373-3 (Diss. von 1970).
  • Ingo Rechenberg, Evolutionsstrategie '94.Frommann Holzboog 1994, ISBN 3-7728-1642-8.
  • Hans-Paul Schwefel: Evolution and Optimum Seeking. Wiley & Sons, New York 1995, ISBN 0-471-57148-2.
  • Hans-Georg Beyer: The Theory of Evolution Strategies. Springer, Berlin Heidelberg New York 1998, ISBN 3-540-67297-4.
  • Hannes Geyer et al., Vergleich zwischen klassischen und verschachtelten Evolutionsstrategien am Beispiel einer nichtlinearen Regression an Oberflächenspannungen in R²., Interner Bericht CI-66/99 des Sonderforschungsbereichs 531: 'Design und Management komplexer technischer Prozesse und Systeme mit Methoden der Computational Intelligence', Dortmund 1999, Download PDF

Genetische Programmierung[Bearbeiten]

Evolutionäre Programmierung[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. J.D. Lohn, D.S. Linden, G.S. Hornby, W.F. Kraus: Evolutionary design of an X-band antenna for NASA's Space Technology 5 mission. In: Antennas and Propagation Society International Symposium. Vol.3, 2004 IEEE, S. 2313 - 2316, 20-25 June 2004
  2. a b c Peter Bentley,David Corne: Creative Evolutionary Systems: Seite 10.
  3. a b David B. Fogel: Evolutionary Computation: Toward a New Philosophy of Machine Intelligence: Seite 59.
  4. a b Cecilia Di Chio et al., Applications of Evolutionary Computation: EvoApplications 2012.
  5. Karsten Weicker, Evolutionäre Algorithmen: Seite 25.
  6. Mitsuo Gen, Runwei Cheng:Genetic Algorithms and Engineering Optimization, Seite 8.
  7. William M. Spears:The Role of Mutation and Recombination in Evolutionary Algorithms, Seite 225f.
  8. Bill Worzel:Genetic Programming Theory and Practice VI, Seite 62.
  9. Oscar Cordón:Genetic Fuzzy Systems: Evolutionary Tuning and Learning of Fuzzy Knowledge Bases, Seite 95
  10. a b J. Stender, E. Hillebrand, J. Kingdon, Genetic Algorithms in Optimisation, Simulation and Modelling: Seite 70.
  11. Ernesto Sanchez, Giovanni Squillero, Alberto Tonda: Industrial Applications of Evolutionary Algorithms
  12. Shu-Heng Chen, Evolutionary Computation in Economics and Finance: Seite 6.
  13. Wayne Wobcke, Mengjie Zhang: Application of a Memetic Algorithm to the Portfolio Optimization Problem. In: AI 2008: Advances in Artificial Intelligence . Springer-Verlag, S. 512.
  14. David G. Mayer, Evolutionary Algorithms and Agricultural Systems: Seite 2.
  15. Gary Fogel, David Corne: Evolutionary Computation in Bioinformatics
  16. Die Evolution der Kooperation. Oldenbourg, München 1987; 7. A. ebd. 2009, ISBN 978-3-486-59172-9
  17. A. M. Turing: Computing machinery and intelligence. In: Mind, 59, Seiten 433-460. 1950. link
  18. Ingo Rechenberg: Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis) (German). Frommann-Holzboog, 1973.
  19. John H. Holland: Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975, ISBN 0-262-58111-6.
  20. Lukáš Sekanina, Evolvable Components: From Theory to Hardware Implementations: Seite 27.
  21. Ting, Chuan-Kang (2005). "On the Mean Convergence Time of Multi-parent Genetic Algorithms Without Selection". Advances in Artificial Life: 403–412. ISBN 978-3-540-28848-0.
  22. Ingo Rechenberg, Evolutionsstrategie. Optimierung technischer Systeme nach Prinzipien der biologischen Evolution , Frommann Holzboog, 1973, ISBN 3-7728-0373-3 (Diss. von 1970), Kapitel 15
  23. Julian F. Miller, Cartesian Genetic Programming: Seite 63.

Weblinks[Bearbeiten]

Evolutionäre Algorithmen allgemein[Bearbeiten]

Genetische Algorithmen[Bearbeiten]

  • Einführung genetischer Algorithmen mit Anwendungsbeispiel, Steffen Harbich, 2007
  • Wikiversity-Kurs Genetische Algorithmen.
  • JGAP Freies Java Framework zur Implementierung genetischer Algorithmen, unterstützt auch die Genetische Programmierung; sehr viele Unit Tests zur Qualitätssicherung, umfangreiche Javadoc-Dokumentation
  • EvoJ Kleines aber effektives und verbreitbares Java Framework für genetischer Algorithmen.
  • HeuristicLab: Freies .NET Environment für heuristische Optimierung (genetische Algorithmen, Evolutionsstrategien, Nachbarschaftssuche, etc.)
  • Boxcar2D, ein genetischer Algorithmus, der ein 2-dimensionales Fahrzeug konstruiert, um ein Gelände zu überwinden

Hybrid-Algorithmen[Bearbeiten]

  • Geneva ("Grid-enabled evolutionary algorithms"), eine freie Bibliothek (Affero GPLv3) zur Optimierung mit Evolutionsstrategien, Genetischen- und Schwarmalgorithmen sowie Simulated Annealing und Parameter Scans. Unterstützt Problembeschreibungen mit gemischten Parametersätzen sowie die Optimierung in Clustern sowie Grid und Cloud