|
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.
|