Natürliche Optimierung

Sven Schirmer

Inhalt• Überblick traditionelle Optimierung• Überblick heuristische Optimierungsmethoden• Wirkungsweise Evolutionäre Algorithmen

– Genetik und Evolution– Kostenfunktion und Suchraum– Selektion– Binärer GA– Kontinuierlicher GA – Anpassung GA-Operatoren: Spezialfall TSP (??)– MOO Multi Objective Optimization

• Ant Colony Optimization (TSP)• Particle Swarm Optimization

Optimierung

Ziel: Finden geeigneter Lösungen für komplexe Problemstellungen

Beispiele:• Traveling Salesman• Chip-Layout• Produktions- und Einsatzplanung• Modellparametrisierung• Mustererkennung

Problem

• oft unbekannte, ggf. multimodale und nicht vollständig berechenbare Fehleroberfläche

• Hohe Anzahl freier Variablen = hochdimensionaler Suchraum

• Kostenfunktion/Fehlerfunktion Berechnung der Qualität einer Lösung

Traditionelle Optimierung

Lineare Optimierung • Nur für Lineare (Un-) Gleichungssysteme

z.B. Produktionsplanung

• Lösungsmethoden– Simplex-Algo (Dantzig)– Innere Punkte

Analytische Optimierung• Über Ableitung zu Minima und Maxima• Nur bei differenzierbaren Kostenfunktionen

Traditionelle Optimierung II

• Brute Force; Exhaustive Search– Extrem rechenaufwendig– Erfolg intervallabhängig

• Nelder Mead Downhill Simplex – Oft werden nur lokale Minima gefunden– Aufwendige Berechnungsmethoden– Ursprünglich wenig parallelisierbar

• Gradientenabstiegsverfahren (Cauchy 1847)

Traditionelle Optimierung

• Oft gefangen in lokalen Minima

• Ergebnis von Startpunkt abhängig

• Deterministisch

• Matlab-Tool: optimtool

Überblick Natürliche Optimierungsmethoden

Methode Operatoren WertebereichGenetische Algorithmen(1975, Holland)

Selektion,

Rekombination,

Mutation

Binär

Diskret

KontinuierlichEvolutionäre Algorithmen(Schwefel, 1995)

Particle Swarm Optimization(Kennedy 1985)

Follow the best kontinuierlich

Ant Colony Optimization(Dorigo,Maria 1997)

Pherom Update Traveling Salesman(Permutation)

In Summe sind verschiedene Optimierungsmethoden

auf unterschiedlichen Problemen gleich gut geeignet

Kein „perfektes“ Optimierungsverfahren

No Free Lunch Theorem(Wolpert / McReady 1997)

Vorteile Natürlicher Optimierungsmethoden

• Massiv-parallele Suche nach brauchbaren Lösungen

• Ohne Ableitungen der Kostenfunktion

• Weniger anfällig für lokale Minima

• Auch für diskrete und nichtkontinuierliche Kostenfunktionen

Nachteile Natürlicher Optimierungsmethoden

• Nicht deterministisch – unterschiedlichste Lösungen bei mehreren Durchgängen möglich

• Erzeugen gute, jedoch nicht unbedingt die beste Lösung

• rechenintensiv

Genetische / Evolutionäre Optimierung

• Heutige Artvielfalt = Resultat vieler Millionen Iterationen natürlicher (stochastischer) Optimierung

• Unterschiedlichste Eigenschaften der Lebewesen ermöglichen Leben in verschiedensten „Nischen“

• Dynamische Änderung der Umweltbedingungen bedingt Weiterentwicklung oder Aussterben

Wie funktioniert das?Genetik - skizzenhaft

• Chromosomen (DNA + viel Protein)

• Gen = Abschnitt auf DNA

• Enthält RNA/Protein Bauanleitungen

Erb-Informationen in 20 Aminosäuren

Art Anz. Chromosomen Anzahl GeneMücke 6 16.047

Frosch 26 20.000

Mensch 46 23.700

Kartoffel 48 …

Goldfisch 96 …

• Allel Ausprägung eines Gens• Paarung Informationen beider

Gene werden kombiniert• Dominante / rezessive Allele• Genotyp bedingt Phänotyp

(Augenfarbe, Hautfarbe…)

Genetik und Evolution - skizzenhaft

• Veränderung innerhalb der Art durch Rekombination und Mutation Mendel 1860

• Erfolgreiche Änderungen pflanzen sich fort Evolution Darwin 1858

Terminologie und Synonyme

• Chromosom = Lösungsvorschlag, Parametersatz, Ausprägung, Genotyp

• Population = Menge von Lösungen in einer Generation

• Anzahl Generationen = Anzahl der GA-Iterationen

• Fitness = Kosten = Qualität

GA - Allgemeiner Ablauf

Wiederholen für N Generationen

Kosten bestimmen

Selektion

Lösung evaluieren

Mutation

Rekombination

Startpopulation bestimmen

Kostenfunktion und Suchraum definieren

Abbruchj/n

Startpopulation bestimmen

Kostenfunktion und Suchraum definieren

Rekombination

Startpopulation bestimmen

Kostenfunktion und Suchraum definieren

Mutation

Rekombination

Startpopulation bestimmen

Kostenfunktion und Suchraum definieren

Suchraum festlegen

• Anzahl freier Variablen = Dimension des Suchraumes

• Wertebereiche sinnvoll eingrenzen!• Binäre GA: Wertebereich quantifizieren =

Chromosomenkodierung

X Y

0 00000 0 0000000

0.2 00001 1 0000001

0.4 00010 2 0000010

0.6 00011 … 3 0000011 ...

3.1 11111 127 1111111

= 12 bit Genom

Kostenfunktion

• Problembeschreibung– analytische Funktion

– Modell– Gleichungssystem

• bewertet die Qualität der Lösung

• GA Optimierung auf Minimum oder Maximum

• tKostenfunktion ~ tGA

Startpopulation

• Gleichmäßige (!?) Verteilung der Lösungen im gesamten Suchraum

• Binär: round(rand(npop,nbit))

• Kontinuierlich: rand(npop,nparam) * (og – ug) + ug

Selektion

• Kosten aller (noch nicht berechneten) Chromosomen bestimmen

• Generationswechsel: Survival of the fittest– Selektionsrate (e.g. 50%) – (wahrscheinlich) die Besten– Oder Grenzwertbasiert – anfangs „überleben“

wenige Chromosomen, später mehr

Rekombination, Reproduktion

• Austausch von Allelen immitiert biolog. Paarungsprozess zur Weitergabe von Eigenschaften

• Auswahl der Partner-Chromosomen– Sortiert: bestes mit zweitbesten usw.– Roulette

– gewichtetes Roulette – Tournament

Rekombination - Binär

• Crossover: Position zufällig auswählen

parents

children

• Multiple Crossover: mehrere Bereiche austauschen; Positionen zufällig auswählen

1 1 0 1 0 0 1 1 1 0 1 0 1 1 0 1

1 1 0 1 1 1 0 1 1 0 1 0 0 0 1 1

Mutation• „verbreitert“ Suchspektrum• ermöglicht das Verlassen lokaler Minima

• Mutationsrate ggf. 20% der Population sehr hoch im Vergleich zur Natur

Elitarismus „schützt“ beste Lösungen

• Binäre Mutation– Z.B.: Für gesamte Populationsmatrix: an zufällig

bestimmten Reihen/Spalten Bits umkehren

• Bereiche rotieren

… ggf. an eigene Problemstellung anpassen

Mutation - Binär

Für jede weitere Generation

1. Qualität der Nachkommen berechnen

2. Selektion

3. Rekombination, Mutation

4. Abbruchkriterium prüfen

Abbruchkriterien1. Anzahl Generationen erreicht

2. Optimierungsziel erreicht

3. Timeout

Konvergenz - TraceAnzeige der Kosten der besten Lösung je Generation

Wenn nicht, liegt ggf. ein Problem in Kostenfunktion vor

Trace für mehrere Durchläufe

Beispiel

Fehleroberfläche

for i=1:70for j=1:70

err_s(i,j)=ga_testfun_bin([-2+i*0.1 - 2+j*0.1]);end

end

Approximierte Lösungen: x=5.0000 y=5.0000 min = -7.5568X=4.3000 y=4.0000 max = 8.6398

• Ausgeprägte lokale Maxima und Minima• Zwei Variablen• Wertebereich: [-2 5]; Intervall 0.1

Matlab GA-Toolboxen

• Gatool – GUI für GA Optimierung minimiert Kosten

• Gaot Toolbox maximiert Kosten

• GPLab– http://gplab.sourceforge.net/features.html

GAOT Toolbox, binäres Problem

[pop] = initializega(init_pop_size,bounds,'ga_testfun_bin',... options, [accuracy 0]);

[sol,endPop,bestSols,trace,allPops]=ga_disp(bounds,'ga_testfun_bin',... options,pop,... %options for evalFN [accuracy 0 0],... %[epsilon prob_ops display] ['maxGenTerm'],... %termination function [generations],... %termination options ['normGeomSelect'],... %selection function [0.08],... %selection function options ['simpleXover'],... %XOverFn [wurst], ... %XOverFn options don’t matter ['binaryMutation shiftMutation'],...

[prob_of_mutation; wurst]);

Demo: „ga_run_bin“

Einfluss der Mutation

• 20 Durchläufe a 60 Generationen über 20 Individuen

Populationsgröße und Konvergenz

Kontinuierlich vs. Binär

• Kontinuierliche EA sind – schneller

– leichter zu adaptieren– genauer

(Michalewicz 1992)

• Gleiche Selektionsmethoden

• Vielfalt genetischer Operatoren

Konvergenzvergleich

Gleiches Optimierungsproblemgleiche Variablengrenzendefault-GA Einstellungen

• Simple / diskrete Rekombination

• ArithmetischC = a*P1 + (1-a)*P2

• HeuristischC = a * (Pbetter – Pworse) + Pbetter)

Rekombination - Kontinuierlich

Mutation - Kontinuierlich

• boundaryMutation

• unifMutation ein Parameter wird in Bereichsgrenzen mutiert

• nonUnifMutation kleinere Mutation in späteren Generationen

• multiNonUnifMutation wie nunUnifMutation, aber für alle Variablen eines Chromosoms

GAOT Toolboxkontinuierliches Problem

sol= ga(bounds,'ga_testfun_bin',... options,pop,... %options for evalFN [accuracy 1 0],... %[epsilon prob_ops display] ['maxGenTerm'],... %termination function [generations],... %termination options ['normGeomSelect'],... %selection function [0.08],... %selection options ['arithXover heuristicXover simpleXover'],... %XOverFn [2 0;2 3;2 0], ... %XOverFn options ['boundaryMutation nonUnifMutation …

multiNonUnifMutation unifMutation'], ... %Mutation fun [4 0 0;6 100 3;4 100 3;4 0 0]); %Mutation options

Demo GA-Kontinuierlich

• ga_run_float.m

Knapsack - Problem

Gegeben: Rucksack mit bestimmten Volumen Vmax; Gegenstände mit unterschiedlichen Volumina v und Wert w

Gesucht: optimale Rucksack-Beladung für maximalen Wert C

max1

=⋅= ∑=

i

N

ii wnC i

N

ii vnV ⋅≥ ∑

=1maxbei und Ν∈n

Knapsack Rahmenbedingungen

• Maximales Volumen = 100

• Welche Parametergrenzen?

ID Volumen Wert

1 5 8 1,6

2 5 8 1,6

9 15 20 1,333

8 15 17 1,133

5 10 10 1

3 6 6 1

7 12 10 0,833

10 30 20 0,667

4 8 5 0,625

6 11 5 0,455

Wert / Volumen

Knapsack Problem

• Diskrete Werte für i ?

Runden der kontinuierlichen Werte vor Berechnung

• Constraints (max. Volumen) einbeziehen?

• Beispiel: ga_knapsack.m

Einfluss der Mutationsoperatoren

ga_diskret(bounds,'costfun_knapsack',... ['boundaryMutation multiNonUnifMutation unifMutation'],… [4 0 0;4 0 0;4 0 0] );

ga_diskret(bounds,'costfun_knapsack',... ['boundaryMutation unifMutation'],… [4 0 0;8 0 0] );

• Rundreiseproblem mit N Orten (2D) und festem Ausgangs- und Endpunkt, jeder Ort nur einmal

• Diskretes Permutations- bzw. Sortierproblem (NP-vollständig – nicht deterministisch, polynomiale Zeit)

• Kostenfunktion :

Traveling Salesman Problem (TSP)

∑=

++−+−=

N

nnnnn yyxxc

1

2

1

2

1)()(

Sortieren mit EA

Bisherige Rekombinations- und Mutationoperatoren unbrauchbar - Permutationsoperatoren notwendig!

Zyklische Rekombination

index = find(p1==1)

while c1(index)==0

{

c1(index)=p1(index)

index=find(p1==p2(index))

}

p1 2 1 7 4 6 5 3 8p2 3 7 2 5 6 4 8 1c1 1

p1 2 1 7 4 6 5 3 8p2 3 7 2 5 6 4 8 1c1 1 8

p1 2 1 7 4 6 5 3 8p2 3 7 2 5 6 4 8 1c1 1 3 8

p1 2 1 7 4 6 5 3 8p2 3 7 2 5 6 4 8 1c1 2 1 3 8

p1 2 1 7 4 6 5 3 8p2 3 7 2 5 6 4 8 1c1 2 1 7 3 8

p1 2 1 7 4 6 5 3 8p2 3 7 2 5 6 4 8 1c1 2 1 7 5 6 4 3 8

left=find(c1==0);c1(left)=p2(left);

Reihenfolgen - Rekombinationcut1 = round(rand*(n-1)+0.5);cut2 = round(rand*(sz-cut1-1)+1+cut1); pm1=p1(1:end-1);pm2=p2(1:end-1);c1=p1;c2=p2;for i=[1:cut1 (cut2+1):size] pm1=strrep(pm1,p2(i),-1); pm2=strrep(pm2,p1(i),-1);endc1((cut1+1):cut2)=…

p2(find(pm2>0));c2((cut1+1):cut2)=…

p1(find(pm1>0));

cut1 cut2+1

1 5 6 7 8

p1 7 2 1 8 4 5 6 3

p2 5 6 7 1 3 8 2 4

pm1 7 -1 1 -1 -1 -1 6 -1

c1 7 1 8 2 4 5 6 3

p1 7 2 1 8 4 5 6 3

p2 5 6 7 1 3 8 2 4

pm1 7 -1 1 -1 -1 -1 6 -1

c1 7 1 8 2 4 5 6 3

p1 7 2 1 8 4 5 6 3

p2 5 6 7 1 3 8 2 4

pm1 7 -1 1 -1 -1 -1 6 -1

c1 7 1 8 2 4 5 6 3

c2 5 7 1 6 3 8 2 4

PMX-Operator (Partially Mapped Crossover)

Pos1 = 3 SS1 = [7 6]

Pos2 = 4 SS2 = [8 6]

p1 5 3 7 6 4 8 1 2

p2 5 4 8 6 1 2 7 3

c1 5 3 8 6 4 7 1 2

c2 5 4 7 6 1 2 8 3

Pos1 = 4 SS1 = [8 1 3 7 6]

Pos2 = 8 SS2 = [1 7 3 6 5]

p1 5 4 2 8 1 3 7 6

p2 2 4 8 1 7 3 6 5

c1 8 4 2 1 7 3 6 5

c2 2 4 5 8 1 3 7 6

Wozu jetzt das?

Ggf. gute Teilgebiete weiterentwickeln

Mutation für Permutation

• Swap Mutation– verdreht zwei zufällig ausgewählte Zahlen

• AdjacentSwap Mutation– Verdreht eine zufällig ausgewählte Zahl mit

ihrem Nachbarn

Mutation für Permutation

• Shift Mutation

• Inversionsmutation

3 5 6 7 4 2 8 1

chi 3 5 6 7 2 8 1 4

par

P1 = 1; P2 = 6

2 4 8 1 7 3 6 5

chi 3 7 1 8 4 2 6 5

par

Wie Qualität der Lösung bewerten?

• Visuell: wenn sich Bewegungslinien nicht schneiden

Demo „orderbasedExample“

Multikriterielle Optimierung

• Engl.: Multi-Objective Optimization (MOO)

• Konkurrierende Ziele gleichzeitig:

432211 xxxxf +++=

432

212

111

xx

xxf +++=

MOOP• values = rand(700,4)

• f1_ = f1(values)

• f2_ = f2(values)

Methode 1: gewichtete Teilfunktionen nur eine Lösung je GA-Durchlauf

MOOP: Pareto-optimale Lösung

Kein Funktionswert läßt sich verbessern ohne einen anderen zu verschlechtern

Wenn Pareto-Menge bekannt, kann Benutzer selbst das „richtige“ auswählen

Pareto-Lösung mit EA suchen

• Dominanz von Lösungen: x1 dominiert x2

wenn:)()( 2111 xfxf <

• MOGA: Nach jedem Durchlauf werden Lösungen iterativ nach Dominanz gerankt: jeweils alle nichtdominierten Chromosomen werden einem Rang zugeordnet (Fonesca/Flemming 1993)

• Cluster vermeiden: Zu nahe Lösungen werden mit höheren Kosten bestraft

)()( 2212 xfxf ≤UND

Futtersuche der Ameisen – Wege - Optimierung

• Ameisen bewegen sich auf Futtersuche anfangs zufällig

• legen Duftmarke (Pherome)– langer Weg wenig Pherom– wenige Ameisen wenig Pherom

• Wegfindung durch Intensität der Pheromspur an Gabelungen

• Pheromspur degeneriert mit Zeitverlauf

ACO – Ant Colony Optimization

• Anwendungsgebiete:– Wegefindung in Graphen – TSP

– Machine Learning– Knapsack– Dynamisches Netzwerkrouting

ACO – TSP - Algorithmus

1. Starttouren initialisieren

2. Für jede Ameise: a) Gesamt-Tour Schritt für Schritt anhand Distanz zur

nächsten Stadt und deren Pherom-Intensität berechnen

b) Gesamt-Tourlänge bestimmen

c) Pherom-Updates für alle Teilstrecken bestimmen

∑=

q

bmn

amn

bmn

amnk

mn d

dp

/

/

ττ

a) ∑−

=+=

1

11,/

n

i

kii

kmn dQτc)

ACO – TSP - Algorithmus

3. Beste Tour ermitteln (Elite-Pheromspur)

4. Pherom-Matrix aktualisieren (inkl. zeitl. Verfall)

5. Zurück zu 2. bis max. Iterationen erreicht

elitemn

N

k

kmnmnmn

ants

ετττξτ ++−= ∑=1

)1(

Demo ACO - antcolony.m

Simple Regeln im natürlichen Schwarmverhalten

• Vorgänger folgen (Heuschrecken)

• Kollisionen vermeiden– Gleiche Richtung– Gleiche Geschwindigkeit

• Anonyme „Anführer“ kennen beste Lösung (Bienen)

• Kommunikation zwischen Individuen

Particle Swarm Optimization (PSO)

• Kennedy / Edward 1985

• Viele Partikel „fliegen“ durch Lösungsraum

• Aktuelle „Kosten“ aller Individuen bekannt

• Partikel streben zur besten Lösung:

newnm

oldnm

newnm

oldnm

bestglobalnm

oldnm

bestlocalnm

oldnm

newnm

vpp

pprpprvv

,,,

,_

,22,_

,11,, )()(

+=

−××Γ+−××Γ+=

VektorParameterp

gkeitGeschwindiv

lenZufahlszahrr

Lernfaktor

−==

==ΓΓ

21

11

,

,

Literatur

• Haupt, Randy L. (2004): Practical Genetic Algorithms (Second Edition). 2. Aufl.

• Kost, Bernd (2003): Optimierung mit Evolutionsstrategien. Eine Einführung in Methodik und Praxis mit Visualisierungsprogrammen. 1. Aufl. Frankfurt am Main: Deutsch.

• Mitchell, Melanie (1998, c1996): An introduction to genetic algorithms. 1. Aufl. Cambridge, Mass: MIT Press.

• Deb, Kalyanmoy (2001): Multi-objective optimization using evolutionary algorithms. 1. Aufl. Chichester ;, New York: John Wiley & Sons.

• Dorigo, Marco; Stützle, Thomas (2004): Ant colony optimization. Cambridge, Mass: MIT Press.