Eithel.net: Simulování ochlazování

Simulované ochlazování je jednou z lokálních metod prohledávání stavového prostoru. Od metody nejlepší první se liší tím, že s určitou, stále klesající pravděpodobností, je schopna přijmout i horší stav a tím vyklouznout z lokálního minima.

Název i algoritmus se inspiroval stejnojmenou technikou z metalurgie. Kov se při této metodě ochlazuje pozvolna, čímž se zabraňuje vzniku krystalů a zvyšuje se pevnost a odolnost materiálu. Atomy se při vyšší teplotě mohou pohybovat materiálem a hledat vhodné místo s nižší energii. Jak teplota klesá, počet pohybujících se atomů také klesá a usazují se ve vhodnějších pozicích. Na konci dává metoda větší šanci na nalezení stavu s celkově menší enegií.

Kostru algoritmu si můžeme popsat:

annealing() {
  t = initTemperature();
  state = initState();

  do {
    do {
      state = getNewState(state, t);
    } while(...);
    t = coolDown(t);
  } while(...);
}

getNewState(state, t) {
  new = getNextRandomState(state);
  Δ = cost(state) - cost(new);
  if(Δ < 0) return new;
  else {
    r = getRandom(0..1);
    if(r < exp(-Δ/t)) return new;
    else return state;
  }
}

Nový stav je přijat vždy, když je lepší než předchozí. Pokud není, je příjat s pravděpodobností exp(-Δ/t).

Tento vzorec říká, že je přijat, pokud je teplota vysoká, nebo rozdíl v ceně malý. Pravděpodobnost přijetí horšího stavu klesá s teplotou.

Algoritmus má mnoho částí k nastavování, ty jsou pro každou úlohu individuální a určují se většinou experimentálně, aby poměr délky výpočtu ku ceně výsledného řešení byl optimální. (Čím déle algoritmus běží, tím větší šance na získání výsledku blížícího se optimu)

Můžeme nastavovat například počáteční tepolotu, počáteční stav, délku vnitřní a vnější smyčky, koeficient ochlazení (většinou 0,8 - 0,95). Koeficient ochlazení nemusí být lineární. Můžeme použít exponenciální závislost, arcustangentu, ...

Pokud je počáteční teplota příliš vysoká, prohledává na začátku algoritmus prostor spíše náhodně a teprve později začíná pracovat správně. Je také vhodné pamatovat si nejlepší dosažený stav, protože ten nemusí být totožný se stavem na konci algortimu.

Možností nastavení je nepřeberně. Dvě ukázky řešení problému si můžete prohlédnout...

Problém batohu

Problém batohu řešený simulovaným ochlazováním. Pátá úloha pro 36PAA

SAT problém

Problém MAXSAT - maximalizace zisku při splnění ohodnocení booleovské formule - řešený simulovaným ochlazováním. Šestá úloha pro 36PAA