Zum Inhalt springen

Evolutionärer Algorithmus

aus Wikipedia, der freien Enzyklopädie
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 14. April 2012 um 09:51 Uhr durch Darian (Diskussion | Beiträge) (Zusammenführung aus Artikel Evolutionsstrategie; Versionsgeschichte im Artikeltext). Sie kann sich erheblich von der aktuellen Version unterscheiden.

Evolutionsstrategien (ES) sind heuristische Optimierungsverfahren und gehören zu den Evolutionären Algorithmen. Sie werden vor allem für Probleme eingesetzt, für die keine geschlossene Lösung vorliegt und stehen in Konkurrenz zu klassischen Suchstrategien.

Viele biologische, technische und menschliche Prozesse laufen nach einem der biologischen Evolution ähnlichen Prinzip ab.

Dieses Prinzip der Evolution besteht aus den Prozessen

  • Generierung neuer Elemente durch Rekombination und durch Variation vorhandener Elemente oder durch Neuentnahme aus einer Art Bibliothek bzw. Gedächtnis
  • Zusammenbringen dieser Elemente mit einem weiteren Prozess, der letztlich zu einer Auswahl von Elementen führt, indem einzelne relativ gefördert und andere relativ geschwächt werden. Es wird also innerhalb der Menge der Elemente als Ganzes eine Differenz, ein Kontrast, eine Auswahl, eine Form erzeugt.
  • (In einem fortlaufenden evolutionären Kreislauf werden die in der Auswahlphase verstärkten Elemente auch verstärkt zu denen, die als Grundlage für die Generierung neuer Elemente in A genommen werden. Es entsteht eine sich selbstverstärkende bzw. sich stabilisierende Form)

Je nachdem, wie weit man diese Definition fasst, umschließt sie die biologische Evolution, die technische Evolution, Kreative Meinungsbildungsprozesse, soziales Lernen, Gedankensysteme, Rückkopplungs- und zirkuläre Editiersysteme, genetische Algorithmen.

Definition

Die Evolutionsstrategien umfassen eine Rubrik der Optimierungsalgorithmen, in denen die biologische Evolution, soweit für die Lösung des Problems vorteilhaft, nachgebildet wird. Das Ziel ist nicht eine möglichst genaue, sondern eine dem Problem angemessene Nachbildung.

Eine typische Evolutionsstrategie umfasst folgende Schritte

  1. Initialisierung: Nach einem zufälligen Verfahren wird eine bestimmte Anzahl von Individuen generiert.
  2. Selektion : Die Selektion bezeichnet die Methode, nach der ein Elter ausgewählt wird. Bei den Evolutionsstrategien werden die Eltern nach dem Zufallsprinzip ausgewählt - unter denen, die nach der Bewertung (s.u.) die aktuelle Generation bilden.
  3. Rekombination (Vererbung): Die Rekombination ist die Art, nach der aus einem oder mehreren Eltern ein oder mehrere Nachkommen generiert werden. Es gibt verschiedene Arten der Rekombination. Bei der einfachsten Methode wird ein selektierter Elter ohne Rekombination übernommen.
  4. Mutation: Die Mutation bezeichnet eine meist geringfügige Veränderung des Nachkommens. Bei den Evolutionsstrategien wird meist eine kleine Zahl auf den ausgewählten Teil (eine Eigenschaft des Individuums) addiert oder subtrahiert. Wie stark der mutierte Wert von dem Ursprungswert abweichen kann, wird durch die Streuung bestimmt (auf den alten Wert wird eine normalverteilte Zahl mit dem Mittelwert 0 und einer Standardabweichung addiert: ).
  5. Bewertung: Mit Hilfe einer Bewertungsfunktion wird die Qualität der Individuen bewertet. Auf dieser Grundlage wird entschieden, welche Individuen die nächste Generation bilden.
  6. Generieren: Eine bestimmte Anzahl der besten Individuen bilden die neue Generation von Individuen. Der nächste Durchlauf wird mit der Selektion begonnen.

Arten

Im folgenden werden die Grundarten der Evolutionsstrategie näher erläutert. Diese Arten können beliebig verschachtelt werden um auf ein Problem zugeschnitten zu werden. Die jeweiligen Algorithmen laufen so lange, bis ein Abbruchkriterium erfüllt ist. Dieses Abbruchkriterium ist meist entweder eine bestimmte Anzahl von maximalen Generationen, das Erreichen des Ergebnisses oder eine Kombination von beidem.

Hier umfasst jede Population nur ein Individuum. Aus dem Elter wird ein neues Individuum generiert. Die Rekombination entfällt bei dieser Methode. Der Nachkomme wird durch Mutation verändert. Mit Hilfe der Bewertungsfunktion wird die Anpassung berechnet. Dann wird der passendere der beiden Individuen in die nächste Generation übernommen.

Hier umfasst jede Generation μ Individuen. Per Zufall wird ein Elternteil ausgewählt und mit ihm ein Nachkomme gebildet. Nach Bewertung werden die besten Individuen in die folgende Generation übernommen.

Hier umfasst jede Generation μ Individuen. Aus den Eltern werden Kinder generiert. Die Anpassung von allen Kindern und Eltern wird berechnet und die passendsten (aus Eltern und Kindern) bilden die nächste Generation. Der Quotient wird als Selektionsdruck bezeichnet.

,

Hier umfasst jede Generation Individuen. Aus den Eltern werden Kinder generiert, mit . Die Eltern werden gelöscht und spielen für die Bildung der nächsten Generation keine Rolle mehr. Die Anpassung von allen Kindern wird berechnet und die passendsten Individuen bilden die nächste Generation. Bei dieser Methode kann kein Individuum länger als eine Generation überleben, und die Anpassungskurve ist im Gegensatz zur + nicht monoton steigend.

, , ,    + + ,    + , ,    , +

Hier gibt es Populationen mit je Individuen. Die Elternpopulationen erzeugen Kinderpopulationen mit je Individuen und die Kinderpopulationen werden für Generationen isoliert. In jeder der Generationen generiert jede isolierte Population Nachkommen. Die Anpassung wird berechnet, und die angepasstesten der Nachkommen werden in die nächste Generation übernommen. Nach den isolierten Generationen werden der besten Populationen ausgewählt und erzeugen als nächste Elternpopulationen wieder Kinderpopulationen. Wie durch + bzw. , lassen sich auch mit verschachtelten Evolutionsstrategien multimodale Optimierungsprobleme lösen. Die Anwendung verschachtelter ES kann in sehr komplexen multimodalen Optimierungsproblemen (z.B. nichtlinearen Regressionen) erfolgreicher sein als die Anwendung gewöhnlicher Evolutionsstrategien.

Das Verhalten kann mit Gipfelspringen und Gipfelklettern erläutert werden: http://www.bionik.tu-berlin.de/institut/s2mulmo.html Im Gütegebirge erzeugt ein Start-Punkt z.B. drei Nachkommen die zufällig verteilt werden. Diese erklimmen dann in der Isolationsphase den jeweils nächsten Gipfel. Nach der Isolationphase werden dann die besten als neue Startpunkte neue Nachkommen erzeugen.

Besonderheiten

Das besondere an den Evolutionsstrategien im Gegensatz zu anderen Evolutionären Algorithmen ist, dass sich der Algorithmus dynamisch anpassen kann. Die Schrittweite, also die Stärke, wie eine Mutation einen Wert verändert, kann dynamisch angepasst werden. Dies wird als Schrittweitenregelung bezeichnet.

1/5-Erfolgsregel

Die von I. Rechenberg [1] theoretisch abgeleitete 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 Streuung der Mutationen erhöht werden; ist der Quotient kleiner, so sollte die Streuung verringert werden.

Probleme

Der Hauptoperator der Evolutionsstrategie ist die Mutation. Hat man eine gute Mutationsstrategie und eine gute Schrittweitenanpassung, so ist der Erfolg am wahrscheinlichsten. Das Problem ist, diese guten Werte zu finden. Rechenberg hat diese zentrale Schwierigkeit mit dem Begriff Evolutionsfenster benannt. Das Evolutionsfenster bezeichnet den schmalen Grat der für die Evolution sinnvollen Schrittweiten zwischen den zu großen Schritten (große Änderungen mit der Möglichkeit von Rückschritten) und zu kleinen Schritten (kleine Änderungen mit der Möglichkeit des Stillstandes) der Mutation. Es existiert noch kein Rezept, wie man garantiert das Evolutionsfenster treffen kann.

Varianten

Geschichte

Das Verfahren der Evolutionsstrategie wurde 1964 von Ingo Rechenberg entwickelt und 1965 publiziert (Royal Aircraft Establishment, Library Translation 1122, Farnborough). Später wurde es von vielen anderen, in besonderem Maße von Hans-Paul Schwefel, weiterentwickelt.

Literatur

  • Ingo Rechenberg, Cybernetic Solution Path of an Experimental Problem (1965), In: Evolutionary Computation - The Fossil Record, Edited by D. B. Fogel, 1998, IEEE Press, 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: New York: Wiley & Sons 1995, ISBN 0-471-57148-2
  • Hans-Georg Beyer: The Theory of Evolution Strategies: Berlin Heidelberg New York: Springer 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, https://eldorado.tu-dortmund.de/bitstream/2003/5371/1/ci66.pdf Download PDF]

Fußnoten

  1. ↑ Ingo Rechenberg, Evolutionsstrategie. Optimierung technischer Systeme nach Prinzipien der biologischen Evolution , Frommann Holzboog, 1973, ISBN 3-7728-0373-3 (Diss. von 1970), Kapitel 15


Versionsgeschichte:


Evolutionäre Algorithmen (EA) sind eine Klasse von stochastischen Optimierungs- und Suchverfahren, die sich an die Grundprinzipien der biologischen Evolution anlehnen. Zu Beginn eines solchen Algorithmus wird eine zufällige Population möglicher Lösungen des Optimierungsproblems erzeugt. Diese werden dann anhand einer sogenannten Fitnessfunktion bewertet, die das zu lösende Optimierungsproblem beschreibt. Diejenigen Lösungen, die die besten Fitness-Werte aufweisen, werden zufällig verändert, während die restlichen verworfen werden. Die neu gewonnenen Lösungen werden dann wiederum bewertet und der Kreislauf setzt sich fort, bis ein Abbruchkriterium erreicht wird. Evolutionäre Algorithmen erfordern im Vergleich zu anderen Optimierungsverfahren nur ein geringes Problemwissen und werden daher für die Lösung vielfältiger Probleme eingesetzt, für die keine spezialisierteren Algorithmen existieren. Es existieren eine Reihe von Varianten dieser Algorithmen mit den Namen Genetische Algorithmen, Evolutionsstrategien, Genetische Programmierung und Evolutionäre Programmierung, die sich historisch unterschiedlich entwickelt haben. In jüngerer Zeit werden all diese Ansätze unter dem Begriff der Evolutionären Algorithmen zusammengefasst und nähren sich zunehmend aneinander an. Daneben hat sich auch der weiter gefasste Begriff Evolutionary Computing etabliert, unter den neben den Evolutionären Algorithmen auch Verfahren fallen, die auf Schwarmintelligenz und Selbstorganisation beruhen.

Verfahren und Bezug zur biologischen Evolution

Während der Evolution wurden durch Veränderungen des Erbgutes hochkomplexe Lebensformen und Organismen an ihre Umwelt- und Lebensbedingungen angepasst. Es wird damit ein sehr schwieriges Optimierungsproblem mit veränderlichen Zielvorgaben gelöst. Das Erstaunliche daran ist die relative Einfachheit der Steuerungsmechanismen. In einem einfachen Modell lässt sich der Prozess auf lediglich drei biologische Prinzipien zurückführen, die iterativ immer wieder durchlaufen werden: Mutation, Rekombination und Selektion.

  • Die Mutation des Erbgutes ist ein ungerichteter Zufallsprozess, der Alternativen und Varianten des Vorhandenen erzeugt. Genetisch entspricht dies neuem Erbgut, das in die Population eingeführt wird und deren Diversität steigert.
  • Die Rekombination der Erbinformation erweitert die Vielfalt, da zuvor gekoppelte Eigenschaften zweier erfolgreicher Individuen nach dem Zufallsprinzip neu kombiniert werden.
  • Die Selektion bewertet die Ergebnisse des Zufallsexperimentes, und zwar ausschließlich anhand der aktuellen Umweltbedingungen. An dieser Stelle wird die Richtung der evolutiven Veränderungen gesteuert, indem sich optimierte Phänotypen stärker vermehren. Genetisch entspricht dies der Entfernung von weniger geeignetem Erbgut, das aus der Population entfernt wird und dessen Diversität vermindert.

Evolutionäre Algorithmen versuchen, diese Prinzipien nachzuahmen, um auf ähnlich effiziente Weise komplexe Optimierungsprobleme zu lösen. Bei klassischen Optimierungsverfahren wie z.B. dem A*-Algorithmus, der Tabu-Suche oder dem Gradientenverfahren wird meist eine einzelne Lösung von einer Anfangsbedingung aus nach deterministischen Regeln verändert, bis ein Optimum der Zielfunktion erreicht ist. Evolutionäre Algorithmen dagegen erzeugen zu Beginn eine ganze Population von "Individuen", die nach stochastischen Regeln verändert und aufgrund ihrer Fitness beurteilt und selektiert werden. Die Individuen können dabei beliebige Objekte darstellen, wie etwa Vektoren von Zahlen in Binär- oder reellwertiger Darstellung, Baumstrukturen, Programme, Konstruktionspläne etc. Diese werden analog zur Biologie durch Suchoperatoren wie Mutation oder Rekombination zufällig verändert. Ein evolutionärer Algorithmus kann auch ohne Rekombination auskommen (d.h. es gibt eine asexuelle Fortpflanzung der einzelnen Individuen mit nur einem Elternteil pro Kind), in bestimmten Fällen ist die Anwendung von Rekombination jedoch effizienter. Der zufälligen Mutation kommt die Aufgabe zu, lokale Optima zu überwinden. Die Bewertung der Fitness der Individuen leitet sich schließlich aus der Zielfunktion des Optimierungsproblems ab. Sie gibt vor, in welche Richtung die zufällige Suche steuert. Die Berechnung der Fitnessfunktion bildet meist den rechenintensivsten Teil des Algorithmus, da je nach Zielfunktion aufwändige Simulationen zum Einsatz kommen können. Je strenger das Bewertungsverfahren und die damit verbundene Selektion arbeiten, desto höher ist der Selektionsdruck. Je höher der Selektionsdruck, desto schneller konvergiert die Population gegen ein Optimum, desto höher ist jedoch auch die Gefahr, dass dies nur ein lokales Optimum ist.

Grundsätzlich laufen Evolutionäre Algorithmen in den folgenden Schritten ab:

  1. Initialisierung: Erzeugen einer ausreichend großen Menge unterschiedlicher Individuen. Diese bilden die erste Generation.
  2. Durchlaufe die folgenden Schritte, bis ein Abbruchkriterium erfüllt ist
    1. Evaluation: Für jedes Individuum der aktuellen Generation wird anhand einer Fitnessfunktion ein Wert bestimmt, der seine Güte angibt.
    2. Selektion: Zufällige Auswahl von Individuen aus der aktuellen Generation. Dabei werden Individuen mit besseren Zielfunktionswerten mit einer höheren Wahrscheinlichkeit ausgewählt.
    3. Reproduktion: Die Daten (Genome) der ausgewählten Individuen werden gemischt (Rekombination) und zufällig verändert (Mutation) und daraus neue Individuen erzeugt. Diese bilden die nächste Generation.

Die Generation, die beim Eintreten des Abbruchkriteriums existiert (bzw. ihr bester Vertreter), wird dann als Lösung des Optimierungsproblems ausgegeben.

Obwohl Evolutionäre Algorithmen Prinzipien der Evolution ausnutzen, gibt es durchaus Kontroversen darüber, inwieweit man sie als Modell für die biologische Evolution ansehen kann. Streng genommen löst die biologische Evolution kein Optimierungsproblem, sondern ein Anpassungsproblem, insbesondere gibt es also kein Abbruchkriterium und ständig wechselnde Umweltbedingungen. Auch der Bezug zur natürlichen Selektion wurde infrage gestellt [1].

Eigenschaften

Zusammenfassend kann man die Vor- und Nachteile der Evolutionären Algorithmen (EA) wie folgt beschreiben:

Vorteile

Nachteile

  • EA bieten im Allgemeinen keine Garantie, das globale Optimum in vernünftiger Zeit zu finden.
  • EA haben oft sehr große Rechenzeitbedarf.

Trotz aller Vorteile sind Evolutionäre Algorithmen eher die schlechtere Wahl für Probleme, für die es spezielle Optimierungsverfahren gibt, da diese in der Regel effizienter arbeiten. So sind z.B. Newton-Raphson-Methoden, die Gradienten bei der Optimierung verwenden, bei der Suche lokaler Minima um ein Vielfaches schneller als Evolutionäre Algorithmen. Die fehlende Anwendung von Problemwissen wird also durch eine potentiell sehr lange Laufzeit erkauft. Diese Erkenntnis wurde 1997 von Wolpert und Macready in Form der "No-free-Lunch-Theoreme"[2] formalisiert und wahrscheinlichkeittheoretisch bewiesen.

Anwendungsgebiete

Grundsätzlich können Evolutionäre Algorithmen in allen Bereichen eingesetzt werden, in denen numerische Lösungen von Optimierungsproblemen gesucht werden. Beispiele für solche Gebiete sind die Ingenieurwissenschaften, die Naturwissenschaften, die Finanzwirtschaft und das Operations Research, das sich mit der Lösung quantitativer betrieblicher Fragestellungen beschäftigt. Beispiele für solche Anwendungen sind:

  • Konstruktion von komplexen Bauteilen oder ganzen Systemen, z.B. im Brückenbau. Evolutionäre Algorithmen dienen hier der Optimierung von Lage, Form und Gewicht der einzelnen Brückenbestandteile. Ähnliche Anwendung auch in der Konstruktion von Gussteilen.
  • Methode zur Optimierung von Kulturmedien für Zellkultivierung.
  • Technische Analyse im Finanzwesen.
  • Erstellen von Fahr-, Stunden- und Raumplänen.

In der angewandten Forschung werden genetische Algorithmen auch zur Kalibirerung von Modellen eingesetzt. Ein Beispiel hierfür ist der Einsatz als Lernparadigma zum Einstellen des Schwellenpotentialvektors oder zum Finden einer geeigneten Netztopologie neuronaler Netze.

Neben praktischen Anwendungen werden Evolutionäre Algorithmen aber auch in der theoretischen Forschung eingesetzt. So hat Robert Axelrodss Versuch, mittels genetischer Algorithmen geeignete Strategien für das iterierte Gefangenendilemma zu finden, den Anstoß zur Entwicklung des Konzepts der evolutionären Spieltheorie gegeben.[3] Aufgrund ihrer Populationsbasiertheit können Evolutionäre Algorithmen auch in der agentenbasierten Modellierung sozialer oder ökonomischer Systeme eingesetzt werden.

Geschichte

Bereits Ende der 1950er Jahre begannen verschiedene Forschergruppen die Prinzipien der Evolution nachzuahmen, um effiziente Optimierungsalgorithmen zu entwickeln[4] [5]. Box und Draper entwickelten in dieser Zeit den Ansatz der Evolutionary Operation (EVOP)[6], der jedoch noch nicht in ein Computerprogramm umgesetzt wurde. In den 1960er und 70er Jahren entstanden drei unterschiedliche Schulen: In den USA entwickelte Lawrence J. Fogel das Evolutionäre Programmieren (EP) und John H. Holland[7] die Genetischen Algorithmen (GA), während Ingo Rechenberg[8] und Hans-Paul Schwefel in Deutschland das Verfahren der Evolutionsstrategie (ES) entwickelten. Diese Schulen entwickelten sich über etwa 15 Jahre hinweg weitgehend unabhängig voneinander. In den 1990er Jahren einigten sich Vertreter der verschiedenen Gebiete auf den gemeinsamen Begriff Evolutionäre Algorithmen (bzw. den weiter gefassten Begriff evolutionary computation)[9]. Seitdem ist eine verstärkte Zusammenarbeit und ein Zusammenwachsen der verschiedenen Schulen zu beobachten. Ebenfalls in den 1990er Jahren etablierte sich ein viertes Gebiet, das Genetische Programmieren, zu dem John Koza[10] wesentliche Beiträge lieferte.

Evolutionäre Algorithmen wurden nicht nur in Hinblick auf praktische Optimierungsprobleme entwickelt, sondern auch als theoretisches Modell der Evolution. Frühe Arbeiten in dieser Richtung wurden von Nils Aall Barricelli[11][12] und Alex Fraser[13] geleistet. Die Arbeiten von Reichenberg und Holland machten diesen Ansatz populär und mit dem Aufkommen leistungsfähigerer Computer wurden Evolutionäre Algorithmen zu einem wichtigen Werkzeug sowohl in der Forschung und in jüngerer Vergangenheit auch in der wirtschaftlichen und industriellen Anwendung.

Typen Evolutionärer Algorithmen

Durch die Problemstellung des Optimierungsproblems sind in der Regel eine oder mehrere Zielfunktionen sowie einen Problemraum, auf dem diese Funktionen definiert sind. Verschiedene Evolutionäre Algorithmen unterscheiden sich vornehmlich in den folgenden Eigenschaften

  • Suchraum (z.B. Binärvektoren, reale Zahlen, Baumstrukturen)
  • Suchoperatoren (z.B. Mutation und Rekombination)
  • Art und Weise, in der vorherige Generationen in die Selektion mit einbezogen werden (extinctive vs. preservative)
  • Fitnesszuweisung und Selektion auf Basis der Zielfunktionen
  • Beziehung zwischen dem Suchraum und dem Problemraum (sog. genotype-phenotype-mapping)

Eine gesonderte Wahl des Suchraums und seiner Beziehung zum Problemraum ist dann erforderlich, wenn die Elemente des Suchraums Grundlage für Elemente des Problemraums sind, die eine höhere Komplexität aufweisen Ein Beispiel dafür sind etwa Baumstrukturen, die nach festen Regeln aus binären Vektoren Genetischer Algorithmen erzeugt werden. Man spricht in solchen Fällen von einer künstlichen Embryogenese, in Anlehnung an das biologische Pendant. Ebenso ist die Fitnessfunktion oft mit der Zielfunktion des Optimierungsproblems identisch, eine gesonderte Wahl der Fitnesszuweisung ist vor allem dann notwendig, wenn mehrere Zielfunktionen vorliegen, die gewichtet werden müssen. Auch die Operation der Selektion kann in verschiedener Weise von den Werten der Fitnessfunktion abhängen, siehe Abschnitt Selektionstrategien. Schließlich ist noch die Frage zu beantworten, in welcher Weise Individuen vorheriger Generationen in die Selektion mit einbezogen werden, d.h. ob die Vertreter der Elterngeneration mit ihren Kindern in Konkurrenz treten (preservative evolutionary algorithm)[14] oder verworfen werden (extinctive evolutionary algorithm)[15], siehe Abschnitt Kombination verschiedener Generationen.

Klassische Varianten

Die unten beschriebenen klassischen Varianten Evolutionärer Algorithmen unterscheiden sich vornehmlich durch ihren Suchraum und die zugehörigen Suchoperatoren. Varianten der restlichen drei Eigenschaften können im Prinzip mit jedem dieser Algorithmen kombiniert werden.

Genetische Algorithmen

Genetische Algorithmen sind von der Terminologie und der Vorgehensweise her am nähesten am Vorbild der biologischen Evolution. Ihr Suchraum besteht aus Vektoren meist binärer, manchmal aber auch ganzer oder reeller Zahlen, die als Genom bezeichnet werden. Dies entspricht der Anordnung der Aminosäuren in der biologischen DNA. Wie im biologischen Vorbild existieren die Suchoperatoren Mutation und Rekombination. Bei der Mutation wird entweder ein zufälliges Element des Genoms geändert oder zwei Elemente werden vertauscht. Bei der Rekombination werden die Eltern-Genome einem Punkt geteilt und jeweils einer der Teile wird zu einem Nachkommen zusammen gefügt. Auch Teilungen an mehreren Punkten sind möglich. In manchen Varianten Genetischer Algorithmen werden auch mit Genomen variabler Länge gearbeitet, so dass auch Einfügungen und Löschungen von Elementen möglich sind. Bisweilen werden an verschiedenen Stellen des Genoms auch verschiedene Datentypen kombiniert. Auch die Rekombination von mehr als zwei Elterngenomen ist möglich und führt in manchen Fällen zu besseren Ergebnissen.[16]

Binäre Genome sind aufgrund der Binärdarstellung im Computer sehr effiziente Repräsentationen der zu lösenden Optimierungsprobleme, weswegen diese Art der Genetischen Algorithmen vergleichsweise schnell ablaufen. Für die Optimierung von Parameterwerten in anderen Darstellungen (reele oder ganze Zahlen) dagegen stellen die Evolutionsstrategien oft das effizientere Verfahren dar. Ist der Lösungsraum eines Problems nicht der der binären Zahlen, wird für die Berechnung der Fitnessfunktion ein genotype-phenotype-mapping benötigt, was den Rechenvorteil durch die Binärrepräsentation ggf. wieder zunichte machen kann.

Eine theoretische Untersuchung des Konvergenzverhaltens Genetischer Algorithmen liefert der Schemasatz von John H. Holland.

Evolutionsstrategien

Die Evolutionsstrategien zeichnen sich dadurch aus, dass sowohl der Suchraum als auch der Problemraum durch (meist reele) zahlen aufgespannt wird. Es ist also kein genotype-phenotype-mapping erforderlich. Zudem wird oft auf Rekombination verzichtet und nur die Mutation als Suchoperator verwendet. Die Zahlenwerte werden dabei meist aus einer Normalverteilung ) gezogen mit den alten Zahlenwert als Mittelwert und einer vorgegebenen Varianz . Diese Varianzwerte werden meist während der Laufzeit des Algorithmus angepasst. Rechenberg hat dazu die 1/5-Erfolgsregel abgeleitet[17], die 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. Auf diese Weise wird eine optimale Balance zwischen der Exploration des Suchraums und dem Zulaufen auf die Maximalwerte der Zielfunktion erreicht.

Genetische Programmierung

Darstellung einer Funktion als Baumstruktur.

Bei der Genetischen Programmierung besteht der Suchraum aus Baumstrukturen oder ganzen Computerprogrammen, die Zielfunktion wird durch eine vorgegebenes Input/Output-Verhalten definiert. Zum Beispiel kann man eine beliebige mathematische Funktion als Baumstruktur mit Zahlen, Variablen und Operationen als Knoten darstellen. Die Zielfunktion ergibt sich in diesem Fall aus Tripeln , die von der gesuchten Funktion reproduziert werden müssen. Dieses Problem bezeichnet man als symbolische Regression.

Ähnlich wie bei Genetischen Algorithmen kommen als Suchoperatoren beim Genetischen Programmieren zufälliges Umhängen, Einfügen oder Löschen von Knoten infrage (Mutation), als auch das Ersetzen eines Teilbaums eines Elternteils durch einen Teilbaum eines anderen (Rekombination).

Die zwar nicht erste, aber grundlegende Arbeit zur Genetischen Programmierung verfasste John Koza. Als Individuen verwendete er Programme in der syntaktisch einfachen Programmiersprache LISP, die in einer Baumstruktur vorliegen. Bei anderen Ansätzen wird auf linearen Programmen (z. B. direkt auf Assembler) oder Graphen operiert. Zuletzt wurden diese Möglichkeiten in der so genannten Linear-Graphen-GP auch kombiniert.

Evolutionäre Programmierung

Anders als bei den anderen Hauptströmungen der Evolutionären Algorithmen existiert für die Evolutionäre Programmierung keine exakt definierte Algorithmus-Variante.

Ein häufiges Merkmal der evolutionären Programmierung ist jedoch, dass es als Suchoperatoren nur Mutation und Selektion verwendet werden und auf die Rekombination verzichtet wird. Begründet wird dies meist mit der zugrundeliegenden Vorstellung, dass die Mitglieder einer Population als Stellvertreter verschiedener Spezies betrachtet werden, nicht als verschiedene Individuen einer einzigen Spezies. Damit gibt es keinen Rekombinationsoperator, da es unter verschiedenen Spezies auch keine Rekombination gibt.

Für die Art der Repräsentation und die Wahl des Mutationsoperators gibt es in der Evolutionären Programmierung keine Festlegung. Das macht es schwer, die Evolutionäre Programmierung insbesondere von den Evolutionsstrategien abzugrenzen, bei denen die Rekombination im Vergleich mit der Mutation ebenfalls eine eher untergeordnete Rolle spielt.

Die künstlichen neuronalen Netze des Dame-Programms Blondie24 wurden mit Hilfe von Evolutionärer Programmierung entwickelt.

Selektionstrategien

Fitness-proportionale Selektion

Bei diesem Verfahren wird jedem Kandidaten eine Wahrscheinlichkeit zugewiesen mit der es selektiert wird. Diese Wahrscheinlichkeit wird proportional zu dessen Fitness gewählt.

Rang Selektion

Wie bei der Fitness-proportionalen Selektion wird jedem Kandidat eine Selektionswahrscheinlichkeit zugewiesen. Diese hängt zwar ebenfalls von der Fitness des Kandidaten ab, allerdings ist nicht der konkrete Wert der Fitnessfunktion sondern der Rang innerhalb der Populution von Bedeutung. Von Vorteil ist dieses Vorgehen dann, wenn einige wenige Kandidaten deutlich stärker sind als der Rest. Bei der Fitness-proportionalen Selektion hätten die schwächeren Kandidaten nur mehr eine sehr geringe Chance ausgewählt zu werden.

Tournament Selektion

Es werden zufällig und gleichverteilt k Kandidaten aus der Population ausgewählt. Aus diesen wird derjenige mit der höchsten Fitness selektiert. Dieses Verfahren lässt sich auch für große Populationen effizient implementieren, da unabhängig von der Populationsgröße immer genau k Kandidaten untersucht werden.

Gewichtete Tournament Selektion

Diese läuft wie die Tournament Selektion ab, der beste Kandidat wird allerdings nicht immer, sondern mit einer hohen Wahrscheinlichkeit selektiert.

Kombination verschiedener Generationen

Verschiedene Evolutionäre Algorithmen unterscheiden sich in der Art und Weise, in der Individuen vorheriger Generationen in die Selektion eingebunden werden. Für die Evolutionsstrategien wurde eine Notation entwickelt[18][19], die auch auf den allgemeinen Fall angewendet werden kann. Danach umfasst eine Elterngeneration Individuen und die darauf folgende Kindergeneration Individuen. Damit sind eine Reihe verschiedener Kombinationen denkbar:

Jede Population umfasst nur ein Individuum. Aus dem Eltern wird ein einzelnes neues Individuum generiert, die Rekombination entfällt bei dieser Methode. Der Nachkomme wird durch Mutation verändert. Mit Hilfe der Bewertungsfunktion wird die Anpassung berechnet. Dann wird der passendere der beiden Individuen in die nächste Generation übernommen (preservative evolutionary algorithm).
Jede Generation umfasst Individuen. Per Zufall wird ein Elternteil ausgewählt und mit ihm ein Nachkomme gebildet. Nach Bewertung werden die besten Individuen in die folgende Generation übernommen (preservative evolutionary algorithm).
Jede Generation umfasst Individuen. Aus den Eltern werden Kinder generiert. Die Anpassung von allen Kindern und Eltern wird berechnet und die passendsten (aus Eltern und Kindern) bilden die nächste Generation. Der Quotient wird als Selektionsdruck bezeichnet (preservative evolutionary algorithm).
  • ,
Jede Generation umfasst Individuen. Aus den Eltern werden Kinder generiert, mit . Die Eltern werden gelöscht und spielen für die Bildung der nächsten Generation keine Rolle mehr. Die Anpassung von allen Kindern wird berechnet und die passendsten Individuen bilden die nächste Generation. Bei dieser Methode kann kein Individuum länger als eine Generation überleben, und die Anpassungskurve ist im Gegensatz zur + -Algorithmen nicht monoton steigend (extinctive evolutionary algorithm).
  • , , ,    + + ,    + , ,    , +
Es gibt Populationen mit je Individuen. Die Elternpopulationen erzeugen Kinderpopulationen mit je Individuen und die Kinderpopulationen werden für Generationen isoliert. In jeder der Generationen generiert jede isolierte Population Nachkommen. Die Anpassung wird berechnet, und die angepasstesten der Nachkommen werden in die nächste Generation übernommen. Nach den isolierten Generationen werden der besten Populationen ausgewählt und erzeugen als nächste Elternpopulationen wieder Kinderpopulationen.
Wie bei + bzw. , -Algorithmen lassen sich auch mit verschachtelten Evolutionsstrategien multimodale Optimierungsprobleme lösen. Die Anwendung verschachtelter ES kann in sehr komplexen multimodalen Optimierungsproblemen (z.B. nichtlinearen Regressionen) erfolgreicher sein als die Anwendung gewöhnlicher Evolutionsstrategien.
Dieses Verhalten kann als Kombination zwischen Gipfelspringen und Gipfelklettern beschrieben werden[20]. Im der Fitnesslandschaft erzeugt ein Start-Punkt z.B. drei Nachkommen, die zufällig verteilt werden. Diese erklimmen dann in der Isolationsphase den jeweils nächsten Gipfel. Nach der Isolationphase werden dann die besten als neue Startpunkte neue Nachkommen erzeugen. Algorithmen mit einem "Reservoir" isolierter Populationen werden auch als elitist evolutionary algorithm bezeichnet[21].

Beispiel für einen Genetischen Algorithmus

Zur Illustration betrachten wir die Festlegungen eines konkreten Genetischen Algorithmus:

  • Sei eine Fitness-Funktion, die wie folgt definiert ist:
  • Das Genom eines Individuums sei hier gegeben durch die Variablen der Fitness-Funktion, also die Liste
  • Ziel ist es, die Fitness-Funktion zu minimieren, also eine Eingabe zu finden, sodass die Funktion einen möglichst niedrigen Wert zurückliefert.
  • Die Rekombination besteht aus einem einfachen Crossover mit 2 Eltern-Genomen, wobei die Eltern aus der alten Population zufällig gewählt werden:
    • Eine Position wird zufällig ausgewählt.
    • Das Kind-Genom wird aus den beiden Eltern-Genomen zusammengesetzt, indem die vorderen Elemente des Genoms des einen Elternteils mit den hinteren Elementen des Genoms des anderen Elternteils kombiniert werden.
    • Sind beispielsweise die Eltern-Genome und sowie , dann ist das Kind-Genom .
  • Die Mutation ist für jede Position
im Genom eine einfache Addition an dieser Position um eine Zahl
. Diese Mutation kommt mit einer Wahrscheinlichkeit von 1% pro Generationswechsel und Position vor.
  • Die Selektion sei wie folgt gegeben: Von der gemeinsamen Population von Eltern und Kindern werden die entsprechend der Fitness-Funktion besten ausgewählt, und zwar so viele, wie es Individuen in der ursprünglichen Eltern-Population gab.
  • Die Startpopulation besteht aus 50 Individuen. Jedes Individuum bekommt für jedes seiner Gene eine zufällige Zahl aus zugeordnet.
  • Abbruchkriterium: Die Generationenfolge wird abgebrochen, wenn sich über die letzten 10 Generationen der Durchschnitt der Fitness aller Individuen der jeweiligen Population nicht geändert hat.
  • Ausgabe des genetischen Algorithmus ist das Genom eines besten Individuums in der letzten Population (die Population zu der Zeit, wann abgebrochen wurde).

Lässt man diesen genetischen Algorithmus laufen, so wird man nach etwa 70 Generationen ein Ergebnis haben, für das gilt: . Dieses Ergebnis ist in diesem konkreten Fall optimal. Man sieht, dass es viele gleichwertige Ergebnisse geben kann, so z. B. oder .

Siehe auch

Literatur

Evolutionäre Algorithmen allgemein

Genetische Algorithmen

Evolutionsstrategien

  • 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, https://eldorado.tu-dortmund.de/bitstream/2003/5371/1/ci66.pdf Download PDF]

Genetische Programmierung

Evolutionäre Programmierung

Einzelnachweise

  1. ↑ Norman R. Paterson. Genetic programming with context-sensitive grammars. PhD thesis, Saint Andrew’s University, September 2002. Online available at http://www.cs.bham.ac.uk/~wbl/biblio/gp-html/paterson_thesis.html
  2. ↑ Wolpert, D. H., & Macready, W. G. (1997). No free lunch theorems for optimization. IEEE Trans. on Evolutionary Computation, 1(1), 67-82.
  3. ↑ Die Evolution der Kooperation. Oldenbourg, München 1987; 7. A. ebd. 2009, ISBN 978-3-486-59172-9
  4. ↑ Kenneth Alan De Jong, David B. Fogel, and Hans-Paul Schwefel. A history of evolutionary computation. In Evolutionary Computation 1: Basic Algorithms and Operators, chapter 6, pages 40–. Institute of Physics Publishing (IOP), 2000. Online available at http://books.google.de/books?id=4HMYCq9US78C
  5. ↑ David B. (editor) Fogel: Evolutionary Computation: The Fossil Record. IEEE Press, New York 1998, ISBN 0-7803-3481-7.
  6. ↑ George E. P. Box and Norman R. Draper. Evolutionary operation. A statistical method for process improvement. Wiley Publication in Applied Statistics. John Wiley & Sons, 1969. ISBN: 0-4710-9305-X, 978-0-47109-305-3.
  7. ↑ John H. Holland: Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975, ISBN 0-262-58111-6.
  8. ↑ Ingo Rechenberg: Evolutionsstrategie – Optimierung technischer Systeme nach Prinzipien der biologischen Evolution (PhD thesis). Fromman-Holzboog, 1973.
  9. ↑ Schwefel, H.-P., & Männer, R. (Eds.). (1991). Parallel problem solving from nature: 1st Workshop, PPSN I. Berlin: Springer.
  10. ↑ John R. Koza: Genetic Programming. MIT Press, 1992, ISBN 0-262-11170-5.
  11. ↑ Nils Aall Barricelli: Esempi numerici di processi di evoluzione. In: Methodos. 1954, S. 45–68.
  12. ↑ Nils Aall Barricelli: Symbiogenetic evolution processes realized by artificial methods. In: Methodos. 1957, S. 143–182.
  13. ↑ Fraser AS: Monte Carlo analyses of genetic models. In: Nature. 181. Jahrgang, Nr. 4603, 1958, S. 208–9, doi:10.1038/181208a0, PMID 13504138.
  14. ↑ Thomas Bäck and Hans-Paul Schwefel. An overview of evolutionary algorithms for parameter optimization. Evolutionary Computation, 1(1):1–23, Spring 1993. ISSN:1063-6560.
  15. ↑ Nadia Nedjah, Enrique Alba, and Luiza De Macedo Mourelle, editors. Parallel Evolutionary Computations, volume 22/2006 of Studies in Computational Intelligence. Springer Berlin / Heidelberg, June 2006. ISBN: 978-3-54032-837-7. doi:10.1007/3-540-32839-4.
  16. ↑ 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.
  17. ↑ Ingo Rechenberg, Evolutionsstrategie. Optimierung technischer Systeme nach Prinzipien der biologischen Evolution , Frommann Holzboog, 1973, ISBN 3-7728-0373-3 (Diss. von 1970), Kapitel 15
  18. ↑ Frank Hoffmeister and Thomas Bäck. Genetic algorithms and evolution strategies – similarities and differences. In PPSN I: Proceedings of the 1st Workshop on Parallel Problem Solving from Nature, pages 455–469, 1990. Published 1991.
  19. ↑ Thomas Bäck and Hans-Paul Schwefel. An overview of evolutionary algorithms for parameter optimization. Evolutionary Computation, 1(1):1–23, Spring 1993. ISSN:1063-6560.
  20. ↑ http://www.bionik.tu-berlin.de/institut/s2mulmo.html
  21. ↑ Marco Laumanns, Eckart Zitzler, and Lothar Thiele. A unified model for multi-objective evolutionary algorithms with elitism. In Proceedings of the 2000 Congress on Evolutionary Computation CEC00, pages 46–53, 2000.

Evolutionäre Algorithmen allgemein

Genetische Algorithmen

Evolutionsstrategien

Genetische Programmierung

Abgerufen von „https://de.wikipedia.org/w/index.php?title=Evolutionärer_Algorithmus&oldid=102031000“