Inhaltsverzeichnis

1  Abstract  3

2  Grundlagen der Optimierung  4

2.1  Einteilung von Optimierungsverfahren  6

2.2  Auswahl der Verfahren  6

3  Die eingesetzten Verfahren  7

3.1  Die evolutionären Algorithmen  7

3.2  Die Evolutionsstrategie  8

3.3  Dierential Evolution  9

3.4  Gradientenabstieg  10

3.5  Modiziertes Hillclimbing  11

4  Die generelle Struktur von Hyper-Heuristiken zur Optimierung  12

4.1  Das allgemeine Rahmenwerk  12

4.2  Lernen mit Verstärkung mit Tabu-Liste  14

5  Die entwickelten Verfahren  16

5.1  3 phasiger Ansatz zur Optimierung  16

5.1.1  Vorüberlegungen  17

5.1.2  Motivation des kooperativen Verfahrens  17

5.1.3  Algorithmus  18

5.2  Ansatz mit dynamischer Verfahrensselektion  18

5.2.1  Vorüberlegungen  21

5.2.2  Motivation  21

5.2.3  Algorithmus  22

5.2.4  Modikationen  22

5.3  Hyper-Strategie mit Verstärkungslernen und Tabu-Liste  22

5.3.1  Vorüberlegungen  24

5.3.2  Algorithmus  25

5.3.3  Modikationen  25

6  Evaluation  27

6.1  Eierpappenfunktion  30

6.1.1  Populationsverlauf  30

6.1.2  Optimierungsfortschritt  30

6.1.3  Gefundene Funktionswerte  33

6.1.4  Funktionsaufrufe  35

6.1.5  Summierte Funktionsaufrufe  36

6.1.6  Spinnennetz Funktionsaufrufe  37

1

6.2 Rosenbrockfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.2.1 Populationsverlauf . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.2.2 Optimierungsfortschritt . . . . . . . . . . . . . . . . . . . . . . . . . 42 6.2.3 Gefundene Funktionswerte . . . . . . . . . . . . . . . . . . . . . . . 43 6.2.4 Funktionsaufrufe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 6.2.5 Summierte Funktionsaufrufe . . . . . . . . . . . . . . . . . . . . . . 45 6.2.6 Spinnennetz Funktionsaufrufe . . . . . . . . . . . . . . . . . . . . . 47

7 Zusammenfassung 47

Abbildungsverzeichnis

1 Rahmenwerke für Hyper-Heuristiken (vgl. Korkmaz et al., 2008) . . . . . . 13 2 Schema-Skizze des 3 phasigen Ansatzes zur Optimierung . . . . . . . . . . 16 3 Schema-Skizze des Ansatzes mit dynamischer Verfahrensselektion . . . . . 20 4 Schema-Skizze der Hyper-Strategie mit Verstärkungslernen und Tabu-Liste 22 5 Populationsverlauf des kooperativen Verfahrens bei der Eierpappenfunktion 31 6 Populationsverlauf der Hyperstrategie bei der Eierpappenfunktion . . . . . 32 7 Zielfunktionsverlauf des kooperativen Verfahrens bei der Eierpappenfunktion 32 8 Zielfunktionsverlauf der Hyperstrategie bei der Eierpappenfunktion . . . . 33 9 Funktionswerte gefundener Optima des kooperativen Verfahrens bei der Eierpappenfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 10 Funktionswerte gefundener Optima der Hyperstrategie bei der Eierpappenfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 11 Funktionswerte gefundener Optima der Dierential Evolution bei der Eierpappenfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 12 Funktionsaufrufe des kooperativen Verfahrens bei der Eierpappenfunktion . 35 13 Funktionsaufrufe der Hyperstrategie bei der Eierpappenfunktion . . . . . . 36 14 Summierte Funktionsaufrufe des kooperativen Verfahrens bei der Eierpappenfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 15 Summierte Funktionsaufrufe der Hyperstrategie bei der Eierpappenfunktion 37 16 Summierte Funktionsaufrufe der Dierential Evolution bei der Eierpappenfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 17 Funktionsaufrufe und Lösungsgüte des kooperativen Verfahrens bei der Eierpappenfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 18 Funktionsaufrufe und Lösungsgüte der Hyperstrategie bei der Eierpappenfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 19 Populationsverlauf des kooperativen Verfahrens bei der Rosenbrockfunktion 40 20 Populationsverlauf der Hyperstrategie bei der Rosenbrockfunktion . . . . . 41 21 Zielfunktionsverlauf des kooperativen Verfahrens bei der Rosenbrockfunktion 42 22 Zielfunktionsverlauf der Hyperstrategie bei der Rosenbrockfunktion . . . . 42

2

23 Funktionswerte gefundener Optima des kooperativen Verfahrens bei der Rosenbrockfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 24 Funktionswerte gefundener Optima der Hyperstrategie bei der Rosenbrockfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 25 Funktionswerte gefundener Optima der Diernetial Evolution bei der Rosenbrockfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 26 Funktionsaufrufe des kooperativen Verfahrens bei der Rosenbrockfunktion . 45 27 Funktionsaufrufe der Hyperstrategie bei der Rosenbrockfunktion . . . . . . 45 28 Summierte Funktionsaufrufe des kooperativen Verfahrens bei der Rosenbrockfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 29 Summierte Funktionsaufrufe der Hyperstrategie bei der Rosenbrockfunktion 46 30 Summierte Funktionsaufrufe der Dierential Evolution bei der Rosenbrockfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 31 Funktionsaufrufe und Lösungsgüte des kooperativen Verfahrens bei der Rosenbrockfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 32 Funktionsaufrufe und Lösungsgüte der Hyperstrategie bei der Rosenbrockfunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

Tabellenverzeichnis

1 Wahlmöglichkeiten für Auswahlfunktion und Akzeptanzfunktion (vgl. Korkmaz et al., 2008) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Algorithmenverzeichnis

1 Lernen mit Verstärkung (vgl. Burke und Subeiga, 2003) . . . . . . . . . . 15 2 Lernen mit Verstärkung mit Tabu-Liste (vgl. Yagiura et al., 2005, S. 136) 15 3 3-pasiger Algorithmus zur Optimierung . . . . . . . . . . . . . . . . . . . . 19 4 Subroutine für 3-pasigen Algorithmus zur Optimierung . . . . . . . . . . . 20 5 Algorithmus mit dynamischer Verfahrensselktion (Teil 1) . . . . . . . . . . 23 6 Algorithmus mit dynamischer Vefahrensselktion (Teil 2) . . . . . . . . . . . 24 7 angepasste Hyperstrategie (Teil 1) . . . . . . . . . . . . . . . . . . . . . . . 26 8 angepasste Hyperstrategie (Teil 2) . . . . . . . . . . . . . . . . . . . . . . . 26

1 Abstract

Ziel der vorliegenden Arbeit ist die Entwicklung eines kooperativen Optimierungsverfahrens, d.h. mehrere Low-Level Heuristiken werden von einer High-Level Heuristik so gesteuert, dass sie ein Problem gemeinsam lösen. Gemeinsam lösen heiÿt hier, sie lösen sich ab, d.h. eine Low-Level Heuristik fängt dort an, wo die andere aufgehört hat.

3

Warum ist eine kooperative Lösung aber sinnvoll? Die Nachbarschaftsstruktur einer komplexen Zielfunktion kann in verschiedenen Regionen der Zielfunktion sehr unterschiedlich sein. In unterschiedlichen Regionen eignen sich lokal eventuell jeweils andere Low-Level Heuristiken als anderswo, d.h. es gibt eventuell keine Erkundungs-Heuristik, die sich überall gleich gut eignet. Ein anderer Vorteil ist: Man hebt den Grad der Allgemeinheit des Suchverfahrens durch kooperative Suche, während ein Verfahren trotzdem (idealerweise) konkurrenzfähig zu Einzelverfahren bleibt. Allgemeinheit kann besonders für nicht-Experten von Vorteil sein, oder wenn wenig Wissen über die Problemstruktur vorhanden ist. In der Literatur spricht man häug von Hyperstrategien, da Hyperstrategien auf einer noch höheren Abstraktionsebene arbeiten als die Metaheuristiken. Hyperstrategien operieren nicht auf Zielfunktionen, sondern sie verwalten Metaheuristiken. In der vorliegenden Arbeit erfolgt zunächst eine allgemeine Einführung über Optimierung und die eingesetzten Low-Level Heuristiken. Es folgt eine Literatur-Befragung über die generelle Struktur von Hyper-Heuristiken. Im Kern der Arbeit werden drei vom Autor selbst entwickelte kooperative Verfahren vorgestellt. Die zwei zuletzt entwickelten Verfahren werden im Rahmen der Evaluation statistisch verglichen.

2 Grundlagen der Optimierung

Optimierungsaufgaben können in drei Kategorien eingeteilt werden, Parameteroptimierung, Reihenfolgeoptimierung und Auswahloptimierung. Die vorliegende Arbeit beschäftigt sich mit Parameteroptimierung. Parameteroptimierung bezeichnet die Suche nach möglichst optimalen Entwurfsparametern für ein Produkt, einen Prozess oder ein System. Bei der Suche wird davon ausgegangen, das die sogenannten Designvariablen beim Entwurf veränderbar sind, wie beispielsweise Querschnitte und andere geometrische Gröÿen. Ein so entstandener Entwurf hat dann eine gewisse Güte, die durch eine Gütefunktion bzw. Zielfunktion bestimmt werden kann. Bei der Festlegung der Zielfunktion müssen oft mehrere teilweise konkurierende Kriterien gewichtet werden, die optimiert werden sollen, beispielsweise Biegesteigkeit, Spannungsverteilung unter Belastung, etc. Dies alles durch einen einfachen Wert zu messen ist oft nicht einfach und efrordert einiges an mathematischer Modellierung, denn die Wahl der Zielfunktion beeinusst nachher maÿgeblich, was im Laufe der Optimierung unter den konkurrierenden Lösungen als optimaler angesehen wird. Bei der mathematischen Modellierung einer Aufgabe der Parameteroptimierung lässt sich das Vorgehen wie folgt beschreiben:

Zunächst müssen die Suchvariablen für den Optimierungsprozess bestimmt werden. Die Suchvariablen sind hier die einstellbaren Gröÿen des Systems, für welche der Optimierungsprozess den optimalen Wert nden soll. Die Suchvariablen werden hier bezeichnet mit x i ; x (u)

^(o) ≤ x i ≤ x i ; i = 1...n.

Normalerweise ist es sinnvoll, für jede dieser Suchvariablen einen geeigneten Wertebe- i

reich anzugeben, der von vorneherein eingrenzbar ist. Die Festlegung des Wertebereiches

4

(u) geschieht hier durch die Angabe von

x i

Aus den Suchvariablen enstehen die sogenannten Suchvektoren x ^{(j) = (x indem jeweils die Suchvariablen einer einzelnen Iteration, angedeutet durch die Hochzahl} (j) zu einem Tupel zusammengefasst werden. Die Tupel sind Elemente des R n und dieser kann bekanntlich zusammen mit den üblichen Operationen und einem Skalarkörper als Vektorraum aufgefasst werden. Die Vektorraumstruktur interessiert im folgenden jdedoch lediglich wegen der Nomenklatur, da meist keine Vektorraum-Eigenschaften nötig sind. Die Vektorraumstruktur hat auÿerdem den Vorteil, dass eine einzige Funktion f : R n → Rbetrachtet werden kann.

Oft sind bestimmte Kombinationen der Suchvariablen nicht möglich. Der Ausschluss solcher Kombinationen bestimmt sich durch die sogenannten Restriktionen. Alle konvexen Teilmengen des R n ^{lassen sich durch eine oder mehrere Restriktionen von der Form} G j (x) = G j ^(x 1 , x 2 , ..., x n ) ≤ b; j = 1...m beschrieben. Als Sonderfall seien alle konvexen Polyeder genannt. Konvexe Polyeder lassen sich sogar sämtlich durch lineare Restriktionen beschreiben.

Als nächstes benötigt man ein mathematisches Modell der Optimierungsaufgabe. Das mathematische Modell wird beschrieben durch die sogenannte Zielfunktion. Oft ist die Beschreibung jedoch nicht direkt möglich, denn der Einuss der Designvariablen auf ein Simulationsmodell kann oft nur durch erneute Simulation bestimmt werden. Die Zielfunktion ist dann eine Gütefunktion, die die Eigenschaften des simulierten Modells bewertet. Die Beschreibung der Güte kann als eine einzige Abbildung F (x) = F ^(x 1 , x 2 , ..., x n ) → min des Suchvektors x (hier die Designvariablen) auf eine Güte aufgefasst werden. Die Abbildung ist möglicherweise also kompliziert zusammengesetzt und daher oft nur relativ teuer zu brechnen. Es drängt sich daher auf, dass ein ezientes Optimierungsverfahren mit möglichst wenig Funktionsauswertungen auskommen sollte. Gefragt ist immer das globale Minimum, hier bezeichnet als x ∗ = (x ∗ 1 , ..., x ∗ n ) , es treten

jedoch häug viele lokale Optima auf, die den Optimierungsprozess erschweren. Deswegen gibt es globale Optimierungsverfahren und lokale Optimierungsverfahren. Globlale Optimierungsverfahren suchen den Bereich meist weiträumig ab, ohne dabei schnell zur Konvergenz gegen ein lokales Optimum zu neigen. Lokale Optimierungsverfahren konvergieren zwar schnell gegen irgendein Optimum, möglicherweise ein lokales, sind aber eventuell sehr weit vom globalen Optimum entfernt. Für konvexe Funktionen nden sie immer direkt das globale Optimum. Kooperative Optimierungsverfahren setzen globale und lokale Optimierungsverfahren parallel ein. Global und lokal ist hier keine schwarz-weiÿ Unterscheidung, sondern eine Abstufung zwischen sehr weiträumig absuchenden Verfahren zu sehr schnell (lokal) konvergenten Verfahren. Jedes solcher Verfahren hat seine spezischen Vor- und Nachteile und in jedem Stadium des Optimierungsprozesses sind andere Verfahren optimal. Die Optimalität hängt allerdings sehr vom gewählten Problem ab. Es muss daher ein Weg gefunden werden, die einzelnen Verfahren im Laufe des Optimierungsprozesses dynamisch auszuwählen. Die dynamische Auswahl setzt voraus, zeitweise die Resultate mehrerer Verfahren miteinander

5

zu vergleichen, d. h. notwendigerweise parallel arbeiten zu lassen. Die parallelen Phasen sollten möglichst kurz gehalten werden, da sie besonders rechenintensiv sind.

2.1 Einteilung von Optimierungsverfahren

Es kann unterschieden werden zwischen mathematischen und experimentellen Ansätzen, damit wird ausgedrückt, ob der Optimierungsprozess an einem physikalischen Modell (z.B. im Windkanal) oder an einem mathematischen Modell vorgenommen wird, was entweder direkt mathematisch modelliert wurde oder aber auf ein Simulationsmodell zurückgreift. Ebenso kann unterschieden werden zwischen statischen und dynamischen Ansätzen, was bezeichen soll, ob für ein System einmalig ein statisches Optimum gesucht werden soll, oder ob es bei wechselnden Bedingungen immer in einem Optimalzustand gehalten werden soll. Die Einteilung zwischen numerischen und analytischen Ansätzen gibt an, ob die Lösung iterativ gefunden wird, oder durch das Lösen einer oder mehrerer Gleichungen. Unterschieden wird auch zwischen deterministischen und stochastischen Ansätzen, die sich darin unterscheiden, ob eine Zufallskomponente den Algorithmus beeinusst oder nicht. Die Optimierung in dieser Arbeit ist immer mathematisch, statisch und numerisch, jedoch werden stochastische und deterministische Verfahren parallel eingesetzt. Deterministische numerische Verfahren liefern bei gegebenem Startpunkt immer das gleiche Resultat, sie sind meist eher lokale Optimierungsverfahren und nden das nächste lokale Optimum. Die stochastische Komponente verlangsamt normalerweise die Konvergenz, ermöglicht es aber, aus einem lokalen Optimum wieder herauszuspringen, um möglicherweise das globale Optimum zu nden. Einfachstes Beispiel ist sicherlich Simulated Annealing, welches die Abkühlung von Metallen simuliert. Mit der sogenannte Metropolis-Wahrscheinlichkeit werden hier bewusst Verschlechterungen in Kauf genommen. Simulated Annealing gehört auch zu einer besonderen Untergruppe der stochastischen Verfahren, den sogenannten naturanalogen Verfahren. Zu den naturanalogen Verfahren gehören wiederum die evolutionären Algorithmen, die das Optimierungspotential der Evolution nutzen.

2.2 Auswahl der Verfahren

Zur weiträumigen Absuchung des Suchraums el die Wahl auf evulutionäre Algorithmen, welche eine Untergruppe der stochastischen/naturanalogen Verfahren bilden. Stochastische/naturanaloge Verfahren arbeiten stets generationsbasiert und verwenden die genetischen Operatoren Mutation, Rekombination und Selektion. Eingesetzt wird hier konkret die Evolutionsstrategie, welche aus Arbeiten von Rechenberg aus den sechsziger Jahren stammt, 1973 veröentlicht wurde und von Schwefel weiter verbessert wurde (vgl. Schneider, S. 22). Die hier ebenfalls eingesetzte Dierential Evolution von R. Storm und K. Price ist sehr viel neuer und stammt aus den 90er Jahren. Sie wurde 1995 erstmals vorgestellt (vgl. Kommer, 2008, S. 22). Nicht alle evolutionären Algorithmen hätten sich aufgrund der unterschiedlichen Kodierungsmöglichkeiten der Chromosome gleichermaÿen für die

6

Aufgabe der Optimierung einer Zielfunktion auf dem R n geeignet. Hier sind binäre Kodierungen eher ungeeignet, weil sie keine sinnvolle Arbeitsweise der genetischen Operatoren zulassen. Beide hier vorgestellten Verfahren arbeiten mit einer reellen Kodierung der Chromosomkomponenten (Gene) und die Arbeitsweise der genetischen Operatoren lässt sich als arithmetische Operationen darstellen. Die Darstellbarkeit als arithmetische Operatoren hat sich für Funktionen auf dem R n als günstig erwiesen. Die globalen Optimierungsmethoden werden ergänzt durch lokale (konvexe) Optimierungsmethoden, die einerseits die lokale Konvergenz beschleunigen können, andererseits aber auch in einfachen Fällen die Lösung sehr viel ezienter alleine nden können. Als Standardverfahren kommt hier der Gradientenabstieg mit Linesearch zum Einsatz. Der Gradientenabstieg zeigt bei einfachen (lokal) konvexen Funktionen eine lineare Konvergenz (vgl. Jarre/Stoer, S. 147), kann jedoch in gebogenen Tälern, wie bei der Rosenbrockfunktion schnell feststecken. Daher kommt auÿerdem noch ein robusteres lokales Suchverfahren zum Einsatz, eine Modikation des Hillclimbings, welches wesentlich exibler ist, für das jedoch in einfachen konvexen Fällen keine lineare Konvergenz nachweisbar ist, was im wesentlichen an seinem sehr einfachen und daher robusten Ansatz liegt.

3 Die eingesetzten Verfahren

3.1 Die evolutionären Algorithmen

Evolutionäre Algorithmen arbeiten nach dem Vorbild der Natur, indem sie das natürliche Optimierungspotential der Evolution nutzen. Die Evolution hat ausgehend von sehr einfachen Lebewesen immer komplexere, immer besser an ihren Lebensraum angepasste Lebewesen hervorgebracht. Die Lebensformen wurden in einem gewissen Sinne optimiert durch die Evolution. Dabei entstehen bei der Vermehrung der Lebewesen durch Rekombination und Mutation des Erbgutes immer neue Varianten, von denen aber nur die am besten angepassten überleben, die sich dann weiter vermehren (Selektion). Das Prinzip ist auch bekannt als Survival of the ttest, die Zielfunktion heist daher hier auch Fitnessfunktion. Bei den evolutionären Algorithmen geht man davon aus, dass ein bestimmtes Erscheinungsbild (Phänotyp) durch ein bestimmtes Chromosom (Genotyp) kodiert ist. Konkret ist das Chromosom die Kodierung einer möglichen Lösung eines Optimierungsproblems, die in den Chromosomen abgespeichert ist. Beispielsweise kann eine bestimmte Ampelschaltung, die optimiert werden soll, kodiert sein. Es existieren verschiedene Arten von Kodierungen, die dem Problem angepasst werden müssen, meist erfolgt die Kodierung binär. Im Falle der Parameteroptimierung hat es sich als günstig erwiesen, die Folge von reellen Parametern einfach als ein Tupel von reellen Zahlen zu kodieren. Ein Tupel von reellen Zahlen ist in gewisser Weise natürlich, weil sich dann die genetischen Operatoren gröÿtenteils als arithmetische Operationen darstellen lassen. Die bekanntesten zwei hier existierenden Verfahren sind die Evolutionsstrategie und die Dierential Evolution. Beide verwenden unterschiedliche Formen der sogenannten genetischen Operatoren, deren

7

Aufgabe hier dargestellt ist.

Selektion: Vielversprechende Lösungen werden zur weiteren Verarbeitung ausgewählt, um aus ihnen evtl. noch bessere Lösungen zu erzeugen.

Rekombination: Zwei vielversprechende Lösungen werden kombiniert, in der Honung, dass sich aus ihnen eine noch bessere Lösung erzeugen lässt. Mutation: Zur Wahrung der Variation in der Population und zur Verhinderung der vorzeitigen Konvergenz, hat es sich als sinnvoll erwiesen, zufällige Veränderungen der Population zu erzeugen.

3.2 Die Evolutionsstrategie

Bei der Evolutionsstrategie wird ein Chromosom wie folgt kodiert:

x ^{= (x} 1 , ..., x n , σ 1 , ..., σ n , φ 1 , ..., φ n(n−1)/2 )

Das Chromosom besteht aus dem Suchvektor ^(x 1 , ..., x n ), den Mutationsschrittweiten ^(σ 1 , ..., σ n ) und den Winkeln ^(φ 1 , ..., φ n(n−1)/2 ). Die Mutationsschrittweiten geben die Streuung einer Normalverteilung an, von denen die einzelnen Mutationsschritte jeweils als Zufallszahlen erzeugt werden. Die Winkel dienen dazu, den Mutationsvektor jeweils im R n in einer von n(n − 1)/2 Ebenen zu drehen. Die Drehung soll eine bessere Anpassung der Hauptsuchrichtung an die Fitnesslandschaft gewährleisten. Ansonsten wären nämlich nur achsenparallele Hauptsuchrichtungen möglich.

Mutation: Man spricht von der korrelierten Mutation durch Addition eines Zufallsvek-tors aus einer Multinomialverteilung. Der Suchvektor x wird durch einen Zufallszahlsvektor z aus einer einer Multinomialverteilung mutiert, indem dieser einfach addiert wird. Die Diagonalelemente der Kovarianzmatrix der Multinomialverteilung entsprechen genau den

σ i . Durch die Einstellung der Winkel sind die Elemente auÿerhalb der Diagonalen nicht 0. Um die oben beschriebene multinomiale Verteilung der Mutation zu ereichen, geht man vor, indem ein sogenannter Mutationsvektor ^Δ gezogen wird mit

^{Δ = (Δ} 1 , ..., ^Δ n ^{); Δ} i ∼ N (0, σ i )

Die einzelnen Komponenten ^Δ i sind nun erst einmal normalverteilt mit Standardabweichung σ i und daher noch unkorreliert. Der Vektor mit den unkorrellierten Komponenten entspräche einer Multinomialverteilung mit einer Diagonalmatrix als Kovarianzmatrix. Die Korrelation der einzelnen Komponenten des Mutationsvektors kann man realisieren, indem man diesen mit Drehmatritzen multipliziert.

Der Mutationsvektor Δ wird nun gedreht in den n(n − 1)/2 Ebenen, indem er mit den entsprechenden Drehmatritzen R pq ^(φ pq ) zu den Winkeln φ i multipliziert wird. Die Variablen p, q geben jeweils an, in welchen beiden Komponenten gedreht wird. Für die n

beiden Komponenten gibt es insgesamt Möglichkeiten. Nun hat man eine Realisation ² von z bezeichnet als ^Δ korr , die sich ergibt aus

8

n

Anschlieÿend mutiert man x indem man ^Δ korr addiert:

x = x ^{+ Δ} korr

Die Winkel und die Mutationsschrittweiten werden nun auch in den Optimierungsprozess einbezogen, indem sie als Elemente des Chromosoms ebenfalls dem gentischen Algorithmus unterworfen sind. Damit wird das Verfahren selbstadaptiv. Die Mutation der σ i verläuft

i = φ i + τ 2 N (0, 1).

Selektion: Die Selektion erfolgt nach dem Eliteprinzip. Eine Generation der Gröÿe μ erzeugt immer etwa 5 bis 7 mal soviele Nachkommen durch Mutation. Aus den λ Chromosomen der mutierten Generation werden nun wieder die μ besten entsprechend der einfachen Generationsgröÿe ausgewählt und mit den μ besten wird weiter verfahren. Sie bilden die neue Ausgangsgeneration.

mut sel → P μ → P λ → P μ →

Interpretation: Das Verfahren als solches entspricht einem generationenbasierten Hillclimbing, welches um die Selbstadaptivität der Schrittweite und der Hauptsuchrichtung erweitert wurde.

3.3 Dierential Evolution

Kodierung der Chromosome: Ein Chromosom besteht hier einfach aus einem Tupel von Parameterwerten. Man könnte auch sagen, dass in diesem Fall das Chromosom und der Suchvektor gleichzusetzen sind.

x ^{= (x} 1 , ..., x n )

Mutation: Die Mutation erfolgt hier, indem ein vielfaches einer zufälligen Suchrichtung zu einem Suchvektor addiert wird. Die Suchrichtung ergibt sich hierbei aus der Dierenz von zwei zufälligen anderen Suchvektoren der Vorgängergeneration. Dabei steht im Exponent der Iterationszähler, die Subscripte r 1 und r 2 sind uniform verteilte Zufallsvariablen, die einen zufälligen Index eines Vektors aus der Population bezeichen. Der so erhaltene Vektor wird in v t+1 i gespeichert. F ist ein Strategieparameter.

= x t i + F · (x t − x t ) v t+1

r 1 r 2 i

Die Form der Mutation hat den Sinn, dass sich dadurch die Schrittweite und die Suchrichtung selbständig adaptieren sollen.

9