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í