36PAA - Batoh řešený metodou simulované ochlazování (pokročilá iterativní metoda)

Zadání

Implementace

Z pokročilých iterativních metod jsem si vybral algoritmus simulované ochlazování. Je popsán "vývojovými diagramy" na následujících obrázcích.

Pokusím se algoritmus popsat slovně. Jedná se o 2 vnořené cykly. Na začátku je nastaveno nějaké řešení a počáteční teplota, která se ve venkovním cyklu postupně snižuje. Teplotou je dána ochota algoritmu přijmout horší řešení. Tím se může algoritmus vymanit z lokálního minima. Ve vnitřním cyklu se hledá nové řešení. To je popsáno na obrázku jako funkce "try". Náhodně vygenerujeme nové přípustné řešení. Pokud je lepší než doposud nalezené, toto řešení přijmeme. Pokud je horší tak jej přijmeme s určitou pravděpodobností, která je dána aktuální teplotou a velikostí zhoršení ceny. Algoritmus končí pokud se teplota sníží na úroveň teploty tuhnutí. Pro správnou funkci algoritmu je velice důležité nastavit parametry (počáteční teplota, teplota tuhnutí, rychlost tuhnutí, velikost equilibria).

Zdrojové kódy

Naměřené hodnoty a výsledky

Aby bylo možné správně nastavit parametry algoritmu je nutné experimentovat. Při experimentech jsem sledoval časovou náročnost a relativní chybu. Pro výpočet globálního maxima (pro výpočet relativní chyby) jsem použil dříve implementované dynamické programování. Algoritmus jsem srovnával s Greedy Proof (metodou nejrychlejšího vzestupu). Experimenty jsou shrnuty v následujících tabulkách a grafech.
Pro přehlednost jsem použil tyto zkratky:

SA = Simulated Annealing = simulované ochlazování
GP = Greedy Proof = metoda nejrychlejšího vzestupu
triv = použito triviální řešení pro inicializaci SA
init GP = použito GA pro inicializaci SA
T0 = počáteční teplota
Tf = teplota tuhnutí
dT = změna teploty
equ = equilibrium

Pokud není uvedeno jinak, experimentoval jsem na instancích o velikosti n = 40. SA bylo na každé instanci spuštěno 20x a výsledná relativní chyba a čas je průměr z výsledů algoritmu.

Měřil jsem na NTB s procesorem Centino 1.4GHz, nastavení max Performance při napájení z adaptéru. Použitý OS: Windows XP SP2 s .net Framework 2.

Nastavení změny teploty

Při tomto experimentu jsem nastavil T0 = (M * suma_cen_veci) / (n * suma_vah_veci), Tf = 10, equ = n a měnil dT v rozmezí 0,8 - 0,999.
dTrelativní chybačas
GPSA trivSA init GPGPSA trivSA init GP
0,9990,15%0,12%0,02%0,0625278,731642,995
0,9950,42%0,07%58,154128,795
0,990,64%0,09%27,1766,054
0,981,14%0,12%13,15932,717
0,9751,29%0,13%10,52524,725
0,952,01%0,14%5,35812,509
0,93,26%0,14%2,6446,039
0,85,50%0,15%1,2712,944

Graf: Závislost relativní chyby na změně rychlosti ochlazování

Graf: Závislost časové složitosti na změně rychlosti ochlazování

Nastavení velikosti equilibria

Nastavení: T0 = (M * suma_cen_veci) / (n * suma_vah_veci), Tf = 10, dT = 0,9 a 0,98, měnil jsem equ v intervalu n / 5 až n * 5
equrelativní chybačas
GPSA trivSA init GPGPSA trivSA init GP
dT = 0,98dT = 0,9dT = 0,98dT = 0,9dT = 0,98dT = 0,9dT = 0,98dT = 0,9
2000,15%0,34%1,16%0,07%0,12%0,062565,66313,23153,19130,184
1600,39%1,31%0,07%0,13%54,19810,345123,09723,945
1200,52%1,53%0,09%0,13%39,3467,92292,75317,866
800,72%2,06%0,10%0,14%26,0675,43861,89911,907
401,13%3,20%0,12%0,15%13,1492,66430,6945,988
201,76%5,85%0,13%0,14%6,841,33215,353,074
132,26%8,18%0,14%0,15%4,3760,98110,3852,013
102,83%10,06%0,14%0,15%3,4350,7017,7711,652
83,45%12,09%0,15%0,15%2,7240,5816,2391,312

Graf: Závislost relativní chyby na velikosti equilibria

Graf: Závislost časové složitosti na velikosti equilibria

Nastavení teploty tuhnutí

Nastavení: T0 = (M * suma_cen_veci) / (n * suma_vah_veci), dT = 0,98, equ = n, měnil jsem Tf v intervalu 1 až 10.
Tfrelativní chybačas
GPSA trivSA init GPGPSA trivSA init GP
10,15%0,94%0,12%0,062527,53930,604
20,94%0,12%23,25425,857
30,99%0,12%20,65922,893
50,96%0,12%17,32518,837
70,99%0,12%15,43317,745
101,08%0,13%13,22914,521

Graf: Závislost relativní chyby na teplotě tuhnutí

Graf: Závislost časové složitosti na teplotě tuhnutí

Nastavení počáteční teploty

Nastavení: Tf = 1, dT = 0,98, equ = n, měnil jsem T0 v intervalu 35 až 200
T0relativní chybačas
GPSA trivSA init GPGPSA trivSA init GP
2000,15%0,98%0,12%0,062532,92834,81
1500,95%0,12%32,24732,547
1000,92%0,12%28,63232,676
801,01%0,12%28,49134,389
601,11%0,12%25,66732,868
501,23%0,12%24,73530,273
451,37%0,12%23,76430,454
401,71%0,12%23,15328,821
371,98%0,12%22,69327,059
352,25%0,12%22,38127,239

Graf: Závislost relativní chyby na počáteční teplotě

Graf: Závislost časové složitosti na počáteční teplotě

Závislost relativní chyby na velikosti instance

Jen tak pro zajímavost, srovnání průměrné relativní chyby pro různě velké instance. Nastavení parametrů: dT = 0,98, Tf = 5, equ = n, T0 = 67,31

Graf: Závislost relativní chyby na velikosti instance

Ukázky průchodu algoritmu stavovým prostorem

Na následujících grafech je zobrazena velikost ceny v závislosti na prozkoumaných stavech pro různé parametry. Pro zvětšení klikněte na prosím na graf.
init GP, dT = 0,8, Tf = 5, equ = n, T0 = 67,31 triv, dT = 0,8, Tf = 5, equ = n, T0 = 67,31
init GP, dT = 0,9, Tf = 5, equ = n, T0 = 67,31 triv, dT = 0,9, Tf = 5, equ = n, T0 = 67,31
init GP, dT = 0,98, Tf = 5, equ = n, T0 = 67,31 triv, dT = 0,98, Tf = 5, equ = n, T0 = 67,31
init GP, dT = 0,98, Tf = 5, equ = n / 5, T0 = 67,31 init GP, dT = 0,98, Tf = 5, equ = 5 * n, T0 = 67,31

Závěr

Algoritmus simulované ochlazování je poměrně snadný na implementaci. Z experimentů můžeme říct, že je časově náročnější než hladový algoritmus a při inicializaci triviální konfiguraci dává průměrně horší výsledky. Pokud inicializujeme SA hodnotou získanou GP algoritmem, v průměru vždy dojde ke zlepšení relativní chyby. Protože algoritmus si pomatuje nejlepší řešení, nemůže nikdy vyjít horší výsledek než u GP.
U tohoto algoritmu (stejně jako u dynamického programování) dopředu známe počet iterací cyklu, tudíž můžeme odhadnout časovou náročnost. Proto je na první pohled trochu divné, řádově rozdílný čas při inicializaci triviálním řešením a řešením dodaným GP algoritmem. Skrytá časová závislost je v generování nového stavu. Ten generujeme tak, že změníme bit na náhodné pozici v současné konfiguraci, ale výsledná konfigurace musí být přípustným řešením. Proto pokud vyjdeme z triviální konfigurace je velká pravděpodobnost, že nový stav vygenerujeme na 1. pokus. U již nalezeného řešení např. algoritmem GP opakujeme generování poměrně dlouho, než dostaneme přípustnou konfiguraci.
Dále z provedených experimentů můžeme udělat tyto závěry: