1. Evolution strategies ----------------------- Methoden der CI Diskrete Modellierung nicht ausreichend für einige Probleme => Bedürfnis nach fehlertoleranten Methoden => CI (sub-symbolische Techniken) Eigenschaften Fehlertoleranz Parallelität Einfache Modellierung Akzeptable Laufzeit für Näherung Natur: Biologische Inspiration -> Theretisches Modell -> Anwendungsspezifische Anpassung Was ist Optimierung? Minimierung / Maximierung der Fitness Optimum := Finde ein x, sodass für alle x* in S: f(x) <= f(x*) Fitnesssfunktion: Bewertung des x \in Suchraum Suchraum (Eingabe), Lösungsraum (Ausgabewerte) kontinuierliche vs. kombinatorische Lösungsmenge Optimierungsmethoden Newton - ? Broyden-Fletcher-Goldfarb-Shanno (BFGS) - ? Evolutionary Algorithm (EA) - ? Partikel Schwarm Optimierung (PSO) - ? EA Was ist das? "Naturinspirierte Optimierungsverfahren" Stochastische Erkundung des Suchraums Problemlösung mit Zufall statt nachdenken Möglichkeit zur Problemoptimierung ohne das Problem vollständig zu verstehen Individuum := Vektor reeller Zahlen plus Strategieparameter Einsatz Wenn kaum Infos/Anforderungen über Suchraum vorhanden Optimierendes Problem ist weder stetig noch diffrenzierbar Algorithmus while(not $Abbruchbedingung): - Für i \in [1..lambda]: - Wähle p Eltern aus P - Erstelle neues x_i anhand von Rekombination - Mutiere x_i - Berechne f(x_i) - Bewertungsfunktion von x_i - Füge x_i zu P hinzu - Selektion der besten Individuen - Beim nächsten Durchlauf: Wähle µ Eltern P aus P' Rekombination Idee - Kombination guter Gene - building block hypothesis (Gute Gene verbreitet sich über Generationen) - genetic repair effect (Annahme: Gemeinsame Merkmale der Eltern vererben sich, anstatt unterschiedlicher Merkmale) Implementierung: - 1-point crossover: Zwei Eltern, ein zufälliger Kreuzungspunkt - n-point crossover: Zwei Eltern, n zufällige Kreuzungspunkte Dominante Rekombination := Randomisierte Kombination der Einzelgene beider Eltern Intermediäre (arithmetische) Rekombination Nachkomme ist arithmetisches Mittel der Eltern (gewichtete oder ungewichtete Variante) PMX (Permutationsoperator), Garantie der Gültigkeit einer Lösung Mutation Idee Exploration des Lösungsraums Hauptquelle genetischer Variation Je näher an Optimum, desto kleiner müssen die Schritte sein Bedingungen an den Operator Erreichbarkeit := Jeder Punkt x der Lösungsraum muss erreichbar von jedem anderen Punkt x' durch Mutation sein (Mutation innerhalb der Lösungsmenge möglich) Driftlosigkeit := Mutationswahrscheinlichkeit in alle Richtungen des Suchraums gleich Skalierbarkeit := Mutationsstärke einstellbar Bitflip-Mutation Jedes Bit wird mit einer Wahrscheinlichkeit: p_m = 1/N geflippt Probleme - Reihenfolge der Elemente (TSB) ??? - Mehrfaches Auftreten von Elementen (Städte) ??? Inversions-Mutation - Reihenfolge der Elemente wichtig - Invertieren eines bestimmten Bereiches des Lösungstrings (Vertauschung) Gauss-Mutation - Mutation in R^N durch Addition reeller Zufallswerte (auf Gauß-/Normalverteilung basierend) - Schrittweiten - Eine Schrittweite: x'=x+z - n-Schrittweiten (Vektor): z := (s_1*N_1(0,1),...,s_n*N_n(0,1)) , N:=Zufalsswert(Erwartungswert, Standardabweichung), s:=Schrittweite Selektion - Drängen der Nachkommen anhand fitnesswerte in bestimmte Richtung - Aufgabe: Beste Lösung erhalten - Selektiinsdruck:= schlechte Lösungen überleben mit geringer Wahrscheinlichekeit - Gegenspieler von Mutatiaon und Rekombination - Gute Lösungen können auch verhindern, dass lokale Optima verlassen werden, um noch bessere Lösungen zu finden - Plus Selektion: Wähle neue Population aus Kindern und Eltern - Komma Selektion: wähle neue Population nur aus den Kindern (- Es existiert Zwischenvariante, mit "TTL"-Parameter für Individuum) - Fitnessproportionale Selektion - Auswahlwahscheinlichkeit an die Fitness gekoppelt - Selektion von schlechten Individuen möglich (mit geringer Wahrscheinlichkeit) - Turnierselektion - Vermeidung der Dominanz der Besten - Wettkampf zufälliger Individuen 2. EA runtime analysis ---------------------- - Komplexitätsklassen (O-Notation) - Partitionen - Aufgeteilt nach Fitness - Lösungen in Fitness legen - Größere Bereiche für Fitnesswerte - Bessere Anpassungsmöglichkeit - Erwartete maximale Laufzeit: Summiere für alle Partitionen 1/p_i , wobei p_i die kleinste Wahrscheinlichkeit für einen Sprung aus der Partition ist - Bestimmung von p_i: min([p(x) for each x in partition]) mit p(x) = Wahrscheinlichkeit für einen Sprung - Dies ist nur sinnvoll, wenn für die Bestimmung nicht jedes Element betrachtet werden muss, sondern mit Äquivialenzklassen gearbeitet werden kann - ggf. die Partitionen direkt so auswählen, dass es sich um Äquivialenzklassen handelt 3. Parameter Control -------------------- - Konzept: - Einflussnahme auf Effizienz und Qualität des EA - Mutationsparameter beeinflusst Laufzeit - Automatisierung der Parameterauswahl (nicht bei Tuning per Hand :P) - Parametertypen - exogen: globale Eigenschaften des Algorithmus, z.B. Populationsgröße - endogen: Individuumsabhängig, z.B. Mutationsrate - statisch: Konstanten - Tuning - per Hand - Meta-EA - Evolution of Evolution - Kontrolle (Laufzeit) - Deterministisch - Parameter abhängig von Generationenzahl - Erst große, dann kleine Schritte - Adaptive Steuerung der Schrittweiten - vom Benutzer definierte Regeln - Idee: bei großem Erfolg => große Schritte & bei kleinem Erfolg => kleine Schritte - Anmerkung: Erfolg = Anzahl erfolgreicher Mutationen geteilt durch Anzahl aller Mutationen (einer Generation) - z.B. Rechenberg 1/5-Erfolgsregel => ab 1/5 gilt der Erfolg als groß - Selbstadaption - EA passt Parameter selbst an - Mutationsstärke: sigma' = sigma * e^(tau*N(0,1)) - Beispiel: tau = 1 / sqrt(N) - Multivariante: sigma' ist Vektor - Parameter nimmt selbst an Evolution Teil - d.h. Rekombination, Mutation, Selektion - Lernparameter - Auch für kombinatorische Probleme - Varianten ? 4. Constraint handling ---------------------- - reale Probleme benötigen häufig Restriktionen => nicht der gesamte Suchraum ist gültig - Restriktionen können in Form von Gleichungen h(x), oder in Form von Ungleichungen g(x) gegeben sein. - es gibt ein Maß für die Restriktionsverletzung G(x), welches sich wie folgt zusammen setzt: die Summe vom Betrag aller Gleichungen h_j(x) addiert zur Summe aller Ungleichungen g_i(x) oder 0 für negative g_i(x). - Straffunktionen - Konzept - Bestrafung von ungültigen Lösungen - f_NEW(x) = f(x) + alpha * G(x) - Typen - Death Penalty - töte ungültige Lösungen - Nachteil: langsam, kann stagnieren - statisch - alpha ist statisch, z.B. 2.0 - dynamisch - alpha = (C*t)^alpha2 - alpha ist abhängig von der Generation, z.B. C=0.5 und t=Generationszähler und alpha2 \in {1,2} - adaptiv - Bestrafung passt sich dem Suchraum an - Erhöhung von Alpha, falls innerhalb der letzten k Generationen vor der aktuellen eine Bestrafung stattfand - Reduktion von Alpha, falls innerhalb der letzten k Generationen vor der aktuellenen keine Bestrafung stattfand - Schrittweitenreduzierung - some unknown bullshit - Meta-Modell - Verfahren um effizient mit Blackbox-Restriktionen umzugehen - Konzept (lineares Meta-Modell): - Sampling von Daten zwischen gültigen und ungültigen Ergebnissen - Binäre Suche auf den gesampleten Daten - ggf. Probleme bei inhomogenen Lösungsräumen (=> Gültigkeitsanalyse) - Reparatur - zusätzliche Funktion welche Punkte aus dem ungültigen Raum in den gültigen Raum projiziert 5. Particle swarm optimization ------------------------------ - Schwarmintelligenz - kollektives, koordiniertes und zielgerichtetes Handeln - Nachteil des Einzelnen wird durch die große Anzahl (Parallelität) ausgeglichen - Nutzung der Umwelt als Gedächtnis - Konzept - Schwarm: Kooperation großer Anzahl von Einheiten (z.B. Ameisen) - Stigmergie: Individuen kommunizieren über Umwelt - Emergenz: Das Ganze ist mehr, als die Summe seiner Teile - Prinzipien der Schwarmbildung - Zusammenhalt: Jeder Partikel orientiert sich an der Position seiner Nachbarn - Ausrichtung: Jeder Partikel bewegt sich in ähnlich Richtung wie seine Nachbarn - Trennung: Kollisionsvermeidung mit Nachbarn - Allgemein: v'=v+ Summe beliebiger anderer "Partikelgeschwindigkeiten" mal faktor (z.B. Nachbarn) - Partikelschwarmoptimierung (PSO) - Optimierheuristik, in der potentielle Lösungen als Schwarm von Partikeln aufgefasst werden - Kontinuirlich - numerisch - Partikel: Position x, Geschwindigkei v - x'= x + v - Anpassung von v - Position p^b: Beste fitness ever des Partikels [Selektion] - Position p^g: Beste fitness ever des Schwarms (alternativ: defenierte Nachbarschaft) [Selektion] - Beschleunigungskoeffizient: c (Tendenz: eigene oder Schwarmfitness) - Zufallswert: r \in [0,1] [Mutation] - (p^b-x) und (p^g-x) [Rekombination] - Addition (beider Differenzen zu x) zu v: v' = v+c1*r1*(p^b - x)+c2*r2*(p^g - x) - Algorithmus while(Abbruchbedingung) { for(i=1; i < Partikelanzahl; i++) { Berechnung von p^b und p^g; Anpassung der Geschwindigkeit v; Anpassung der Partikelposition x; Berechne Fitness f(x); } } - Entspricht (1,1)-EA - Wahl der Nachbarschaft Problemabhängig (Topologie) - p^g => Algorithmus konvergiert schneller, gefahr der lokalen Optima - Trägheitsparameter w - Bessere Konvergenzergebnisse, wenn linear verringer - w < 0 sorgt für konvergentes verhalten - v' = w*v + ... - Diskret - kombinatorisch, z.B. TSB - Permutationen, v gibt Vertauschungsvektor an - Ameisenalgorithmen - Modellierung von Ameisenverhalten, um Optimierungsaufgaben zu lösen - Double-Bridge-Experiment - Verwitterungsanteil - Algorithmus (Ant Colony Optimization (ACO)) while(not Abbruchbedingung) { foreach(Ameise a in Ameisenpopulation) { "Belegung der Variablen" <- ??? Berechnung der Fitness von Ameise a } Anpassung der Pheromone } - Ameise legt ggf. mehr Pheromone ab, wenn fitness des wegen gut - Einsatz, wenn eine zusätzliche heuristische Information zur Verfügung steht 6. Multi-objective optimization ------------------------------- - Konzept - Konfliktäre Optimierungsziele (z.B. Kosten und Leistung) - Finde Minimum des (normierten) Fitnessvektors - Schwach dominierend: x <= x' , wenn für alle i Werte f(x_i) <= f(x_i') - (Stark) dominierend: x < x', wenn x<=x' UND falls es EIN i gibt, sodass f(x_i) < f(x_i') - Vektoren können nicht verglichen werden x || x' (inkompatibel), wenn kein x das andere (schwach) dominiert - Pareto Front (Lösungsmenge im Zielraum): Menge der Fitnessvektoren, dess x-Werte von keinem anderen Wert dominiert werden (Optimums) - Pareto Set (Suchraum): Menge alle Werte, dessen Fitnesswerte in der Pareto Front liegen - f(PS) = PF - EMOA (Evolutionary Multi-Objective Optimization) - EA, der in alle Optimierungsrichtungen gleich optimiert - liefert nur Optimums zurück - posteriori-selection: Danach erst Auswahl der Optimums - Non-Dominated Sorting - Gibt Partitionen von Nicht-Dominirten Lösungen zurück (Rang) - Crowding Distanz - Maß der Streung auf der PF der Fitnesswerte - soll maximiert werden - d_c(x) für Extremwerte: unendlich - d_c(x) = Manhatten-Distanz zwischen vorherigem und nächstem x - Für jede Fitnessdimension Distanz berechnen und der d_c hinzufügen - NSGA-2 - Führe Non-Dominated Sorting aus - Ausführen von crowding distance als Akzeptanzkriterium - Filter, der weit auseinanderstehende Lösungen übrig lässt - SMS-EMOA - Maximierung des "bedeckten" Raumes bzgl. Referenzpunkt (statt Abstand, wie bei NSGA-2) - Durch gleichmäßge Verteilung der Punkte - Berechnung über Hypervolumen - Fläche = Rechteck von Referenzpunkt und Punkt nahe der Pareto Front - Effizientestes Ergebnis - Rake Selection - Ziehe Strecke zwischen Eckpunkten der PF - Bilde Geraden, die orthogonale zu dieser Strecke liegen - Abstand der senkrechten Geraden bestimmt die Anzahl der Lösungen - Schnittpunkte (oder Punkte in der Nähe) von PF und Gerade bilden neue PF - Es gibt PF die sich (sehr) schlecht mit der Rake Selection vereinfachen lassen (- Abstand zur Gerade und Fitness kann gewichtet verglichen werden) 7. Evolutionary kernel shape optimization (Kerndichteverfahren) ----------------------------------------- - Thema: Mustererkennung - Regression - Definition : "untersucht eine mögliche Korrelation zwischen Datenpunkten mit einem angenommenen inneren Zusammenhang" - Muster-Label-Paaren - -> Interpolation von Daten auf Basis von Eckdaten - Histogramme - Graphische Darstellung der Häufigkeitsverteilung metrisch skalierter Merkmale - Einteilung in Klassen - Parzen-Window Schätzer - "Schätzung der Wahrscheinlichkeitsverteilung einer Zufallsvariable" - Schätzt Punkteverteilung (kontinuierlich) - Summmieren der Kernelfunktion - Kernel-Funktionen - Verdichtungsfunktion für parameterfreie Abschätzungstechniken - Gauß-Kernel (Gauss-Funktion) - Epanechnikov-Kernel (-x^2 Parabel) - Bedingungen - Fläche (Inegrahl) K(x) ist 1 - K(-x) = K(x) für alle x - Symmetrie: Integrahl von x*K(x) = 0 -Hybrid-Kernel - Gewichtete Summe von Kerneltypen - Kernel-Bandbreite - Silverman’s Regel - Formel für Bandbreite: Je höher Standardabweichung und Anzahl Muster, desto höher Bandbreite - Nadaraya-Watson - Schätzt eine unbekannte Regressionsfunktion aus den Beobachtungsdaten - Basiert auf Kerndichte-Schätzung - Multivariat: Funktion hängt von mehreren Parametern ab - Je höher Bandbreite, desto höher "Glätte" der Funktion - Evolutionäre Parametersuche - EA zur Schätzung von Bandbreite und Gewichtung bei Hybridkernel - Lokale Modelle - Parameterwahl abhängig von lokaler Kurve - Codebookvektoren (frei parametriesierbare Vektoren) 8. Powell evolution strategies ------------------------------ - Problem: Viele lokale Optama behindern Zufallssuche - Lösungen: EA restarten, lokale Suche: Erst in lokale Minima springen - Hybrid Meta-Heuristik Lokale Suche findet lokale Optima, EA sucht aus lokalen Minima das globale Minimum - Perturbation: Störung, Mutation, Zufallsoptimirung -? - Begriff: Hybrid - Kollaborativ - Sequenzielles Relay (Nacheinander) - Verknüpft / ineinandergegriffen - Integrativ - Gleichzeitig (Iterated local search (ILS) lokal in EA) - EA in lokal und EA in global - ILS: pertubation, local search, apply acceptance criterion - Powell's Methode - Höhenlinien (stufenweise Annährung) - Interpolation des Weges - Powel Evolutions Strategie - Meta-Heuristik (lokale Suche mit globale EA Suche) - ILS mit Powell's Method - Schrittweite - Je häufiger in DAS SELBE (Stagnation, Fitnesswerte ändern sich nur sehr geringfügig) lokale Minumum gesprungen wird, desto größer wird die Schrittweite - (unterschiedliche Minima => kleinere Schrittweite) - No-free-lunch - Es existiert kein bester Algorithmus für alle Probleme - Algorithmus Wende Powell auf initiale Individuen an Bilde Durchschnitt Für jeden initialen Individuen: Mutiere Wende Powell Methode an Bilde Durchschnitt Passe Schrittweite (anhand Fitnessdiff) an Verdopplung/Halbierung empfolen 9. Fuzzy logic ----------------- - Fuzzy-Mengen - Welt ist unscharf - Definition von Schwellwerten - Definition unscharfer Mengen (Fuzzy-Mengen) - Fuzzy-Mengen sind Teilmenge einer Grundmenge - Menge aller Paare (x, µ_m(x) ), wobei M die Fuzzy-Menge - Element bekommt Gradzugehörigkeit/Unsicherheit zur Grundmenge (KEINE Wahrscheinlichkeiten!) - Zugehörigkeitsfunktion µ(x), bildet auf Grad auf Intervall [0,1] ab - Dreiecksfunktion aber auch andere Varianten (Gauß/Trapez, mit Überscheidungen, z.B. Fuzzy-Alter) - Mengenbegriffe - Träger: µ(x) ist größer als 0 (da sonst in keiner Menge) - α-Schnitt: Alle Elemente über einer unteren Grenze α auf µ(x) (Fuzzy-Werte) - Kern von M: µ(x) = 1, alle x aus der Grundmenge, welche zu "1" in der Menge M liegen - Fuzzy-Operationen - t-Norm (Konjunktion): Schnitt zweier Fuzzy-Mengen, Schnittoperation muss selbst kontextabhängig definiert werden (meist min) - s-Norm (Disjunktion): Vereinigung zweier Fuzzy-Mengen (meist max) - Komplement (Negation): µ_m_k(x) := 1- µ_m(x) - De Morgan: Gilt !(M1 n M2) = !M1 u !M2 - Gleichheit: Zwei Fuzzy-Mengen sind gleich, wenn beide Zugehörigkeitsfunktionen µ(x) gleich sind für alle x - Teilmenge: M1 teil von M2, wenn µ_m1(x) <= µ_m2(x) - Fuzzy-Inferenz - Unscharfe Inferenz = (Kern des) approximatives Schließen - B' = A' o (A->B), wobei - (A->B) = Matrix mit allen Kombinationen von Regeln/Abbildungen von Menge A auf B - A' ist Eingabe Fuzzymenge - Modus Ponens (Folgepfeil) - Prämisse: x aus A => y aus B Oder: !A oder B - Prämisse bei Fuzzy unscharf "sehr hoch", "stark" für A oder B - Implikation als Relation mit zwei Parameter (Problemangemessen wählen) - Mamdani-Implikation: Über Minimum{x,y} - Wenn zu 0.1 kalt, dann maximal zu 0.1 Heizung an - Kleene/Dienes-Implikation: Maximum{1-x, y} - Äquivialent zu Mamdani-Implikation, zu verwenden wenn x und y gegenläufig sind (z.B. zu 0.1 warm ...) - Lukasiewicz: min{1, 1−x+y} - Fuzzy-Regler - Vergleich Soll- und Ist-Wert in Abhängigkeit von Steuerparameter - Ist -> Fuzzyfizierung -> Inferenz -> Defuzzyfiziere -> Steuergröße (für herbeiführung des Sollzustands) - Regelbasis (Menge von Regeln) - Regel = Zuordnung Prämisse -> Konklusion - Erfüllungsgrad der Regeln anhand Eingabe = Erfüllungsgrad (Zugehörigkeitsgrad µ(x)) - Regeln können mengentheoretisch Verknüpft sein - Aggregation: Bestimmung der Ausgabe-Fuzzy Menge (Kombination der Konklusion der Regeln) - Defuzzifizierung - Variante 1) Mittelwert Teilmenge von Max-Kriterium-Methode - Variante 2) Schwerpunkt