Suche Home Einstellungen Anmelden Hilfe  

Evolutionäre Algorithmen

Ingo Wegener, Fachbereich Informatik, Universität Dortmund
 

1. Einleitung
Die Lösung von algorithmischen Problemen gehört zu den Kernproblemen der Informatik. Insbesondere Optimierungsprobleme haben Wissenschaftlerinnen und Wissenschaftler herausgefordert. Es gibt darunter Probleme, die mit speziellen Methoden sehr effizient gelöst werden können. Sehr viele Probleme haben sich jedoch als NP-äquivalent erwiesen, d.h. sie sind durch Algorithmen, die für alle Eingaben eine optimale Lösung effizient berechnen, nur dann zu lösen, wenn eine vielfach untermauerte Hypothese, die sogenannte NPP-Vermutung, falsch ist. Dennoch fallen diese komplexen Aufgaben tagtäglich in vielen Anwendungen an - und werden "erfolgreich bearbeitet". Dies liegt teilweise daran, dass nicht jede Eingabe für ein schwieriges Problem schwer zu bearbeiten ist. Das TSP (TSP=travelling salesman problem, dt. Problem des Handlungsreisenden) ist sicher einfach, wenn alle Städte auf einem Kreis liegen. Darüber hinaus ist man in Anwendungen oft mit fast optimalen Lösungen zufrieden (viele Eingabedaten sind selber ungenau) und man kann deterministische Algorithmen durch randomisierte Algorithmen ersetzen, die auch durch Zufallsbits gesteuert werden. Anstatt nach Algorithmen zu suchen, die immer schnell eine optimale Lösung finden, ist man mit Algorithmen zufrieden, die für viele Eingabedaten, insbesondere "typische" Eingabedaten, mit hoher Wahrscheinlichkeit in annehmbarer Zeit eine zufriedenstellende Lösung finden. Diese randomisierten Suchstrategien sind oft in Analogie zu in der Natur oder in der Technik beobachteten Prozessen gebildet worden. Dies hat zu griffigen und werbewirksamen Namen wie lokale Suche, Tabu Search, Simulated Annealing, Sintflut-Algorithmus, genetischer Algorithmus oder evolutionärer Algorithmus geführt. Wir wollen untersuchen, wann diese Suchstrategien erfolgreich eingesetzt werden können und welche Eigenschaften sie haben. Unser Schwerpunkt liegt in der Untersuchung von evolutionären Algorithmen. Zunächst werden wir randomisierte Suchstrategien vorstellen und anhand von Optimierungsszenarien diskutieren, wann man überhaupt hoffen kann, randomisierte Suchstrategien mit Erfolg einzusetzen. Danach beschreiben wir einige unserer Ergebnisse zur Analyse evolutionärer Algorithmen.
 

2. Randomisierte Suchstrategien
Suchstrategien beschreiben ein allgemeines Vorgehen, um in einem Suchraum S, auf dem eine Bewertungsfunktion f: S->R gegeben ist, nach einem Punkt mit maximaler Bewertung zu suchen. Der Einfachheit halber beschränken wir uns hier auf den diskreten Fall S={0,1}n und merken nur an, dass sich der Fall S=Rn ähnlich behandeln lässt. Eine Suchstrategie muss beschreiben, wie der Startpunkt x1 und wie auf der Basis von i bewerteten Punkten (x1,f(x1)),...,(xi,f(xi)) der (i+1)-te Suchpunkt xi+1 gewählt werden. Dabei verlangen wir nur, dass sich xi+1 effizient berechnen lässt. Nach t Schritten wissen wir, welcher der bisher untersuchten Punkte der beste ist, aber wir wissen nicht, ob wir schon einen optimalen Punkt gefunden haben. Wir können uns einen unendlichen Suchprozess vorstellen, bei dem uns die erwartete Zeit interessiert, bis wir zum ersten Mal einen optimalen Punkt gefunden haben. In der Praxis wird man den Suchprozess zu einem Zeitpunkt abbrechen und wir können zufrieden sein, wenn wir garantieren können, dass die Wahrscheinlichkeit, einen optimalen Punkt gefunden zu haben, sehr nahe bei 1 liegt.

Evolutionäre und genetische Algorithmen übertragen die aus der biologischen Evolution bekannten Prinzipien der Mutation, des Genaustausches (meistens als Crossover bezeichnet) und der Selektion auf Optimierungsprozesse. Gemäß des biologischen Vorbildes werden Punkte im Suchraum Individuen genannt. Die zu einem Zeitpunkt aktuellen Individuen bilden die Population, die sich von Generation zu Generation verändert. Die Bitfolge, die ein Individuum beschreibt, wird als Erbmasse aufgefasst. Eine Mutation bewirkt eine zufällige Veränderung der Erbmasse. Oft werden die einzelnen Bits unabhängig voneinander mit Wahrscheinlichkeit 1/n negiert. Mit hoher Wahrscheinlichkeit wird so ein recht ähnliches Individuum erzeugt, aber jedes denkbare Individuum hat eine positive Wahrscheinlichkeit erzeugt zu werden. Mutationen bewirken, dass die randomisierte Suche nicht in lokalen Optima stehenbleibt. An einem Crossover sind zwei Individuen beteiligt. Es sollen Individuen erzeugt werden, die gemeinsame Teile der Erbmasse von den Erzeugern übernehmen. Beim sogenannten gleichverteilten Crossover (uniform crossover) wird jedes Bit unabhängig von den anderen mit Wahrscheinlichkeit 1/2 vom ersten bzw. zweiten Erzeuger übernommen. Man kann sich vorstellen, dass die aktuelle Population eine bestimmte Anzahl von neuen Individuen erzeugt. Die neue Population wird bei sogenannten Plus-Strategien aus der alten Population und den neuen Individuen ausgewählt, während bei sogenannten Komma-Strategien nur die neuen Individuen zur Auswahl stehen. Die Auswahl erfolgt zufallsgesteuert aufgrund der Bewertungen f(x) der Suchpunkte x, in der Sprechweise hier der Fitnesswerte f(x) der Individuen x. Evolutionäre Algorithmen bilden eine große Klasse von randomisierten Suchstrategien mit vielen frei einstellbaren Parametern, es gibt also nicht den evolutionären Algorithmus. Auf Möglichkeiten, diese Parameter im Laufe der Zeit zu adaptieren, oder ihre Wahl selbst mit evolutionären Algorithmen vorzunehmen, sei ebenso nur hingewiesen wie auf die Möglichkeit, mit getrennten Populationen zu arbeiten, die in größeren Zeitabständen Information austauschen. Im Vergleich zu anderen randomisierten Suchstrategien wie lokaler Suche oder Simulated Annealing ist die einfachste Evolutionsstrategie, der (1+1)-EA interessant, die Populationsgröße ist 1 und es wird durch Mutation ein neues Individuum erzeugt, das das alte Individuum verdrängt, wenn es mindestens so fit ist.
 

3. Szenarien für die Anwendung von randomisierten Suchstrategien
Es gibt eine Vielzahl von randomisierten Suchstrategien, die mit mehr oder weniger Erfolg angewendet werden. Insbesondere von evolutionären Algorithmen wurde behauptet, dass sie "robust" sind. Dies soll bedeuten, dass sie für spezielle Probleme von speziellen Methoden geschlagen werden können, aber im Durchschnitt über "alle" Probleme "am besten" sind. Es ist leicht einzusehen und als "No Free Lunch Theorem" bekannt geworden, dass alle Suchstrategien, die Punkte nur einmal auswerten, im Durchschnitt über alle Funktionen f: A->B (A und B endlich) gleich gut sind. Wir argumentieren im folgenden, warum dieses NFL-Theorem für die Entwicklung von Optimierungsstrategien irrelevant ist.

Aus praktischer Sicht befindet man sich oft in einem One-Shot-Szenario, ein ganz konkretes Problem ist zu lösen, alle Parameter sind bekannt. Menschen, die einmal im Leben ein Haus bauen, stehen beim Kauf "des besten Grundstücks" vor so einem Problem. In diesem Szenario lässt sich keine Theorie betreiben. Mit Glück findet man das Traumgrundstück am ersten Tag, ohne überhaupt strategisch vorgegangen zu sein. Aus diesem Vorgehen kann niemand etwas lernen.

Typischerweise behandeln wir in der Informatik spezifische Probleme mit freien Parametern. So müssen Makler vorgehen, die viele Menschen beim Grundstückskauf beraten. In so einem Fall wird eine randomisierte Suchstrategie, die keine problemspezifischen Komponenten beinhaltet, kaum gegen spezialisierte Algorithmen konkurrieren können. Wer von evolutionären Algorithmen hört, mit denen das TSP "besonders gut" gelöst wird, kann sicher sein, dass Komponenten aus evolutionären Algorithmen mit problemspezifischen Ideen gemischt wurden.

Neben diesem Bereich gibt es sogenannte Black Box Szenarien. Dabei wird angenommen, dass die zu optimierende Funktion f nicht in einer Form vorliegt, in der man sie analysieren kann. Dies kann verschiedene Gründe haben. Das zu behandelnde System, die Weltwirtschaft oder der Aktienmarkt, kann so komplex sein, dass wir "den Wert" unserer Handlungen nicht berechnen, sondern nur beobachten können. Dies gilt ebenso für komplexe technische Systeme. Andererseits mag unser Ziel darin bestehen, eine "robuste" randomisierte Suchstrategie zu entwerfen, die sich auf "typischen Problemen" "gut verhält". Viele Firmen haben weder das Kapital noch die Zeit oder das Know-How, um für ein gegebenes Optimierungsproblem mit dem bekannten Methodenreservoir und problemspezifischen Kenntnissen einen maßgeschneiderten Algorithmus zu entwerfen. Sie benötigen robuste Algorithmen. Wie lassen sich nun derartige Algorithmen bewerten? Schlägt hier nicht das NFL-Theorem zu? Nein, die meisten Probleme, also z.B. die meisten Funktionen f: {0,1}100->{0,1}20, wobei die Parameter 100 und 20 eher klein sind, können in der Praxis gar nicht vorkommen. Die Anzahl derartiger Funktionen ist mit  so unermesslich, dass nur ein Anteil von weniger als  eine Beschreibung hat, die mit einem Gigabyte auskommt. Suchstrategien sind jedoch nur anwendbar, wenn es auf effiziente Weise möglich ist, für einen Suchpunkt x den Funktionswert f(x) zu berechnen. Dafür benötigt f eine kompakte Beschreibung, z.B. durch ein Programm, eine Hardwarekomponente oder eine andere "Apparatur". Das NFL-Theorem gilt zwar im NFL-Szenario, aber realistische Black Box Szenarien sehen anders aus.

Ziel der Forschung ist es also, verschiedene Suchstrategien für verschiedene Black Box Szenarien zu vergleichen. In dieser Allgemeinheit ist die Aufgabe mit den heutigen Methoden nicht bearbeitbar. Wir können aber das Verhalten der Suchstrategien auf ausgewählten Funktionenklassen behandeln. Eine robuste Suchstrategie sollte auf "einfachen" Problemen besonders effizient sein. Die besondere Schwierigkeit der Analyse von evolutionären Algorithmen liegt im Crossover Operator, der zu Abhängigkeiten zwischen den Individuen führt. Aus mathematischer Sicht sind dynamische quadratische Systeme zu analysieren. Selbst die Analyse von lokaler Suche, Simulated Annealing oder des (1+1)-EA mit jeweils nur einem aktuellen Suchpunkt ist weit komplizierter, als man dies vielleicht erwartet.
 

4. Einige Resultate
Zum Abschluss sollen einige Ergebnisse unserer Arbeitsgruppe (Stefan Droste, Thomas Jansen, Ingo Wegener) vorgestellt werden. Der einfache (1+1)-EA erweist sich in vielen Experimenten als erstaunlich erfolgreich. Wir haben den (1+1)-EA auf verschiedenen Funktionenklassen analysiert. Lineare Funktionen f: {0,1}n->R, also Funktionen der Form f(x1,...,xn)=w0+w1x1+...+wnxn, lassen sich per Hand trivial optimieren. Robuste Suchstrategien sollten auf dieser Funktionenklasse keine Schwierigkeiten haben. Tatsächlich genügen für jede lineare Funktion im Durchschnitt (über die Zufallsentscheidungen) O(n log(n)) Schritte, um das Optimum zu finden. Der Beweis dieses Ergebnisses ist leider schon entmutigend kompliziert. Allerdings ist das Ergebnis optimal, da, falls alle wi0 sind, die Rechenzeitschranke exakt ist. Darüber hinaus lässt sich dieses Rechenzeitverhalten nur garantieren, wenn die Mutationswahrscheinlichkeit für die einzelnen Bits c/n für eine Konstante c beträgt. Die in Experimenten herausgefundene Empfehlung für die Mutationswahrscheinlichkeit konnte für die Klasse der linearen Funktionen als optimal nachgewiesen werden. Wenn wir wüssten, dass die Funktion linear ist, könnten wir das Optimum deterministisch in n Schritten erreichen. Der (1+1)-EA ist geringfügig langsamer, aber er benutzt die Tatsache, dass die Funktion linear ist, nicht. Es wurde vermutet, dass Polynome vom kleinem Grad leicht zu optimieren sind. Aber schon die Optimierung von Polynomen vom Grad 2 ist NP-schwierig. Für ein konkretes Polynom vom Grad 3 benötigen alle bekannten randomisierten Suchstrategien nicht nur im Durchschnitt, sondern sogar mit hoher Wahrscheinlichkeit exponentielle Zeit. Eine andere Vermutung war, dass unimodale Funktionen (mit Ausnahme des global besten Punkts reicht es überall, nur ein bestimmtes Bit zu ändern, um schon einen besseren Punkt zu erhalten) mit dem (1+1)-EA leicht zu optimieren sind. Wir haben eine Beispielfunktion beschrieben, für die der (1+1)-EA mit hoher Wahrscheinlichkeit exponentielle Zeit braucht.

Die Erfolge des (1+1)-EA zeigen, dass man auf Crossover oft verzichten kann. Andererseits haben Experimente auch den Nutzen des Crossover Operators bestätigt. Dennoch war es lange ein offenes Problem, für eine konkrete Funktionenfolge nachzuweisen, dass ein evolutionärer Algorithmus mit Crossover polynomielle Rechenzeit benötigt, während alle evolutionären Algorithmen ohne Crossover mehr als polynomielle Rechenzeit brauchen. Dieses Problem konnten wir vor kurzem lösen. Wir halten dieses Ergebnis für einen Durchbruch, nicht weil wir nun über eine konkrete Funktion etwas wissen, sondern weil es nun Methoden gibt, den Effekt von Crossover in manchen Fällen zu analysieren.
 

5. Experimente oder theoretische Analyse?
Wenn die theoretische Analyse so schwierig und die Durchführung von Experimenten so einfach ist, wozu benötigen wir dann eigentlich die theoretische Analyse? Mit wiederholten Experimenten lässt sich das Verhalten von randomisierten Optimierungsstrategien auf ausgewählten Funktionen hinreichend genau untersuchen. Aber diese Ergebnisse haben auch nur Aussagekraft für die ausgewählten Funktionen. Verallgemeinernde Aussagen, sowohl auf längere Eingaben oder gar auf ganze Funktionenklassen, sind spekulativ. So haben unsere Resultate Vermutungen, die durch Verallgemeinerungen von Experimenten entstanden sind, in vielen Fällen falsifiziert. Darüber hinaus ergeben sich aus der theoretischen Analyse Erkenntnisse, die in die Weiterentwicklung der Algorithmen einfließen.

Adresse
Prof. Dr. Ingo Wegener
Universität Dortmund
Lehrstuhl Informatik II
44221 Dortmund
Email: wegener@ls2.cs.uni-dortmund.de
WWW: http://ls2-www.cs.uni-dortmund.de/~wegener

Lebenslauf
Prof. Dr. Ingo Wegener (geb. 4.12.1950) hat sein Diplom (1976), seine Promotion (1978) und seine Habilitation (1981) an der Fakultät für Mathematik der Univ. Bielefeld abgelegt. Von 1980-1987 war er erst Vertretungsprofessor und dann C3-Professor am Fachbereich Informatik der Johann-Wolfgang Goethe-Universität Frankfurt am Main. Seit 1987 ist er C4-Professor am Fachbereich Informatik der Universität Dortmund. Er hat weitere C4-Rufe an die Universitäten in Würzburg und Koblenz erhalten.

Seine Forschungsgebiete sind die Komplexitätstheorie und Effiziente Algorithmen, wobei in der Komplexitätstheorie die Komplexität Boolescher Funktionen für verschiedene Modelle von Schaltkreisen und Branchingprogrammen im Mittelpunkt steht. Dies führte in den letzten Jahren zu der Behandlung von BDD-basierten Datenstrukturen für Boolesche Funktionen, die in vielen Informatikgebieten, insbesondere in der Verifikation (Verhinderung des Pentium-Bugs) Anwendung finden. Bei der Analyse von Algorithmen hat sich die Klasse evolutionärer Algorithmen als Schwerpunkt herausgestellt. Ingo Wegener hat 6 Bücher verfasst, ein weiteres wird im Frühjahr 2000 erscheinen. Seine wissenschaftlichen Ergebnisse hat er in 8 Buchbeiträgen, 67 Zeitschriftenartikeln und 37 Konferenzartikeln veröffentlicht.

Ingo Wegener hat 1994 die Universitätsmedaille der Universität Dortmund für ausgezeichnete Lehre erhalten. Er war 10 Jahre in der Bundesjury Mathematik/Informatik für "Jugend forscht" und leitet seit nunmehr 4 Jahren den Bundeswettbewerb Informatik. Von 1993-2001 ist er als DFG-Fachgutachter für Theoretische Informatik gewählt, von 1997-2001 leitet er den DFG-Fachausschuss Informatik.

Benutzer: Gast • Besitzer: schwill • Zuletzt geändert am: