Lokalni-prohledavani.md

# Lokální prohledávání U osmi dam na šachovnici nikoho nezajímá, v jakém pořadí jsi je tam kladl. Zajímá jen výsledné rozestavení. U rozvrhu směn nikoho nezajímá, kterou směnu jsi přesunul první. U [obchodního cestujícího](Geneticke-algoritmy#tsp-obchodní-cestující) je řešením okruh, ne postup, kterým jsi na něj přišel. V takových úlohách je **cesta irelevantní**, a všechno, co dělá [A*](Informovane-prohledavani), je zbytečná práce. Udržovat frontu uzlů, pamatovat si předchůdce, rekonstruovat trasu - nic z toho k ničemu není, když stačí konfigurace. Tahle stránka ukazuje tři metody, které si pamatují **jeden stav** (nebo hrstku) a snaží se ho vylepšit. Předpokládá to [stavový prostor](Stavovy-prostor) a je dobré mít přečtené [informované prohledávání](Informovane-prohledavani), protože se tu na kontrast s ním pořád odkazuje. Navazují na to [genetické algoritmy](Geneticke-algoritmy), které jsou lokálním prohledáváním s populací. ## Hill Climbing Horolezecký algoritmus je nejjednodušší možná metoda a vejde se do tří řádků: 1. Začni v libovolném stavu.2. Opakuj: přesuň se do **nejlepšího sousedního** stavu.3. Pokud žádný soused není lepší než aktuální, zastav. Paměť je **konstantní**. Držíš jeden stav a nic víc. To je proti `O(b^d)` u [BFS](Neinformovane-prohledavani#bfs-nejkratší-cesta-za-cenu-kterou-nezaplatíš) tak zásadní rozdíl, že se lokální metody používají i tam, kde by systematické prohledávání teoreticky šlo. Cenou za to je, že algoritmus **nemá ponětí, kde byl a kam by mohl**. Vidí jen své bezprostřední okolí, a proto ho zastaví první kopec, na který vyleze. ### Tři způsoby, jak uvíznout **Lokální maximum.** Vrchol, ze kterého vedou všechny cesty dolů, ale globální optimum je někde jinde. Algoritmus zastaví a ohlásí úspěch. **Plošina (plateau).** Rovná oblast, kde jsou všichni sousedé stejně dobří. Algoritmus nemá podle čeho vybrat a buď zastaví, nebo se plácá na místě. **Hřeben (ridge).** Úzký hřbet stoupající šikmo. Každý jednotlivý krok podél os vede dolů, přestože ve směru hřebene se dá stoupat dál. Tohle je nejzákeřnější případ, protože vypadá jako lokální maximum a není. ### Co s tím **Random restarts.** Když algoritmus zastaví, začni znovu z náhodného stavu a ponech si nejlepší dosažený výsledek. Je to hrubé, ale funguje překvapivě dobře - u úloh, kde má většina restartů rozumnou šanci na dobré řešení, se optimum najde po pár desítkách pokusů. **Random sideways moves.** Povol kroky do stejně dobrého stavu, čímž se dá projít plošina. Musí se to omezit počtem, jinak se na rovině zacyklíš navěky. **Ani jedno neřeší hřebeny.** Na ty pomůže jedině změna definice sousedství - přidat operátory, které se pohybují ve víc dimenzích naráz. ## Simulované žíhání Žíhání je metalurgický postup: kov se zahřeje a pak **pomalu** chladne, aby se atomy stihly usadit do uspořádané mřížky s nízkou energií. Když ho zchladíš rychle, zamrznou v nepořádku a materiál je křehký. Simulované žíhání ten proces napodobuje. **Povolí občasné zhoršující tahy, a to tím častěji, čím je teplota `T` vyšší.** ```function SIMULATED-ANNEALING(problem, schedule):    current ← problem.initial-state    for t = 1 to ∞ do        T ← schedule(t)        if T = 0 then return current        next ← náhodně vybraný soused stavu current        ΔE ← next.value − current.value        if ΔE > 0 then current ← next        else current ← next s pravděpodobností e^(ΔE/T)``` Rozeber si ten poslední řádek, je v něm celá metoda. Když je `ΔE` **kladné**, tah zlepšuje a přijme se vždycky. Když je **záporné**, přijme se s pravděpodobností `e^(ΔE/T)`. Z toho plynou dvě věci, které stojí za to si uvědomit: **Čím horší tah, tím menší šance.** `ΔE = −1` má výrazně větší pravděpodobnost než `ΔE = −10`. Algoritmus tedy nepřijímá zhoršení naslepo, ale preferuje malá. **Čím nižší teplota, tím menší šance.** Při vysokém `T` je exponent blízko nule a pravděpodobnost blízko jedné - algoritmus bloudí skoro náhodně. Při `T` blížícím se nule se z něj stane obyčejný hill climbing. **Průběh je tedy plynulý přechod od náhodné procházky k horolezectví.** Nejdřív se prostor prozkoumá zhruba, pak se dolaďuje. ### Teoretická záruka a co z ní doopravdy plyne Stacionární rozdělení stavů je Boltzmannovo: `P(x) ∝ e^(E(x)/T)`. Z toho plyne známá věta: **pokud se `T` snižuje dostatečně pomalu, algoritmus konverguje k optimálnímu stavu.** Ta věta je pravdivá a v praxi téměř k ničemu. „Dostatečně pomalu" znamená logaritmický plán chlazení, u kterého by výpočet trval déle než vyčerpávající prohledávání celého prostoru. **V reálu se používá geometrické chlazení** (`T ← 0,95·T` po každém kroku), u kterého žádná záruka neplatí a které funguje dobře. Tohle je typický vztah teorie a praxe v optimalizaci: záruka existuje, aby bylo vidět, že metoda není nesmysl, ne aby se podle ní nastavoval `schedule`. ## Local Beam Search Kompromis mezi jedním stavem a systematickým prohledáváním: - Drž `K` stavů naráz, na začátku náhodných.- V každé iteraci vygeneruj **všechny následníky všech `K` stavů**.- Vyber z celé té množiny `K` nejlepších a zbytek zahoď. Klíčová věta, kterou si zapamatuj: **tohle není totéž jako `K` paralelních běhů hill climbingu.** Jednotlivá prohledávání spolu „komunikují" tím, že se výběr dělá ze společné množiny. Když jedna větev najde slibnou oblast, ostatní se do ní přesunou, protože jejich vlastní následníci se do nejlepší `K`-tice nedostanou. To je zároveň jediná slabina metody. **Všech `K` stavů se rychle sejde na jedné hromádce** a diverzita zmizí - máš pak `K` skoro identických stavů a metoda degeneruje na hill climbing s `K`-násobnými náklady. Řeší se to **stochastickým výběrem** místo prostého „ber nejlepší", což je přesně nápad, ze kterého vyrostly [genetické algoritmy](Geneticke-algoritmy). ## Kdy použít co | Situace | Metoda ||---|---|| Cesta je součástí řešení | **nic z téhle stránky**, jdi na [A*](Informovane-prohledavani) || Rychlý odhad, hladká funkce | hill climbing s restarty || Členitý prostor s mnoha lokálními optimy | simulované žíhání || Vyplatí se paralelismus a máš paměť | local beam search || Řešení jde přirozeně zakódovat a kombinovat | [genetický algoritmus](Geneticke-algoritmy) | ## Kde lokální prohledávání přestává platit **Nedozvíš se, že jsi našel optimum.** Metoda vrátí stav, u kterého jsou všichni sousedé horší. To je jediné, co ti zaručí. Jestli je to globální optimum, nezjistíš nikdy. **Neumí říct „řešení neexistuje".** Na úlohách s tvrdými omezeními (splnitelnost, rozvrh s neřešitelným zadáním) běží donekonečna a nic ti neřekne. **Výsledek závisí na definici sousedství.** Změna operátorů promění celý tvar prostoru - hřeben se může stát svahem a lokální maximum zmizet. Tohle je ta věc, na které se optimalizace ladí nejvíc, a přitom se o ní nejmíň mluví. **Nedeterminismus komplikuje ladění.** Dva běhy nedají totéž. Když měníš parametry, měň **jednu věc naráz** a porovnávej průměr z mnoha běhů, ne jeden výsledek. ## Praktická pravidla **Zafixuj si seed a pak ho zase pusť.** Nejdřív s pevným generátorem, aby se dalo ladit. Pak s náhodným, aby ses nechytil na jednom šťastném běhu. **Hill climbing s restarty zkus vždycky první.** Je to deset řádků a u řady úloh je to všechno, co potřebuješ. Teprve když nestačí, jdi na žíhání. **Chlazení laď na počtu iterací, ne na `T`.** Rozhodni, kolik kroků si můžeš dovolit, a plán nastav tak, aby `T` na konci té doby dorazilo k nule. **Zapamatuj si nejlepší nalezený stav zvlášť.** Žíhání může skončit v horším stavu, než jakým prošlo v polovině. Bez zvláštní proměnné o něj přijdeš. **Když ti to uvízne, sáhni po sousedství, ne po parametrech.** Ladění teploty vytěží pár procent, jiná definice sousedního stavu občas řád. ## Kam dál - **[Genetické algoritmy](Geneticke-algoritmy)** - local beam search s křížením, čili co se stane, když se stavy smějí míchat- **[Informované prohledávání](Informovane-prohledavani)** - druhá polovina světa, kde cesta rozhoduje- **[MLP a backpropagation](MLP-a-backpropagation)** - gradientní sestup je hill climbing na spojité funkci, i s lokálními minimy- **[Shlukování](Shlukovani)** - k-means je lokální prohledávání, které o tom neví