36 PAA - Problémy a algoritmy

Úloha 5: Seznámení s pokročilou iterativní metodou

Jan Dohnal (dohnaj1@fel.cvut.cz)

Zadání

• Zvolte si heuristiku, kterou budete řešit problém vážené splnitelnosti booleovské formule (simulované ochlazování, simulovaná evoluce, tabu prohledávání)

• Tuto heuristiku použijte pro řešení problému batohu.

• Hlavním cílem domácí práce je seznámit se s danou heuristikou, zejména se způsobem, jakým se nastavují její parametry (rozvrh ochlazování, selekční tlak, tabu lhůta...) a modifikace (zjištění počáteční teploty, mechanismus selekce, tabu atributy...). Není-li Vám cokoli jasné, prosíme ptejte se na cvičeních.

• Problém batohu není příliš obtížný, většinou budete mít k dispozici globální maxima (exaktní řešení) z předchozích prací, například z dynamického programování.

• Zpráva z tohoto úkolu má být co nejstručnější: použitá metoda, způsob nastavení parametrů, výsledky.

Použitá metoda

Pro řešení této úlohy jsem zvolil metodu simulovaného ochlazování. Jedná se o jednu z pokročilých iterativních metod pro řešení NP problémů. Využívá se postupného „snižování teploty“, kdy teplota ovlivňuje pravděpodobnost přijmutí nového stavu zhoršujícího optimalizační kritérium současného řešení. Pokud je teplota vysoká, pravděpodobnost přijmutí stavu, který má horší optimalizační kritérium než současný stav, je vyšší, než v případě nízké teploty. Tedy pokud je teplota vysoká, pravděpodobnost akceptace stavu, který má horší optimalizační kritérium než současný stav je vyšší, než pokud je teplota nízká.

Popis algoritmu simulovaného ochlazování následuje:

state = init_state;  //pocatecni stav
t = t0;                 //pocatecni teplota
do {
  do {
    state = try(state, t);
  } while (! equilibrium(state, t, ...) );
  t = cool(t);
} while (! frozen(t, ...) );
//nalezení dalšího stavu
try(state, t) {
  new = random_thing(state);
  delta = cost(new) - cost(old);
  //zlepseni ci pripustne zhorseni
  if ( (delta < 0) || (random() < exp(-delta/t)) )
    return new;
  return state;
}

Jako počáteční řešení pro algoritmus simulovaného ochlazování jsem využil výsledná data z dynamického programování. Pro řešení problému batohu jsem si zvolil instanci dimenze 27, nad kterou jsem prováděl výpočty a měření.

Nastavení parametrů

Parametry simulovaného ochlazování ovlivňující běh algoritmu a výsledek jsou tyto:

• t₀ (počáteční teplota) - má vliv na přijetí horšího stavu (nižší teplota znamená nižší pravděpodobnost přijetí horšího stavu). Nižší hodnota znamená rychlejší konvergenci.

• α (koeficient ochlazování) - ovlivňuje snižování teploty. Je nutné najít optimální hodnotu pro kvalitní výsledky.

• i (práh iterace) - práh iterace určuje konec algoritmu. Pokud nedojde ke změně po stanovený počet iterací, algoritmus skončí. Vyšší hodnota umožňuje dosáhnout lepších výsledků.

Naměřené hodnoty

Pro instanci dimenze 27 jsem naměřil následující hodnoty a výsledky v závislosti na zvolené počáteční teplotě t₀, koeficientu ochlazování α a prahu iterace i.

Závěr

V této práci jsem se snažil seznámit s principem algoritmu simulovaného ochlazování. Pro zjednodušení jsem zvolil omezené množství vstupních dat, výsledek mne však mile překvapil, jelikož algoritmus nabídl rozumnou optimalizaci řešení. Při experimentování s algoritmem jsem zjistil, že výsledek silně závisí na volbě vstupních parametrů.