Im Kapitel 2 geben wir einen Überblick über alle Evolutionären Algorithmen mit der oben beschriebenen Reproduktion und Selektion. Als Mutation haben wir einen Diffusionsprozeß angenommen. Im eigentlichen Sinne zählt die zuerst behandelte Boltzmann-Strategie nicht zu den Evolutionären Strategien, da es im engerem Sinne keine Reproduktion und Selektion gibt. Aufgrund der ähnlichen Struktur der dynamischen Gleichungen wird sie aber im erweiterten Sinne mit dazugezählt. Danach führen wir die Darwin-Strategie ein, welche ein klassisches Beispiel für eine evolutionäre Strategie ist. Eine Analyse dieser beiden Strategien hat ein gegenläufiges Verhalten beim Überwinden einer Barriere ergeben. Da dieser Fall eine Standardsituation auf Fitnesslandschaften ist, führen wir eine Mischung der Darwin- und Boltzmann-Strategie ein. Dabei entsteht die Gemischte Strategie, die sich schon in vielen Computerexperimenten bewährt hat. In den nächsten beiden Abschnitten behandeln wir die Frage nach einer Anpassung der Mutationsstärke (äquivalent mit der Schrittweite) und leiten erstmalig die Gleichung für die Veränderung der Schrittweite bei einer Darwin-Strategie her. Die Grundidee für diese adaptive Darwin-Strategiestammt von Schwefel, der sie in der Folgezeit ausgiebig untersucht hat. Ein ähnliches Problem tritt auch bei der Boltzmann-Strategie auf, die als freien Parameter für die Schrittweite eine reziproke Temperatur besitzt. Eine "Abkühlung" führt zu einem Hängenbleiben der Strategie in den lokalen Minima. Dabei setzen wir voraus, daß die Abkühlung so langsam vor sich geht, daß dabei das globale Minimum gefunden wird. Diese Strategie wird als "simulated annealing" bezeichnet. Wie wir uns denken, ist die Wahl der Abkühlung das eigentliche Problem. Rose fand einen evolutionären Ausweg aus diesem Dilemma, indem er jedem Individuum der Gemischten Strategie eine Temperatur gab, die auch der Selektion ausgesetzt wurde. Dadurch konnte die Strategie ihre Abkühlungskurve selbst finden. Im letzten Abschnitt dieses Kapitels gehen wir noch der Frage nach einer einheitlichen Darstellung der dynamischen Gleichung nach. Dabei ergibt sich eineverallgemeinerte Wärmeleitungsgleichung, die auf einem metrischen Raum definiert ist. Die Wahl der Metrik und Koeffizienten listen wir für alle Strategien auf. Die Bedeutung dieses Ergebnisses liegt in der späteren Klassi kation begründet. Den größten Teil der Arbeit bildet das Kapitel 3, welches sich mit dem Vergleich der Strategien beschäftigt. Dazu führen wir verschiedene Maße zur Messung von Geschwindigkeiten der Strategien ein. Diese Maße bestehen vorrangig aus Kombinationen der Erwartungswerte von Polynomen der Fitnessfunktion sowie deren zeitliche Ableitungen. Wir behandeln und berechnen diese Größen anhand von zwei Beispielen: der Parabel und des Doppeltopfes. Beide Fälle stellen zugleich dieeinfachsten Probleme für eine Optimierung dar. Für die Parabel ist es wichtig, daß wir die Geschwindigkeit der Strategie messen. Die einfachste Größe, die dies beschreibt, ist die zeitliche Änderung des Erwartungswerts der Fitness. Sie ist die Geschwindigkeit der Strategie auf der Fitnesslandschaft. Als weitere interessante Größe betrachten wir die Varianz der Verteilungsfunktion der Individuen auf der Fitnesslandschaft. Sie gibt Auskunft über die Variabilität der Individuen bezüglich der Fitness. Diese beiden Größen werden im Fall der Parabel für die Boltzmann- und Darwin-Strategie explizit berechnet. Dabei ergeben sich ähnliche Ergebnisse, die für diesen Fall nicht erstaunlich sind, da die Strategie immer dem Gradienten der Fitnessfunktion folgen. Das zweite Beispiel ist der Doppeltopf. Hierbei interessiert uns vor allem die Wahrscheinlichkeit, daß die Strategie von einem Topf in den anderen wechselt. Dazu starten wir im lokalen Minimum und versuchen in das globalen Minimum zu gelangen. Die Wahrscheinlichkeit dafür ist durch das Integral über die Wahrscheinlichkeitsverteilung 1 gegeben. Deren zeitliche Ableitung läßt sich als Strom von Suchern durch die Barriere interpretieren. Eine Untersuchung dieser Größen für die Boltzmann-und Darwin-Strategie erbringt das Ergebnis, daß die Boltzmann-Strategie auf achen Fitnessland-schaften schneller als die Darwin-Strategie ist. Andererseits ist die Darwin-Strategie auf stark zerklüfteten Landschaften schneller als die Boltzmann-Strategie. Das gegenläuge Verhalten beider Strategien beim Problem des Doppeltopfes legt die Idee der Mischung der Strategien nahe. Nun fragen wir uns natürlich, ob eine Mischung wirklich den gewünschten Erfolg zeigt. Im nächsten Abschnitt wird daher erneut der Doppeltopf behandelt. Dabei zeigen wir, daß die gemischte Strategie für fast alle Parametersätze das globale Minimum findet. Desweiteren werden Kriterien für die Wahl des Mischungsparameters angegeben. Im letzten Abschnitt dieses Kapitels beschreiben wir die Simulationsalgorithmen der Boltzmann- und Darwin-Strategie. Im Kapitel 4 beschäftigen wir uns mit den mathematischen Eigenschaften von Schrödinger-Operatoren. Dabei steht der Zugang über das Spektrum zusammen mit den Eigenschaften des sogenannten Wärmeleitungskerns am Anfang im Mittelpunkt des Interesses. Wir zeigen, daß die Geschwindigkeit der Strategie mit solchen Eigenschaften wie Spektraldichte im Zusammenhang steht. Andererseits ist das Spektrum auch in der Quantenmechanik anwendbar. Durch die Bestimmung der Änderung der Autokorrelationsfunktion in Bezug auf die Erwartungswerte der Fitness wird über eine Hierarchie das gesamte Spektrum aufgebaut. Eine Diskussion des Einflusses einer Deformation der Fitnessfunktion auf das Spektrum rundet diesen ersten Abschnitt ab. Gerade die Diskussion dieser Beziehung zu den Korrelationen sowie die Diskussion der Deformation der Fitnessfunktion sind neu. Der Hauptteil des Kapitels ist der Klassifikation von Schrödinger-Operatoren durch die Untersuchung der topologischen Eigenschaften des Lösungsraums gewidmet. Zuerst führen wir das Problem auf ein algebraisches Problem zurück, was gleichzeitig eine Vereinfachung der ursprünglichen Fragestellung bedeutet. Eine Charakterisierung der Äquivalenzklassen ist mit Hilfe der Singularitätstheorie möglich. Dabei treten als kleinste Einheiten der Fitnesslandschaft 6 Singularitäten auf, d.h. falls zwei Fitnesslandschaften die gleiche Zerlegung der Landschaft bezüglich der Singularitäten besitzen, so verhalten sich die Strategien ebenfalls gleich. Damit ist ein Zusammenhang zwischen der Struktur der Fitnesslandschaft und dem Verhalten der Strategien gefunden. Als weitere Anwendung dieses Ergebnisses erhalten wir eine Charakterisierung des Grundzustandes von Schrödinger-Operatoren. Aufbauend auf den mathematischen Ergebnissen des letzten Kapitels wird in Kapitel 5 die Klassifikation der Strategien durchgeführt. Dabei erhalten wir das wichtige Resultat, daß zwei Fitnesslandschaften, die lokal aus den gleichen Singularitäten (siehe Tabelle 4.5) bestehen dasselbe Verhalten der Evolutionären Strategie implizieren. Dieses Ergebnis wurde zuerst nur für die Darwin-Strategie erhalten, um es dann auch auf die anderen behandelten Strategien auszudehnen. Im letzten Kapitel der Arbeit wird noch der Frage nach derVeränderung der Mutationsverteilung nachgegangen. Bisher haben wir dafür eine Diffusionsnäherung benutzt, die aber im allgemeinen in Computerexperimenten nicht verwendet wird. Lassen wir diese Einschränkung fallen, so wechselt die Beschreibungsweise von partiellen Differentialgleichungen zu Integro-Differentialgleichungen. Eine Angabe der Lösung ist über die Methode des iterierten Kerns möglich. Am Beispiel der Gauß- bzw. Cauchy-Verteilung werden die Standardprobleme Parabel und Doppeltopf studiert. Die Ergebnisse erbrachten für die Gauß-Verteilung ein ähnliches Ergebnis wie für die Diffusionsnäherung. Dagegen sind die Eigenschaften der Lösung für die Cauchy-Verteilung im Falle des Doppeltopfes von denen der Gauß-Verteilung verschieden. Eine Darstellung der einheitlichen Beschreibung dieser Strategien sowie ein Ansatz zur Klassifikation beenden das letzte Kapitel. Am Schluß der Arbeit befinden sich 4 Anhänge, welche die umfangreichen Rechnungen und Formeln enthalten. Im Anhang A berechnen wir eine wichtige Invariante von Fitnesslandschaften, die über den Einfluß von Zwangsbedingungen auf die Optimierung die Aussagen treffen. Danach analysieren wir im Anhang B die Gegenwertprobleme der Boltzmann- und Darwin-Strategie, um eine alternative Möglichkeit zu den Berechnungen des Kapitels 3 zu erhalten. Der Anhang C ist der vollständigen Berechnung des Stromes für den Fall eines stückweise quadratischen Doppeltopfes gewidmet. Im Anhang D schließlich ist eine Zusammenstellung der Formeln für die Gemischte Strategie am Beispiel der Parabel und des Doppeltopfs zu finden.
| Identifer | oai:union.ndltd.org:HUMBOLT/oai:edoc.hu-berlin.de:18452/15026 |
| Date | 22 December 1997 |
| Creators | Asselmeyer, Torsten |
| Contributors | Nietzsch, J., Keiper, Robert, Ebeling, Werner |
| Publisher | Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät I |
| Source Sets | Humboldt University of Berlin |
| Language | German |
| Detected Language | German |
| Type | doctoralThesis, doc-type:doctoralThesis |
| Format | application/pdf, application/postscript |
Page generated in 0.0032 seconds