Algoritmy umelej inteligencie #3 - Simulované žíhanie
Mobile
4
 min read
August 5, 2022

Algoritmy umelej inteligencie #3 - Simulované žíhanie

Jan Kandráč
Jan Kandráč
Android Developer
LinkedIn Logo

Simulované žíhanie (angl. Simulated Annealing) je inšpirované žíhaním v metalurgii. Spočíva v rozpálení kovu na vysokú teplotu a následnom pomalom chladení. Takto sa vnútorná štruktúra kovu najprv rozbije a následne sa veľmi pomaličky “opraví”. Takto vznikne kov, ktorý má podstatne lepšie vlastnosti ako na začiatku procesu.

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

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.

Snímka obrazovky z pretekov autonómnych podov na stránke codingame.com

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á.

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).

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

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:

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.

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

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!

Like what you see?
Join our newsletter.

Great! Welcome to newsletter.
Oops! Something went wrong while submitting your email.
High quality content once a month. No spam, we promise.
Your personal data is processed in accordance with our Memorandum on Personal Data Protection.

Páči sa vám náš content?
Odoberajte newsletter.

Great! Welcome to newsletter.
Oops! Something went wrong while submitting your email.
Vaše osobné údaje sú spracované v súlade s našim Memorandom na ochranu osobných údajov.