6. Úloha

Jan Doležel

Zadaní

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:

Řešení

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...

Nastavení parametrů

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

Výpočet ohodnocení stavu

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.

Počáteční stav

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:

Počet opakování

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).

Počáteční teplota

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

Vnitřní smyčka

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á.

Koeficient ochlazení

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

Vnější smyčka

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

Závěr

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í.