Úvod do algoritmov umelej inteligencie #3 - Simulované žíhanie

Veľmi jednoduché video ukazujúce žíhanie v metalurgii / šperkárstve 👇

Žíhanie v metalurgii môže na seba vziať aj takúto podobu

Pamätáte si, ako sme sa pri HillClimbing a TabuSearch pozerali na všetkých susedov, a vybrali si najlepšieho? Simulované žíhanie robí to isté, ale... Ale s istou pravdepodobnosťou je ochotné akceptovať aj horšie riešenie. Ak sa totiž v správny okamih rozhodneme pre horšie riešenie, môžeme sa neskôr dostať k lepším = vymaniť sa z lokálneho minima/maxima.

Použitie

Predtým ako sa vrhneme na algoritmus sa len krátko zamyslím nad tým, kedy sa simulované žíhanie používa... Je ideálnym kandidátom, ak máme optimalizovať viacero parametrov rovnakého typu naraz (vektory). Klasický príklad je problém obchodného cestujúceho, alebo optimalizácia spotreby paliva na nejakej ceste. Ak si budete chcieť tento algoritmus vyskúšať, opäť odporúčam stránku codingame.com

• Problém obchodného cestujúceho.
• Pristávanie na marse.
• Bot programming - preteky autonómnych vozidiel.
• a ďalšie.

Osobne tento algoritmus používam, keď chcem extrémne rýchlo dosiahnuť aspoň uspokojivé riešenie. Ak chcem, aby bolo riešenie čo najpresnejšie, siahnem po genetických algoritmoch, ktorým sa budeme venovať neskôr.

Algoritmus

Rovnako ako pri ostatných optimalizačných algoritmoch vytvoríme náhodné riešenie. Jeho optimalizácia však bude spočívať v tom, že predom definovaný počet krát (n) znížime teplotu a na základe tejto teploty a vygenerovaného suseda ho môžeme akceptovať alebo odmietnuť. Zjednodušená forma algoritmu by fungovala takto:

1. riesenie =  náhodné riešenie
2. teplota = úvodná teplota
3. n krát
   a. susedne_riesenie = susedné riešenie na základe riesenie
   b. susedne_riesenie je lepšie ako riesenie‍

           i.  true ⇒ riesenie = susedne_riesenie‍

           ii. false ⇒ riesenie = susedne_riesenie ak je teplota dosť vysoká???

      c. zníž teplotu

4. Vráť najlepšie riesenie doteraz nájdené

Kedy je teplota dosť vysoká?

Kedy je však teplota dosť vysoká aby sme susedne_riesenie akceptovali (bod 3b)? Sem prichádza na rad klasický vzorec, ktorý nám pozorovanie žíhania prinieslo. susedne_riesenie akceptujeme s pravdepodobnosťou:

P(∆E)=e^{\frac{-∆E}{t}}

Kde ∆E  je rozdiel skóre susedného riešenia a pôvodného riešenia. Hoci vzorček vyzerá trochu strašidelne, implementácia tejto formulky je v skutočnosti jednoduchá.

fun accept(actual: Solution, neighbor: Solution, temp: Double) : Boolean {
    val diff = neighbor.cost - actual.cost
    if (diff < 0) { return true }
    return random.nextDouble() < exp(-diff / temp)
}

view rawWhen the temperature is high enough.kt hosted with ❤ by GitHub

Ako znížime teplotu?

Teplotu môžeme znížiť rôznymi spôsobmi (bod 3c). Pravdepodobne vás napadne viacero spôsobov, ale radšej si ich napíšme:

1. Lineárne znižovanie teploty: T' = T - α
2. Geometrické znižovanie teploty: T' = T ^. α
3. Pomalé znižovanie teploty: T' = T/(1+βT)

Varianty

Keď som sa venoval tomuto algoritmu, ukázalo sa, že viacero ľudí si jeho použitie predstavuje inak. V podstate existujú 2 hlavné prúdy:

1. Suseda získame malou zmenou a s istou pravdepodobnosťou ho akceptujeme.
2. Čím je väčšia teplota, tým výraznejšie zmeny môžeme robiť v susedovi.

Ďalej sa algoritmus vie rôzniť napríklad v tom kedy meníme teplotu. Niekto mení teplotu v každej iterácii, niekto necháva algoritmus chladnúť každých n-opakovaní.

Nikto nevie jednoducho povedať, ako nastaviť počiatočnú teplotu, a nikto nevie povedať, ako rýchlo treba nechať teplotu vychladnúť (hodnota α).

Riešenie pre problém 8 dám

Pozrime sa znova, ako sa dá v tom prípade vyriešiť problém ôsmich dám. Ak tento problém ešte nepoznáte, pozrite si článok venovaný TabuSearch.

1. Vytvoríme si náhodné riešenie (1).

var riesenie = Array(boardSize) { random.nextInt(boardSize) }

2. n krát spustíme hlavný cyklus (3).

for (i in 0 until 10000) { }

3. v cykle získame novú teplota (3c). Písal som síce o postupnom znižovaní teploty, ale aj takýmto spôsobom môžem získať nižšiu a nižšiu teplotu:

val teplota = 100.0 / (i + 100)

4. získame si nové susedne_riesenie (3a). V našom prípade jednu náhodnú kráľovnú presuniem na náhodný riadok v tom istom stĺpci.

val susedne_riesenie = neighbor(riesenie)

5. ak prejdeme akceptačnou funkciou (3b), uložíme si nového suseda ako aktuálne riešenie.

if (accept(riesenie, susedne_riesenie, teplota)) {
    riesenie = susedne_riesenie
}

Celý program môžete nájsť na GitHube

Na rozdiel od TabuSearch simulované žíhanie našlo riešenie pre 20 dám a našlo ho dokonca za 30 milisekúnd, pre 40 dám za 40-200 ms. Pre 50 dám sa mi podarilo nájsť riešenie za 200-800 ms. Najväčšia šachovnica, ktorú som riešil, bola 80x80 (~10s). Takéto výsledky sú s predchádzajúcimi algoritmami nepredstaviteľné.

Solution "8, 13, 3, 17, 7, 10, 4, 0, 18, 15, 6, 11, 19, 12, 16, 2, 5, 1, 9, 14" found in 3028 iterations and 30ms

Riešenie pre problém obchodného cestujúceho

Problém obchodného cestujúceho som už spomenul. Tento problém si zaslúži samostatný článok, preto sa mu tu nebudem venovať. Pomocou simulovaného žíhania vyzerá moje riešenie nasledovne.

‍

‍

Pre 50 miest nájde simulované žíhanie uspokojivé riešenie do pár sekúnd.

❗️Pozor! Video je výrazne spomalené 🙂

Tak čo? Už začínate mať pocit, že sa blížime k trochu inteligentnejším programom? Nabudúce nás čaká Genetický algoritmus. Jeden z mojich obľúbených!