OPTIMALIZAČNÍ ÚLOHY Problém optimalizace v různých oblastech: - minimalizace času, materiálu, … - maximalizace výkonu, zisku, … - optimalizace umístění komponent, propojení, ...
Modelový příklad problém obchodního cestujícího: - Je dána mapa obsahující N měst. - Města jsou spojena silnicí o známé délce. - Pro každá dvě města existuje alespoň jedna cesta po silnici, která je spojuje; těchto cest může být více. ÚKOL: Najděte co nejkratší uzavřenou cestu procházející alespoň jednou každým městem.
OPTIMALIZAČNÍ ÚLOHY –pokrač. • další příklady: -
-
navrhnout optimální řešení plošného spoje při znalosti rozměrů součástek, rozmístění vývodů, schématu jejich propojení a různých omezení při rozmísťování; nalezení základního stavu (stavu s minimální energií) pro systém s komplikovaným Hamiltoniánem, např. pro spinové sklo; problém rozvrhu - Je třeba optimálně navrhnout využití učeben, času pedagogů a žáků na nějaké velké škole. …
• optimalizační problém je obecně obtížný - pro složitější systém je těžké nebo prakticky nemožné najít absolutně nejlepší řešení (globální minimum); - pro “lineární problém“ v principu existuje řešení, ale výpočetní čas může být “astronomický“.
OPTIMALIZAČNÍ ÚLOHY –pokrač. • V praxi nemusíme znát absolutně nejlepší řešení. Uspokojí nás dobré řešení získané pomocí aproximace. Jednou z možných metod je metoda Simulated Annealing (SA) – řízené ochlazování
• Řešení hledáme na základě analogie se statistickou fyzikou tzv. simulované žíhání: - Ústředním momentem je zavedení funkce nákladů (tzv. Cost function). - Funkci, kterou chceme minimalizovat ztotožníme s potenciálem a zavedeme teplotu T jako řídící parametr. - Měníme konfigurace a postupně snižujeme teplotu. S. Kirkpatrick et all. Science 1983 Vol. 220 no. 4598 pp. 671-680
ALGORITMUS 1) Nastavíme počáteční teplotu T 2) Změníme konfiguraci C -> C’ 3) Spočteme změnu nákladové funkce U DU=U(C’ ) - U(C) 4) Změnu konfigurace přijmeme podle Metropolisova pravidla
WC C '
exp D U / T 1
DU 0 pro DU 0
5) Po NT krocích snížíme teplotu T a pokračujeme bodem 2)
OPTIMALIZAČNÍ ÚLOHY –pokrač. Lze ukázat, že k cíli vždy vede logaritmické ochlazování
Tk
T0 log k
Výhody SA - Lze řešit problémy s libovolnými systémy a libovolnou funkcí
nákladů. - Nalezení optimálního řešení je statisticky zaručeno. - I pro složité problémy je programový algoritmus velmi jednoduchý.
Nevýhody SA - Ochlazování typu 1/log k, které zaručuje statistické nalezení řešení, je velmi pomalé. - Je-li funkce nákladů jednoduchá, hladká a má jen několik minim, jsou jiné metody výrazně rychlejší. - Nikdy si nemůžeme být zcela jisti, zda jsme již skutečně nalezli optimální řešení a je-li možné již výpočet ukončit.
DALŠÍ MOŽNÉ PŘÍKLADY K ŘEŠENÍ • Další varianty obchodního cestujícího: - když více cest mezi dvěmi městy není dopředu jasné, která je nejkratší; - cesta má začínat a končit v různých daných městech; - každé město se smí navštívit jen jednou; - etc. • Další příklad optimalizačního problému: minimalizovat počet disket (CD) pro uložení daného počtu souborů o daných velikostech.
• atd.
Problém obchodního cestujícího popis úlohy k řešení - Je dána mapa obsahující N měst. - Města jsou spojena silnicí o známé délce. - Pro každá dvě města existuje alespoň jedna cesta po silnici, která je spojuje; těchto cest může být více. ÚKOL: Najděte co nejkratší uzavřenou cestu procházející alespoň jednou každým městem. 1. "Konfigurace" je posloupnost N měst, "energie"
je délka trasy. 2. Jako počáteční "konfiguraci" zvolte N-tici (1, 2, ..., N). 3. Simulujte za snižující se "teploty".
Problém obchodního cestujícího ALGORITMUS V každém kroku se v konfiguraci výmění 2 náhodně vybraná města. Pokud se tím celková délka cesty sníží, je nová konfigurace přijata. Pokud je delší, konfigurace se přijme s pravděpodobností
exp(-dx/T).
Složením transpozic lze získat libovolnou permutaci, je tedy možné dojít k libovolné konfiguraci měst.
Příklad řešení – M. Setvín konfigurace měst
8.000 7.000 6.000 5.000 4.000 3.000 2.000 1.000 0.000 0.000
2.000
4.000
ochlazování
6.000
8.000
10.000
temperature 12 10 temperature
8 6 4 2 0 0
5
10
15
20
25
30
35
Příklad řešení – M. Setvín 8.000
8.000
7.000
7.000
6.000
6.000
5.000
5.000
4.000
4.000
3.000
3.000
2.000
2.000
1.000
1.000
0.000 0.000
2.000
4.000
6.000
8.000
10.000
0.000 0.000
2.000
4.000
a) 8.000
7.000
7.000
6.000
6.000
5.000
5.000
4.000
4.000
3.000
3.000
2.000
2.000
1.000
1.000
2.000
4.000
6.000
c)
8.000
10.000
b)
8.000
0.000 0.000
6.000
8.000
10.000
0.000 0.000
Řada1
2.000
4.000
6.000
d)
8.000
10.000
Příklad řešení – M. Setvín 90
10 měst 1000 kroků v každém cyklu
Total distance
80 70
RUN1
60
RUN2 RUN3
50 40 30 20 10 0 0
50 měst 10000 kroků v každém cyklu
5
10
15
20
25
30
35
500 450 400
RUN1
350
RUN2
300
RUN3
250 200 150 100 50 0 0
5
10
15
20
25
30
35
Příklad řešení – V. Holubec
Algoritmus: V. Cerny, Journal of optimization theory and application, Vol. 45 (1985) p. 41
Ukládání souborů popis úlohy k řešení
N souborů o různých délkách se má uložit na co nejmenší počet disket co nejvýhodnějším způsobem. 1. Navrhněte vhodnou hodnotící funkci („interakční energii“). 2. Navrhněte MC metodu; jeden zkušební krok může být přesun souboru z diskety na disketu. 3. Simulujte za snižující se "teploty".
