Simulované žíhání jako nástroj k hledání optimálního řešení

Simulované žíhání jako nástroj k hledání optimálního řešení Michael Pokorný - Střední škola aplikované kybernetiky s.r.o. [email protected]

21. června 2011

Michael Pokorný - Střední škola aplikované kybernetiky s.r.o. - [email protected] Simulované žíhání jako nástroj k hledání optimálního řešení

Úvod

I

Nedeterministická metoda optimalizace

I

Scott Krikpatrick, C. Daniel Gelatt, Mario P. Vecchi 1983, Vlado Černý 1985 Intuice: postupné chlazení kovu

I

I I I

I

Vznikají velké a pravidelné krystaly bez nepravidelností Molekuly hledají minimum vnitřní energie Zahřátí umožňuje uvolnění z lokálního minima

Užitečné na velký stavový prostor bez nutnosti zcela ideálního řešení nebo na černé skříňky


Popis

I

Molekula −→ stav, energie −→ ohodnocení stavu, teplota se „přimyslí”

I

Stav fluktuuje podle velikosti teploty a podle toho, jestli jde „do kopce” nebo „z kopce”

I

Stav ∈ R, Z, RN , ...


Algoritmus Vstup: T0 (počáteční teplota), x~0 (počáteční stav) T ← T0 , ~x ← x~0 , k ← 0 opakuj x~n ← stav z okolí ~x x~n ) ) p ← g( f(~x )−f( T ~x ← x~n s pravděpodobností p k ←k +1 T ← h(T0 , k) dokud k < kmax ;


Charakteristické funkce I

I

Skoková funkce g a ochlazovací funkce h charakterizují optimalizaci Obvyklé kombinace: I

I I

„Klasická”: g1 (x) =

exp(x) 1

x<0 , x≥0

h1 (T0 , k) = T0 · Qk−1 „Moderní”: g2 (x) = (1 + exp(−x))−1 , h2 (T0 , k) = log T(K0 +2) 2 x FSA (fast simulated annealing): g3 (x) = 12 + arctan , π h3 (T0 , k) = 1+T0K + Cauchyho rozdělení vzdálenosti nového N0

stavu v závislosti na teplotě −→ rychlé a přesné


1D funkce 1

0.8

0.6

0.4

f(x)

0.2

0

-0.2

-0.4

-0.6

-0.8 0

5

10 x

15

20

Minimalizace f(x) = exp( −x 10 ) · cos(x) na intervalu h0; 20i Michael Pokorný - Střední škola aplikované kybernetiky s.r.o. - [email protected] Simulované žíhání jako nástroj k hledání optimálního řešení

Výsledky - 1D funkce 20 Stav Energie Teplota 15

10

5

0

-5 0 100 200 300 400 500 Krok- [email protected] Michael Pokorný - Střední škola aplikované kybernetiky s.r.o.

Simulované žíhání jako nástroj k hledání optimálního řešení

600

Výsledky - 1D funkce 20 18

Stav Energie Teplota

16 14 12 10 8 6 4 2 0 -2 0 500 1000 1500 2000 2500 Krok- [email protected] Michael Pokorný - Střední škola aplikované kybernetiky s.r.o.


3000

Výsledky - 1D funkce - FSA 18 16

Stav Energie Teplota

14 12 10 8 6 4 2 0 -2 0 5 10 15 20 25 30 35 40 Krok- [email protected] Michael Pokorný - Střední škola aplikované kybernetiky s.r.o.


45

50

Rosenbrockova funkce 2.5

6000 f(x,y)

2

5000

1.5 4000 1 y

3000 0.5 2000 0 1000

-0.5 -1 -2.5

0 -2

-1.5

-1

-0.5

0

0.5

1

1.5

2

x

R(x, y ) = (1 − x)2 + 100(y − x 2 )2 Michael Pokorný - Střední škola aplikované kybernetiky s.r.o. - [email protected] Simulované žíhání jako nástroj k hledání optimálního řešení

Himmelblauova funkce 4

350

3

300

2

250

1 y

200 0 150 -1 100

-2

50

-3 f(x,y) -4

0 -4

-3

-2

-1

0 x

1

2

3

4

H(x, y ) = (x 2 + y − 11)2 + (x + y 2 − 7)2 Michael Pokorný - Střední škola aplikované kybernetiky s.r.o. - [email protected] Simulované žíhání jako nástroj k hledání optimálního řešení

Problém batohu I

I I

0-1 knapsack problem: různé předměty s různou hmotností, každý s jinou hodnotou. Batoh má omezenou hmotnost. Jak vypadá nejhodnotnější batoh? NP-complete, ale lze rozumně řešit žíháním Stav je věcí v batohu, energie je −(cenav cvbatohu) 80

70

60

y

50

40

30

20

10

0 0

1000

2000

3000

4000

5000 x

6000

7000

8000

9000

10000


Shrnutí

I

Simulované žíhání je rychlé a funkce může být černá skříňka

I

FSA je ještě rychlejší a lepší


Poděkování

Děkuji doc. Ing. Jaromíru Kukalovi, Ph.D. za inspirující odborné vedení miniprojektu a Ing. Vojtěchu Svobodovi, CSc. za organizaci Fyzikálního týdne vědy na Jaderce 2011.


Simulované žíhání jako nástroj k hledání optimálního řešení

Recommend Documents