k = 1/5
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í.
Problém řešte některou z pokročilých lokálních heuristik:
Vybral jsem si metodu simulovaného ochlazování, která se dá popsat následujícím pseudo-kódem:
TState annealing() {
t = initTemperature();
max = state = initState();
do {
do {
state = getNewState(state, t);
if(cost(state) > cost(max)) max = state;
} while(...);
t = coolDown(t);
} while(...);
return max;
}
TState getNewState(state, t) {
new = getNextRandomState(state);
Δ = cost(new) - cost(state);
if(Δ < 0) return new;
else {
r = getRandom(0..1);
if(r < exp(-Δ/t)) return new;
else return state;
}
}
Zde je mnoho parametrů k nastavování, můj postup a nastavení následuje...
Algoritmus a jeho parametry jsem testoval na rozličných instancích 3SAT (pro počet proměnných = 10, 20, 30, 40, 50, 60 a počet klauzulí v násobku 1x až 6x počet proměnných), celkem 150 instancí. Váhy pro jednotlivé proměnné jsem vygeneroval náhodně v rozsahu 0-9.
Vzhledem k tomu, že předem neznáme optimální řešení, vztahují se grafy většinou k úspěšnosti - nalezení alespoň nějakého řešení.
Pracovat jen s přípustnými stavy nelze - kdybychom nalezli algoritmus, který najde pro jeden přípustný stav sousední přípustný stav, nemusíme se žíháním vůbec zabývat. Stačilo by projít všechny přípustné stavy (je jich velice málo) a vybrat ten nejlepší.
V algoritmu je sousední stav - getNextRandomState - vygenerován jako stav, který má změněnu jednu proměnnou (nahodně zvolenou) = operace XOR
Jelikož chceme maximalizovat zisk - součet vah proměnných, které jsou ohodnoceny jedničkou, je maximální - základ je jasný. Algoritmus by však vůbec nehledal řešení, ale skončil by se všemi proměnnými nastavenými na 1. Musíme tedy diskvalifikovat nepřípustné stavy.
Výsledný vzorec: Σwixi - Σk*maxWeight
Druhá suma je přes počet klauzulí, které jsou ohodnoceny 0. maxWeight je maximální váha přes všechny proměnné. Parametr k jsem zkoušel volit následovně:
Závislost ukazuje pravděpodobnost nalezení řešení v závislosti na nastavení k. Nejvýhodnější zdá se být nastavení k = 3, pro vyšší čísla se čas výpočtu zbytečně prodlužeje.
Máme na výběr z několika možností:
Pokud vycházíme z již nalezeného řešení, tak pro problémy, které mají malý poměr řešení F(Y)=1 ku všem možným kombinacím ohodnocení proměnných (nebo správná řešení jsou ve stavovém prostoru vzdálena) se z tohoto lokálního minima nedostaneme a řešit problém touto metodou tak ztrácí smysl.
Vycházel jsem z náhodného ohodnocení proměnných, protože mně to umožnilo efektivněji využít možnost:
Celý algoritmus můžeme několikrát opakovat a vybrat nejlepší ohodnocení proměnných. Se zvyšujícím se počtem opakování se zvyšuje i pravděpodobnost nalezení lepšího řešení. Tato závislost je však přibližně logaritmická - nad určitý počet opakování je již přínos zanedbatelný a jen se prodlužuje čas výpočtu.
Závislost je pravděpodobnost nalezení správného řešení na počtu opakování. Nejvhodnější se zdá opakovat algoritmus 5krát a vybrat nejlepší řešení. (Z nějakého záhadného důvodu je hodnota 5 magická :o) a má lepší výsledky než vyšší čísla - i po několikerém opakování testu).
Zkoušel jsem několik vzorců pro výpočet počáteční teploty:
n - počet proměnných, m - počet klauzulí, k - koeficient (1/100 .. 10)
Podle grafy průběhů ve stavovém prostoru, se zdá, že na počtu klauzulí výpočet moc nezáleží (na poměru n/m však ano!)
Nejlépe si vedl první vzorec. Pro několik hodnot k uvádím graf:
Nejlepší výsledky dosahuje výpočet n * maxWeight / 20. Pro větší hodnoty k se na začátku zbytečně nic neděje, pro nižší můžeme přijít o lepší výsledek. (V grafu jsou vždy tři průběhy)
k = 1/5
k = 1/20
k = 1/50
Můžeme volit pevný počet opakování, nebo například v závislosti na počtu proměnných:
Jako optimální se jeví opakovat vnitřní smyčku 5 * počet proměnných. Pro větší koeficient je doba výpočtu opět zbytečně dlouhá.
Měnil jsem ho v rozmezí 0.8 až 0.95. Jinou metodu než násobení koeficientem jsem nezkoušel (exponenciální snižování, sigmoida, ...).
Koeficient ochlazení jsem zvolil 0,9.
k = .85
k = .9
k = .95
Zkoušel jsem test na teplotu (1 až 0.05) a zda se stav ve vnitřní smyčce alespoň jednou změnil.
Při testu pouze na teplotu běží algoritmus velice dlouho a ke konci se již nic významného neděje. Po přidání testu na změnu ve vnitřní smyčce se čas výrazně zkrátil a kvalitu řešení to téměř neovlivnilo.
V testovaném rozsahu (0.05 až 1) se výsledky pohybují na hranici statistické chyby. Zvolil jsem tedy ukončení algoritmu při teplotě 0.1
Různých nastavení parametrů existuje neskutečné množství, lze i vyzkoušet různé vzorce. Algotimus je svým založením náhodný a proto je třeba vyladit ho na co nejlepší poměr ceny řešení ku době výpočtu.
Algoritmus s výše popsaným nastavením byl na zkušebních instancích úspěšný na přibližně 88% (nalezl alespoň nějaké řešení). Kvalita vzhledem k maximalizaci zisku se těžko posuzuje, protže neznám optimální řešení. Podle zběžného pohledu a porovnáním jednotlivých běhů programu odhaduji, že se nalezená řešení pohybovala v průměru kolem 95% ceny optima.
Algoritmus si velice dobře poradil s jednoduššími instancemi, avšak při poměru počtu proměnných ku počtu klauzulí kolem 4 - 5 nalezl řešení jen výjimečně (cca 5% případů). To odpovídá poznatkům uvedeným v prezentaci Barta Selmana.
Čím větší šanci má algoritmus v "rozkmitu" (větší počáteční teplota, vyšší koeficient ochlazování, delší vnitřní smyčka, ...), tím déle trvá, je "náhodnější", ale má také větší šanci najit lepší řešení.