Evolutionäre Algorithmen sind ein Teilgebiet des Soft Computing und beruhen als naturanaloge Heuristiken auf einer groben Abstraktion von Mechanismen der natürlichen Evolution. Bevorzugtes Anwendungsgebiet sind Optimierungsfragestellungen, die einer konventionell-analytischen Modellierung nicht zugänglich sind.
Begriff und Ursprung
Evolutionäre Algorithmen (EA) sind breit anwendbare stochastische Metaheuristiken. Sie imitierten Vorgänge der biologischen Evolution auf abstrakter Ebene [Nissen 1997] [Gerdes et al. 2004]. Synonym verwendet man den Begriff Evolutionary Computation [Bäck 2002] [Fogel 2006] [Eiben und Smith 2007].
Kernmechanismen der Evolution sind die Replikation und Variation (durch Mutation und Rekombination) von Erbinformationen sowie eine Selektion zugunsten der besten Merkmalsträger. In Evolutionären Algorithmen entsprechen Lösungsalternativen des gegebenen Anwendungsproblems den Individuen einer sich fortentwickelnden Population. Im Laufe des künstlichen Evolutionsprozesses entstehen so immer bessere Lösungen.
Vorläufer und Hauptformen
Die EVOP-Methode von Box [1957] und die Arbeit Bremermanns [1962] stellen wichtige Vorläufer dar. Die heutigen Hauptströmungen entstanden ab den Sechziger Jahren. Man unterscheidet:
-
Genetische Algorithmen [Michalewicz 1999] [Bäck 2002],
-
Genetische Programmierung [Koza 2005],
-
Evolutionsstrategien [Beyer und Schwefel 2002],
-
Evolutionäre Programmierung [Fogel 2006].
Dabei stehen sich auf der einen Seite Genetische Algorithmen und Genetische Programmierung konzeptionell nahe. Auf der anderen Seite weisen Evolutionsstrategien und Evolutionäre Programmierung, obwohl unabhängig entstanden, Ähnlichkeiten auf.
Eigenschaften
Die Operatoren von Evolutionären Algorithmen arbeiten auf einer Repräsentation des Anwendungsproblems, die häufig binär oder reellwertig ist, aber auch andere Formen annehmen kann. Der Abstimmung von Lösungsrepräsentation, Variationsoperatoren und Selektionsmechanismus kommt große Bedeutung zu. Hier liegen auch die Unterschiede der EA-Hauptströmungen. Die Feineinstellung der Verfahrensparameter ist ebenfalls bedeutsam. Sie kann manuell oder selbstadaptiv erfolgen.
Für eine zielgerichtete Suche sind nur Angaben zur Güte (Fitness) der Lösungen nötig. Diese Fitnesswerte werden i.d.R. aus Zielfunktionswerten berechnet, können aber auch anders ermittelt werden. Es gibt keine restriktiven Anforderungen an die Zielfunktion.
Gegenüber anderen modernen Heuristiken grenzen sich Evolutionäre Algorithmen vor allem durch ihren populationsbasierten Ansatz ab. So wird parallel und interagierend in verschiedenen Bereichen des Lösungsraumes gesucht. Lokale Suboptima können überwunden werden.
Stochastische Verfahrenselemente werden bewußt eingesetzt. Die Variationsoperatoren generieren laufend neue Lösungsstrukturen (exploration). Lösungen werden dank der Selektion auf erfolgversprechende Regionen des Suchraumes fokussiert (exploitation). Die richtige Balance von exploration und exploitation ist erfolgskritisch.
Es gibt zahlreiche Ansatzpunkte, um EA an die gegebene Aufgabenstellung anzupassen und so ihre Leistungsfähigkeit zu erhöhen, z.B. über die Lösungsrepräsentation und komplementäre Suchoperatoren, intelligente Decodierungs- und Reparaturmechanismen, die Gestaltung der Fitnessfunktion, eine gezielte Initialisierung oder die Kombination mit anderen Lösungsverfahren.
Als populationsbasierte Verfahren sind EA rechenintensiv. Aufwendig ist auch die methodisch notwendige Erzeugung vieler Zufallszahlen. EA können, wie alle heuristischen Verfahren, nicht garantieren, dass eine global optimale Lösung gefunden wird.
Aktuelle Entwicklungen
An Bedeutung gewinnen gegenwärtig estimation of distribution algorithms [Lozano et al. 2006]. Sie verbinden Elemente Evolutionärer Algorithmen mit Methoden des maschinellen Lernens und probabilistischer Modellierung.
Daneben haben sich Konzepte entwickelt, die zwar nicht evolutionär sind, aber dennoch als verwandt angesehen werden. Hierzu gehören z.B. Ameisenalgorithmen [Dorigo und Stützle 2004] und die Partikelschwarmoptimierung [Kennedy et al. 2001].
Literatur
Bäck, T. (Hrsg.): Handbook of Evolutionary Computation. Institute of Physics Publishing: Bristol, 2002.
Beyer H.-G., Schwefel, H.-P.: Evolution Strategies: A Comprehensive Introduction. In: Natural Computing 1 (2002), S. 3–52.
Box, G.E.P.: Evolutionary Operation: A Method for Increasing Industrial Productivity. In: Applied Statistics. 6/2 (1957), S. 81-101.
Bremermann, H.J.: Optimization through Evolution and Recombination. In: Yovits, M.C.; Jacobi, G.T.; Goldstein, G. D. (Hrsg.): Self-Organizing Systems. Spartan Books: Washington, 1962, S. 93–106.
Dorigo, M.; Stützle, T.: Ant Colony Optimization. MIT Press: Cambridge, 2004.
Eiben, A.; Smith, J.E.: Introduction to Evolutionary Computing. 2. korr. Druck, Springer: Berlin, 2007.
Fogel, D.B.: Evolutionary Computation. Toward a New Philosophy of Machine Intelligence. 3. Aufl., Wiley & Sons: Hoboken, 2006.
Gerdes, I.; Klawonn, F.; Kruse, R.: Evolutionäre Algorithmen. Vieweg: Wiesbaden, 2004.
Kennedy, J.; Eberhart, R.C.; Shi, Y.: Swarm Intelligence. Morgan Kaufmann: San Francisco, 2001.
Koza, J.R.: Genetic Programming IV. Routine Human-Competitive Machine Intelligence. Kluwer: Boston, 2005.
Lozano, J.A.; Larrañaga, P.; Inza, I.; Bengotxea, E.: Towards a New Evolutionary Computation: Advances in the Estimation of Distribution Algorithms. Springer: Berlin, 2006.
Michalewicz, Z.: Genetic Algorithms + Data Structures = Evolution Programs. 3. Aufl. (korr. Druck), Springer: Berlin 1999.
Nissen, V.: Einführung in Evolutionäre Algorithmen. Vieweg: Wiesbaden, 1997
