evolution strategies

• Infos
• Paper
• Abkürzungen
• BBH - building block hypothesis
• CMA - covariance matrix adaptation
• CSA - cumulative step-zize adaptation
• EA - evolutionary algorithm
• EC - evolutionary computation
• ES - evolution strategy
• EP - evolutionary programming
• GA - genetic algorithm
• GR - genetic repait
• TSP - traveling salesman problem
• TUB - Technical University of Berlin
• 1 Einleitung
• Inspirationen gehen zurück bis zu frühen Pionieren
• John von Neumann
• 3 wesentliche Paradigmen herauskristallisiert
• Neuronale Netze
• fuzzy logic
• evolutionary computation
• verwendet Problemlöser
• diese unterliegen
• Geburt
• Tod
• Variation
• Selektion
• zusammengefasst unter den Bezeichnungen
• computational intelligence
• soft computing
• natural computation
• 2 kurzer Abriss der Geschiche
• experimental evolutionary optimizaton
• erste Experimente mit 3D-Objekt in Windkanal
• Veränderung zu einer Form mit minimalem Widerstand pro Volumen
• Ausgeführt im Juni 1964
• Erkenntnis:
• einfache randomisiert Heuristik erbringt gleiches Ergebnis wie
  diskrete, gradienten-orientierte numerische Strategie
• führte zu weiteren Anwedungen
• Design einer Heißwasserdüse
• genetischer Algorithmus
• Düse segmentiert
• jedes Segment hat
• Länge
• Durchmesser
• Eigenschaften und Zahl der Segmente in "Genen" variabel codiert
• führte zu einem unerwartet guten Ergebnis - das seinem Verständnis weit voraus ging
• verwendete Regeln
• 1. verändere jede Variable zu jedem Zeitschritt
• geringe Abweichung
• zufällig
• 2. wenn die neue Variablenmenge die alte in der Güte übertrifft: übernehmen, sonst alte beibehalten
• Vorgehen wurde später (1+1)-Evolutionsstrategie benannt
• continuous decision variables and first theoretical results
• Einführung der Verwendung von Gauß-Verteilungen
• Erkenntnisse
• Konvergenzgeschwindigkeit ist invers proportional zur Zahl der Variablen
• Konvergenzgeschwindigkeit ist proportional zur Biegung der Objektfunktion
• lineare Konvergenz kann man erhalten, indem man die Mutationsrate stets in einer geeigneten Größenordnung einstellt
• optimale Mutationsrate ist abhängig von bestimmterErfolgswahrscheinlichkeit - unabhängig von der Dimension des Suchraumes
• optimale Mutationsrate im Bereich von 1/5 für die untersuchten Modellfunktionen
• bezüglich der (m + 1)-Strategie
• m Eltern, 2 selektiert und rekombiniert, dann mutiert
• Crossover kann Evolution substantiell beschleunigen (gemessen an Generationen)
• die Population kann lernen ihre Mutationsrate selbst anzupassen
• Numerical evolutionary optimizationsuperimposed onto simulation models
• Einführung der (m + l)-Evolutionsstrategie
• Erzeugung von l ³ 1 Nachfahren
• die l schlechstesten der m + l Individuen werden verworfen
• Einführung der (m, l)-Evolutionsstrategie
• Wie (m + l), jedoch werden die Eltern in jedem Falle verworfen
• 3 grundlegender evolutionsärer Algorithmus
• Ziel
• Optimierung einer gegebenen Objekt- oder Qualitäts-Funktion F
• im Bezug auf Entscheidungs-Variablen / Kontroll-Parameter y = (y₁, y₂,...) - oft Objekt-Parameter genannt
• Notation
• F(y) ® opt.
• y Î Y
• Suchraum
• Evolutionsstrategien arbeiten auf Populationen P von Individuen a
• ein Individuum a_k steht für
• spezielle Menge von Objekt-Parametern y_k
• Objekt-Funktions-Wert F_k = F(y_k)
• Fitness
• oft auch zusätzlich Strategie-Parameter s_k
• steuern die statistischen Eigenschaften der genetischen Operatoren
• im speziellen:
• Mutations-Operator
• Rekombinations-Operator
• können sich während des Evolutions-Prozesses mit entwickeln
• sind bei selbst-adaptiven Systemen nötig
• a_k = (y_k, s_k, F(y_k))
• exogene Strategie-Parameter
• Populationsgröße m
• Nachkommenzahl l
• MixingNumber r
• Anzahl der Eltern für die Erzeugung eines Nachkommen
• r= 1 = Klonieren
• Spezialfall
• keine Rekombination
• Schreibweise vereinfacht sich zu (m , l), oder, (m+l)
• gewöhnliche Schreibweise: (m/r, l) oder (m/r+ l)
• während eines Schrittes werden l Nachkommen a_l' aus der Menge der m Eltern-Individuen a_m erzeugt
• die Größe der Nachkommen-Population ist in der Regel ungleich der der Elterngeneration
• Algorithmus


• in Generation g=0 wird die Elterngeneration P_p⁽⁰⁾ erzeugt
• in Schleife: jeweils erzeugen und Mutieren eines Nachkommen
• dazu: selektieren der 1 £ r £ m Eltern
• Marriage
• zufallsbasiert
• nicht von den Parametern der Eltern abhängig
• wenn r = 1 ®Nackomme ist einfach Kopie eines Elters
• wenn r = m ®alle potenziellen Eltern werden mitglied der Elternfamilie
• Zeile 7: Rekombination der endogenen Strategie-Parameter
• Zeile 8: Rekombination der endogenen Objekt-Parameter
• Zeile 9: Mutation der Strategie-Parameter
• Zeile 10: Mutation der Objekt-Parameter
• unter Verwendung der neuen Strategieparameter!
• nach dem Erzeugen der Nachkommen-Population P₀^(g) wird selektiert und übrig bleibt die neue Eltern-Generation P_p^(g+1)
• als Terminationsbedingung kommen in Frage:
• Ressourcen-Kriterien
• Maximalzahl von Generationen
• Maximalzahl von CPU-Zeit
• Konvergenzkriterien
• im Raum der Fitness-Werte
• im Raum der Objekt-Parameter
• im Raum der Strategie-Parameter
• Selektion
• Teil jedes evolutinären Algorithmus
• zielorientierter Selektions-Operator
• gibt der Evolution eine Richtung
• im Falle der evolutionären Algorithmen: deterministischer Prozess
• Arbeitsweise: neue Eltern-Generation zur Zeit (g+1) wird erhalten durch
• Auswahl der m besten Individuen
• P_p^(g+1) := {a_{1; g} , ..., a_{m; g}}
• a_m;g bedeutet: Wähle das mth beste der g Individuen
• zwei Möglichkeiten: g= m + l (Plus-Strategie - elitist),m; l (Komma-Strategie)
• die erste schließt die Elterngeneration bei der Auswahl mit ein
• bei der zweiden Methode wird nur aus den Nachfahren gewählt.
• beide Methoden haben spezielle Anwendungsfelder
• Komma-Strategie wird bei unbegrenzten Suchräumen verwendet
• Y = IRⁿ zum Beispiel
• Plus-Strategie wird in diskreten, fest großen Suchräumen verwendet
• Beschränkungen bei der (m/r,l)-Strategie:
• m < l
• m = l bedeutet:
• Alle erzeugten Individuen werden selektiert
• ®kein Selektionsdruck
• ®random walk im Parameterraum
• Mutation
• grundlegender Variations-Operator
• primäre Quelle der genetischen Variation
• Design ist Problem-abhängig
• Anforderungen
• Erreichbarkeit
• von einem parentalen Status (y,s) aus muss jeder andereStatus (y',s') in endlich vielen Schritten erreichbar sein
• Verzerrungs-Freiheit
• Variations-Operatoren sollen keinerlei Verzerrung bewirken
• über das Prinip der maximalen Entropie kommt man zur Normalverteilung
• bei unbegrenzten stetigen Suchräumen zur
• Normalverteilung
• bei unbegrenzten diskreten Suchräumen zur
• geometrischen Verteilung
• siehe auch
• Entropie
• Skalierbarkeit
• Mutationsrate sollte anpassbar sein
• Ziel: Entwicklungsfähigkeit
• Beispiele
• Im Raum der Reellen Zahlen
• Suchraum = IR^N
• y' = y + z
• z = s(N₁(0,1),...,N_N(0,1))
• N_i(0,1) sind unabhängige zufällige Werte der Standard-Normalverteilung
• es kommt zu keiner Verzerrung, das Verteilung symmetrisch ist
• ® jede Komponente y_i' folgt der Dichtefunktion p(y')=(1,s×(2p)^(1/2))/()exp (- (1,2)/()((y_i' - y_i)²,s²)/())
• minimalste Mutationen sind der Normalfall
• Ziehungen sind isotropisch verteilt um parentalen Zustand
• Isotropie
• Nicht immer ist isotropie erwünscht!
• Rotation möglich durch Multiplikation mit Rotationsmatrix:z = M(s₁N₁(0,1),...,s_NN_N(0.1))
• M = (orthognale Rotationsmatrix)
• Rotationsmatrix
• M bewirkt Korrelationen der Komponenten von z
• binäre Suchräume
• Verzerrungsfreiheit durch "microscopic reversibility"
• d.h.: Flip 0Þ1 ist gleichwahrscheinlich wie Flip 1Þ0
• Mutationsrate p_m wird oft mit p_m = (1,N)/() gewählt
• theoretische Gründe
• empirische Gründe
• bisher keine überzeugende Argumente für adaptive Mutationsrate gefunden
• Rekombination
• diskret bzw. dominant
• Elterlicher Vektor a⁽ⁱ⁾ = (a⁽ⁱ⁾₁,...,a⁽ⁱ⁾_D)
• ®rekombinierter Vektor: r = (r₁,...,r_D)
• r_k = a^(m)_k - m = Random(1,...,r)
• für k-te Komponente des Vektors r wird zufällig ein Elter gewählt und dessen k-te Komponente übernommen
• intermediär
• r_k = (P_m=1,ra^(m)_k,r)/()
• berechnet lediglich den Schwerpunkt der Eltern-Vektoren
• "Centroid"
• benötigt in diskreten Räumen weitere Operatoren wie Rundung um zurück in den diskreten Raum abzubilden
• Vorteile
• Building Block Hypothesis
• verschieden gute Bausteine
• von verschiedenen Eltern
• zusammengemischt
• ®Kombination guter Eigenschaften
• bisher nicht so richtig gut bewiesen
• genetic repair and similarity extraction
• kontrovers zur
• Building Block Hypothesis
• Idee:
• nicht die verschiedenen Eigenschaften werden "zusammengewürfelt"
• sondern: die gemeinsamen Eigenschaften der Eltern
• ®Extraktion der Ähnlichkeiten
• 4 Adaption der endogenen Strategieparameter
• Variation von s
• wenn s sehr klein gewählt wird, wird im Schnitt jede2. Mutation die lokale Erfolgsdomäne treffen
• ®kleines s ®stetiger Fortschritt
• Erfolgswahrscheinlichkeit
• P_s = Wsk. (Nachfahre ersetzt Elter)
• geht gegen (1,2)/() für s®0
• aber: kleines s
• ® kleine Fortschrittsrate
• progress rate, f
• geht gegen 0 für s ®0
• ®Effizienz wird kleiner
• Gegensatz: sehr großes s (s ® ¥)
• Treffer in lokale Erfolgsdomäne wird seltenes Ereignis
• ®P_s geht gegen 0
• ®Fortschrittsrate f®0
• dazwischen: Band von s-Werten, die hohe Fortschrittsrate bewirken
• "Evolutions-Fenster"
• (1,5)/()-Erfolgsregel
• für (1+1)-ES
• um lokale Performance möglichst nahe an das Optimum zu bringen
• stelle Mutationsrate so ein, dass die (gemessene) Erfolgsrate etwa bei 0.2 liegt
• wenn P_s < (1,5)/() Þ verringere die Mutationsrate
• wenn P_s > (1,5)/() Þ vergrößere die Mutationsrate
• Schätzwert für P_s bestimmen:
• über eine feste Generationszahl mitteln
• P_S = (G_S,G)/()
• G = Zahl der beobachteten Generationen
• G_S = Anzahl der erfolgreichen Mutationen
• s= (s,a)/() - wenn P_S>(1,5)/(),s×a - wenn P_S<(1,5)/(),s - sonst
• a = konstanter Faktor
• abhängig von Generationszahl G
• Anzahl der Dimensionen N
• Selbstadaption
• Idee:
• jedes Individuum hat eigene Menge der Strategieparameter
• Parameter unterliegen Mutation und Rekombination und Selektion
• werden somit ebenfalls optimiert
• Vorgehen:
• multiplikativ
• s_l' = s_lexp(z}
• Exponentialfunktion wird benutzt, um auf der logarithmischen Skala additive Mutation zu erhalten:log(s_l') = log(s_l) + z
• z= Zufallsgröße
• Eine Möglichkeit: z = t N_l(0,1)
• ist eine normalverteile Zufallsgröße
• t ~ (1,N)/()
• andere Möglichkeit z = ± ln(a)(gut beim Sphären-Modell)
• a > 1
• ®s' = sa - wenn u(0,1] £ 0.5,s/a - wenn u(0,1] > 0.5
• u(0,1] ist ein uniformer Zufallsgenerator
• a = 1 + t ist ein Lernparameter
• Meta-ES
• verschachtelte Evolutionsstrategie, hierarchisch organisierte ES
• Beschreibung in Form der [ m' / r' ¨ l' (m/r,l)^g]-ES
• ¨ = + oder ,
• m' Eltern-Populationen von (m/r¨l)-Strategien
• erzeugen l' (m/r¨l)-Stratgie-Nackommen
• evolvieren über g Generationen unabhängig voneinander
• danach: Selektion der besten m' Populationen als Basis für die nächsten l' Nachkommen-Strategien