Ein einheitliches Modell für Populationsstrukturen in Evolutionären Algorithmen

Abstract

Es gibt heute keine Konferenz im Bereich Evolutionärer Algorithmen mehr, auf der nicht mindestens ein Beitrag die Parallelisierung dieser Verfahren zum Thema hat. Waren es in der 80er Jahren im wesentlichen neue oder für neugehaltene Konzepte von Parallelität sowie neue Naturanalogien Motivation der gewählten Kommunikationsschemata, so stehen nun eher Anwendungen im Vordergrund, die aus rein pragmatischen Gründen auf bewährte Parallelisierungsansätze zurückgreifen. Dabei zeichnet sich jedoch weder eine Kanonisierung der Terminologie noch der Theorie, soweit überhaupt vorhanden, ab. Dies führt dazu, daß ähnliche Ansätze unter völlig verschiedenen Namen mehrfach entdeckt werden, oder daß konzeptionell unterschiedliche Varianten mit nahezu gleichlautenden Bezeichnungen versehen werden. Die uneinheitliche Terminologie kann nur zum Teil dadurch erklärt werden, daß sich Fachbegriffe bei einem relativ neuen Forschungsgebiet erst einmal etablieren müssen. Einen wesentlichen Einfluß hat nämlich auch die Tatsache, daß das Gebiet als solches nur schwer abzugrenzen ist, und, schlimmer noch, daß noch nicht einmal Einigkeit über den Kern dessen besteht, was mit dem Begriff Evolutionäre Algorithmen bezeichnet wird. Historisch gesehen gibt es zwei Extreme. Auf der einen Seite stand die Idee, einfache Computermodelle zur Simulation der natürlichen Evolution zu entwickeln. Das vorrangige Ziel dabei war es, anhand einfacher Modelle mehr über das natürliche Vorbild zu lernen. Auf der anderen Seite gab es schon früh Ansätze, aus den Prinzipien der Evolution Strategien zur Optimierung technischer Systeme abzuleiten. Daher wurden häufig Begriffe aus der Populationbiologie und der Vererbungslehre sowie der Numerik, Kodierungstheorie und dem Bereich mathematischer Optimierung miteinander vermischt. Bei den parallelen Evolutionären Algorithmen setzt sich diese Entwicklung fort. Meist werden Begriffe aus der parallelen Datenverarbeitung und der Biologie im gleichen Kontext verwendet. Als besonders schwierig stellt sich daher die Bewertung einer vorgenommenen Parallelisierung dar. Ziel der vorliegenden Arbeit ist es, für die zwei wesentlichen Eigenschaften einer parallelen Variante eines Evolutionären Algorithmus', nämlich die lokaleSelektion und die räumliche Struktur der Population, ein formales Gerüst für eine einheitliche, abstrakte Darstellung bereitzustellen. Nach einer Einführung in die Basisvarianten Evolutionärer Algorithmen folgt eine Diskussion früher veröffentlichter Ansätze mit strukturierten Populationen. Im folgenden Kapitel wird dann eine auf Hypergraphen basierende vereinheitlichte Modellierung von Populationsstrukturen definiert. Die verbreiteten Populationsstrukturen Panmixie, Migrationsmodell und Nachbarschaftsmodell werden im vorgestellten Formalismus ausgedrückt. Anschließend wird eine Implementierung eines Evolutionären Algorithmus' für beliebige Populationsstrukturen im Rahmen des vorher definierten Modells vorgestellt. Das folgende Kapitel gibt einen Überblick über Varianten von Selektionsoperatoren für verschiedene Populationsstrukturen. Im sechstenKapitel wird eine verbreitete Technik zur Untersuchung von Selektionsoperatoren in Evolutionären Algorithmen, die Analyse des Takeover-Verhaltens, auf beliebige Populationsstrukturen übertragen. Es wird gezeigt, daß die Berechnung der exakten Takeover-Wahrscheinlichkeit mittels Markov-Ketten im allgemeinen an der Größe des Zustandsraums scheitert. Stattdessen wird mit dem probabilistischen Durchmesser von Populationsstrukturen zu einem gegebenen Selektionoperator eineVerallgemeinerung der Takeover-Zeit definiert. Nach einer Parameterstudie, die die Eignung von einigen Populationsstrukturen für bestimmte Anwendungsklassen untersucht, folgt die Darstellung einiger weiterer Konzepte, die sich bei der Anwendung von Populationsstrukturen als nützlich erwiesen haben. Danach wird ein spezielles Populationsmodell vorgestellt, das sich in konkreten Anwendungen bewährt hat.