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 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*, 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 a je dobré mít přečtené informované prohledávání, protože se tu na kontrast s ním pořád odkazuje. Navazují na to genetické 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 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.

Kdy použít co

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 - local beam search s křížením, čili co se stane, když se stavy smějí míchat
• Informované prohledávání - druhá polovina světa, kde cesta rozhoduje
• MLP a backpropagation - gradientní sestup je hill climbing na spojité funkci, i s lokálními minimy
• Shlukování - k-means je lokální prohledávání, které o tom neví