36PAA - Problém vážené splnitelnosti booleovské formule - simulované ochlazování

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ů):

Zdrojové kódy (C#)

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:

Implementoval jsem ji tak, že sečte váhy proměnných nastavených na true a od nich odečte maximální váhu proměnné pro každou nesplněnou klausuli. Z toho vyplívá, že pokud je formule splněná vrací součet vah proměnných.

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;
equ = equ_k * var_count;

kde 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

dT50 klausulí75 klausulí90 klausulí
NFtimeAvgErrBestErrNFtimeAvgErrBestErrNFtimeAvgErrBestErr
0,9950,00%223,71,70%0,20%0,00%275,92,90%0,20%0,80%316,21,90%0,80%
0,9450,00%17,34,40%0,60%0,40%25,74,20%1,80%4,80%27,71,50%0,50%
0,8980,00%9,54,20%0,70%2,40%13,64,20%1,70%5,20%14,91,30%2,10%
0,8530,00%6,36,50%1,40%1,60%8,74,40%3,70%7,20%10,11,30%0,90%
0,810,00%4,66,60%2,70%3,20%6,43,80%4,00%9,60%7,50,90%0,70%
0,770,00%47,20%3,90%5,20%5,23,30%4,30%10,00%6,20,50%0,80%
0,7310,00%3,16,90%4,30%5,60%4,43,60%6,00%11,60%4,80,60%3,50%
0,6950,40%2,95,50%4,70%6,80%3,82,80%4,70%12,00%4,10,70%3,00%
0,660,00%2,47,70%5,00%4,80%3,33,50%7,40%13,20%3,81,60%6,20%
0,6270,40%2,39,00%4,00%6,80%2,83,40%5,90%13,20%3,40,90%3,30%
0,5960,80%25,30%4,30%8,00%33,30%4,70%14,40%3,20,10%0,60%
0,5662,80%1,95,90%3,30%9,20%2,82,90%6,90%12,00%2,80,90%2,30%
0,5382,00%1,68,90%8,00%10,80%2,32,70%6,10%12,80%2,40,50%2,20%
0,5111,60%1,510,10%10,60%10,80%1,92,30%9,00%12,40%2,41,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_k50 klausulí75 klausulí90 klausulí
NFtimeAvgErrBestErrNFtimeAvgErrBestErrNFtimeAvgErrBestErr
10,00%10,94,60%0,50%1,20%13,13,30%1,70%6,00%15,21,50%0,90%
20,00%19,53,40%0,20%0,00%26,24,50%3,00%2,40%30,12,00%2,10%
30,00%28,92,90%0,20%0,00%39,24,50%1,30%2,40%452,30%1,40%
40,00%38,83,10%0,40%0,00%52,33,90%1,10%2,80%601,80%0,50%
50,00%47,82,80%0,30%0,40%65,13,40%0,70%3,20%76,91,90%1,10%
60,00%57,42,00%0,10%0,00%79,83,30%1,10%0,80%90,61,80%1,30%
70,00%68,92,30%0,20%0,40%93,13,60%0,20%1,20%105,42,30%0,80%
80,00%77,52,40%0,40%0,00%104,83,50%1,20%1,20%122,32,30%0,70%
90,00%85,72,20%0,30%0,00%119,63,50%0,70%2,80%139,41,90%0,50%
100,00%97,92,00%0,20%0,40%132,63,40%0,80%2,40%157,52,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

Tf50 klausulí75 klausulí90 klausulí
NFtimeAvgErrBestErrNFtimeAvgErrBestErrNFtimeAvgErrBestErr
10,00%10,54,50%0,90%1,20%13,64,00%1,30%5,20%15,81,50%1,20%
20,00%8,65,60%1,00%1,60%133,30%2,30%5,20%13,31,80%1,70%
30,00%7,75,50%1,00%1,20%11,93,20%2,30%6,00%12,61,20%1,40%
40,00%75,00%0,90%1,20%10,43,50%0,70%6,00%11,71,40%1,20%
50,00%7,24,00%0,50%1,60%9,85,00%2,30%5,20%11,31,20%0,40%
60,00%6,54,60%1,00%2,00%8,94,00%1,90%6,00%10,31,70%3,70%
70,40%65,40%2,40%3,20%9,43,30%0,70%5,60%9,71,30%1,00%
80,00%5,67,10%1,40%2,00%8,24,70%2,30%5,20%9,41,30%1,50%
90,00%5,86,30%1,90%1,20%8,54,70%2,90%5,60%9,31,30%1,20%
100,40%5,66,60%1,40%2,00%8,43,80%1,50%5,60%9,21,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_k50 klausulí75 klausulí90 klausulí
NFtimeAvgErrBestErrNFtimeAvgErrBestErrNFtimeAvgErrBestErr
0,10,00%9,94,90%1,00%1,20%134,40%2,00%4,40%15,11,30%0,80%
0,20,00%114,80%0,40%0,40%15,13,60%1,30%5,60%171,10%2,80%
0,30,00%11,35,40%0,60%0,80%15,94,10%1,80%4,00%18,11,50%1,70%
0,40,00%11,84,90%1,00%1,20%16,43,70%0,40%6,40%19,31,50%1,00%
0,50,00%11,95,00%1,20%2,80%16,33,90%1,70%6,00%19,51,40%1,00%
0,60,00%12,35,40%0,60%1,60%17,64,70%1,10%5,60%20,41,40%0,90%
0,70,00%12,65,00%0,80%2,00%17,94,00%2,20%4,40%21,41,50%0,70%
0,80,00%12,95,40%0,80%0,80%17,34,70%2,60%5,20%20,71,10%1,00%
0,90,00%12,95,00%0,40%1,20%18,14,10%1,30%5,20%21,11,80%0,70%
10,00%13,65,00%0,40%1,20%18,53,90%2,60%5,20%21,11,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í: Pro tyto hodnoty se nepodařilo nalézt řešení maximálně ve 14% případů a chyba oproti nejlepšímu řešení dodaného ze vstupu byla 2%. K těmto výsledkům velkou měrou přispívá opakování výpočtu každé instance 5x.
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: