Uloha 1

Řešení problému batohu metodou hrubé síly a jednoduchou heuristikou

Specifikace úlohy: [[homeworks:01:start|]]

Možná řešení: Problém batohu můžeme řešit buď exaktně (dostaneme přesné řešení), nebo aproximací (dostaneme přibližné řešení). Exaktní přístup prochází všechny varianty a zjistí nejlepší z nich - z toho vyplývá, že bude mít pro NP těžkou úlohu velikou složitost, standardně exponenciální. Aproximační přístup jde na úlohu jiným způsobem, protože mu nejde o nejlepší řešení, ale o “přijatelné” řešení. Díky tomu nemusí procházet všechny varianty, a tak je běžně mnohem rychlejší než exaktní řešení.

Kód řešení: {{:student:blazeva1:bag_solution.zip|}}

Exaktně

Exaktní řešení úlohy batohu je NP těžké. Vyřešit zadání exaktní metodou pro N > 22 trvá nepoměrně dlouho, tak nejsou výsledky zahrnuty.

Implementace projití všech variant využívá bitové reprezentace velkého celočíselného typu v C++ (bit čísla reprezentuje jestli je věc v batohu). Složitost je exponenciální.

Měření (velikost problému, počet instancí, průměrný čas na instanci v mikrosekundách):

N inst time 4 275 182,567 10 12 4481 15 1 187094 20 1 7160340 22 1 30707600

{{:student:blazeva1:ex.png|}}

Aproximací

Díky aproximaci podle poměru ceny/váhy můžeme nějaké řešení dostat v téměř lineárním čase.

Implementace spočte poměr cena/váha, tyto objekty seřadí od nejlepšího a snaží se batoh plnit objekty prioritně podle tohoto poměru

Měření (velikost problému, počet instancí, průměrný čas na instanci v mikrosekundách, relativní chyba, maximální relativní chyba):

n inst time chyba max chyba 4 1973 253,531 0,0217451 0,363636 10 1103 453,509 0,012862 0,114801 15 833 600,313 0,00475892 0,0854271 20 644 777,005 0,00600086 0,0843373 22 620 807,639 0,00686694 0,0722892 25 552 907,172 0,00498356 0,0367893 27 549 911,925 0,0050165 0,106017 30 509 982,686 0,00493019 0,0551378 32 485 1031,65 0,00341192 0,0334076 35 418 1196,23 0,00280185 0,0460922 37 419 1195,2 0,00343609 0,0819672 40 396 1263,35 0,00199487 0,0233723

{{:student:blazeva1:aprox.png|}} {{:student:blazeva1:chyba.png|}}

Závěr

Naměřená data odpovídají očekávání. Exaktní řešení vykazuje exponenciální časovou složitost O(2^n) a aproximační má kuli řazení časovou složitost logaritmicky lineární O(n log n).

Pozorujeme, že se relativní chyba aproximačního řešení se zvětšujícím se problémem zmenšuje, to si vysvětluji tím, že průměrný (náhodný) případ batohu je se zvětšujícím se počtem věcí pro aproximaci přínosný, protože dostane více věcí s různým poměrem cena/váha a pravděpodobnost, že věc s dobrým poměrem nebude v batohu se zmenšuje. Nesmíme však opominout worscase případ, tj. kdyby se někdo snažil aproximačnímu řešení podstrčit “špatná” data, tak si vede mnohem hůř než pro případ náhodný (porovnejme výsledky měření chyb).


Uloha 2

Řešení problému batohu dynamickým programováním, metodou větví a hranic a aproximativním algoritmem

Specifikace úlohy: [[homeworks:02:start|]]

Problém batohu můžeme řešit nejen pomocí exaktního algoritmu a jednoduchého aproximativního algoritmu podle poměru cena/váha - další řešení jsou sice od těchto odvozena, ale vykazují poměrně jiné chování. Jednotlivé metody jsou popsány uvnitř této zprávy.

Kód řešení: {{:student:blazeva1:mainfpx2.cpp.tar|}}

Metoda větví a hranic

První je [[homeworks:knapsack:branchbound|]], která je odvozená od exaktního řešení. Opět prohledává celý prostor, ale vynechává zbytečné větve (váha už je moc veliká, nebo součet zbytku cen nemůže vylepšit řešení). Tudíž, očekáváme stejný výsledek jako u exaktního řešení, jen v rychlejším čase. Je nutno podotknout, že složitost v nejhorším případě je stále exponenciální, ale takovéto zlepšení v praxi znamená znatelné zlepšení doby výpočtu (pokud nejsme ochotni obětovat přesnost výsledku), i přesto, že v asymptotické analýze takové konstanty zanedbáváme.

N naive b&b 4 1.04 2.82 10 89.64 10.26 15 3801.38 41.48 20 140952 951.28 22 600696 3786.02

{{:student:blazeva1:naive_a_bab3.png|}}

V grafu je pro čas použita logaritmická stupnice (jinak z něj nešlo nic vyčíst). Vidíme, že naivní imlementace odpovídá v grafu exponenciální funkci. Dále pozorujeme chování řešení s prořezáváním - to že pro velmi malá data má režii, která je na grafu až přehnaně znát. Dále vidíme, že si pro stejná data v průměru vede mnohem lépe než exaktní řešení. Avšak stejně jako exaktní řešení se rychle dostává do neúnosné časové náročnosti.

Metoda dynamického programování

Obecně nám [[homeworks:knapsack:dynprog|]] poskytne řešení, které zvýší paměťovou složitost řešení, avšak zato nám poskytne lepší složitost časovou - což je jedním ze základních principů zlepšení časové složitosti algoritmu vůbec. Z praktických důvodů jsem se rozhodl udělat řešení pomocí dynamického programování přes dekompozici podle cen (je dále použito v FPTAS). Dynamické řešení si pamatuje všechny mezivýsledky pro kombinace započítání věcí do batohu. Díky chytrému předpočítání je výhoda v tom, že nemusíme rekurzí procházet všechny další možnosti podstromu, ale pouze syny aktuálního uzlu. To vede na pseudopolynomiální řešení, které kromě počtu věcí navíc závisí na součtu cen přes všechny věci. Lze vidět, že toto řešení půjde efektivně použít pro řešení poměrně velikých problémů (mnoho věcí batohu), kde však máme omezenou cenu.

N naive b&b dynamic 4 1.04 2.82 44.06 10 89.64 10.26 305.28 15 3801.38 41.48 785.72 20 140952 951.28 1378.42 22 600696 3786.02 1734.36 25 ? 26885.7 2283.66 27 ? 104136 2666.44 30 ? ? 3350.36 32 ? ? 3699.68 35 ? ? 4507.2 37 ? ? 4891.46 40 ? ? 6143.5

{{:student:blazeva1:dyn2.png|}}

Na tomto měření vidíme, že toto řešení má velikou režii, ale i přes to má složitost mnohem lepší než prořezávání. Díky tomu, že jsou vstupní zadána s rozumnou velikostí cen, tak se tento algoritmus jeví jako mnohem lepší, nezapomeňme však, že pro určitá zadání by byl zcelka nepoužitelný (i pro málo instancí, ale veliké ceny). Prořezávání trvalo nepřiměřeně dlouho už při 27 instancích, zato toto řešení všechny měřené instance vyřešilo v rozumném čase.

FPTAS algoritmus

Pro tento problém existuje také [[homeworks:knapsack:apx|plně polynomiální časově aproximační schéma]]. Takový algoritmus pak umožňuje pro zadanou přesnost epsilon řešit problém v polynomiálním čase (0 < epsilon <= 1). Algoritmus je vyvozen z dynamického řešení (je vlastně úplně stejný), akorát u vstupních cen se zanedbá několik posledních bitů. Časová náročnost se se zmenšující se chybou zvětšuje nejhůře polynomiálně (jinými slovy je polynomiálně závislý na přesnosti řešení). Pro epsilon 0 je algoritmus stejný jako řešení dynamické, a pro dané epsilon si spočte kolik bitů může maximálně odebrat, aby největší chyba byla menší než právě zadané epsilon. Pokud chceme u algoritmu měřit chybu co nejpřesněji, tak by bylo potřeba to dělat reverzně … totiž zkusit jej spustit pro různé hodnoty odebraných bitů a pak z toho dopočítat jaké bylo původní epsilon. Mě však zajímalo, jak se bude algoritmus chovat pro konkrétní zadané epsilon (jestli ho opravdu nepřesáhne) a jaká bude časová složitost pro zadaný počet odebraných bitů.

{{:student:blazeva1:fptas_eps4.png|}}

Všimněme si na obr. jak se chovají fce pro různě určený počet zanedbaných bitů. Za každý zanedbaný bit se funkce času algoritmu propadne na polovinu. To dává smysl, protože zanedbání bitu odpovídá dělení dvěma, a tak takové chování je očekávané. Pro vytvoření FPTAS algoritmu toto chování zanedbáváni bitů spojíme s požadovanou nejhorší chybou přes vzoreček b = max(0,(int)log2(eps*maxItemCost/noOfItems)), to by nám mělo zaručit, že největší chyba na libovolných datech je epsilon.

{{:student:blazeva1:fptas_eps5.png|}} {{:student:blazeva1:fptas_max.png|}}

Měření ukazuje jak se chyba s větším epsylonem zhoršuje. Vidíme že všechna měření odpovídají maximální chybě (jsou vždy menší jak 0.1) a zároveň se nestane, že pro větší eps by bylo lepší řešení než pro menší eps., což jsme očekávali. Nutno podotknout, že eps=0 v grafu není vidět, protože má nulovou chybu.

Závěr

Díky tomu, že má problém batohu FPTAS algoritmus, tak je považován za jeden z jednodušších z množiny NP problémů. Různé implementace řešení tohoto problému přes měření ukazují své výhody a nevýhody – prořezávání má stále exponenciální složitost, dynamika je závislá na max. ceně, a FPTAS funguje pěkně, pokud nám nevadí, že obětujeme přesnost řešení.


Uloha 3

Experimentální hodnocení kvality algoritmů

Specifikace úlohy: [[homeworks:03:start|]]

Problém batohu můžeme řešit nejen pomocí exaktního algoritmu a jednoduchého aproximativního algoritmu podle poměru cena/váha - další řešení jsou sice od těchto odvozena, ale vykazují poměrně jiné chování. Jednotlivé metody jsou popsány uvnitř této zprávy.

Kód řešení: {{:student:blazeva1:paa3.cpp.tar|}}

Prozkoumání citlivosti metod řešení problému batohu na parametry instancí generovaných generátorem náhodných instancí.

Prvně zkontrolujeme podezření uvedené před samotným zadáním úkolu, to jest:

1) výpočetní náročnost dynamického programování může být citlivá na maximální cenu,

Z implementace řešení přes dynamiku je vidět, že vytváří pole veliké podle maximální ceny a to potom necitlivě na konkrétních cených jednotlivých batohů prochází. Z tohoto jde očekávat, že závislost doby běhu programu na maximální ceně bude lineární.

{{:student:blazeva1:3-1-dyncost.png|}}

Měření odpovídá očekávání. Obával jsem se, že se bude algoritmus pro různý počet věcí chovat jinak, ale všechna měření (pro 4, 10 a 100 věcí) nakonec ukázaly stejné chování.

2) výkon metod, které vycházejí ze stavu „prázdný batoh“ se může lišit od metod, vycházejících ze stavu „plný batoh“ podle poměru celková váha / kapacita batohu,

Tento výrok nemohu do detailu ověřit, protože implementaci algoritmu, který vychází ze stavu plný batoh nemám. Z algoritmů, které jsme měli implementovat je na vycházející stav závislý BAB. Je tedy namístě u tohoto reprezentanta změřit domu běhu v závoslosti na poměru součtu vah a kapacity batohu (parametr m).

{{:student:blazeva1:3-2-babtom.png|}}

Měření odhaluje, že doba běhu BAB je nejdelší pro instance kde je nastaveno, že kapacita batohu je 0.4 ze součtu vah všech věcí. BAB algoritmus je velmi rychlý pro instance s věcmi s malou celkovou váhou, protože pak se může mnoho věcí dát do batohu a už není mnoho možností jak to zlepšit. Je také rychlý pro instance s věcmi, které jsou v poměru s batohem veliké, protože v tu chvíli se do batohu nedá moc věcí dát, a tak se mnoho možností rychle prořeže.

3) není jasné, jakou roli hraje granularita instance (převaha malých nebo převaha velkých věcí).

K tomuto se ještě vrátím dále.

Měření pro různé parametry

Hrubá síla

Implementace metodou hrubé síly je citlivá pouze a jenom na počtu věcí - prochází totiž všechny kombinace a v každé udělá díl práce nezávislý na čemkoli jiném. Toto měření je již provedeno v předchozích úkolech, tak se soustředím na naměření dalších algoritmů.

Porovnání BAB, DYN a APPROX metod pro změnu různých parametrů:

Maximální váha věcí

Žádný algoritmus není závislý na váze maximální věci, a proto na maximální váze věci nezáleží. Jediný problém který by se mohl vyskytnout je přetečení datového typu.

{{:student:blazeva1:3-3-maxw.png|}} {{:student:blazeva1:3-3-maxw-error.png|}}

Maximální cena věcí

Jediný algoritmus, který je závislý na maximální ceně věcí je dynamický, a tak pozorujeme jeho lineární závislost na tomto parametru.

{{:student:blazeva1:3-3-maxc.png|}} {{:student:blazeva1:3-3-maxc-error.png|}}

Poměr kapacity batohu k sumární váze

Ani dynamika ani aproximační algoritmus nic chytrého při procházení nedělají, a tak pouze branch and bounds, který v zácislosti na zbývajících prvcích procházení dělá závěr jestli pokračovat nebo ne, je závislý na tomto parametru. Proč se toto děje jsem již diskutovat výše (otázka 2).

Aproximativní algoritmus dosahuje pro větší poměr lepších výsledků, protože počet kombinací vynechaných předmětů se zmenšuje a s tím i šance, že se aproximativní algoritmus netrefí do rozumného výsledku.

{{:student:blazeva1:3-3-m-e.png|}} {{:student:blazeva1:3-3-m-error.png|}}

Granularita

Granualita určuje v závislosti na hodnotě parametru d jestli bude v batohu větší pravděpodobnost velkých (d=1) nebo malých věcí (d=-1). Záleží tedy na tom jak nastavíme parametr d.

Pro měření d=1 (více velkých věcí) se časová složitost algoritmů zásadně nemění. Aproximační algoritmus dosahuje lepších výsledků když je více velkých věcí z důvodů popsaných otázce 2).

{{:student:blazeva1:3-3-granpos.png|}} {{:student:blazeva1:3-3-granposerror.png|}}

Pro měření d=-1 (více malých věcí) opět není časová složitost pozměněna. Aproximační algoritmus nemá o mnoho lepší výsledky, protože více malých věcí mu nezlepší šanci trefit se do lepšího výsledku.

{{:student:blazeva1:3-3-granneg.png|}} {{:student:blazeva1:3-3-grannegerror.png|}}

Závěr

Opět jsme si potvrdili pseudopolynomiální charakteristiku dynamického řešení a nově zjistili jak branch and bounds reaguje na změnu poměru kapacity batohu na celkový součet vah. Obecně se pak ukazuje trend aproximačního algoritmu pro lepší výsledky v případech, kdy nemá na výběr z mnoha možností.


Uloha 4

Experimentální hodnocení kvality algoritmů

Specifikace úlohy: [[homeworks:04:start|]]

Kód řešení: {{:student:blazeva1:paa4.tar|}}

Stručný popis zvoleného algoritmu

Simulované ochlazování je velmi obecný algoritmus pro aproximační řešení problémů s velkým stavovým prostorem. Myšlenka algoritmu je dovolít nejen zlepšení výsledku, ale i jeho zhoršení. Díky tomuto přístupu se pak algoritmus může snáze dostat z lokálního minima a prohledat část stavového prostoru, kde se nachází lepší výsledky.

Má implementace se takřka do písmene drží přednášky PAA. Funkce frozen se dívá jestli hodnota P přijetí špatného řešení dává smysl. Funkce cool ochladí teplotu podle koeficientu chlazení. Funkce equilibrium se dívá jestli je počet vyzkoušených kroků > 2*věcí nebo přijetých > věcí (zabrání pomalému chlazení při nízkých teplotách).

Program přijímá několik parametrů: * HEAT počáteční teplota * ANNEAL koeficient chlazení * INITPROB počáteční šance přijetí horšího řešení * DELTAPAR hodnota rozdílu horšího výsledku pro kterou bude platit šance přijetí INITPROB

Sousední stav se najde tak, že je přidána náhodná věc a pak se ubírá dokud není váha pod zadanou mezí.

Zhodnocení Vašich experimentů.

Pro jednu instanci se hodnota řešení postupně v iteracích vyvijí k lepšímu. Vidíme, že na začátku (rozsah 0-30) algoritmus zkouší mnoho různých řešení, ale i přesto, že dovoluje značné zhoršení, tak se výsledek zlepšuje. Dále (rozsah 30-60) se pravděpodobnost pro větší zhoršení stále zmenšuje, a tak skoku vzhůru jsou podstatně menší, řešení se přes malé hrbolky dostává do stále lepších řešení. Nakonec (rozsah 60-120) se algoritmus dohledává lokálním maximum, protože jsem sestup do lokálního maxima neimplementoval, ale nechal jsem aby se s tím algoritmus popral sám.

{{:student:blazeva1:4-1-result.png|}}

Experimentujte s různými nastaveními parametrů

Pro různé hodnoty koeficientu chlazení bylo změřeno následující chování relativní chyby a času výpočtu. Lze vidět, že pomalejší ochlazování vede k delšímu běhu algoritmu (několikanásobně), ale zato má lepší výsledky.

{{:student:blazeva1:4-2-chybaacasnachlazeni.png|}}

Hodnoty pravděpodobnosti přijetí horšího řešení ovlivňují dobu běhu a relativní chybu také. Avšak všiměme si, že oboje ovlivňuje mnohem méně, než rychlost ochlazování.

{{:student:blazeva1:4-4-chybaacasnastartp.png|}}

Rychlost běhu algoritmu a relativní chyba nejsou závislé na počáteční teplotě, protože jsem ve svém kódu hodnoty pro výpočet parametrů ve výrazu pro pravděpodobnost přijetí horšího výsledu dopočítal ze vstupu. Díky tomu se celý výraz mění v závislosti na počáteční teplotě a ve výsledku tedy nemá na výpočet vliv.

{{:student:blazeva1:4-5-errcasnateplu.png|}}

Počáteční hodnota pro nastavení zadané hodnoty pravděpodobnosti přijetí má vliv na dobu výpočtu, ale ne na výsledek.

{{:student:blazeva1:4-6-errcasnainitp.png|}}

=== Závěr === Simulované ochlazování je rozumný aproximativní algoritmus. Díky procházení pouze jednoho stavu najednou nemá velké nároky, ale jeho schopnost najít dobré řešení hodně závisí na dobrém nastavení parametrů. Jako u mnoha algoritmů se i zde objevuje tradeoff času za lepší výsledek.

U knapsack problému se algoritmu docela daří. Často najde exaktní řešení a pokud ne, tak často najde velmi dobré řešení (rel chyba do 1%).


Uloha 5

Řešení problému vážené splnitelnosti booleovské formule pokročilou iterativní metodou

Specifikace úlohy: [[homeworks:05:start|]]

Kód řešení: {{:student:blazeva1:paa5.tar.gz|}}

Úkolem je vytvořit program, který bude řešit úlohu 3-SAT, tj. splnitelnost booleaovské formule v CNF.

Zvolené řešení

Pro implementaci řešení splnitelnosti booleovské formule jsem zvolil simulované ochlazování. Popis vlastní implementace je dále v textu, nejdříve se však zastavíme u generování instancí problému 3-SAT.

Generování testovacích instancí

Pro generování náhodných isntancí jsem vycházel z proskytnutého generátoru pro knapsack (načítání parametrů). Tento generátor vvytváří daný počet ‘N’ instancí 3-SAT problému s ‘l’ proměnnými, ‘c’ klauzulemi, ’m’ maximální váhou a ‘p’ pravděpodobností zápornosti literálu. Aby bylo rozmístění literálů v klauzulích náhodné a zároveň se použili všechny proměnné, tak jsou vybrané literály vkládány na náhodná nevyplněná místa (dokud je z čeho vybírat) a zbytek je doplněn náhodnými literály na náhodná nevyplněná místa.

Díky implementaci takto parametrizovaného generátoru bude jednoduché testovat chování vlastní implementace simulovaného žíhání na 3-SAT problému pro různě nastavené instance.

Poznámka ke grafům

Pro úplnost jsem do grafů pod titul zahrnul data, se kterými byl graf vytvořen. V závorce jsou parametry generátoru (-l literálů -c klauzulí -p p_negace -m max_val) a v hranaté závorce jsou parametry algoritmu [-t init_teplo -a chlazeni -d rozdil_horsiho_reseni -p p_prujeti_horsiho_o_d -c zpomaleni_penalizace]

Algoritmus řešení

Vlastní implementace probíhala úpravou implementace ze 4. úlohy (implementace pro knapsack problém). Jelikož byla implementace navržena dosti obecně byla její úprava na tento úkol poměrně jednoduchá. Bylo však potřeba do detailu promyslet několik věcí:

  • Jak reprezentovat stav prostoru?
  • Jak reprezentovat zadání?
  • Jak se bude generovat soused?
  • Budou se procházet i nevalidní oblasti stavového prostoru?

Na každou z těchto otázek je třeba při implementaci odpovědět a zvážit alternativy.

Použité struktury

Pro reprezentaci stavu prostoru byla vytvořena třída State. Ta ukládá jednak ohodnocení každé proměnné, pak součet vah proměnných nastavených na 1 a nakonec jestli je stav validním řešením. Struktura také obsahuje utilitní metody pro: přechod do sousedního stavu, přepočet sumární váhy a získání váhy (důležité u relaxace).

Zadání přijímá program ze standardního vstupu a vytváří list Klauzulí, tříd které obsahují Literály. Literály si pamatují id a jestli jsou negativní, mají také metody pro vyhodnocení vlasntí hodnoty pro předaný stav prostoru. Klauzule obsahuje 3 Literály a metodu pro vyhodnocení pro zadaný stav, kterou deleguje na Literály.

Generování souseda

Stavový prostor 3-SAT problému není kontinuální jako u knapsack, u kterého bylo jisté, že žádná věc v batohu je validní stav a postupným přidáváním se výsledek zlepšuje, ale jednou se dotane přes váhu a přestane být validní. Řešení pro vyskočení z nevalidního stavu bylo jednoduché, totiž odebírat věci dokud nebude sumární váha opět menší než daná maximální váha. U 3-SAT ale není ani nulové ani maximální ohodnocení všech proměnných zárukou validního stavu. Jelikož pro validitu řešení musíme splnit všechny klauzule, je potřeba prostor prohledávat jak přidáváním tak odebíráním splněných proměnných. Nejjednodušší operace, která dosahuje této valstnosti je změna ohodnocení náhodné proměnné, která je použita v implementaci.

Nevalidní stavy

Výše popsaný přístup generování souseda čas od času skončí v nevalidním stavu, a narozíl od knapsacku mohou být oblasti s validním ohodnocením proměnných od sebe úplně odřízlé těmi nevalidními. Toto řeší relaxace, tj. umožnit přijmutí nevalidního řešení s tím, že bude jeho hodnota penalizována. Penalizace nevalidního řešení ale nemůže být staticá (např. přenásobění vždy stejnou konstantou od 0-1), protože pokud je sumární váha pozitivního ohodnocení všech proměnných přenásobená tímto koeficientem větší než řešení, tak zůstane prohledávání po celou dobu v této oblasti a neprohledává relevantní oblasti prostoru, jak je vidět na následujícím grafu.

{{:student:blazeva1:5-1-1.png|}} {{:student:blazeva1:5-1-2.png|}}

Tomuto jevu můžeme předejít tím, že penalizace se v průběhu prohledávání stále zvyšuje. Díky tomu vždy dojde na chvíli, kdy penalizace překročí mez, ve které se mohou nacházet potenciální řešení (2. graf výše). Zvyšování penalizace můžeme zavést poměrem teplota / počáteční_teplota, avšak tento parametr nemusí mít efekt jaký očekáváme. Ano, sice vyřeší to, že penalizace se bude zmenšovat, ale jelikož se teplota zmenšuje exponencielně, tak se bude také zmenšovat i tento poměr. Mohlo by se vyplatit tento parametr pozměnit funkcí a tím oddálit jeho rychlé klesání. Jaké je dobré nastavení tohoto parametru je otázkou, kterou se budeme zabývat v budoucí sekci.

Parametry algoritmu

Dosavadní měření byly s parametry danými pouhým odhadem (heat 500, anneal 0.99, init_prob_for_worse 0.8, i_p_dif_heat 20 a punish_invalid=1). Řešení sice bylo nalezeno, ale nebylo nic, co by nám říkalo že toto nastavení je dobré. V této sekci se tedy podíváme, jaký vliv májí různé parametry na výsledek.

Počáteční teplota (-h)

Tato verze implementace simulovaného ochlazování má oproti typické implementaci navíc parametr u výrazu pro výpočet pravděpodobnosti přijetí horšího řešení. Tento parametr je dopočítán výrazem

DELTA = -log (INITPROB) / (DELTAPAR/heatInit * log (EULER)).

To umožňuje zadat na vstupu pravděpodobnost přijetí pro zadaný rozdíl součtu vah a parametr bude dopočítán tak aby výraz pro výpočet pravděpodobnosti přijetí horšího řešení

e = pow(EULER,-DELTA*delta/heat),

vyšel jako zadaná pravděpodobnost.

Díky tomu je možné měnit pravděpodobnost přijetí horšího řešení spolu se vzdáleností, pro kterou taková pravděpodobnost platí, a nemusíme se zabývat otázkou jakou teplotu nastavit. Tento přístup má za následek necitlivost algoritmu na vstupní teplotu, což pozorujeme na následujících grafech pro 3 odlišně obtížné instance.

{{:student:blazeva1:5-3-heat2.png|}}

{{:student:blazeva1:5-3-heat.png|}}

{{:student:blazeva1:5-3-heat3.png|}}

Pozorujeme, že pro jednu instanci se může doba běhu lyšit (pozorujeme pravou Y osu) cca o 20%, což je závislé na náhodě při prohledávání stavového prostoru. Se zvětšující se obtížností také pozorujeme zvyšující se počet nepovedených pokusů, to je také dáno náhodou.

Náhoda sice různé běhy algoritmu odliší, ale nepozorujeme žádnou korelaci s hodnotou počáteční teploty. Pro další měření tedy budeme nastavovat teplotu na 1000.

Koeficient chlazení (-a)

Rychlost ochlazování má přímý dopad na počet kroků, které algoritmus provede. Pro nízký počet kroků má algoritmus moc málo času na nalezení řešení, a tak je vysoká šance, že se nepodaří najít žádné řešení. Se snižující se rychlostí chlazení (koeficient se blíží 1) se počet kroků a výpočetní doba zvyšuje exponenciálně. Pozorujeme, že se postupně vytrácí nenalezená řešení (s váhou 0) a kolem hodnoty koeficientu 0.7 je pravděpodobnost nalezení znatelně vyšší a nad hranicí 0.9 je řešení nalezeno vždy.

{{:student:blazeva1:5-3-annealing.png|}}

Zřejmě se s pomalejším ochlazováním zvyšuje pravděpodobnost nalezení řešení, Pozorujme, jak se chová změna hodnoty koeficientu pro jednodušší a obtížnější instanci problému.

{{:student:blazeva1:5-3-annealing2.png|}} {{:student:blazeva1:5-3-annealing3.png|}}

Jde vidět, že pro jednodušší instanci je hranice vysoké pravděpodobnosti je u nižší hodnoty koeficientu chlazení. Pro těždí instanci není hranice nalezení instance k nalezení, takže pravděpodobnost i pro pomalé chlazení je malá.

Tato měření potvrzují, že čím pomaleji chladíme, tím vyšší je šance nalezení výsledku. Je zajímavé, že kromě pravděpodobnosti nalezení výsledku se nám také zlepšuje pravděpodobnost lepší hodnoty výsledku, která je ale nad určitou mez srovnatelná. Pomalejší chlazení tedy nezaručuje lepší výsledek. Hlavně z prvního grafu je vidět, že výsledek se sice zlepšuje, ale nad koeficient 0.7 už mají nalezené výsledky srovnatelnou kvalitu.

Protože má nastavení velký vliv na dobu běhu, tak jsem u dalších měření z časových důvodů dával 0.95 a pro zajímavější případy 0.98-0.995.

Pravděpodobnost přijetí horšího výsledku (-p)

Tento parametr určuje jak je pravděpodobné, že se přijme horší řešení. Tato akce je typická pro simulované ochlazování a bez ní by se jednalo v podstatě o hladové prohledávání. Pojďme se podívat jak na změnu tohoto parametru reaguje algoritmus.

{{:student:blazeva1:5-3-gap.png|}}

Ukazuje se, že s vyšším parametrem je výpočetní doba vyšší a že od určité meze jsou výsledky podstatně lepší. Zde vidíme krásnou ukázku toho, jak se parametr projevuje na “vyskočení” z lokálního maxima. Zdá se, že lokální maxima tohoto problému jsou nespojená s globálním maximem, a proto je pro parametr < 70% veliká šance uváznutí v lokálním maximu. Naopak, pokud se z lokálního maxima vymaníme (par > 90%), tak máme velikou šanci nalezení velmi dobrého výsledku. To znamená, že tento problém nemá u nalezeného maxima strmý kopec, a tak není pravděpodobnost nalezení tohoto výsledku zanedbatelná.

Druhý jev, který z grafu pozorujeme, jsou propady výpočetního času u hodnot parametru nad 65% a kolem 34%. Toto má jednoduché vysvětlení, totiž že funkce eqilibrium je implementována podle přednášky tak, že při procházení validních stavů trvá poloviční čas. Díky tomu je doba běhu zkácena, pokud se pohybujeme ve validním okolí dobrého výsledku.

Pro podpoření vyložených doměnek přikládám měření pro lehčí a těžší instanci.

{{:student:blazeva1:5-3-gap2.png|}} {{:student:blazeva1:5-3-gap3.png|}}

Vidíme, že měření podporují tvrzení. Navíc vidíme, že i pro obtížnější instanci je tento parametr velice důležitý k nalezení výsledku. Je tedy očividné, že budeme nastavovat tento parametr na 99% pro všechny běhy dalších měření.

Vzdálenost, pro kterou platí předchozí parametr (-d)

Tento parametr je silně spojený s předchozím (pravděpodobnost přijetí hořdího řešení pro daný rozdál hodnot), protože toto je ten rozdíl hodnot, pro který předchozí parametr platí. Ostatní rozdíly hodnot jsou spočítané výrazem, který je typický pro simulované ochlazování.

double e = pow(EULER,-delta/heat);

Ve své implementaci jsem k tomuto výrazu přidal ještě DELTA.

double e = pow(EULER,-DELTA*delta/heat);

Ta je spočtená z parametrů -d a -p. V předchozí sekci k měření -p jsme zjistili, že se vyplatí ji nastavit na vysoké procento. Tento parametr lze v podstatě ještě zvýšit tím, že zvýšíme vzdálenost horšího řešení pro který platí.

Jelikož nastavení při experimentu pro minulý parametr bylo -d=20, tak zkusme nyní iterovat od 1 do 200 pro 3 různě obtížné instance.

{{:student:blazeva1:5-3-distance1.png|}}

{{:student:blazeva1:5-3-distance.png|}}

{{:student:blazeva1:5-3-distance2.png|}}

Se zvyšující se hodnotou vzdálenosti se parametr DELTA spošte tak, aby takové horší řešení bylo přijato téměř na 100%. Vidíme, že doba běhu ke konci konverguje. Je to tím, že od určité hodnoty nebude mít tato vzdálenost veliký vliv, protože přeroste velikost nejlepšího nevalidního řešení.

Z pohledu nejlepšího nalezeného řešení se nezdá, že by měl tento parametr nějaký vliv. Jak je to možné, když je tak pevně svázán s parametrem -p? Odpověď by mohla ležet v nastavení už prověřeného parametru -p. Pojďme prověřit jakou má závislost nalezené řešení v případě, že -p není 99 %, ale třeba 20 %.

{{:student:blazeva1:5-3-distance3.png|}}

Konečně vidíme jaký má tento parametr vliv na kvalitu řešení a čas. Pro nižší nastavení parametru -p je vidět, že pro nízké hodnoty parametru -d vychází veliký počet nenalezených řešení. Je tedy potřeba nastavit buď -d nebo -p dostatečně vysoko na to, aby jsme se vyhnuli této oblasti.

Parametry -d a -p jsou očividně velice svázány, pro další meření zůstanu u nastavení -p=0.99 a -d=20.

Zmírnění/Urychlení rychlosti penalizace nevalidních stavů (-c)

Jak slíbeno v sekci “Nevalidní stavy” se zde budeme zabívat tím, jestli se vyplatí měnit rychlost změny penalizace nevalidních stavů. V programu je tento jev použit při vracení hodnoty nevalidního stavu takto.

return val * pow(heat/(double)heatInit,POWCUR);

Samotnou implementaci jsem měnil a měřil jak dopadne. To znamená, že se hodnota nevalidních stavů v průběhu algoritmu mění. Díky mocnění této hodnoty můžeme dosáhnout efektu spomalení nebo zrychlení tohoto jevu. Podívejme se jaký má vliv na výsledek zmírnění a urychlení penalizace nevalidních stavů.

return val * pow(heat/(double)heatInit,1/POWCUR); // zmírnění
return val * pow(heat/(double)heatInit,POWCUR); // urychlení

{{:student:blazeva1:5-3-power.png|}} {{:student:blazeva1:5-3-power2.png|}}

Pozorujeme, že extrémistický přístup k nastavení tohoto parametru nevede k dobrým výsledkům.

Při přehnání zmírnění rychlosti penalizace dlouho čekáme, než začneme nevalidní stavy penalizovat. Je možné, že se nám tento přístup chvíli může vyplatit (2 < par < 4), ale výše (par > 4) už je penalizace moc strmá a tak algoritmus prochází prostor bez zábran a hned nato ho necháme uvíznout v lokálním maximu.

Při přehnání zrychlení rychlosti penalizace se dostaneme do oblasti kde najednou nemusíme dosáhnout dobrého výsledku. To znamená, že algoritmus ztrácí schopnost se vymanit z lokálního maxima, protože nevalidní hodnoty jsou penalizovány moc a příliš brzy.

Z výsledků usuzuji, že mírné zmírnění rychlosti penalizace může být prospěšné, necháme tedy nastaven tento parametr na implementaci “zmírnění” s hodnotou 3.

Testování pro různé instance na zjištěném nastavení

Nyní vyzkoušíme jak se implementace chová pro různé instance. Takže pro konstantní nastavení algoritmu, budeme měnit parametry generátoru a zkusíme najít jaké instance zvládá dobře nebo špatně.

Zkoušené nastavení: (-d 20 -h 1000 -a 0.98 -p 0.99 -c 3)

Klauzule / literál

První zkouška je spíše pro přehled, abychom věděli, pro jaké hodnoty algoritmus najde řešení a kdy ne. Toto bude (nepřesně) korespondovat i s tím, kdy má daná instance řešení a kdy ne.

{{:student:blazeva1:5-4-one1.png|}} {{:student:blazeva1:5-4-one2.png|}}

Vidíme měření pro jednu a deset instancí. Měření pro jednu instanci naznačuje, že když máme 40 literálů a 60 klauzulí, tak začíná přechod do oblasti, kdy už nejsme schopni najít řešení. Pokud je literálů stále 40, ale klauzulí 120, tak už nemáme moc velkou šanci.

Mšření pro 10 instancí nám ukazuje spíše pravděpodobnost náledu (výsledky se průměrují). Zde jde vidět postupný přechod v rozsahu 60-120 od jednoduchých instancí k těm nezvládnutelným.

Pravděpodobnost negativních literálů

Nastavení generátoru obsahuje parametru pro nastavení poměru negativních literálů. Jak se chová algoritmus pro různé hodnoty tohoto parametru?

{{:student:blazeva1:5-4-two.png|}}

Podle očekávání by měly instance na začátku být lehce řešitelné (vše lze nechat nastavené na 1), ale jak se dostáváme k 50 %, tak začínají vnikat kolize, a instance je mnohem obtížnější k vyřešení. Po chvíli však toto údolí projdeme a ocitneme se na straně, kde je mnoho literálů záporných. V tu chvíli se úloha trochu mění, totiž že nehledáme jak “zapnout” klauzule, ale špíš, jak je “nevypnout”. Kolizí je mnohem méně, a tak je možné i zde najít validní řešení a z nich vybírat nejlepší. Pro ilustraci se podívejme na stejná měření pro různé hodnoty počtu literálů a klauzulí.

{{:student:blazeva1:5-4-two2.png|}} {{:student:blazeva1:5-4-two3.png|}}

{{:student:blazeva1:5-4-two4.png|}}

Závěr

Implementaci simulovaného ochlazování pro problém 3-SAT považuji za úspěšnou. Sice nebude porovnatelná k nejlepším implementacím na světě, ale díky vkusné parametrizaci algoritmu i generátoru bylo možné se podívat na chování algoritmu jako takového v různých situacích při různých nastaveních. Pro rozumná zadání se daří najít řešení, avšak není jak porovnat kvalitu algoritmu bez referenčních dat, ale z měřených dat (nejtěší instance měření tepla) můžeme polemizovat o tom že funguje dobře, protože se nestává (pokud najde řešení), že by našel takové řešení, které je mnohem lepší než všechna ostatní nalezená řešení.