15. Princip simulovaného ochlazování, význam parametrů a způsoby jejich řízení. (NI-KOP)

---

Simulované ochlazovaní

• Probabilistická optimalizační metoda inspirovaná metalurgickým procesem žíhání

Algoritmus

# Funkce ktera zkusi jit na novy stav. 
# Pokud je novy stav lepsi:
    # Vrati novy stav
# Pokud je stav horsi
    # zjisti o kolik
    # Prijme s nejakou pravdepodobnosti
    # Jinak vrati puvodi
function try (state) {
    q = Q.random_choose();
    new = q(state);
    if (new.better(state)) return new;
    δ = new.howmuchworse(state);
    if (random(0,1) < exp(- δ/T))return new;
return state;
}

# Algoritmus samotheno ochlazovani
Počáteční teplota -> T;
Ø -> best;
while (!frozen (T, ...)) {
    while (!equilibrium (...)) {
        state = try(state);
        if (state.better(best)) state -> best;
    }
    T = cool (T, ...);
}

1. Volba počátečních parametrů

   • Náhodně vygenerovat počáteční řešení
   • Stanovit počáteční teplotu $T_0$
   • Definovat ochlazovací schéma
   • Nastavit délku ekvilibria

2. Generování sousedního řešení

   • Vygenerovat náhodného souseda aktuálního řešení
   • Vypočítat změnu kvality řešení $\Delta E$

3. Rozhodování o přechodu

   • Pokud je nové řešení lepší:
     • Přejít na nové řešení
   • Pokud je řešení horší:
     • Vypočítat pravděpodobnost přechodu $p = \exp(-\Delta E/T)$
     • Náhodně rozhodnout o přijetí podle pravděpodobnosti

4. Aktualizace teploty

   • Snížit teplotu podle zvoleného schématu
   • Provádět pouze po dosažení ekvilibria

5. Ukončovací kritérium

   • Kontrola teploty
   • Pokud teplota příliš nízká → ukončit
   • Jinak opakovat hlavní cyklus

Klíčové funkce

• frozen(T,...)
  • Funkce která zjišťuje zda jsme už došli do "konce"
  • Typy implementace
    • Pevný počet iterací
    • Detekovaní dlouhodobé stagnace
    • ...
• equilibrium(...)
  • Funkce zjišťuje zda ještě máme pokračovat v aktuálním vyhledávaní a s aktuální teplotou
  • Řídí diversifikaci / intenzifikaci
  • Typy implementace
    • Pevný počet iteraci
    • Počet přijatých kroku
    • ...
• cool(T,...)
  • Funkce která sníží teplotu.
  • Ovlivňuje tak dobu chlazeni
  • Řídí diversifikaci / intenzifikaci
  • Typy implementace:
    • Pevný krok ochlazeni
    • Procentuální krok ochlazeni
    • ...

Klíčové charakteristiky

Pravděpodobnostní přechod

• Řízen teplotou $T$
• Vyšší teplota = vyšší šance přijmout horší řešení
• Nižší teplota = preference lepších řešení

Ekvilibrium

• Série kroků při konstantní teplotě
• Zabraňuje příliš rychlému ochlazování
• Umožňuje průzkum okolí aktuálního řešení

Řízení algoritmu

• Diverzifikace
  • Pokud často spadáme do lokálního minima je třeba zvýšit diverzifikaci
  • Typy řízení:
    • Zpomaleni ochlazovaní
    • Zvýšení počtu kroků v equilibriu
• Intenzifikace
  • Pokud je vypočet příliš pomalý musíme zvýšit intenzifikaci