Úloha z předmětu 36PAA
Martin Tůma
Zpráva by měla obsahovat:
Jako heuristiku jsem zvolil simulované ochlazování, jehož základní princip uvádí následující odstavec.
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í.
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)
Graf 1: Vývoj ceny aktuálního stavu řešení v závislosti na iteraci algoritmu. (Naměřená data)
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í.
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ě.
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ě.
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šší.
[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
1. batoh_sa.c - Program pro řešení metodou simulovaného ochlazování.