Lokální prohledávání Lokální prohledávání (LS) 3 Princip M pracuje s úplnými nekonzistentními přiřazeními proměnných snaží se lokálními opravami snížit počet konfliktů Příklad: umístění n dam na šachovnici iniciální přiřazení umístí každou královnu do každého sloupce a řádku bez ohledu na diagonální omezení přesunujeme královnu v jejím sloupci do jiného řádku tak, abychom odstranili co nejvíce konfliktů 3 LS vyřeší řádově větší problémy než algoritmy založené na prohledávání do hloubkyl 3 Přibližná metoda prohledávání 3 neúplná metoda nezaručuje nalezení (vyloučení existence) řešení i když existuje (neexistuje) 3 malé paměťové nároky Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 2 Lokální prohledávání Terminologie lokálního prohledávání -0 Stav 0: ohodnocení všech proměnných M Evaluace E: hodnota objektivní funkce (počet nesplněných podmínek=počet konfliktů) M Globální optimum: stav s nejlepší evaluací M Lokální změna: změna hodnoty (jedné) proměnné & Okolí o: množina stavů lišící se od daného stavu o jednu lokální změnu Lokální optimum: stav, v jehož okolí jsou stavy s horší evaluací; není globálním optimuml M Striktní lokální optimum: stav, v jehož okolí jsou pouze stavy s horší evaluací; není globálním optimum M Ne-striktní lokální optimum: stav, v jehož okolí exisují stavy se stejnou evaluací; není globálním optimum M Plateau: množina stavů se stejnou evaluací minimum Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 3 Lokální prohledávání Algoritmus lokálního prohledávání Algoritmy lokálního prohledávání mají společnou kostru proceduře LS(MaxPokusu,MaxZmen) parametry algoritmu 6 : = náhodné ohodnoceni proměnných for i := 1 to MaxPokusu while GPodminka do for j := 1 to MaxZmen while LPodminka do if E(0)=O then return 0 vyber ô e o(0) if akceptovatelne(č) then 6 := ô 6 := novyStav(fl) return nejlepši 6i M Jak stanovit MaxPokusu, MaxZmen? 3 pokračovat dokud existuje přiřazení s lepší evaluací M restart (MaxPokusu>l) v některých případech diskutabilní Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 4 Lokální prohledávání Metoda největšího stoupání (hill climbing) HC Začíná v náhodně vybraném stavu Hledá vždy nejlepší stav v okolí Okolí = hodnota libovolné proměnné je změněna, velikost okolí n x (d - 1) Útěk ze striktního lokálního minima pomocí restartu proceduře HC(MaxZmen) restart: 0 : = náhodné ohodnoceni proměnných for j := 1 to MaxZmen do if E(0) = 0 then return 0 if 0 je striktní lokální optimum then goto restart else 0 := stav z o{0) s nejlepší evaluaci goto restart end HC Hana Rudová, Omezující podmínky, 25. listopadu 2019 5 Lokální prohledávání Metoda minimalizace konfliktu (MC) M Okolí u HC je poměrně velké: n x {d - 1) ale pouze změna konfliktní proměnné může přinést zlepšení M konfliktní proměnná = vystupuje v některých nesplněných podmínkách MC mění pouze konfliktní proměnné * okolí = hodnota zvolené proměnné je změněna, velikost okolí d - 1 proceduře MC(MaxZmen) 6 : = náhodné ohodnoceni proměnných PocetZmen := 0 while E(0) > 0 a PocetZmen 0 a PocetZmen (1 - p) 0.02 < p < 0.1 vyber náhodně hodnotu a pro V else vyber hodnotu a, která minimalizuje počet konfliktů pro V if a^současná hodnota V then při řad' a do V PocetZmen := PocetZmen+1 return 0 Hana Rudová, Omezující podmínky, 25. listopadu 2019 8 Lokální prohledávání Největší stoupání s náhodnou procházkou procedure HCRW(MaxZmen, p) Rozdíly od MCRW 6 : = náhodné ohodnoceni proměnných PocetZmen := 0 while E(0) > 0 a PocetZmen s nejlepší evaluací if a^současná hodnota V then pri rad' a do V PocetZmen := PocetZmen+1 return 0 Hana Rudová, Omezující podmínky, 25. listopadu 2019 9 Lokální prohledávání Tabu seznam Setrvání v lokálním optimu je speciálním případem cyklu Jak se obecně zbavit cyklů? stačí si pamatovat předchozí stavy a zakázat opakování stavu paměťově příliš náročné (mnoho stavů) můžeme si zapamatovat pouze několik posledních stavů (zabrání krátkým cyklům)l Tabu seznam = seznam tabu (zakázaných) stavů I M stav lze popsat význačným atributem (není nutné uchovávat celý stav) M (proměnná,hodnota): zachycuje změnu stavu (uložíme původní hodnoty) tabu seznam má fixní délku {tabu tenure) „staré" stavy ze seznamu vypadávají s přicházejímími novými stavyl Aspirační kritérium = odtabuizovaní stavu 3 do stavu lze přejít, i když je v tabu seznamu (např. krok vede k celkově lepšímu stavu)l 3 Tabu seznam je používán samostatně i v kombinaci s jinými metodami LS Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 10 Lokální prohledávání Algoritmus prohledávání s tabu seznamem M Tabu seznam zabraňuje krátkemu cyklení Povoleny jsou pouze tahy mimo tabu seznam a tahy splňující aspirační kritérium M Tabu seznam (TS) v kombinaci s metodou stoupání (HC): proceduře TSHC(MaxZmen) 6 : = náhodné ohodnoceni proměnných I PocetZmen := 0 while E(0) > 0 a PocetZmen do tabu seznamu, kde c je současná hodnota V smaž nejstarši položku v tabu seznamu při řad' a do V PocetZmen := PocetZmen+1 return 0 Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 11 Lokální prohledávání Výběr souseda: přehled 3 Metoda stoupání (HC) soused s nejlepší evaluací vybrán Tabu prohledávání (TS+HC) «• soused s nejlepší evaluací vybrán (metoda stoupání) sousedé z tabu seznamu nemohou být vybránil M Minimální konflikt (MC) soused je omezen na náhodně vybranou konfliktní proměnnou ' výběr její hodnoty s nejlepší evaluací 3 Náhodná procházka (RW) soused vybrán náhodně 3 Min. konflikt (metoda stoupání) s náhodnou procházkou MC+RW (HC+RW) s malou pravděpodobností: náhodný výběr souseda M jinak: minimální konflikt (metoda stoupání) Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 12 Lokální prohledávání Simulované žíhání (simulated annealing) SA 3 Myšlenka: simulace procesu ochlazování kovů na začátku při vyšší teplotě atomy více kmitají a pravděpodobnost změny krystalické mřížky je vyšší 3 postupným ochlazováním se atomy usazují co „nejlepší polohy" s nejmenší energií a pravděpodobnost změny je menší => na začátku je tedy pravděpodobnost toho, že akceptujeme zhoršování řešení, vyšší I Akceptování nového stavu vždy při zlepšení při zhoršení pouze za dané pravděpodobnosti, která klesá se snížením teploty Cykly algoritmu «• vnější: simulace procesu ochlazování snižováním teploty T čím nižší bude teplota, tím nižší bude pravděpodobnost akceptování zhoršení M vnitřní: počítáme, kolikrát jsme neakceptovali zhoršení (dán limit Maxlter) Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 13 Lokální prohledávání Metropolisovo kritérium Rozdíl mezi kvalitou nového (5) a existujícího (9) řešení M AE = E(5)-E(0) & E (chybovost) musí být minimalizováno Metropolisovo kritérium I 3 lepší (někdy případně i stejně kvalitní) řešení akceptováno: AE > 0 horší řešení (AE > 0) akceptováno pokud U < e~AE/T U náhodné číslo z intervalu (0,1)1 • pomůcka: porovnej e-10/100 vs. e-100/100,a e-10/100 vs. e-10/l Hana Rudová, Omezující podmínky, 25. listopadu 2019 14 Lokální prohledávání Algoritmus simulovaného žíhání procedure SA( TInit, TEnd, Maxlter ) 6 : = náhodné ohodnoceni proměnných a := 6 (dosud nejlepší nalezené přiřazeni) for T := TInit to TEnd PocetChyb := 0 while PocetChyb < Maxlter vyber lokálni změnu z 0 do ô if E (ô) CSP nad disjunkcemi boolean proměnných M SAT je NP-úplnýl 1 LS řeší poměrně velké formule formulace LS je velice přirozená a jeho použití je velice populární M lokální změna je překlápěním (flipping) hodnoty proměnné Algoritmus GSAT (greedy SAT) M postupné překlápění proměnných 3 evaluace udává, jaký je (vážený) počet nesplněných klauzulí Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 16 Lokální prohledávání Algoritmus GSAT proceduře GSAT(A,MaxPokusu,MaxZmen) (A je CNF formule) for i := 1 to MaxPokusu do 0 : = náhodné ohodnoceni proměnných for j := 1 to MaxZmen do i f A je splnitelná pomoci 0 then return 0 V := proměnná, jejíž změna hodnoty nejvíce sníží počet nesplněných klauzuli 0 := přiřazeni, které se liši od 0 změnou hodnoty V return nejlepši 0i M Příklad: {-.C, -A v v C, -AvDvf, v --C} 3 iniciální přiřazení (všechny proměnné mají hodnotu 1) nesplňuje první a poslední klauzuli změna A,D,E nemá vliv na počet nesplněných klauzulí změna C na 0 splní první i poslední klauzuli ale nesplní —>A v ~*B v C (evaluace=l) 3 změna B má evaluaci 1 také, pokud ale změníme C a pak B, pak dostáváme evaluaci 0 Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 17 Lokální prohledávání Heuristiky pro GSAT GSAT lze kombinovat s různými heuristikami, které zvyšují jeho efektivitu M obzvláště při řešení strukturovaných problémů Použití náhodné procházky spolu s minimalizací konfliktů Vážení klauzulí * některé klauzule zůstávají po řadu iterací nesplněné, klauzule tedy mají různou důležitost splnění „těžké" klauzule lze preferovat přidáním váhy 3 váhu může systém odvodit ±> na začátku mají všechny klauzule stejnou váhu ±> po každém pokusu zvyšujeme váhu u nesplněných klauzulí 3 Průměrování řešení M standardně každý pokus začíná z náhodného řešení 3 společné části předchozích řešení lze zachovat ±> restartovací stav se vypočte ze dvou posledních výsledků bitovým srovnáním stejné bity zachovány, ostatní nastaveny náhodně Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 18 Lokální prohledávání Hybridní prohledávání 3 Příklady kombinace lokálního prohledávání prohledává úplná nekonzistentní přiřazení a stromového prohledávání * rozšiřuje částečné konzistentní přiřazeni 1. Lokální prohledávání před nebo po stromovém prohledávání např: M před: lokální prohledávání nám poskytne heuristiku na uspořádání hodnot I M po: lokálním prohledáváním se snažíme lokálně vylepšit spočítané řešení (optimalizace) 2. Stromové prohledávání je doplněno lokálním prohledávání v listech prohledávacího stromu i v jeho uzlech např. lokální prohledávání pro výběr hodnoty nebo vylepšení spočítaného řešení 3. Lokální prohledávání je doplněno stromovým prohledáváním pro výběr souseda z okolí a nebo pro prořezávání stavového prostoru Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 19 Lokální prohledávání Iterativní dopředně prohledávání 3 Iterative Forward Search (IFS) 3 Hybridní prohledávání: konstruktivní nesystematický algoritmus pracuje nad modelem s pevnými a měkkými omezujícími podmínkami M pevné podmínky: musí být splněny M měkké podmínky: reprezentují účelové funkce, jejichž vážený součet je minimalizován Pracuje s konzistentními přiřazeními Základní myšlenky (blízký dynamickému backtrackingu) ' začíná s prázdným přiřazením M vybere novou proměnnou k přiřazení M pokud nalezne konflikt, zruší přiřazení všech proměnných v konfliktu s vybranou proměnnou 3 výběr hodnot pomocí konfliktní statistiky výběr proměnných není pro algoritmus kritický, protože lze proměnné přiřadit opakovaně Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 20 Lokální prohledávání Iterative Forward Search Algorithm A (partial) feasible solution ■ Unassigned variables Hana Rudová, Omezující podmínky, 25. listopadu 2019 21 Lokální prohledávání Iterative Forward Search Algorithm A (partial) feasible solution < m £- o ■ Unassigned variables Hana Rudová, Omezující podmínky, 25. listopadu 2019 22 Lokální prohledávání Iterative Forward Search Algorithm A (partial) feasible solution Select a value < m £- o □ 1? 1? U 1? T Unassigned variables Hana Rudová, Omezující podmínky, 25. listopadu 2019 23 Lokální prohledávání Iterative Forward Search Algorithm A (partial) feasible solution Select a value < m £- o ■ Some variables can be unassigned Unassigned variables Hana Rudová, Omezující podmínky, 25. listopadu 2019 24 Lokální prohledávání IFS: algoritmus procedure IFS() iteration = 0; % čítač iterací current = 0; % aktuální řešení best = 0; % nejlepší řešení while canContinue (current, iteration) do iteration = iteration + 1; variable = selectVariable (current); value = selectValue (current, variable); unassign(current, conflictingVariables(current, variable, value)); assign(current, variable, value); if better (current, best) then best = current return best end IFS procedure conflictingVariables: kontroluje konzistenci tak, aby byla splněna omezení na přiřazených proměnných, a vrací konfliktní proměnné unassign: odstraní přiřazení konfliktních proměnných Hana Rudová, Omezující podmínky, 25. listopadu 2019 25 Lokální prohledávání IFS: konfliktní statistika Předpoklad: při výběru hodnoty a proměnné A je nutné zrušit přiřazení hodnoty b proměnné B, tj. [A = a — -> B = b] V průběhu výpočtu si tedy lze pamatovat: A = a => 3x^B = b, 4x^B = c, 1 x ^ C = a, 120 x ^ D = al Při výběru hodnoty vybíráme hodnoty s nejnižším počtem konfliktů vážených jejich frekvencí I konflikt započítáme pouze tehdy, pokud to vede k odstranění přiřazení J př. A = a => 3x^B = b, 4x^B = c, 1 x ^ C = a, 120 x^D = a A = b => lx^ B = a, 3x^ B = b, 2 x ^ C = a Máme přiřazení B = c,C = a,D = b a vybíráme hodnotu pro A: nechť AIa vede ke konfliktu s BI c: lyhodnoceno jako 4 • není konflikt s C/a, tak se nezapočítává ±* nechť Alb vede ke konfliktu s C/a: lyhodnoceno jako 2 -i* tj. vybereme hodnotu b pro proměnnou A Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 26 Lokální prohledávání