Gliederung Analytische L¨osung 3 / 37 Analytische L¨osung ...pi.informatik.uni-siegen.de/Mitarbeiter/berlik/lehre/ws0607/ci/ci3.pdf · Ein n-Simplex ist ein durch seine n +1 Eckpunkte

Computational Intelligence

1 / 37

Gliederung

1 Analytische Losung

2 OptimierungsalgorithmenKalkulbasierte Verfahren

Indirekte kalkulbasierte VerfahrenDirekte kalkulbasierte Verfahren

Zufallsgesteuerte VerfahrenRein zufallsgesteuerte VerfahrenNaturanaloge Verfahren

Enumerative VerfahrenZusammenfassung

Dr. Stefan Berlik (Praktische Informatik)


. Analytische Losung 3 / 37

Analytische Losung – Uberblick

IdeeBerechne die Positionen potentieller Optima, d.h. die Stellen an denender Gradient verschwindet

Zu erfullende Bedingungen, damit ~x∗ ein lokales Minimum ist

Notwendige Bedingung Der Gradient ∇f (~x∗) verschwindet

Hinreichende Bedingung Die Hesse’sche Matrix ∇2f (~x∗) ist positivdefinit

Vorausetzungen

Die Gleichungen der Zielfunktion f : X → F mussen symbolischvorliegen

Die Zielfunktion ist (zweifach) differenzierbar

Die Nullstellen des Gradienten sind berechenbar




Gradient

Differentialoperation, die ein Vektorfeld erzeugt

Liefert an jeder Stelle den Vektor in Richtung der starksten Steigungder Funktion

Definition: Vektor der n-partiellen Ableitungen der Funktion f (~x)

∇f (~x) =

(∂f (~x)

∂x1, . . . ,

∂f (~x)

∂xn

)




Hesse’sche Matrix

Matrix der n2 zweiten partiellen Ableitungen der n ersten partiellenAbleitungen bezuglich der n Entscheidungsvariablen

∇2f (~x) =

∂2f (~x)∂x1∂x1

· · · ∂2f (~x)∂x1∂xn

.... . .

...∂2f (~x)∂xn∂x1

· · · ∂2f (~x)∂xn∂xn




Beispiel

Zielfunktionf (~x) = x2

1 + x22

Gradient∇f (~x) = (2x1, 2x2)

-2

0

2

-2

0

2

0

5

10

15

-2

0

2

Abbildung: Funktionsplot

-3 -2 -1 0 1 2 3

-3

-2

-1

0

1

2

3

Abbildung: Gradientenfeld




Beispiel (II)

Zielfunktionf (~x) = x2

1 + x22

Hesse’sche Matrix

∇2f (~x) =

(2 00 2

)Eigenwerte der Hesse’schen Matrix

{2, 2}Die Eigenwerte sind positiv, d.h. die Matrix ist positiv definit




Beispiel (III) – Bestimmung der Minima der Zielfunktion

Notwendige Bedingung

Identifiziere potentielle Extrema

∇f (~x∗)!= (0, 0)

⇔ (2x1, 2x2) = (0, 0)

⇔ (x1, x2) = (0, 0)

D.h. ~x∗ = (0, 0)T ist ein potentielles Extremum (in diesem Fall daseinzige)

Hinreichende Bedingung

Prufen ob die Extremstelle ein Minimum ist

Die Hesse’sche Matrix ist (hier konstant) positiv definit

Das Extremum ist somit ein Minimum




Probleme

Mathematische Formulierung der Zielfunktion ist unbekannt (liegtz.B. nur in Form eines Programms vor)

Ableitungen konnen nicht berechnet werden

Aufwand zur Bestimmung der Ableitungen ist zu groß

Gleichungssysteme i.d.R. nicht losbar



. Optimierungsalgorithmen 11 / 37

Iterative Verfahren – Uberblick

Optimierverfahren

kalkülbasiert zufallsgesteuert enumerativ

Kalkulbasierte Verfahren nutzen Informationen des Gradienten zur Suchedes Optimums

Zufallsgesteuerte Verfahren nutzen Zufallsprozesse zur Suche desOptimums

Enumerative Verfahren werten die Zielfunktion schlicht in allen Punktendes Suchraums aus



. Optimierungsalgorithmen 12 / 37

Iterative Verfahren – Uberblick (II)

Optimierverfahren

kalkülbasiert zufallsgesteuert enumerativ

direkt indirekt

SimulatedAnnealing

naturanalogeVerfahren

vollständig

EvolutionäreProgrammierung

Evolutions-strategien

GenetischeAlgorithmen

GenetischeProgrammierung

modifiziert

SimplexAlgorithmus

NewtonVerfahren

EvolutionäreAlgorithmen

reinzufallsgesteuert

erschöpfendeSuche

Branch-and-Bound

Monte CarloVerfahren

Abbildung: Klassifikation von Optimierungsalgorithmen [Goldberg 1989]



. Optimierungsalgorithmen . Kalkulbasierte Verfahren 13 / 37

Kalkulbasierte Verfahren – Uberblick

Allgemein

Nutzen Gradienten- oder Ableitungsinformationen hoherer Ordnung

Werden deshalb auch als Gradientenverfahren bezeichnet

KlassifikationDirekte Verfahren arbeiten

’direkt‘auf der Zielfunktion

Iterative, meist deterministische AlgorithmenNutzen die Gradienteninformation implizit durchAuswahl der nachfolgenden Suchschritte

Indirekte Verfahren arbeiten’indirekt‘mit der Zielfunktion

Berechnen potentielle Positionen der OptimaGewinnen Gradienteninformation explizit durchMethoden der klassischen Analysis




Kalkulbasierte Verfahren – Uberblick (II)

Klassifikation ist nicht immer eindeutig

Insbesondere: Welche Verfahren sollen als direkt angesehen werden?

Strenge Klassifikation [Wright 1995]:”A direct search method does

not ‘in its heart’ develop an approximate gradient.“




Simplex-Verfahren

IdeeVariiere wiederholt die n + 1 Eckpunkte eines im n-dimensionalen Raumaufgespannten Korpers

Iteratives, deterministisches Verfahren

Vorgeschlagen von Spendley, Hext & Himsworth [1962]

Der Suchkorper ist ein regulares n-Simplex

Nicht verwandt mit dem Simplex-Verfahren zur Optimierung linearerGleichungssysteme




Simplex-Verfahren – n-Simplex

Definition (n-Simplex)

Die konvexe Hulle einer Menge von n + 1 Punkten in allgemeiner Lage imn-dimensionalen euklidischen Raum ist ein n-Simplex.

Erlauterung

Ein n-Simplex ist ein durch seine n + 1 Eckpunkte beschriebenern-dimensionaler Korper (genauer: ein Polytop), der imn − 1-dimensionalen Raum nicht mehr darstellbar ist

Beispiele

Im 2-dimensionalen Raum: Ein 2-Simplex ist ein Dreieck

Im 3-dimensionalen Raum: Ein 3-Simplex ist ein Tetraeder




Simplex-Verfahren – Regulares n-Simplex

Definition (Regulares n-Simplex)

Ein regulares n-Simplex ist ein n-Simplex dessen Eckpunkte aquidistantangeordnet sind.

Beispiele

Im 2-dimensionalen Raum: Ein regulares 2-Simplex ist eingleichseitiges Dreieck

Im 3-dimensionalen Raum: Ein regulares 3-Simplex ist ein regularerTetraeder




Simplex-Verfahren – Algorithmus

Simplex Algorithmus

1 Wahle ein (zufalliges) durch die Punktmenge M = {~P1, . . . , ~Pn+1}mit Pi ∈ X beschriebenes n-Simplex S0 und berechne dieFunktionswerte f (~Pi ) in den Eckpunkten ~P1, . . . , ~Pn+1

2 Bestimme den schlechtesten Punkt ~P−

3 Reflektiere ~P− am Schwerpunkt der durch die restlichen n Punkte

gebildeten Hyperebene in den Punkt ~P ′

4 Berechne f (~P ′)

5 Losche ~P− aus M und fuge ~P ′ hinzu

6 Gehe zu Schritt 2 bis ein Abbruchkriterium erfullt ist




Simplex-Verfahren – Reflektionsoperation

P1

P2

P’

P3

P4

P3

P1

P2

P’




Simplex-Verfahren – Sonderfalle

Oszillation Der neu erzeugte Punkt ist wieder der schlechteste. Wahledann den zweitschlechtesten Punkt als ~P−

Rotation Obige Maßnahme fuhrt zur Rotation des gesamtenSimplex um den dem Optimum am nachsten liegendenPunkt. Halbiere deshalb die Kantenlange




Erweitertes Simplex-Verfahren

Beobachtung

Die Kantenlange kann beim Simplex-Verfahren ausschließlich verkleinertwerden, was die Konvergenzgeschwindigkeit des Verfahrens beschrankt.

Erweiterung durch Nelder & Mead [1965]

Flexiblerer Reflexionsoperator

Zusatzlicher Kontraktions- / Expansionsoperator

Das Verfahren arbeitet somit mit irregularen Simplizia




Gradientenverfahren

IdeeFuhre, beginnend beim Startpunkt, im Suchraum kleine Schritte jeweilsin Richtung des steilsten Abstiegs aus, bis ein (lokales) Minimum erreichtist.

Iteratives Verfahren

Auch als Methode des steilsten Abstiegs bezeichnet




Gradientenverfahren – Algorithmus

Gradientenverfahren1 Wahle einen (zufalligen) Startpunkt ~x (0) ∈ X2 Bestimme den Gradienten am aktuellen Punkt ~x (i):

∇~x f (~x (i)) =

(∂f (~x (i))

∂x1, . . . ,

∂f (~x (i))

∂xn

)3 Fuhre einen Suchschritt in entgegengesetzter Richtung des

Gradienten aus:~x (i+1) = ~x (i) − η∇~x f (~x (i))(η ist der Schrittweitenparameter)





Gradientenverfahren – Probleme

Wahl des Schrittweitenparameters

Bei einem zu kleinem Wert (geringe Schrittweite) kann es langedauern, bis das Minimum erreicht ist

Bei einem zu großen Wert (große Schrittweite) kann es zumOszillieren kommen (Hin- und Herspringen im Suchraum)

Losungsmoglichkeiten: Momentumterm, adaptive Schrittweiten

Stagnation in lokalen Minima

Da der Gradient nur lokale Steigungsinformation reprasentiert, wirdggf. nur ein lokales Minimum erreicht

Dieses Problem kann hier nicht prinzipiell behoben werden

Losungsmoglichkeiten: Mehrfaches Ausfuhren von verschiedenenStartpunkten erhoht die Wahrscheinlichkeit, das globale Minimumzu finden.




Gradientenverfahren – Beispiel

Zielfunktion:

f (x) =5

6x4 − 7x3 +

111

6x2 − 17x + 5

Parameter: Startpunkt x (0) = 2.5, Schrittweite η = 0.005

-1 1 2 3 4 5 6x

-2

2

4

6

8

10

fHxL i x (i) f(x (i)

)f ′

(x (i)

)∆x (i)

1 2.5 1.302 −3.667 −0.0182 2.518 1.233 −3.766 −0.0193 2.537 1.162 −3.865 −0.0194 2.556 1.086 −3.964 −0.0205 2.576 1.007 −4.061 −0.0206 2.560 0.923 −4.158 −0.0217 2.617 0.836 −4.252 −0.0218 2.639 0.745 −4.344 −0.0229 2.660 0.649 −4.432 −0.02210 2.683 0.550 −4.517 −0.023




Gradientenverfahren – Beispiel (II)

Zielfunktion:

f (x) =5

6x4 − 7x3 +

111

6x2 − 17x + 5

Parameter: Startpunkt x (0) = 3, Schrittweite η = 0.25

-1 1 2 3 4 5 6x

-2

2

4

6

8

10


)f ′

(x (i)

)∆x (i)

1 3 −1 −5 −1.252 4.25 1.425 16.823 4.2063 0.044 4.283 −15.403 −3.8514 3.895 −2.389 5.494 1.3735 2.522 1.222 −3.784 −0.9466 3.468 −2.882 −2.225 −0.5567 4.024 −1.461 9.032 2.2588 1.766 2.226 1.209 0.3029 1.463 1.625 2.620 0.65510 0.808 0.005 0.948 0.237




Gradientenverfahren – Beispiel (III)

Zielfunktion:

f (x) =5

6x4 − 7x3 +

111

6x2 − 17x + 5

Parameter: Startpunkt x (0) = 1.7, Schrittweite η = 0.05

-1 1 2 3 4 5 6x

-2

2

4

6

8

10


)f ′

(x (i)

)∆x (i)

1 1.7 2.134 1.587 0.0792 1.621 1.992 1.996 0.1003 1.521 1.770 2.424 0.1214 1.400 1.452 2.787 0.1395 1.260 1.049 2.948 0.1476 1.113 0.623 2.762 0.1387 0.975 0.276 2.200 0.1108 0.865 0.073 1.448 0.0729 0.792 −0.009 0.791 0.04010 0.753 −0.032 0.375 0.019




Gradientenverfahren – Finite Differenzen Methode

Was tun, wenn die Ableitungen nicht berechnet werden konnen?

Naherungslosung mittels FiniteDifferenzen Methode bestimmen

Vorwarts-FD-Operator

d

d~xf (~x) ≈ f (~x + ∆~x)− f (~x)

∆~x

x x+Dxx

fHxL

fHx+DxL

fHxL

fHxL

f’HxL



. Optimierungsalgorithmen . Zufallsgesteuerte Verfahren 29 / 37

Zufallsgesteuerte Verfahren – Uberblick

Zufallsprozess ist integraler Teil der Strategie

Klassifikation

Rein zufallsgesteuerte Verfahren basieren (fast) ausschließlich aufZufallsprozessen

Rein stochastische Algorithmen(Im Wesentlichen) keine intelligente Algorithmik

Naturanaloge Verfahren nutzen Zufallsprozesse lediglich als Teil desVerfahrens

Iterative, stochastische AlgorithmenBilden in der Natur beobachtbare Konzepte nach




Monte Carlo Verfahren

IdeeWerte die Zielfunktion in n zufallig gewahlten Punkten des Suchraumsaus

Statistische Aussagen uber die erzielbare Gute moglich

ParallelisierbarAber: Erworbenes Wissen uber die Zielfunktion wird nicht weitergenutzt

Exponentielles Wachstum der Anzahl zu uberprufender Punkte umbei steigender Dimension der Zielfunktion den Uberdeckungsgradkonstant zu halten




Zufallsabstieg

IdeeBestimme die Richtung in der die Funktion abnimmt durch Auswertenzufallig gewahlter Punkte aus der Nachbarschaft des aktuellen Punktes

Zufallsabstieg1 Wahle einen zufalligen Startpunkt ~x0 ∈ X2 Wahle zufallig einen Punkt ~x ′

’in der Nahe‘des aktuellen Punktes ~xi

3 Setze

~xi+1 =

{~x ′ falls f (~x ′) ≤ f (~xi )

~xi sonst





Simulated Annealing – Motivation

Inspiriert durch den Ausgluhvorgang in der Metalurgie

Metallstucke werden erhitzt und kontrolliert abgekuhlt um dieKristallgroße zu erhohen und Defekte im Kritsallgitter zu reduzieren

Das Metall wird weicher und lasst sich einfacher bearbeiten

Zu Beginn des Prozesses ist die Systemenergie (d.h. Temperatur)hoch

Die Wahrscheinlichkeit, dass Atome zwischen verschiedenenKristallstrukturen wechseln ist deshalb ebenfalls hochGroßere Anderungen sind moglichDie interne Energie der Atome kann abnehmen oder sogar nochansteigen

Im Verlauf des Prozesses sinkt die Systemenergie

Die Wahrscheinlichkeit, dass Atome zwischen verschiedenenKristallstrukturen wechseln sinkt somit ebenfallsLediglich kleine Anderungen treten auf, insbesondere keine, die dieEnergie der Atome erhohen wurdenDie Zustande niedrigster Energie bleiben bestehen




Simulated Annealing

Idee [Kirkpatrick et al. 1983]

Ubergange von hoheren auf niedrigere Minima sollen wahrscheinlichersein als umgekehrt

Verbesserung desGrandientenvertahrens in demSinn, dass lokale Optimauberwunden werden konnen

f(x)

x




Simulated Annealing – Prinzipien

Aktuelle Losung wird zufallig variiert

Bessere Losungen werden stets ubernommen

Auch schlechtere Losungen konnen mit einer gewissenWahrscheinlichkeit ubernommen werden

Diese Wahrscheinlichkeit sinkt mit

Steigendem Qualitatsnachteil der neuen LosungenSinkender

’Systemtemperatur‘uber die Zeit




Simulated Annealing – Algorithmus

Simulated Annealing1 Wahle einen zufalligen Startpunkt ~x0 ∈ X2 Wahle zufallig einen Punkt ~x ′

’in der Nahe‘des aktuellen Punktes ~xi

3 Setze

~xi+1 =

~x ′ falls f (~x ′) ≤ f (~xi ), sonst

~x ′ mit Wahrscheinlichkeit p = e−∆fkT ,

~xi mit Wahrscheinlichkeit 1− p,wobei∆f = f (~x ′)− f (~xi ) die Qualitatsverringerung der Losung,k = ∆fmax die (geschatzte) maximale Differenz

der Funktionswerte undT den Temperaturparmeter bezeichnen.




. Optimierungsalgorithmen . Enumerative Verfahren 36 / 37

Enumerative Verfahren – Uberblick

Allgemein

Die Zielfunktion wird in allen Punkten des Suchraums ausgewertet

Das Optimum wird garantiert gefunden, da der Suchraumvollstandig uberpruft wird

Branch-and-Bound

Entscheidungsbaum-Verfahren

Operationen:

Branch Zerlege das Problem in TeilproblemeBound Finde Schranken fur die Teilprobleme

Ziel: Identifiziere suboptimale Teilbaume, die nicht weiter betrachtetwerden mussen

Nachteile

Nur fur diskrete Suchraume anwendbar

Die Große behandelbarer Probleme ist beschrankt



. Optimierungsalgorithmen . Zusammenfassung 37 / 37

Zusammenfassung der vorgestellten Optimierverfahren

Die meisten der vorgestellten Verfahren suchen im wesentlichen lokal

Zu einem Zeitpunkt wird nur ein Losungskandidat betrachtetLosungskandidaten werden nur leicht variiert, d.h. Anderungenbleiben lokal

Problem: Es wird ggf. nur ein kleiner Teil des Suchraums untersucht

Mogliche Losung: Mehrmaliges Starten des Algorithmus ausverschiedenen StartpunktenAber: Zwischen den einzelnen Laufen findet keineInformationsubertragung stattMogliche Losung: Große Variation der Losungskandidaten bis zumExtremfall der volligen NeuberechnungAber: Zwischen den einzelnen Losungskandidaten findet zu wenig /keine Informationsubertragung statt (Vgl. Monte-Carlo-Methode)

Hieraus folgt

Werte bereits erarbeitetes Wissen aus, d.h. Losungskandidatenmussen im Zusammenhang stehenUberdecke den Suchraum moglichst groß


Documents

Gliederung Analytische L¨osung 3 / 37 Analytische L¨osung ...pi.informatik.uni-siegen.de/Mitarbeiter/berlik/lehre/ws0607/ci/ci3.pdf · Ein n-Simplex ist ein durch seine n +1 Eckpunkte