5. Úloha

Jan Doležel

Zadaní

Řešte problém batohu jednou z následujících technik:

Řešení

Vybral jsem si metodu simulovaného ochlazování, která se dá popsat následujícím pseudo-kódem:

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

  do {
    do {
      state = getNewState(state, t);
      if(cost(state) > cost(max)) max = state;
    } while(...);
    t = coolDown(t);
  } while(...);
  return max;
}

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

Zbývá zde několik parametrů k nastavení:

počáteční teplota
(Σci / N) / (Σwi / M)
výchozí řešení
prázdný batoh
vniřní smyčka
opakuje se N*5 krát
ochlazení
koeficientem 0.9
vnější smyčka
dokud ve vnitřní smyčce nastává změna nebo teplota neklesne pod 0.1

Cena stavu je cena věcí v batohu a následující stav je generován operací XOR na jeden bit batohu (každá věc je reprezontována jedním bitem - je/není v batohu).

Naměřené hodnoty

Algoritmus a jeho parametry jsem testoval na rozličných instancích (pro N = 4, 10, 15, 20, 22, 25, 27, 30, 32, 35, 37, 40, 60, 61, 62) pro každou velikost instance bylo 50 různých instancí, celkem 750 instancí.

Několik vybraných průběhů (osa y je cena řešení - červená tečka vlevo ukazuje optimalní cenu; osa x postup stavovým prostorem):

figure

N = 4

figure

N = 10

figure

N = 15

figure

N = 22

figure

N = 27

figure

N = 35

figure

N = 40

figure

N = 61

figure

N = 62

Následující graf ukazuje na kolik procent se řešení přiblížilo optimu pro jednotlivé instance:

figure
figure

Závislost času na velikosti instance

Možné změny

Počáteční teplota

Použitá počáteční teplota vykazovala nejstabilnější chování na všech testovaných instancích. Dále jsem testoval následující možnosti, ale ty měly mnohem větší chybu pro malé nebo velké instance (k = 1/10 .. 100):

Výchozí řešení

Zkoušel jsem prázdný batoh, náhodné řešení i řešení nalezené heuristikou poměru cena/váha s testem nejcennější věci. Větší rozdíly se neobjevili.

Vnitřní smyčka

Nastavení se mně zdálo optimální, neměnil jsem ho

Koeficient ochlazení

Měnil jsem ho v rozmezí 0.8 až 0.95. Jinou metodu než násobení koeficientem jsem nezkoušel.

Vnější smyčka

Zkoušel jsem nejdříve pouze test na teplotu, později jsem přidal i test, zda se stav ve vnitřní smyčce alespoň jednou změnil.

Závěr

Podle testů není tato technika na problém batohu příliš vhodná. Průměrná chyba pro všech 750 instancí byla 1.84%. Pro heuristiku poměru cena/váha s testem nejcennější věci vycházela průměrná chyba 0.42%. Přičemž s heuristikou máme zaručenu maximální chybu 50% (simulované ochlazování negarantuje žádnou maximální chybu) a algoritmus heuristiky je i rychlejší. Pustíme-li simulované ochlazování na řešení nalezené heuristkou dosáhneme pouze 0.02% vylepšení - to opravdu nestojí za to.

Teplota musí být nastavena relativně vysoká, aby algoritmus mohl věci z batohu odebírat a neuvízl v lokálním maximu. Někdy může být důležité odebrat cennou věc, která ovšem váží přiliš mnoho. Potom se ovšem cena stavu může pohybovat ve velkém rozpětí a křivka průběhu "lítá odshora dolů". Měrění potvrdila, že čím větší počáteční teplota, tím lepší řešení algoritmus našel. Doba hledání se však prodloužila.

Když jsem přidal k testu ukončení vnější smyčky i test neměnnosti stavu ve vnitřní smyčce, čas se výrazně zkrátil a řešení utrpělo jen malé zhoršení v řádu desetin procenta.

Pro tuto úlohu by možná bylo vhodnější řešení pomocí genetického algoritmu. Ale ani to by dle mého názoru v průměru nepřekonalo řešení nalezené heuristikou a určitě by potřebný čas byl řádově delší.

Z přibližných řešení je pro tuto úlohu vhodná heuristika poměru cena/váha s testem nejcennější věci.