• ©Jan Schmidt 2011 Katedra číslicového návrhu Fakulta informačních technologií České vysoké učení technické v Praze • Zimní semestr 2011/12 EVROPSKÝ SOCIÁLNÍ FOND PRAHA & EU: INVESTUJENE DO VAŠÍ BUDOUCNOSTI
MI-PAA
7. Heuristické metody • Co očekáváme od praktických heuristik? • Lokální a globální přístup • Najít vůbec nějaké řešení a najít lepší – konstruktivní a iterativní fáze • Jednoduché heuristiky pouze nejlepší a prvé zlepšení • Problém s lokálními extrémy a co s ním • Prohledávání s návratem
Co očekáváme od heuristických metod • Použitelnost v praxi: – na praktických instancích – s přijatelnou přesností – s přijatelným výpočetním časem
na praktických instancích
• Omezení a optimalizace: – nejlepší čas pro potřebnou přesnost – nejlepší přesnost v časovém limitu
• Přesnost: – přibližné řešení – přesné řešení
výpočty v reálném čase důkazy správnosti
2
• metafora stavového prostoru • pojem aktuálního stavu
použití
iterativní konstruktivní
lokální metody heuristické metody globální metody • dekompozice instance na menší instance téhož problému
překonání lokálního minima
3
lokální metody
uváznou
překonání lokálního minima
jednoduché vycouvají s návratem
překonají pokročilé 4
Lokální metody Stavový prostor a okolí stavu Systematické a úplné metody Praktické aplikace: neúplné metody
5
Stavový prostor instance problému batohu řešené hladovým algoritmem 100
110 101
111
001
011
000 triviální v každém kroku je právě jedna konfigurace aktuální
010
přidej věc 1 přidej věc 2 přidej věc63
Lokální metody 100
000 aktuální stav
110 101
111
001
011
okolí aktuálního stavu
010
přidej věc 1 přidej věc 2 přidej věc73
Okolí stavu, sousední stav kam se dostanu jedním krokem • Definice: okolí stavu s S je množina stavů, dosažitelných z s aplikací některé operace q Q. kam se dostanu nejvýše k kroky • Definice: k-okolí stavu s S je množina stavů, dosažitelných z s aplikací nejméně jedné a nejvýše k operací q Q.
• Definice: stavy z okolí stavu s S se nazývají sousední stavy (sousedé) stavu s.
8
Lokální metoda • má vždy jeden aktuální stav • uvažuje sousední stavy z (relativně malého) okolí
9
{počáteční stav} Ø closed Ø best
open
nejlepší nejdříve do hloubky do šířky
open.empty() ne
ano
aktuální stav
state open.get() state closed? ano
okolí aktuálního stavu
ne
state.solution() and state.better (best) ne
lokální metoda
ano
state best
best= Ø? q open.put (q (state)) closed.put (state)
ano
řešení neexistuje
ne
řešení je best
10
Praktické metody • Úplné a systematické metody uschovají každý stav z okolí pro pozdější zkoumání – proto jsou exaktní – proto mohou mít nadpolynomiální složitost
• Když vybereme (nějak) z každého okolí jen jeden stav – strategie je neúplná, nelze zaručit řešení – můžeme najít řešení v přijatelném čase – nepotřebujeme strukturu open – má vždy jen jeden prvek – strukturu closed si většinou nemůžeme dovolit, musíme se spolehnout na vlastnosti stavového prostoru nebo řízení algoritmu 11
{počáteční stav} state Ø best
Typická struktura jednoduché lokální heuristiky
state = Ø? ne
ano
funkce try () nedokáže najít další stav
stop ()? ne
ano
jiný důvod (čas …)
state.solution() and state.better (best) ne
zkus najít další stav
ano
state best
best= Ø? ano
state
try (state)
řešení neexistuje nebo je neznáme
ne
řešení je best 12
Příklad • Dvě jednoduché heuristiky • Konstruktivní a iterativní fáze • Dá se to doopravdy použít ...
13
Problém diskrétního rozmístění • Dáno: – množina n modulů K={k1, …,kn} – množina m pozic P={p1, …,pm}, m ≥ n – propojení modulů jako hypergraf G (K, N), kde N je množina spojů n – cenová funkce W (R, n), která pro každé přiřazení R: K P odhadne cenu realizace spoje n.
• Nalézt: – prosté přiřazení R: K P (rozmístění), které minimalizuje součet ohodnocení W (R, n) přes všechny spoje. 14
Algoritmus max konjunkce min disjunkce • Nechť H (G, k1, k2) je heuristická funkce, která na základě grafu G odhadne stupeň vazby modulů k1 a k2. • Nechť K+(R) označuje množinu modulů, které jsou právě rozmístěny (mají dvojici v R), K-(R) množinu právě nerozmístěných modulů. • Obdobně definujeme množinu obsazených pozic P+(R) a volných pozic P-(R). • R (ki, pj), buď ze zadání nebo pomocnou heuristikou.
15
Algoritmus max konjunkce min disjunkce 1. Vyber modul k K-(R) takový, že H(G,k,l)=max. l K+(R)
max. přidrátovaný k rozmístěným modulům
2. Je-li jich více, vyber z nich modul k takový, že H(G,k,l)=min. l K-(R)
3. Najdi pozici p P-(R) takovou, že W(R (k,p), n)=min. n
min. přidrátovaný k nerozmístěným modulům pozice pro nejlevnější dráty
kde suma je přes všechny spoje incidentní s k. 4. R R (k,p) 5. Opakuj 1., dokud K-(R) není prázdná.
16
Okolí • Krok: dáme nerozmístěný prvek na volnou pozici. • Vezmeme K-(R), najdeme nejlepší prvek podle heuristické funkce. • Vezmeme P-(R), najdeme nejlepší prvek podle optimalizačního kritéria.
• „Šidíme“ tak hledání nejlepšího prvku (k,p) K-(R) P-(R) (nepotřebovali bychom heuristickou funkci!). Stavový prostor je acyklický. Algoritmus se zastaví po n krocích. 17
Konstruktivní heuristika • Začali jsme ze (skoro) triviální konfigurace • Dopracovali jsme se k řešení (konfiguraci, která vyhovuje omezením – zde prosté zobrazení R) •
konstruktivní heuristika
18
Iterativní zlepšování 1.
2. 3.
Najít pozice p1 a p2 takové, že vzájemným prohozením jejich „obsahu“ (modul nebo nic) se nejvíce zlepší hodnota optimalizačního kritéria. Není taková stop. Provést záměnu, opakovat 1.
Stavový prostor je acyklický (nemohu provést záměnu, která by nezlepšila optimalizační kritérium – nemohu se vrátit)
19
Okolí • Vezmu P P, najdeme nejlepší prvek podle optimalizačního kritéria • Můžeme to „šidit“: – najdeme pozici p1, která „toho má nejvíc zapotřebí“ (heuristická funkce) – najdeme pozici p2, kde je zlepšení největší
• Jiná možnost: hledáme v P P, ale spokojíme se s první záměnou, která zlepší optimalizační kritérium 20
Iterativní heuristika • Začali jsme z řešení • Dopracovali jsme se k lepšímu řešení • iterativní heuristika
Dvojfázové heuristiky • Prvá fáze – konstruktivní – náhodná, více náhodných řešení (viz GSAT minule)
• Druhá fáze iterativní 21
Jednoduché heuristiky Pouze nejlepší Prvé zlepšení Okolí heuristik Kernighan-Lin 22
{počáteční stav} state Ø best
Čím se mohou lišit jednoduché lokální heuristiky
state = Ø? ne
ano
• stavovým prostorem • okolím • výběrem z okolí • zastavením
stop ()? ne
ano
state.solution() and state.better (best) ne
ano
state best
best= Ø? ano
state
try (state)
řešení neexistuje nebo je neznáme
ne
řešení je best 23
Pouze nejlepší (best only) try (state) Ø
candidate
q new = q (state))
return candidate
new.solution() and new.better (state) and new.better (candidate) ne
ano
new candidate 24
Metoda pouze nejlepší • celá heuristika se zastaví, jestliže v nějakém stavu neexistuje zlepšující tah • pokud better() používá jiné hodnocení než optimalizační kritérium, solution() může chybět • jiné názvy: metoda nejrychlejšího sestupu/vzestupu, horolezecký algoritmus • na pořadí prohledávání okolí nezáleží
25
Prvé zlepšení (first improvement) try (state)
záleží na pořadí q
new = q (state))
return Ø
randomizace náhodné pořadí
new.solution() and new.better (state) ne
ano
return new 26
Metoda první zlepšení • celá heuristika se zastaví, jestliže v nějakém stavu neexistuje zlepšující tah • pokud better() používá jiné hodnocení než optimalizační kritérium, solution() může chybět • na pořadí prohledávání okolí záleží
27
Návrh heuristiky
mnoho jednoduchých a rychlých iterací
mnoho operací, které nemění konfiguraci drasticky
méně sofistikovaných iterací
méně radikálních („dlouhých“) operací občas
28
Okolí heuristik Kernighan-Lin aplikuj opakovaně danou transformaci až do stop podmínky bez ohledu na optimalizační kritérium nebo heuristickou funkci aktuální stav
„Kernighan-Lin“: řada heuristik původně pro TSP, později hlavně pro bisekci grafu
z takto získaného okolí vyber nejlepší stav jako příští hledání dalšího stavu 29
Problém lokálních extrémů
30
Lokální minimum hodnota optimalizačního kritéria
lokální minimum: všechny sousední stavy mají horší hodnotu optimalizačního kritéria
globální minimum spojovací čáry jen pro názornost
kroky iterativní heuristiky 31
Správný průběh iterativní heuristiky hodnota optimalizačního kritéria různá počáteční řešení
stejně kvalitní výsledná řešení
kroky iterativní heuristiky 32
Uváznutí v lokálních minimech hodnota optimalizačního kritéria
různá počáteční řešení
zastavení v lokálních minimech kvalita výsledného řešení silně závisí na kvalitě počátečního řešení
kroky iterativní heuristiky 33
Problém lokálních extrémů • Heuristiky, které neřeší uváznutí v lokálním extrému (pouze nejlepší, první zlepšení a jim podobné) se zastaví v lokálním minimu • Projev: závislost výsledného řešení na počátečním, tzv. nedostatečná iterační síla • Centrální problém lokálních heuristik
34
Řešení • Zvětšení okolí • Více náhodných počátečních řešení (GSAT) – odstranění následků, ne příčiny – závisí na možnosti generovat náhodná řešení
• Návraty – odvolání rozhodnutí, které vedly do slepé uličky
• Únik – kroky, které připustí zhoršení aktuálního stavu – nutnost dokonalejšího řízení algoritmu (bloudění) – nutnost řízení ochoty k horšímu řešení 35
Zvětšení okolí k-okolí o m transformacích má mk stavů!
Kernighan-Lin (pokud zahrne tyto stavy) 3-okolí
1-okolí
36
Prohledávání s návratem
37
Prostor prohledávání ????? prostor prohledávání
bod prostoru prohledávání
oblast stavového prostoru
stavový prostor
38
Základní prohledávání s návratem (backtracking) • V algoritmech, kde se postupně ohodnocují proměnné, nejčastěji konstruktivní úlohy • Heuristická funkce, udávající pořadí, v jakém mají proměnné být ohodnocovány • Rozpoznání slepé uličky – pro úplné řešení (list prohledávacího stromu) – pro částečně ohodnocenou konfiguraci
• Omezení prohledávacího prostoru
• Není zaručena polynomiální složitost • Tyto techniky se používají i v kombinaci s jinými 39
Problém dam na šachovnici Rozestavit n dam na šachovnici n×n tak, aby se vzájemně neohrožovaly
konflikt
40
Dopředná kontrola (forward checking) Udržovat informaci, která dovolí (snadno, rychle) se vyhýbat konfliktům
41
Zpětné skoky (backjumping) pořadí umisťování dam
je třeba vrátit se až sem, jinak budeme narážet na stejný problém
který darebák jako poslední ucpal políčko v tomto sloupci? 43
