Zad�n�
Je d�na booleovsk� formule F prom�nn�ch X=(x1,
x2, ... , xn) v
konjunktivn� norm�ln� form� (tj. sou�in sou�t�).
D�le jsou d�ny celo��seln� kladn�
v�hy W=(w1, w2, ... , wn). Najd�te
ohodnocen� Y=(y1, y2, ... , yn) prom�nn�ch x1, x2, ... , xn tak, aby F(Y)=1
a sou�et vah prom�nn�ch, kter� jsou ohodnoceny
jedni�kou, byl maxim�ln�.
Je p��pustn� se omezit na formule, v nich� m�
ka�d� formule pr�v� 3 liter�ly (probl�m 3
SAT). Takto
omezen� probl�m je stejn� t�k�, ale mo�n�
se l�pe programuje a l�pe se posuzuje obt�nost
instance (viz Selmanova prezentace v odkazech).
Popis algoritmu
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� �e�en� (oproti �loze "Batoh" p�ij�m�me i �e�en�, kdy je formule nespln�n�). 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).
Implementace
Form�t vstupn�ho souboru
Form�t vstupn�ho souboru jsem p�evzal od Martina Prchl�ka. Oproti DIMACS CNF form�tu obsahuje v�hy prom�nn�ch a nejlep�� �e�en� dodan� BruteForcem. Popis form�tu (��dk�):
- 1. - pr�zdn� ��dek
- 2. - spr�vn� �e�en�
- 3. - po�et_prom�nn�ch po�et_klausul� po�et_prom�nn�ch_v_klausuli
- 4 - n. - jednotliv� klausule (��slo je index prom�nn�, ��slov�no od 1, pokud je ��slo z�porn� znamen� negovanou prom�nnou
- n+1 - v�hy prom�nn�ch
Zdrojov� k�dy (C#)
- MPFormatInputReader.cs - Reader vstupn�ho form�tu, vrac� t��du SAT
- Program.cs - obaluj�c� k�d pro experimenty, m��en� �asu a chyb
- SAT.cs - t��da reprezentuj�c� data formule, v�hy, metody pro vyhodnocen� splnitelnosti a ohodnocen� stavu
- SimAnneal.cs - Algoritmus simulovan� ochlazov�n�, v constructoru o�ek�v� t��du SAT a parametry simulovan�ho ochlazov�n�
Ohodnocovac� funkce getGrant
N�vrh t�to funkce je velice d�le�it� pro spr�vnou funkci cel�ho algoritmu. Jsou na n� kladeny tyto po�adavky:
- Zv�hod�ovat prom�nn� s v�t�� v�hou
- Znev�hod�ovat nespln�n� klausule
Nam��en� hodnoty a v�sledky
Aby bylo mo�n� spr�vn� nastavit parametry algoritmu je nutn� experimentovat.
P�i experimentech jsem sledoval graf pr�chodu stavov�m prostorem, �asovou n�ro�nost a relativn� chybu.
Pro v�po�et relativn� chyby jsem pou�il hodnoty ze vstupn�ho souboru.
Z d�vodu �asov� n�ro�nosti m�m k dispozici data pro 20 prom�nn�ch a 50, 75 a 90 klausul�.
Experimenty jsou shrnuty v n�sleduj�c�ch tabulk�ch a grafech.
Pro p�ehlednost jsem pou�il tyto zkratky:
T0 = po��te�n� teplota
Tf = teplota tuhnut�
dT = zm�na teploty
equ = equilibrium
NF = �e�en� nenalezeno
time = �as v ms
Avg (AvgErr) = pr�m�rn� relativn� chyba v�sledku z k m��en�
Best (BestErr) = nejni��� relativn� chyba vybran� z k m��en�
Pokud nen� uvedeno jinak, jsou nastaveny toto hodnoty: T0_k = 0.1,Tf = 1,dT = 0.9, equ_k = 1. Algoritmus byl na ka�d� instanci spu�t�n 5x a v�sledn� relativn� chyba a �as je pr�m�r z v�sledk� algoritmu. Takto bylo postupov�no pro ka�dou instanci (50 instanc� pro ka�dou velikost probl�mu).
Teplota tuhnut� (Tf) a rychlost zm�ny (dT) jsou zad�ny absolutn�. Naproti tomu po��te�n� teplota (T0) a velikost equilibria (equ) jsou vzta�eny k velikosti instance (m�n�me pouze multiplikativn� konstantu) takto:
T0 = T0_k * var_count * maxW;
kde
equ = equ_k * var_count;
var_count je po�et prom�nn�ch a maxW je maxim�ln� v�ha prom�nn�.
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� rychlosti ochlazov�n�
P�i tomto experimentu jsem m�nil dT od 0.5 do 0.995
Tabulka �.1
| dT | 50 klausul� | 75 klausul� | 90 klausul� | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| NF | time | AvgErr | BestErr | NF | time | AvgErr | BestErr | NF | time | AvgErr | BestErr | |
| 0,995 | 0,00% | 223,7 | 1,70% | 0,20% | 0,00% | 275,9 | 2,90% | 0,20% | 0,80% | 316,2 | 1,90% | 0,80% |
| 0,945 | 0,00% | 17,3 | 4,40% | 0,60% | 0,40% | 25,7 | 4,20% | 1,80% | 4,80% | 27,7 | 1,50% | 0,50% |
| 0,898 | 0,00% | 9,5 | 4,20% | 0,70% | 2,40% | 13,6 | 4,20% | 1,70% | 5,20% | 14,9 | 1,30% | 2,10% |
| 0,853 | 0,00% | 6,3 | 6,50% | 1,40% | 1,60% | 8,7 | 4,40% | 3,70% | 7,20% | 10,1 | 1,30% | 0,90% |
| 0,81 | 0,00% | 4,6 | 6,60% | 2,70% | 3,20% | 6,4 | 3,80% | 4,00% | 9,60% | 7,5 | 0,90% | 0,70% |
| 0,77 | 0,00% | 4 | 7,20% | 3,90% | 5,20% | 5,2 | 3,30% | 4,30% | 10,00% | 6,2 | 0,50% | 0,80% |
| 0,731 | 0,00% | 3,1 | 6,90% | 4,30% | 5,60% | 4,4 | 3,60% | 6,00% | 11,60% | 4,8 | 0,60% | 3,50% |
| 0,695 | 0,40% | 2,9 | 5,50% | 4,70% | 6,80% | 3,8 | 2,80% | 4,70% | 12,00% | 4,1 | 0,70% | 3,00% |
| 0,66 | 0,00% | 2,4 | 7,70% | 5,00% | 4,80% | 3,3 | 3,50% | 7,40% | 13,20% | 3,8 | 1,60% | 6,20% |
| 0,627 | 0,40% | 2,3 | 9,00% | 4,00% | 6,80% | 2,8 | 3,40% | 5,90% | 13,20% | 3,4 | 0,90% | 3,30% |
| 0,596 | 0,80% | 2 | 5,30% | 4,30% | 8,00% | 3 | 3,30% | 4,70% | 14,40% | 3,2 | 0,10% | 0,60% |
| 0,566 | 2,80% | 1,9 | 5,90% | 3,30% | 9,20% | 2,8 | 2,90% | 6,90% | 12,00% | 2,8 | 0,90% | 2,30% |
| 0,538 | 2,00% | 1,6 | 8,90% | 8,00% | 10,80% | 2,3 | 2,70% | 6,10% | 12,80% | 2,4 | 0,50% | 2,20% |
| 0,511 | 1,60% | 1,5 | 10,10% | 10,60% | 10,80% | 1,9 | 2,30% | 9,00% | 12,40% | 2,4 | 1,00% | 3,00% |
Grafy �.1
| relativn� chyba | # nenalezen�ch stav� | �asov� slo�itost | pr�chod stavov�m prostorem |
 |
 |
 |
 |
Nastaven� velikosti equilibria
P�i tomto experimentu jsem m�nil equ_k od 1 do 10. Pouze p�ipomenu, �e velikost equilibria je vzta�en� k velikosti instance a to takto:equ = equ_k * var_count.
Tabulka �.2
| equ_k | 50 klausul� | 75 klausul� | 90 klausul� | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| NF | time | AvgErr | BestErr | NF | time | AvgErr | BestErr | NF | time | AvgErr | BestErr | |
| 1 | 0,00% | 10,9 | 4,60% | 0,50% | 1,20% | 13,1 | 3,30% | 1,70% | 6,00% | 15,2 | 1,50% | 0,90% |
| 2 | 0,00% | 19,5 | 3,40% | 0,20% | 0,00% | 26,2 | 4,50% | 3,00% | 2,40% | 30,1 | 2,00% | 2,10% |
| 3 | 0,00% | 28,9 | 2,90% | 0,20% | 0,00% | 39,2 | 4,50% | 1,30% | 2,40% | 45 | 2,30% | 1,40% |
| 4 | 0,00% | 38,8 | 3,10% | 0,40% | 0,00% | 52,3 | 3,90% | 1,10% | 2,80% | 60 | 1,80% | 0,50% |
| 5 | 0,00% | 47,8 | 2,80% | 0,30% | 0,40% | 65,1 | 3,40% | 0,70% | 3,20% | 76,9 | 1,90% | 1,10% |
| 6 | 0,00% | 57,4 | 2,00% | 0,10% | 0,00% | 79,8 | 3,30% | 1,10% | 0,80% | 90,6 | 1,80% | 1,30% |
| 7 | 0,00% | 68,9 | 2,30% | 0,20% | 0,40% | 93,1 | 3,60% | 0,20% | 1,20% | 105,4 | 2,30% | 0,80% |
| 8 | 0,00% | 77,5 | 2,40% | 0,40% | 0,00% | 104,8 | 3,50% | 1,20% | 1,20% | 122,3 | 2,30% | 0,70% |
| 9 | 0,00% | 85,7 | 2,20% | 0,30% | 0,00% | 119,6 | 3,50% | 0,70% | 2,80% | 139,4 | 1,90% | 0,50% |
| 10 | 0,00% | 97,9 | 2,00% | 0,20% | 0,40% | 132,6 | 3,40% | 0,80% | 2,40% | 157,5 | 2,00% | 0,50% |
Grafy �.2
| relativn� chyba | # nenalezen�ch stav� | pr�chod stavov�m prostorem |
 |
 |
 |
Nastaven� teploty tuhnut�
P�i tomto experimentu jsem m�nil Tf od 1 do 10.Tabulka �.3
| Tf | 50 klausul� | 75 klausul� | 90 klausul� | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| NF | time | AvgErr | BestErr | NF | time | AvgErr | BestErr | NF | time | AvgErr | BestErr | |
| 1 | 0,00% | 10,5 | 4,50% | 0,90% | 1,20% | 13,6 | 4,00% | 1,30% | 5,20% | 15,8 | 1,50% | 1,20% |
| 2 | 0,00% | 8,6 | 5,60% | 1,00% | 1,60% | 13 | 3,30% | 2,30% | 5,20% | 13,3 | 1,80% | 1,70% |
| 3 | 0,00% | 7,7 | 5,50% | 1,00% | 1,20% | 11,9 | 3,20% | 2,30% | 6,00% | 12,6 | 1,20% | 1,40% |
| 4 | 0,00% | 7 | 5,00% | 0,90% | 1,20% | 10,4 | 3,50% | 0,70% | 6,00% | 11,7 | 1,40% | 1,20% |
| 5 | 0,00% | 7,2 | 4,00% | 0,50% | 1,60% | 9,8 | 5,00% | 2,30% | 5,20% | 11,3 | 1,20% | 0,40% |
| 6 | 0,00% | 6,5 | 4,60% | 1,00% | 2,00% | 8,9 | 4,00% | 1,90% | 6,00% | 10,3 | 1,70% | 3,70% |
| 7 | 0,40% | 6 | 5,40% | 2,40% | 3,20% | 9,4 | 3,30% | 0,70% | 5,60% | 9,7 | 1,30% | 1,00% |
| 8 | 0,00% | 5,6 | 7,10% | 1,40% | 2,00% | 8,2 | 4,70% | 2,30% | 5,20% | 9,4 | 1,30% | 1,50% |
| 9 | 0,00% | 5,8 | 6,30% | 1,90% | 1,20% | 8,5 | 4,70% | 2,90% | 5,60% | 9,3 | 1,30% | 1,20% |
| 10 | 0,40% | 5,6 | 6,60% | 1,40% | 2,00% | 8,4 | 3,80% | 1,50% | 5,60% | 9,2 | 1,40% | 3,20% |
Graf �.3: Z�vislost relativn� chyby na teplot� tuhnut�
Nastaven� po��te�n� teploty
P�i tomto experimentu jsem m�nil T0 od 0,1 do 1. Pouze p�ipomenu, �e velikost po��te�n� teploty je vzta�ena k velikosti instance a to takto:T0 = T0_k * var_count * maxW.
Tabulka �.4
| T0_k | 50 klausul� | 75 klausul� | 90 klausul� | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| NF | time | AvgErr | BestErr | NF | time | AvgErr | BestErr | NF | time | AvgErr | BestErr | |
| 0,1 | 0,00% | 9,9 | 4,90% | 1,00% | 1,20% | 13 | 4,40% | 2,00% | 4,40% | 15,1 | 1,30% | 0,80% |
| 0,2 | 0,00% | 11 | 4,80% | 0,40% | 0,40% | 15,1 | 3,60% | 1,30% | 5,60% | 17 | 1,10% | 2,80% |
| 0,3 | 0,00% | 11,3 | 5,40% | 0,60% | 0,80% | 15,9 | 4,10% | 1,80% | 4,00% | 18,1 | 1,50% | 1,70% |
| 0,4 | 0,00% | 11,8 | 4,90% | 1,00% | 1,20% | 16,4 | 3,70% | 0,40% | 6,40% | 19,3 | 1,50% | 1,00% |
| 0,5 | 0,00% | 11,9 | 5,00% | 1,20% | 2,80% | 16,3 | 3,90% | 1,70% | 6,00% | 19,5 | 1,40% | 1,00% |
| 0,6 | 0,00% | 12,3 | 5,40% | 0,60% | 1,60% | 17,6 | 4,70% | 1,10% | 5,60% | 20,4 | 1,40% | 0,90% |
| 0,7 | 0,00% | 12,6 | 5,00% | 0,80% | 2,00% | 17,9 | 4,00% | 2,20% | 4,40% | 21,4 | 1,50% | 0,70% |
| 0,8 | 0,00% | 12,9 | 5,40% | 0,80% | 0,80% | 17,3 | 4,70% | 2,60% | 5,20% | 20,7 | 1,10% | 1,00% |
| 0,9 | 0,00% | 12,9 | 5,00% | 0,40% | 1,20% | 18,1 | 4,10% | 1,30% | 5,20% | 21,1 | 1,80% | 0,70% |
| 1 | 0,00% | 13,6 | 5,00% | 0,40% | 1,20% | 18,5 | 3,90% | 2,60% | 5,20% | 21,1 | 1,50% | 1,80% |
Grafy �.4
| relativn� chyba | # nenalezen�ch stav� | pr�chod stavov�m prostorem |
 |
 |
 |
Sledov�n� po�tu nalezen�ch �e�en� a relativn� chyby na po�tu spu�t�n� algoritmu
Jeliko� algoritmus simulovan� ochlazov�n� je randomizovan�, d�v� p�i ka�d�m spu�t�n� jin� v�sledky. Pokud chceme zlep�it v�sledky, spust�me algoritmus v�cekr�t a z v�sledk� vybereme to nejlep��.Graf �.5: Z�vislost relativn� chyby na po�tu spu�t�n� algoritmu
Graf �.6: Z�vislost # nenalezen�ch �e�en� na po�tu spu�t�n� algoritmu
Z�v�r
Algoritmus simulovan� ochlazov�n� je pom�rn� snadn� na implementaci. Jako nejd�le�it�j�� krok vid�m ve spr�vn�m navrhnut� ohodnocovac� funkce, tak aby algoritmus nutila ke spr�vn�mu �e�en�.Vzta�en� parametr� k po�tu prom�nn�ch a maxim�ln� v�ze se uk�zalo spr�vn�. Pro instance, kter� byly k dispozici (20/50, 20/75, 20/91 - po�et prom�nn�ch / po�et klausul�), se uk�zalo toto nastaven� jako optim�ln�:
- Po��te�n� teplota T0 = 0,1 * var_count * maxW;
- Teplota tuhnut� Tf = 1
- Rychlost ochlazov�n� dT = 0,9
- Velikost equilibria equ = 1 * var_count;
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 u n�kter�ch m��en� chyb� �asov� z�vislost (ch�pav� �ten�� ji z popisu algoritmu snadno odvod�). 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.
- 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.
- Zv��en� po�tu opakov�n� v�po�tu jedn� instance zvy�uje procento nalezen�ch �e�en� a sni�uje chybu v�sledku. �asovou n�ro�nost line�rn� zvy�uje.
- Pro v�t�� po�et klausul� je obt�n�j�� nal�zt �e�en�