Řešení problému batohu pokročilou iterativní heuristikou
Úloha z předmětu 36PAA
Martin Tůma
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. Můžete použít dostupné instance problému [1], anebo si vygenerujte své instance pomocí generátoru [2]. Používejte instance s větším počtem věcí (>30).
- 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 slekce, 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 by měla obsahovat:
- Stručný popis zvoleného algoritmu
- Zhodnocení Vašich experimentů. Zkoušejte sledovat vývoj řešení (populace u GA) v průběhu běhu algoritmu. Graf potěší...
- Experimentujte s různými nastaveními parametrů
- Výsledek měření = čas výpočtu a rel. chyba. Pokud nejste schopni vypočítat rel. chybu, stačí uvést vývoj výsledné ceny (počáteční -> koncová)
- Pokuste se vyvodit nějaké závěry
Řešení
Jako heuristiku jsem zvolil simulované ochlazování, jehož základní princip uvádí následující odstavec.
Simulované ochlazování
Simulované ochlazování je lokální metoda prohledávání stavového prostoru, která je inspirovaná stejnojmenou technikou používanou v metalurgii. Metoda umožňuje při prohledávání jako následující stav s určitou pravděpodobností přijmout i stav horší než aktuální a vyhnout se tak lokálním minimům. Tato pravděpodobnost klesá s klesající teplotou, což zajištuje konvergenci algoritmu. Podrobný popis algoritmu uvádí například [3].
STATE anneal(void)
{
temp = INIT_TEMP
state = INIT_STATE
best = state
do {
do {
state = next_state(state, temp)
best = better(state, best)
} while (!equilibrium())
temp = cool(temp)
} while (!frozen(temp))
return best
}
Kostra algoritmu simulovaného ochlazování.
Naměřené hodnoty
Měření probíhala na souboru instancí velikosti 40 [1]. Naměřené relativní chyby jsou vždy průměry ze všech instancí ve vstupním souboru při změně zkoumaného parametru. Čas výpočtu je udáván pro celý vstupní soubor. Vývoj řešení je měřen na první instanci souboru.
Testovací konfigurace: CPU Duron 900MHz, OS Linux, GCC 3.4.4 (žádné optimalizační flagy)
Vývoj řešení
Graf 1: Vývoj ceny aktuálního stavu řešení v závislosti na iteraci algoritmu. (Naměřená data)
Čas výpočtu a relativní chyba v závislosti na koeficientu ochlazování
| c [-] | ηø [%] | ηmax [%] | t [s] |
|---|---|---|---|
| 0.800 | 0.307 | 12.353 | 3.440 |
| 0.825 | 0.193 | 7.345 | 4.040 |
| 0.850 | 0.203 | 7.345 | 4.460 |
| 0.875 | 0.284 | 12.353 | 5.772 |
| 0.900 | 0.203 | 9.849 | 7.276 |
| 0.925 | 0.253 | 12.353 | 9.841 |
| 0.950 | 0.112 | 4.841 | 14.749 |
| 0.975 | 0.096 | 4.841 | 29.738 |
Graf 2: Čas výpočtu a relativní chyba v závislosti na koeficientu ochlazování.
Čas výpočtu a relativní chyba v závislosti na výchozí teplotě
| Tinit [-] | ηø [%] | ηmax [%] | t [s] |
|---|---|---|---|
| 100 | 0.304 | 12.353 | 2.032 |
| 200 | 0.242 | 9.849 | 2.772 |
| 500 | 0.185 | 7.345 | 3.884 |
| 1000 | 0.203 | 7.345 | 4.812 |
| 3000 | 0.233 | 9.849 | 5.832 |
| 5000 | 0.250 | 9.849 | 5.928 |
Graf 3: Čas výpočtu a relativní chyba v závislosti na výchozí teplotě.
Čas výpočtu a relativní chyba v závislosti na koncové teplotě
| Tfinal [-] | ηø [%] | ηmax [%] | t [s] |
|---|---|---|---|
| 0.1 | 0.082 | 2.337 | 8.657 |
| 1 | 0.092 | 2.337 | 6.108 |
| 5 | 0.079 | 2.337 | 4.380 |
| 10 | 0.145 | 4.841 | 3.804 |
| 20 | 0.381 | 14.858 | 3.100 |
Graf 4: Čas výpočtu a relativní chyba v závislosti na koncové teplotě.
Závěr
Simulované ochlazování se ukázalo být poměrně efektivní heuristikou pro řešení problému batohu. V porovnání s heuristikou typu nejrychlejšího vzestupu dosahuje při "rozumné" době běhu1 výpočtu prakticky srovnatelné výsledky.
Testy dále ukázaly, že metoda je poměrně citlivá na nastavení parametrů, jejihž změny navíc nejsou navzájem nezávislé. Pro daný soubor (a budeme-li tento brát jako reprezentativní pro všechny instance velikosti 40 tak i pro úlohy velikosti instance 40) se jako ideální nastavení jeví tyto hodnoty: výchozí teplota: 500, koncová teplota: 5, koeficient ochlazování: 0.825 a počet iterací vnitřního cyklu: 10000. Při tomto nastavení metoda dává průměrnou relativní chybu 0.08%, maximální relativní chybu 2.34% a (na dnes již obstaróžním HW) čas výpočtu na instanci: 88ms
1Bohužel jsem pro tuto úlohu z důvodu poruchy neměl k dispozi HW na kterém byly testovány předchozí metody, proto nelze dobu běhu porovnat, nicméně lze předpokládat, že bude u simulovaného ochlazování vyšší.
Reference
[1]
http://service.felk.cvut.cz/courses/36PAA/knapsolv.html#bench
[2]
http://service.felk.cvut.cz/courses/36PAA/wknapgen.html
[3]
http://service.felk.cvut.cz/courses/36PAA/prez/PAA8ochl.pdf
Přílohy
1. batoh_sa.c - Program pro řešení metodou simulovaného ochlazování.