Úloha 6 - Problém vážené splnitelnosti booleovské formule (simulované ochlazování)

Zadání:

Je dána booleovská formule F proměnnný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.

Popis problému:

Problém je velmi podobný problému batohu. Věc buď v batohu byla(1) nebo nebyla(0). V tomto problému se nastavuje, zda je proměnná ohodnocena true(1) nebo false(0). Proto jsem mohl do značné míry využít kódu z předchozí úlohy. Na rozdíl od problému batohu, kde řešením byly všechny stavy, kromě těch, kdy byl batoh přetížen, je tento problém komplikovanější, neboť řešením může být pouze stav, kdy jsou všechny klauzule(termy) true. Těchto řešení může být samozřejmě více, ale optimální je pouze jedno. Jelikož ale nemám k dispozici k testovaným instancím optimální řešení, nemám možnost, jak optimalitu ověřit, případně jak moc se řešení nalezené programem liší od optimálního. Proto se v této zprávě zaměřím na úspěšnost nalezení nějakého řešení.

Pro připomenutí znovu popíšu pseudokód algoritmu:

 

Textové pole: ochlazovani() { t = pocatecniTeplota(); stav = pocatecniStav(); jm = jmenovatel(t); do { // vnejsi smycka do { // vnitrni smycka state = novystav(stav, jm); } while(...); t = ochlazeni(t); } while(...); } novyStav (stav, jm) { novy = nahodnyStav(stav); d = cena(stav) - cena(novy); if(d < 0) return novy; else { r = getRandom(0..1); if(r < exp(-d/jm)) return novy; else return stav; } }

 

červeně zvýrazněný výpočet určuje pravďepodobnost, že dojde k použití stavu s horším ohodnocením.

 

Stejně jako v předchozí úloze, lze nastavit několik parametrů algoritmu. Jak jsem je nastavil ve své práci já, je uvedeno zde (parametry jsem určil pomocí exp. vyhodnocení):

1.      počáteční teplota
(počet_klauzulí)/(počet_proměných) * (parametr počáteční teploty)

2.      zamrzající teplota
parametr zamrzající teploty

3.      konstanta equilibria
(počet proměnnćyh)*(parametr počtu testů)

4.      koeficient ochlazování
parametr ochlazování

Hlavním problémem řešení této úlohy pro mě byl způsob výpočtu ohodnocení stavu. Použil jsem tento vzorec:

ohodnocení =

kde N je počet proměnných, M je počet klauzulí, wmax je největší použitá váha.

 

Dalším problémem bylo určení jmenovatele do výpočtu exp(-d/jm). Jako jmenovatel jsem nemohl použít hodnotu teploty, protože poté by šance na využití stavu s horším ohodnoconím mohly být příliš malé.

Proto jsem se rozhodl, že se v řešení omezím na instance, kde maximální váha proměnné je 50. Tím jsem docílil toho, že jsem mohl určit přibližné rozdíly v cenách stavů, ve kterých je určitý rozdíl v počtu splněných klauzulí. Poté jsem si stvořil tabulku pravděpodobností, díky které jsem dospěl k výslednému vztahu pro výpočet jmenovatele:

jmenovatel = teplota*100*(parametr jmenovatele)

Parametr jsem použil proto, abych mohl pomocí experimentálního vyhodnocení určit ideální hodnotu, kterou by se měla teplota násobit.

 

 

Experimentální vyhodnocení:

Na základě experimentálního vyhodnocení chci nastavit co nejlepší parametry pro můj algoritmus. Poté porovnám výsledky dosažené pomocí nastaveného a nenastaveného algoritmu. Nakonec se pokusím zjistit, zdali je algoritmus použitelný i pro instance s vyšším počtem proměnných než je 20.

 

Nastavení parametrů jsem dodržoval toto, pokud není nikde uvedeno jinak:

 

Počet
proměnných

Počet
klauzulí

Parametr

počáteční teploty

Zamrzající
teplota

Ochlazovací

konstanta

Konstanta

equilibria

Parametr

jmenovatele

20

80

1

0.1

0.9

16

1.5

 

 

 

A.               Závislost řešení na parametru jmenovatele:

 

Nejprve jsem se pokusil určit, jak mám nastavit parametr jmenovatele. Změřil jsem tedy počty nalezených měření pro instance s 20 proměnnými. Pro každé měření jsem vygeneroval 5 instancí. Každou tuto instanci jsem testoval 20x. Každá hodnota je tedy průměr 100 hodnot získaných měřením.

 

V tabulkách udávám počet nalezených řešení a také poměr splněných klauzulí k počtu klauzulí dané instance.

Jelikož jsem volil mnoho možností, udávám samotnou tabulku.

B.                Závislost řešení na počtu klauzulí:

 

Nulový stav

Náhodný stav

Počet klauzulí

Počet
stavů

Počet

 nalezených řešení

Kvalita

řešení

Počet

 nalezených řešení

Kvalita

řešení

20

7040

2179,58

0,9995

2172,87

1,0000

30

8320

1559,03

1,0000

1567,08

1,0000

40

9280

749,66

1,0000

749,69

1,0000

50

9920

358,06

1,0000

353,85

1,0000

60

10560

82,75

0,9992

81,92

0,9997

70

10880

81,36

1,0000

81,37

0,9994

80

11520

10,17

0,9959

9,71

0,9959

Je vidět, že volba náhodného stavu nemá na počet nalezených řešení veliký vliv. Proto v dalším měření budu používat nulový poćáteční stav.Z grafů je také patrné, že poćet nalezených řešení klesá s rostoucím poměrem počet klauzulí/počet proměnných. V dalším měření budu pracovat s formulemi o 80 klauzulích. Zajímavé mi přijde to, že i přes vysoký počet nalezených řešení se stane, že konečný výsledek nesplňuje podmínku, aby výsledná formule byla true. To je podle všeho dáno tím, že se v době kdy je vyšší teplota nastaví konfigurace proměnných tak, že je formule nesplnitelná a při nižších teplotách již algoritmus není schopen se s tím vypořádat. Možností jak to odstranit je více – např. zvýšit ohodnocení splněné klauzule, popř. zavést bonus za splněnou formuli. Lze ale předpokládat, že by v takovém případě došlo k snížení množství nalezenćyh řešení. – dotestovat!!

B. Závislost řešení na ochlazovací konstantě

Ochlazovací
konstanta

Počet
stavů

Počet

 nalezených řešení

Kvalita

řešení

0,8

4480

436,43

0,9950

0,85

6080

535,35

0,9955

0,9

9280

738,10

0,9960

0,95

18880

1154,83

0,9950

0,96

23680

1515,50

0,9981

0,97

31680

1795,56

0,9975

0,98

47680

2305,50

0,9970

0,99

95680

3149,81

0,9977

 

 

 

Se zvyšující se konstantou ochlazování stejně jako u batohu exponenciálně roste počet navštívených stavů. Kvalita řešení mírně roste, stejně tak počet nalezených řešení. Na základě naměřených hodnot jsem si vybral ochlazovací konstantu 0,95.

D. Závislost přesnosti řešení a počtu stavů na konstantě equilibria

Konstanta

equilibria

Počet
stavů

Počet

 nalezených řešení

Kvalita

řešení

5

6,58

3600

0,9946

10

8,56

7200

0,9959

15

10,07

10800

0,9949

20

10,53

14400

0,9966

25

11,20

18000

0,9965

30

11,50

21600

0,9969

40

11,71

28800

0,9974

50

12,26

36000

0,9966

 

S rostoucí konstantou equilibria roste složitost algoritmu, ale tím také počet nalezených řešení. Kvalita řešení se nám jeví jako nejlepší u konstanty 40. V případě hodnoty 50 je nejvyšší počet nalezenćyh řešení.Jelikož nechci, aby výpočet trval neúměrně dlouho, tak volím hodnotu 20.

E. Závislost přesnosti řešení a počtu stavů na konstantě iniciální teploty

Násobící konstanta
počáteční teploty

Počet
stavů

Počet

 nalezených řešení

Kvalita

řešení

0,2

6400

9,45

0,995125

0,5

9280

10,56

0,996125

1

11520

10,39

0,996875

1,5

12480

10,48

0,99575

2

13440

10,08

0,996

3

14720

10,31

0,9955

4

15680

10,49

0,996875

S rostoucí konstantou mi logaritmicky roste počet navštívených stavů stavového prostoru. Počet nalezených řešení je spíše náhodný (pokud násobitel není velmi malý) – to si vysvětluji tím, že s nynějším nastavením ohodnocení stavu má algoritmus už tak v počátku svého běhu dostatek volnosti, takže navýšení úvodní teploty nemá na běh algoritmu příliš veliký vliv. Na kvalitu řešení parametr očividně také nemá žádný vliv. Vybírám si hodnotu 0,5.

Porovnání řešení s vybranými parametry:

Nyní použiji vybrané konstanty a porovnám výpočty s neoptimalizovaným algoritmem. V následující tabulce jsou uvedeny zvolené defaultní parametry simulovaného ochlazování. Tabulky obsahují pouze nově naměřené hodnoty, v grafech je pak srovnání s původním nastavením.

 

Počáteční
teplota

Zamrzající
teplota

Ochlazovací

konstanta

Konstanta

equilibria

Puvodní hodnoty:

1

0.1

0.9

16

Vybrané hodnoty:

0,5

0.1

0.95

20

Závislost řešení na počtu klauzulí:

 

Původní parametry

Vybrané parametry

Počet klauzulí

Počet
stavů

Počet

 nalezených řešení

Kvalita

řešení

Počet
stavů

Počet

 nalezených řešení

Kvalita

řešení

20

7040

2011,49

1,000

12800

3339,31

1,000

30

8320

1500,53

1,000

16000

2801,12

1,000

40

9280

714,68

1,000

18000

1328,72

1,000

50

9920

379,12

0,999

20000

663,15

1,000

60

10560

87,87

1,000

21200

124,39

1,000

70

10880

78,88

0,999

22400

107,08

1,000

80

11520

9,30

0,996

23600

11,79

0,996

 

Závěr:

Podle předpokladů se mi podařilo vyladěním parametrů simulovaného ochlazování zlepšit nalezení kvalitnějších řešení za cenu vyšší složitosti. Nicméně nárůst kvality není o mnoho vyšší. Při měření v závislosti na počtu parametrů se mi nepodařilo najít více splněných stavů, u měření v závislosti na počtu termů jsou výsledky o něco lepší.
Hlavním problémem, proč se mi nepodařilo najít lepší výsledky bude ve funkci pro ohodnocení stavů. Určitě to chce vymyslet nějaké sofistikovanější řešení. Už během měření jsem předpokládal, že vyladěním parametrů se to o mnoho nezlepší, napadlo mě ale během něj založit ohodnocení stavů také v závislosti na nastavené proměnné. Cenou proměnné by například mohl být počet termů, které by nastavením určité proměnné byly true. To už je ale zase o dalších a dalších experimentech, možná by to pomhlo, možná ne.

Pozn: I když jsem měření prováděl v závislosti na počtu navštívených stavů, zmíním zde konfiguraci, na které jsem měření provádel. Měření probíhala na stroji s procesorem Intel Core Duo 1.667 GHz, 512 MB RAM, Win Xp Home SP2, MSVC 7.1 v debug módu.

Zdrojové kódy v C++ a data:

uloha6.zip
satgen.zip
data.zip