36PAA - ulohy (Michal Trs)

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 (zde (stránka již neexistuje)), anebo si vygenerujte sv� instance pomoc� gener�toru (stránka již neexistuje). 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 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�.

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

SimAnneal.cs - Implementace algoritmu simulovan�ho ochlazov�n�
Batoh-SimAnneal.zip

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.

dT	relativn� chyba			�as
dT	GP	SA triv	SA init GP	GP	SA triv	SA init GP
0,999	0,15%	0,12%	0,02%	0,0625	278,731	642,995
0,995		0,42%	0,07%		58,154	128,795
0,99		0,64%	0,09%		27,17	66,054
0,98		1,14%	0,12%		13,159	32,717
0,975		1,29%	0,13%		10,525	24,725
0,95		2,01%	0,14%		5,358	12,509
0,9		3,26%	0,14%		2,644	6,039
0,8		5,50%	0,15%		1,271	2,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

equ	relativn� chyba					�as
	GP	SA triv		SA init GP		GP	SA triv		SA init GP
	GP	dT = 0,98	dT = 0,9	dT = 0,98	dT = 0,9	GP	dT = 0,98	dT = 0,9	dT = 0,98	dT = 0,9
200	0,15%	0,34%	1,16%	0,07%	0,12%	0,0625	65,663	13,23	153,191	30,184
160		0,39%	1,31%	0,07%	0,13%		54,198	10,345	123,097	23,945
120		0,52%	1,53%	0,09%	0,13%		39,346	7,922	92,753	17,866
80		0,72%	2,06%	0,10%	0,14%		26,067	5,438	61,899	11,907
40		1,13%	3,20%	0,12%	0,15%		13,149	2,664	30,694	5,988
20		1,76%	5,85%	0,13%	0,14%		6,84	1,332	15,35	3,074
13		2,26%	8,18%	0,14%	0,15%		4,376	0,981	10,385	2,013
10		2,83%	10,06%	0,14%	0,15%		3,435	0,701	7,771	1,652
8		3,45%	12,09%	0,15%	0,15%		2,724	0,581	6,239	1,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.

Tf	relativn� chyba			�as
Tf	GP	SA triv	SA init GP	GP	SA triv	SA init GP
1	0,15%	0,94%	0,12%	0,0625	27,539	30,604
2		0,94%	0,12%		23,254	25,857
3		0,99%	0,12%		20,659	22,893
5		0,96%	0,12%		17,325	18,837
7		0,99%	0,12%		15,433	17,745
10		1,08%	0,13%		13,229	14,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

T0	relativn� chyba			�as
T0	GP	SA triv	SA init GP	GP	SA triv	SA init GP
200	0,15%	0,98%	0,12%	0,0625	32,928	34,81
150		0,95%	0,12%		32,247	32,547
100		0,92%	0,12%		28,632	32,676
80		1,01%	0,12%		28,491	34,389
60		1,11%	0,12%		25,667	32,868
50		1,23%	0,12%		24,735	30,273
45		1,37%	0,12%		23,764	30,454
40		1,71%	0,12%		23,153	28,821
37		1,98%	0,12%		22,693	27,059
35		2,25%	0,12%		22,381	27,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:

��m bl�e dT k 1 t�m men�� relativn� chyba, ale v�t�� asov� n�ro�nost.
Po��te�n� teplotu je vhodn� volit jako funkci velikosti instance. V experimentu d�v� nejlep�� v�sledky n * 2. Na dostuduj jsem na�el tento vztah: M * suma(ceny) / (N * suma(v�hy)), kter� d�v� podobn� v�sledky.
Teplotu tuhnut� je nejlep�� "vykoukat" z graf� pro z�vislost ceny na po�tu prozkouman�ch stav�. Pokud se cena nem�n�, m�lo by doj�t k zamrazen�. To m��eme p��mo o�et�it v programu a nemus�me tento parametr nastavovat.
Velikost equilibria, ��m v�t�� t�m men�� relativn� chyba, ale v�t�� asov� n�ro�nost.

36PAA - Batoh �e�en� metodou simulovan� ochlazov�n� (pokro�il� iterativn� metoda)