Semestrální práce z předmětu X36PAA

Autor: Jan Skalický (skalij2@fel)
cvičení předmětu X36PAA, pondělí 11:00 (zima 2007)
datum poslední aktualizace: 5.02.2008, 22:36

Prohlášení o autorství:
Zde předkládanou práci jsem vytvořil samostatně s využitím informačních zdrojů uvedených v závěru práce

Obsah

1. Úloha 1 - Řešení problému batohu metodou hrubé síly a jednoduchou heuristikou
2. Úloha 2 - Problém kýblů
3. Úloha 3 - Řešení problému batohu dynamickým programováním, metodou větví a hranic a heuristikou
4. Úloha 4 - Experimentální hodnocení algoritmů pro řešení problému batohu
5. Úloha 5 - Seznámení se se zvolenou pokročilou iterativní metodou na problému batohu
6. Úloha 6 - Problém vážené splnitelnosti booleovské formule

1. Zadání

   • Naprogramujte řešení 0/1 problému batohu hrubou silou. Na zkušebních datech pozorujte závislost výpočetního času na n.
   • Naprogramujte řešení 0/1 problému batohu heuristikou podle poměru cena/váha. Pozorujte
     • závislost výpočetního času na n. Grafy jsou vítány (i pro exaktní metodu).
     • průměrné zhoršení proti exaktní metodě
     • maximální relativní chybu. Absolutní chyba nic neříká!
   
   

2. Platforma

   Úloha byla řešena programem napsaným v jazyce C (ansi). Program "batoh" je parametrizován požadovaným algoritmem, počtem jeho iterací pro měření času krátkých zadání a na standardním vstupu očekává instance problému ve "školním" formátu. Na standardím výstupu se objevují řešení ve "školním" formátu. Aplikace je nezávislá na host OS.
   
   

3. Řešení hrubou silou (bruteforce)

   Algoritmus prochází všechny konfigurace batohu a pamatuje si tu, která nejlépe vyhovuje optimalizačnímu kritériu. Tok programu je řízen rekurzí, která v každém kroku rozhoduje o umístění jedné věci do batohu. Pokud by vložení této věci způsobilo přetížení batohu, použije se pouze cesta rozvíjející konfigurace, které tuto věc neobsahují. Tato optimalizace poněkud prořezává strom rekurzivního sestupu (ve verzi programu implementující prořezávání shora i zdola není tato optimalizace u metody hrubé síly použita).
   
   Časová složitost je O(2ⁿ), protože v každém kroku rekurze se program větví obecně do 2 cest, tak aby v pokryl všechny možné konfigurace. Paměťová složitost je O(n), protože pro každou věc udržujeme informaci o vložení/nevložení která je v případě rekurzivního přístupu realizována pozicí v programu a ukládána v aktivačních záznamech na HW zásobníku.
   
   

4. Řešení hladovým přístupem s heuristikou typu cena/váha (c/w greedy heuristic)

   Algoritmus realizuje hladový výběr a proto nezaručuje optimální řešení. Dokonce nezaručuje žádnou max. relativní odchylku od optimálního řešení. Hodnotícím kritériem pro výběr je poměr ceny a váhy věci. Algoritmus nejprve provede řazení věcí instance podle tohoto poměru a poté je od prvku s největším poměrem přidává do batohu, pokud zůstane nepřetížen.
   
   Časová složitost je složitost řazení a procházení jednorozměrného pole, tozn. O(n*log(n) + n). Paměťová složitost je O(n), protože udržujeme informaci o mapování původních prvků do seřazenéného pole abychom byli schopni rekonstruovat vektor řešení s prvky v původním pořadí.
   
   

5. Naměřené výsledky

   Čas byl měřen na CPU Athlon XP 1600+, OS Windows XP v prostředí cygwin programem time (user) parametrizovaným voláním programu batoh. V případě potřeby byl nastaven počet opakování požadovaného algoritmu uvnitř programu batoh na více než 1 (typicky 1000000, 10000, 100) tak, aby byl minimalizován režijní čas načtení úlohy vůči času běhu algoritmu pro vlastní řešení nebo pro velmi malé výpočetní doby. Vstupem byly školní instance problému.
   
   

   Výpočetní časy [ms] velikost instance doba bruteforce doba heuristiky 4 0.022 0.055218 10 1.220 0.17859 15 57.02 0.3061 20 1655 0.4186 22 6031 0.4718 25 49077 0.5437 27 208311 0.5843 30 1655937 0.6686 32 - 0.7186 35 - 0.8031 37 - 0.8452 40 - 0.9452

   
   
   Vidíme, že časová složitost hrubé síly přesně odpovídá exponenciálnímu průběhu v celém rozsahu velikosti instancí. Složitost hladového výběru s heuristikou je asymptoticky lineárně-logaritmická, ale kvůli přidané lineární složce je tento trend viditelný jen nepatrně.
   
   Následující tabulka ukazuje maximální a průměrnou relativní chybu řešení s hladovou heuristikou vůči optimálnímu řešení. Obě veličiny jsou vyjádřeny v závislosti na velikosti instance v balíku 50 testovacích. Relativní chyba je rozdíl mezi součtem cen věcí v batohu na výstupu měřeného algoritmu a největším možným, normalizovaným k němu (kladná chyba znamená méně hodnotný batoh, záporná není možná).
   
   

   Relativní chyby heuristiky [%] velikost instance maximální průměrná 4 36.36 2.17 10 11.48 1.29 15 8.54 0.48 20 8.43 0.6 22 7.23 0.69 25 3.68 0.5 27 10.6 0.5 30 5.51 0.51 32 3.34 0.34 35 4.61 0.28 37 8.20 0.34 40 2.34 0.20

   
   

6. Závěr

   Oba algoritmy pracují dle předpokladu. Hrubá síla nachází optimální řešení, avšak se značnou časovou složitostí, což potvrzují výsledky měření. Hladový přístup s jednoduchou heuristikou nezaručuje optimální řešení, což ukazuje tabulka s relativní chybou vůči němu. Tato nevýhoda je kompenzována podstatně nižší časovou složitostí algoritmu, která pro malé velikostio instancí vychází jen nepatrně superlineární.
   
   

7. Odkazy

   Zdrojový kód programu batoh zde
   Makefile zde

1. Zadání

   Navrhněte a implementujte heuristiku řešící zobecněný problém dvou kýblů. Heuristiku otestujte na všech následujících příkladech a srovnejte s prohledáváním stavového prostoru do šířky (BFS). Volitelně srovnejte i s prohledáváním do hloubky (DFS). Zvolenou heuristiku popište ve zprávě.
   
   

2. Platforma

   Úloha byla řešena programem napsaným v jazyce C++. Program "kyble" je parametrizován požadovanou prohledávací strategií a na standardním vstupu očekává instance problému. Na standardím výstupu se objevují řešení. Aplikace je nezávislá na host OS.
   
   

3. Algoritmus

   Jádrem programu je prohledávání stavového prostoru. Jedná se o prohledávání typu Best-first-search, které používá prioritní frontu k uložení a výběru otevřených uzlů. Speciálním použitím fronty umožňuje program realizovat prohledávání typu BFS (do šířky), DFS (do hloubky) a náhodného prohledávání (pořadí odebíraných uzlů závisí na implementaci fronty). Hledání s použitím informace od heuristiky je pak obecný způsob použití BestFS. Implementovaným typem prohledávání je algoritmus A*, který při hodnocení uzlů pracuje nejen s heuristickou informací, ale i s kumulovanou cenou aplikace přechodových operátorů do aktuálního stavu (složka historie). Použitá heuristika je vícesložková a neklade si nárok na to, býti přípustnou, což znamená, že není zajištěna optimalita nalezeného řešení. Kritériem pro návrh heuristiky byla kromě minimalizace cesty zejména velikost nalezené části prohledávacího prostoru.
   
   Uzavřené stavy uchovává algoritmus v dynamicky alokovaném pole, které se idnexuje mapováním z povrchu hyperkrychle (souřadnice konfigurace kýblů), což se projevuje konstantní časovou složitostí při testování uzavřenosti stavu, extrahovaného z fronty. Při nalezení zlepšující cesty do již uzavřeného stavu, provádí algoritmus jeho reexpanzi (volitelně, nemá význam u BFS/DFS), což má za následek přehodnocení i jeho potomků a použití zlepšené cesty v budoucnu. K této situaci dochází např. tehdy, poskytuje-li heuristika nepřesou informaci o optimálním pořadí expanze stavů.
   
   Pokud program nalezne řešení (právě pokud nějaká cesta do cílového stavu existuje), je výstupem délka cesty, šířka - počet nalezených různých stavů prostoru, počet expanzí uzlů (může být větší než šířka o reexpandované uzly) a počet extrakcí z prioritní fronty (je větší než počet expanzí o uzly, které již není potřeba expandovat), volitelně i cesta samotná. Pokud neexistuje cesta do cílového stavu, algoritmus po prohledání prostoru ohlásí neexistenci řešení.
   
   

4. Heuristika

   Experimentováním s různými byla použita heuristika s 4 složkami:
   
   
   • Penalizace stavů s prázdnými nebo plnými kýbly

     Přičítá hodnocení za každý stav s konfigurací vzniklou úplným vylitím nebo naplněním kýblu

   • Preference stavů s parciálními řešeními na správných místech

     Odečítá hodnocení za každý kýbl se správným množstvím kapaliny

   • Preference stavů s parciálními řešeními na libovolných místech

     Odečítá hodnocení za každý kýbl, který je naplňen jako některý jiný v koncovém stavu

   • Preference stavů vedoucích přímo do stavů s parciálními řešeními

     Odečítá hodnocení za každý kýbl, který lze do koncového stavu dostat jeho vylitím, naplněním a zejm. pokud je to možné udělat jeho přelitím do jiného nebo přelitím jiného do tohoto kýble

   Každá složka ovlivňuje výslednou heuristiku jinou měrou, danou experimenty na testovacích datech. Důraz byl však kladen více na generičnost než přeučení koeficientů pro konkrétní instance problému. Všechny složky jsou tudíž použitelné i samostatně nebo v jiných kombinacích s nevelkou změnou jejich vlivu na celkové hodnocení.
   
   Speciálním typem implementovaných heuristik jsou jednoduché předpisy, které konkretizují chování BestFS na BFS/DFS.
   
   

5. Naměřené výsledky

   Výstupy programu na školních instancích problému (každá tabulka reprezentuje jednu prohledávací strategii):
   
   

   Prohledávání RandomFS ID length width expand extract 1.1 1095 7972 7971 58253 1.2 280 3856 3855 40179 1.3 193 1249 1248 3068 1.4 551 5638 5637 45497 2.1 8991 43897 43896 235150 2.2 6218 35282 35281 144860 2.3 5744 33379 33378 132542 2.4 290 2066 2065 4647 2.5 4036 25976 25975 88464 3.1 10474 51453 51452 279165 3.2 4751 30590 30589 105718 3.3 4269 28333 28332 93530 3.4 502 3687 3686 8699 3.5 2365 17755 17754 48614 3.6 5514 33932 33931 125840 avg 3685 21671 21670 94282

   Prohledávání DFS ID length width expand extract 1.1 5943 8121 8120 84160 1.2 2262 4186 4185 44432 1.3 968 970 969 3552 1.4 470 2391 2390 37359 2.1 36603 44564 44563 503690 2.2 36424 46280 46279 548557 2.3 37690 45764 45763 523235 2.4 867 868 867 2341 2.5 7302 7309 7308 28306 3.1 40398 41333 41332 330919 3.2 40483 41427 41426 332367 3.3 10613 10629 10628 40337 3.4 10858 10877 10876 41580 3.5 31483 31871 31870 207368 3.6 6019 6022 6021 20474 avg 17892 20174 20173 183245

   Prohledávání BFS ID length width expand extract 1.1 10 8992 8991 177859 1.2 8 8797 8796 141301 1.3 8 8020 8019 106812 1.4 3 210 209 372 2.1 16 49349 49348 1102583 2.2 12 42433 42432 781173 2.3 11 35339 35338 564351 2.4 5 1430 1429 5197 2.5 7 8106 8105 66132 3.1 14 59201 59200 1331314 3.2 12 58387 58386 1184589 3.3 10 40770 40769 564302 3.4 5 2379 2378 10100 3.5 7 11935 11934 76183 3.6 9 32693 32692 371482 avg 9.1 24536 24535 432250

   BestFS s heuristikou ID length width expand extract 1.1 14 27 26 45 1.2 13 24 23 29 1.3 10 14 13 17 1.4 4 5 4 5 2.1 25 198 197 550 2.2 23 1517 1516 4466 2.3 25 203 202 478 2.4 17 64 63 145 2.5 15 161 160 479 3.1 14 67 66 174 3.2 27 359 358 980 3.3 18 55 54 114 3.4 8 10 9 12 3.5 8 12 11 14 3.6 10 24 23 43 avg 15.4 183 182 503

   BestFS s heuristikou + reexpanze ID length width expand extract 1.1 14 27 26 45 1.2 13 24 23 29 1.3 10 14 13 17 1.4 4 5 4 5 2.1 25 216 258 790 2.2 23 1061 1344 3911 2.3 24 137 164 360 2.4 16 40 44 89 2.5 15 192 243 867 3.1 14 67 66 174 3.2 25 277 323 853 3.3 14 40 42 79 3.4 8 10 9 12 3.5 8 12 11 14 3.6 10 24 23 43 avg 14.9 143 173 486

   ID = instance ID
   length = délka nalezené cesty
   width = mohutnost dosaženého prostoru
   expand = počet expanzí uzlů
   extract = počet extrakcí z fronty
   
   Originální výstupy programu:
   
   
   • Prohledávání BFS zde
   • Prohledávání DFS zde
   • Prohledávání RandomFS zde
   • BestFS s heuristikou zde
   • BestFS s heuristikou + reexpanze zde
   
   

6. Závěr

   Implementovaná heuristika značným způsobem omezila použitý vyhledávací prostor oproti hledání BFS, což je patrné z naměřených výsledků. Jde o několikařádový rozdíl. Pro některé případy instancí jde heuristkou naváděné prohledávání dokonce přímo za cílem. V některých případech dojde ještě k dodatečnému zlepšení (zejm. v šířce prohledávání), povolíme-li reexpanze uzavřených uzlů.
   
   

7. Odkazy

   Zdrojový kód programu kyble zde
   Makefile zde
   Školní instance zde

1. Zadání

   • Naprogramujte řešení 0/1 problému batohu metodou větví a hranic (B&B) tak, aby omezujícím faktorem byla hodnota optimalizačního kritéria. Tj. použijte ořezávání shora (překročení kapacity batohu) i zdola (stávající řešení nemůže být lepší než nejlepší dosud nalezené)
   • Naprogramujte řešení 0/1 problému batohu nebo alespoň 0/1 exaktního problému batohu bez cen metodou dynamického programování.
   • Naprogramujte řešení 0/1 problému batohu heuristikou podle poměru cena/hmotnost s testem nejcennější věci.
   
   

2. Platforma

   Úloha byla řešena programem napsaným v jazyce C (ansi). Program "batoh" je parametrizován požadovaným algoritmem, počtem jeho iterací pro měření času krátkých zadání a na standardním vstupu očekává instance problému ve "školním" formátu. Na standardím výstupu se objevují řešení ve "školním" formátu. Aplikace je nezávislá na host OS a parametrem --help zobrazí návod k použití.
   
   

3. Řešení metodou Branch and Bound

   Algoritmus prohledává stavový prostor rekurzí která rozhoduje o vložení/nevložení věci (s indexem podle hloubky rekurze) do aktuální konfigurace. Ve stromu sestupu dochází k dynamickému prořezávání dle váhy aktuální konfigurace - pokud je batoh přetížen a dle ceny - pokud zbývající věci nemohou zlepšít dosavadní cenu, ani v případě, že by byly všechny přidány. Ačkoliv má toto prořezávání velký dopad na většinu úloh z praxe, dají se vymyslet kontrainstance, na kterých se neprojeví a algoritmus bude realizovat úplné prohledávání (rozhodování o zlepšujících věcech je umístěno na konci prostoru).
   
   Zbývající cena je předávána v parametru, aby nemusela být v každém volání rekurze počítána z vektoru konfigurace. Vyhodnocení lepší konfigurace stačí provádět až v listech rekurze - po vyplnění celého vektoru konfigurace. Její průběžné vyhodnocení po cestě nemá význam pro dynamiku prořezávání, neboť nemůže nastat případ, kdy by mohla být tato informace použita dříve, než se dojde k nějakému z listů aktuálního sestupu (alespoň k takovému, který nic dalšího nepřidává a ten je vyhodnocen jako by byli jeho předci v sestupu), kromě singulárního případu s nulovým ohodnocením cen, které zůstanou neprořezané a dle pořadí operací v rekurzi budou proto bezcenné předměty do konfigurace přidávány.
   
   

4. Řešení metodou dynamického programování

   Problém batohu vykazuje vlasnosti optimální podstruktury - překrývajících se podproblémů. Byla implementována dekompozice podle kapacity batohu, tozn. ptáme se na řešení podbatohu v závislosti na dostupné kapacitě a počtu použitých věcí (od první po nějakou). Některé z takových podbatohů nemusíme řešit opakovaně, protože si jejich řešení pamatujeme v matici, kde nezáporná hodnota indikuje cenu optimálního řešení podbatohu a záporná neplatný výsledek.
   
   Algoritmus realizuje jednoprůchodový postup shora dolů a to tak, že se na podbatohy ptá rekurzivně podle potřeby a řeší pouze pokud tuto informaci ještě nemá. V opačném případě nebo pokud se jedná o triviální podúlohu končí volání bez dalšího větvení. Rekonstrukce vektoru řešení je prováděna porovnáváním nikoliv se sousedním prvkem matice (test, zda-li věc do batohu nepatří), ale s prvkem vzniklým posunutím indexu kapacity o váhu věci (test, zda-li věc do batohu patří), a to proto, aby algoritmus sbíral bezcenné věci v souladu s ostatními implementovanými.
   
   

5. Řešení kombinovanou heuristikou

   Jedná se o vylepšení původní hladové heuristiky typu cena/váha. Po jejím průchodu se testuje, zda-li obdržený výsledek není horší než konfigurace obsahující pouze nejcennější věc. V tom případě obsahuje cílová konfigurace pouze tuto věc. Toto vylepšení má význam zejména u instancí, které obsahují větší počet menších věcí z větším poměrem a jednu větší věc s menším poměrem, která se v optimální konfiguraci vyskytuje. Součet menších věcí nechá v batohu volnou kapacitu podle granularity jejich vah, kterou samotná větší věc dokáže využít a překompenzovat tak svůj menší poměr cena/váha. S takovou situací si původní heuristika, díky hladovému přístupu, neporadí, ale zde implmentované vylepšení ji dokáže opravit a sníží tak průměrnou chybu heuristiky.
   
   

6. Naměřené výsledky

   Čas byl měřen stejnou metodikou jako v úloze 1.
   
   

   Výpočetní časy [ms]

   velikost instance	doba bruteforce	doba B&B	doba dynamického	doba heuristiky
   4	0.022	-	-	-
   10	1.220	-	-	-
   15	57.02	-	-	-
   20	1655	44	8.95	0.3124
   22	6031	173	10.64	0.3561
   25	49077	1314	14.82	0.4077
   27	208311	5171	18.90	0.4452
   30	1655937	41358	24.36	0.5202
   32	-	163530	29.68	0.5546
   35	-	1298233	36.40	0.6296
   37	-	5215061	42.80	0.6733
   40	-	-	52.18	0.7421

   
   
   Vidíme jasný exponenciální trend B&B, kterě zde z hlediska absolutních časů naráží na fakt, že v každém s balíků 50 testovacích úloh je obsažena jedna neprořezatelná instance. Průměrné zrychlení oproti hrubé síle je však patrné, ačkoliv asymptotická složitost zůstává. Rychlost dynamického programování je lineární vůči velikosti instance, ale rovněz vůči kapacitě, která s velikostí instance nesouvisí - je pseudopolynomiálni a zde superlineární kvůli roustoucí kapacitě v závislosti na velikosti instance. Nová, kombinovaná heuristika, nevykazuje znatelnou odlišnost vůči původní, protože přidaný test se provede v lineárním čase, což původní závislost asymptoticky nezhorší.
   
   Grafy těchto závislostí nejsou příliš zajímavé, protože jejich trend je zřejmý už z tabulky a nevelké odchylky od něj jsou způsobeny pouze volbou konkrétních instancí.
   
   

   Relativní chyby heuristiky (původní) [%] velikost instance maximální průměrná 4 36.36 2.17 10 11.48 1.29 15 8.54 0.48 20 8.43 0.6 22 7.23 0.69 25 3.68 0.5 27 10.6 0.5 30 5.51 0.51 32 3.34 0.34 35 4.61 0.28 37 8.20 0.34 40 2.34 0.20

   Relativní chyby heuristiky (nová) [%] velikost instance maximální průměrná 4 24.75 1.33 10 11.48 1.10 15 2.77 0.31 20 4.08 0.43 22 3.02 0.54 25 2.59 0.42 27 1.85 0.29 30 1.75 0.40 32 2.28 0.27 35 1.82 0.19 37 1.76 0.18 40 0.95 0.15

   
   
   Test přidaný do nové heuristiky poněkud zlepšuje její přesnost v průměrném případě. Maximální relativní chyba však klesla značně, protože právě tyto případy jsou přidaným testem podchyceny. Také je zřejmé, že maximální relativní chyba v tomto případě nemůže překročit (dokonce ani dosáhnout) 50%.
   
   

7. Závěr

   Algoritmy pracují dle předpokladu. B&B nachází řešení vesměs daleko rychleji než hrubá síla, avšak pro neprořezatelné instance běží stejně dlouho. Dynamické programovaní řeší problém v pseudopolynomiálním čase, což jej činí problematickým v případě obecného použití. Jeho výhodou je o několik řádů větší rychlost pro typy úloh z praxe (zde školní instance batohu). Hladový přístup s kombinovanou heuristikou nezaručuje optimální řešení, ale dá se dokázat, že alespoň jeho polovinu.
   
   Různé algoritmy mohou generovat výstupní vektory s drobnými rozdíly, pokud se jedná o stejný součet jejich cen (typicky prohození 2 i více prvků se stejným součtem cen a s podobnými váhami). Děje se tak díky odlišné konstrukci výstupního vektoru.
   
   

8. Odkazy

   Zdrojový kód programu batoh zde
   Makefile zde

1. Zadání

   • Prozkoumejte citlivost metod řešení problému batohu na parametry instancí generovaných generátorem náhodných instancí. Máte-li podezření na další závislosti, modifikujte zdrojový tvar generátoru.
   • Na základě zjištění navrhněte a proveďte experimentální vyhodnocení kvality řešení a výpočetní náročnosti.
   • Pokud možno, prezentujte algoritmy jako body v ploše, jejíž souřadnice jsou výše uvedená kritéria.
   
   

2. Platforma

   Úloha byla řešena programem napsaným v jazyce C (ansi). Program "batoh" je parametrizován požadovaným algoritmem, počtem jeho iterací pro měření času krátkých zadání a na standardním vstupu očekává instance problému ve "školním" formátu. Na standardím výstupu se objevují řešení ve "školním" formátu. Aplikace je nezávislá na host OS a parametrem --help zobrazí návod k použití.
   
   

3. Experiment

   Nejprve je třeba zjistit citlivost jednotlivých metod na parametry řešených instancí. Jsou zde jistá podezření:
   
   
   • výpočetní náročnost dynamického programování může být citlivá na maximální cenu,
   • 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,
   • není jasné, jakou roli hraje granularita instance (převaha malých nebo převaha velkých věcí).
   
   Data experimentu musí být reprezentativní, aby jeho výsledky neodpovídaly na otázku omezenou. Byl použit školní generátor instancí, který je rozsáhle parametrizován. Lze u něj volit tyto parametry: velikost instance (počet věcí), počet instancí v balíku, maximální váha věci, maximální cena věci, poměr sumární váhy ke kapacitě batohu (dále "měrná kapacita batohu") a charakter granularity, kterým je možno ovlivnit, zda instance bude obsahovat spíše malé nebo spíše velké věci. Pro převahu malých věcí je pravděpodobnost, že věc s váhou w bude v instanci zahrnuta p=1/w^k. Pro převahu velkých věcí platí symetrický vztah p=1/(w_max-w)^k. Exponent pravděpodobnosti u granularity k je posledním parametrem generátoru.
   
   V experimentech byly použity exaktní metody - řešení metodou větví a hranic (B&B) a řešení metodou dynamického programování (s dekompozicí podle kapacity batohu) a aproximativní metody - hladové heuristiky. K implementacím z úlohy 3 byla navíc přidána heuristika vycházející z plného batohu (v grafech označována jako "c/w reversed"), která odebírá věci podle nejhoršího poměru cena/váha až do dosažení přípustné konfigurace (nepřetížený batoh). Oproti přidávající heuristice bude mít tato vždy horší nebo stejnou kvalitu, protože dosažením připustného stavu končí a nezjišťuje již, zda-li by některý z dříve odebraných předmětu nebylo možno vrátit zpět. Pozitivním důsledkem tohoto faktu je menší počet testovaných konfigurací, ale vzhledem k tomu, že tyto hladové přístupy mají v konstruktivní fázi lineární časovou složitost a předtím je ještě nutno předměty řadit, není tento důsledek zásadní. Obě heuristiky byly kombinované s testem nejcennější věci. Tato volba nemá vliv na počet testovaných konfigurací (resp. přidává konst. 1) a ukázalo se, že v průměrném případě ani na kvalitu řešení, protože test na nejcennější věc se projeví jen ve velmi specifických případech. Výhodou zůstává zaručená relativní chyba (50%), ale v praxi (ve všech měřeních zde) je průměrná dosahovaná kvalita, jak ukazují naměřené výsledky, řádově lepší.
   
   Řešení hrubou silou nebylo třeba testovat, protože není citlivé na vlastnosti instance.
   
   

4. Naměřené výsledky a jejich interpretace

   Všechna měření zjišťují operační a kvalitativní závislosti testovaných algoritmů na vlastnostech instancí (resp. parametrech při jejich generování). Protože časové závislosti by mohly být ovlivněné implementací datových struktur apod. bylo přistoupeno k měření počtu testovaných konfigurací. U metody větví a hranic se tento počet zvyšuje po změně konfigurační proměnné (a následném rekurzivním řešení zbytku konfiguračních proměnných), tozn. pokud je stavový prostor prořezán, počet testovaných konfigurací je ušetřen. U dynamického programování se toto číslo zvyšuje při požadavku na řešení netriviálního podproblému, který ještě nebyl řešen. Použitá implementace postupuje shora dolů a tak se jedná vlastně o počet vyplněných (použitých) buněk v tabulce dynamického programování. Narozíl od přístupu zdola nahoru jsou tedy ušetřeny buňky, jejichž příslušné podproblémy není nutno řešit a nejedná se tedy vždy o součin počtu věcí instance a kapacity batohu (dekompozice podle kapacity). U hladových heuristik jde o počet kroků konstruktivní fáze.
   
   Kvalita aproximativních algoritmů je udána průměrnou relativní chybou na balíku instancí oproti optimálnímu řešení exaktní metodou (ve skutečnosti je zde skriptem počítána relativní chyba průměru, která se zde však od průměrné relativní chyby liší zanedbatelně, takže i fluktuance vlivem realizace náhodného výběru jsou signifikantnější). Každé měření bylo provedeno na balíku 50 instancí se stejně nastavenými vlastnostmi a výsledná hodnota je jejich aritmetický průměr. Vzhledem k faktu, že máme 5 vlastností instancí, které je třeba měnit, a k dosažení výsledků, na kterých lze pozorovat trendy závislostí, bude potřeba min. cca 5 hodnot z definičního oboru, měníme parametry generátoru hladově. Parametr, který je středem zájmu, se mění a ostatní zůstávají na výchozích hodnotách, které jsme, vzhledem k požadavku co nejpoužitelnějšího pokrytí prostoru všech instancí, zvolili takto:
   
   
   • maximální váha věci = 100
   • maximální cena věci = 300
   • měrná kapacita batohu = 0.5
   • charakter granularity = 0 (nerozlišovat velké/malé věci)
   • exponent pravděpodobnosti = 0 (není důležitý vzhledem k výchozímu nastavení charakteru granularity)
   
   Citlivost algoritmů může být rovněž závislá na velikosti instance problému (závislosti mohou být např. posunuté nebo s jiným sklonem, intuitivně lze však očekávat např. zachování monotónnosti). Z tohoto důvodu byla všechna měření provedena 2x - pro menší instance o 15 věcech a pro větší instance o 35 věcech. Grafy z jednotlivých měření jsou na následujících obrázcích (některé osy jsou logaritmické):
   
   

   Obr 4.1.1 Citlivost algoritmů na max. váhu věci - instance velikosti 15	Obr 4.1.2 Citlivost algoritmů na max. váhu věci - instance velikosti 35

   
   Na obr. 4.1.1 a 4.1.2 vidíme jasnou lineární závislost operační složitosti dynamického programování na maximální váze věci. To je důsledkem dekompozice podle kapacity batohu. Operační složitosti heuristik stagnují a metoda větví a hranic vykazuje fluktuance bez dlouhodobého trendu. Pro menší instance je operační složitost větví a hranic menší než pro dynamické programování. Ke změně ve prospěch dynamického programování dochází pro max. váhu věci > cca 100. Pro větší instance se však již projeví exponenciální asymptotická složitost větví a hranic a počet testovaných konfigurací řádově převyšuje pseudopolynomiální závislost dynamického programování, i pro velkou max. váhu věci. Relativní chyby heuristik jsou menší pro větší instance, dopředná heuristika má menší chybu, ale větší operační složitost (to platí vždy). Je zde podezření, že pro větší max. váhu věci padají relativní chyby pro menší instance zhruba na úroveň chyb pro větší intance, kde tento trend na konci definičního oboru grafu nepozorujeme.
   
   

   Obr 4.2.1 Citlivost algoritmů na max. cenu věci - instance velikosti 15	Obr 4.2.2 Citlivost algoritmů na max. cenu věci - instance velikosti 35

   
   Z obr. 4.2.1 a 4.2.2 pozorujeme necitlivost všech algoritmů na max. cenu věci. Pouze metoda větví a hranic má oproti dynamickému programování jistý rozptyl výsledků, což je dáno její citlivostí na výběr konkr. instance. Zdá se, že relativní chyba heuristiky vycházející z plného batohu pro větši instance klesne zhruba na 2/3 se stoupající max. cenou věci mezi 100 a 300.
   
   

   Obr 4.3.1 Citlivost algoritmů na měrnou kapacitu batohu - instance velikosti 15	Obr 4.3.2 Citlivost algoritmů na měrnou kapacitu batohu - instance velikosti 35

   
   Obr. 4.3.1 a 4.3.2 dávají představu o závislostech na měrné kapacitě batohu. Závislosti se tvarem neliší pro menší a větší instance. Dynamické programování vykazuje rostoucí závislost s klesající derivací, pro větší instance je poněkud plošší. Pro malou měrnou kapacitu je totiž nutné vyplňovat menší část tabulky. Zajímavá je závislost větví a hranic, která má na grafech maximum okolo 0.3. Tehdy je prostor problému špatně prořezatelný. Pro situace, kdy se naopak do batohu vejde většína (váhově) věcí, je prostor prořezatelný podstatně lépe a od měrné kapacity cca 0.5 pro menší instance a cca 0.8 pro větší testuje metoda větví a hranic dokonce méně konfigurací než dynamické programování. Složitost reverzní heuristiky klesá s měrnou kapacitou, protože není potřeba odebírat mnoho věcí z batohu pro dosažení přípustné konfigurace. Relativní chyby obou heuristik vykazují jasný klesající trend s rostoucím parametrem. Pro menší instance začínají hodnoty chyb poměrně vysoko. Více se projeví prokletí kombinatorické exploze, než když je měrná kapacita batohu velká, protože pro malou kapacitu je nízká pravděpodobnost toho, že heuristiky naleznou nějakou vhodnou kombinaci věcí pro řešení. Jednodušší je totiž nevložit do batohu malý počet špatných věcí.
   
   

   Obr 4.4.1 Citlivost algoritmů na granularitu (velké věci) - instance velikosti 15	Obr 4.4.2 Citlivost algoritmů na granularitu (velké věci) - instance velikosti 35

   
   Grafy na obr. 4.4.1 a 4.4.2 zachycují závislost na exponentu granularity (viz výše) při převaze velkých předmětů. Pokud se exponent blíží nule, přestává instance rozlišovat mezi velkými a malými věcmi, takže všechny grafy začínají stejnými hodnotami, jako když se mezi nimi nerozlišuje. Dynamické programování reaguje počtem testů na stoupající exponent - výraznější převahu velkých/malých předmětů, pozitivně (zhruba nepřímo úměrně) od exponentu cca 1. Metoda větví a hranic reaguje o něco dříve, ale naopak negativně a podíl mezi počtem testů na začátku a konci intervalu je cca 3. Reverzní heuristika velice mírně stoupá. Pro větší instance se tyto trendy nemění, pouze počáteční hodnoty pro malý exponent se mění s asymptotickou složitostí metody ve stejném smyslu jako v předchozích grafech. Relativní chyby heuristik rapidně klesají mezi hodnotou exponentu 1 a 2, pro vyšší exponent se blíží nule nebo ji s velkou přesností dosahují úplně. Pro většinu velkých věcí totiž nečiní heuristikám potíže obsáhnout v konfiguraci řešení zbývající malé věci, které jsou mnohem výhodnější a mají tudíž na kvalitu řešení majoritní vliv.
   
   

   Obr 4.5.1 Citlivost algoritmů na granularitě (malé věci) - instance velikosti 15	Obr 4.5.2 Citlivost algoritmů na granularitě (malé věci) - instance velikosti 35

   
   Grafy na obr. 4.5.1 a 4.5.2 zachycují závislost na exponentu granularity (viz výše) při převaze malých předmětů. Od předchozích grafů se liší zejména počtem testů provedených metodou větví a hranic, kdy do exponentu cca 1 tato závislost klesá, poté stoupá rychleji a končí na úrovni posledních výsledků při převaze velkých předmětů. Pro menší instance tak pro exponent do hodnoty 1 zůstává metoda větví a hranic zhruba stejně náročná jako dynamické programování (pro výchozí hodnotu max. váhy věci). Prakticky totožně reaguje i reverzní heuristika. Zdá se tedy, že nepřímá úměrnost (exponent je 1) mezi váhou věci a pravděpodobností jejího výskytu v instanci má pozitivní vliv na prořezatelnost prostoru a rovněž odebírání podle poměru cena/váha. Statistická korelace mezi těmito dvěma veličinami je poměrně zajímavá. Relativní chyby heuristik opět klesají, ale narozdíl od preference velkých věcí je průběh klesání spíše konkávní.
   
   

5. Zdroje dat

   Data, ze kterých byly vygenerovány grafy jsou zaznamenány v následující tabulce. Výchozí hodnoty parametrů jsou zvýrazněny.
   
   

   Počet testovaných konfigurací - velikost 15 - B&B c/w greedy c/w reversed dynamic Citlivost na max. váhu věci 10 2653.36 15.00 7.22 396.16 30 2422.52 15.00 7.18 924.96 100 2436.36 15.00 7.10 2187.68 300 2922.20 15.00 7.20 4815.72 1000 2364.96 15.00 7.08 9625.26 3000 2414.60 15.00 6.94 15040.82 Citlivost na max. cenu věci 30 2563.92 15.00 7.20 2253.40 100 2588.24 15.00 7.06 2179.96 300 2436.36 15.00 7.10 2187.68 1000 2535.04 15.00 7.20 2224.90 3000 2045.80 15.00 7.14 2228.82 10000 2909.88 15.00 7.20 2265.52 Citlivost na měrnou kapacitu batohu 0.1 418.80 15.00 12.54 237.46 0.3 2330.80 15.00 9.44 1230.76 0.5 2436.36 15.00 7.10 2187.68 0.7 626.12 15.00 4.78 2875.26 0.9 106.16 15.00 2.62 3118.88 Citlivost na granularitu (velké věci) 0.2 2470.32 15.00 7.14 2331.22 0.5 2926.16 15.00 7.60 2561.08 1 4910.64 15.00 8.52 2479.82 2 6511.48 15.00 8.94 639.70 5 6069.12 15.00 9.00 117.50 Citlivost na granularitu (malé věci) 0.2 1803.96 15.00 6.62 2013.68 0.5 1362.00 15.00 5.88 1781.00 1 977.04 15.00 4.42 1046.50 2 976.64 15.00 4.36 187.58 5 5304.68 15.00 8.62 95.62

   Počet testovaných konfigurací - velikost 35 - B&B c/w greedy c/w reversed dynamic Citlivost na max. váhu věci 10 29456622.08 35.00 15.24 2433.80 30 20169951.24 35.00 15.10 6632.32 100 18647307.56 35.00 14.52 20252.12 300 25378966.76 35.00 14.32 54118.12 1000 21541501.32 35.00 14.88 171341.08 3000 24398856.84 35.00 14.82 475238.28 Citlivost na max. cenu věci 30 17918618.96 35.00 14.56 20093.96 100 28384490.52 35.00 15.14 19994.22 300 18647307.56 35.00 14.52 20252.12 1000 21105483.16 35.00 14.50 19956.54 3000 30158870.16 35.00 14.48 20027.32 10000 17642352.24 35.00 14.58 20108.48 Citlivost na měrnou kapacitu batohu 0.1 429778.44 35.00 27.16 4020.04 0.3 41287624.00 35.00 20.40 13323.04 0.5 18647307.56 35.00 14.52 20252.12 0.7 448283.76 35.00 9.38 24485.40 0.9 1332.52 35.00 4.22 26484.42 Citlivost na granularitu (velké věci) 0.2 35562225.64 35.00 15.14 22130.50 0.5 48610888.64 35.00 16.06 25458.30 1 74274891.36 35.00 17.70 29186.96 2 214910014.00 35.00 18.92 11760.36 5 162250672.04 35.00 19.00 741.80 Citlivost na granularitu (malé věci) 0.2 12698166.28 35.00 13.68 18312.72 0.5 4269138.84 35.00 11.70 14292.14 1 478020.68 35.00 7.94 8199.64 2 2364167.92 35.00 8.48 1269.82 5 116589937.48 35.00 18.06 500.40

   Relativní chyby - vel. 15 [%] c/w greedy c/w reversed Cit na max. váhu věci 10 0.97 2.60 30 1.27 2.59 100 0.98 2.94 300 0.77 2.66 1000 1.28 2.87 3000 0.50 1.62 Cit na max. cenu věci 30 0.70 2.28 100 0.70 2.70 300 0.98 2.94 1000 0.76 2.50 3000 0.82 2.01 10000 1.16 3.36 Cit na měrnou kapacitu 0.1 2.44 5.82 0.3 1.18 3.79 0.5 0.98 2.94 0.7 0.54 0.92 0.9 0.12 0.48 Cit na granul. (velké) 0.2 1.23 2.77 0.5 1.11 3.13 1 0.97 2.33 2 0.20 0.20 5 0 0 Cit na granul. (malé) 0.2 1.08 2.22 0.5 0.79 2.04 1 0.71 1.58 2 0.44 1.23 5 0 0.13

   Relativní chyby - vel. 35 [%] c/w greedy c/w reversed Cit na max. váhu věci 10 0.35 1.56 30 0.29 1.36 100 0.27 1.10 300 0.55 1.31 1000 0.23 1.41 3000 0.31 1.46 Cit na max. cenu věci 30 .49 1.77 100 .38 1.82 300 .27 1.10 1000 .31 1.01 3000 .39 1.24 10000 .43 1.20 Cit na měrnou kapacitu 0.1 1.10 2.94 0.3 0.66 2.54 0.5 0.27 1.10 0.7 0.23 0.63 0.9 0.06 0.15 Cit na granul. (velké) 0.2 0.39 1.78 0.5 0.35 1.26 1 0.33 1.10 2 0.06 0.24 5 0 0 Cit na granul. (malé) 0.2 0.24 1.60 0.5 0.21 1.17 1 0.44 1.09 2 0.43 1.09 5 0 0.02

   
   Generátorem instancí bylo vygenerováno 50 balíků po 50 instancích (6 + 6 + 5 + 5 + 5 variant pohyblivých parametrů (3 totožné) = 25, vše s 2 velikostmi 15 a 35). Z těchto zadání vzniklo aplikací 4 použitých algoritmů 200 souborů s výsledky. Seskupením dat shellovým skriptem vzniklo z výstupních souborů 60 souborů statistik (30 pro každou velikost, z toho 10 pro analýzu chyb - 5 parametrů * 2 heuristiky a 20 pro analýzu operačních složitostí - 5 parametrů * 4 algoritmy). Soubory statistik byly pak vstupem pro zdrojové soubory grafů.
   
   

6. Závěr

   Provedli jsme experimentální hodnocení algoritmů pro řešení problému batohu. Potvrdili jsme některé intuitivní trendy v citlivosti algoritmů na vlastnostech instancí a zjistili některé další závislosti. Zajímavá je kladná statistická korelace mezi počtem testovaných konfigurací metodou větví a hranic a reverzní hladovou heuristikou typu c/w pro instance preferující malé věci v závislosti na exponentu pravděpodobnosti (nepřímo úměrné váze) jejich výskytu v instanci.
   
   Exaktní metody jsou obecně mnohem náročnější na počet testovaných konfigurací než hladové heuristiky, které ovšem nelze použít při požadavku na optimální řešení. Rozdíl mezi metodou větví a hranic a dynamickým programováním vychází nejen z jejich rozdílných asymptotických časových složitostí, ale také je patrné, že metoda větví a hranic vykazuje větší rozptyl hodnot počtu testovaných konfigurací - je více citlivá na vlastnosti i na konkrétní instanci. Pro menší instance, menší max. cenu věci nebo některé extrémní případy instancí (velká měrná kapacita batohu) může být však méně náročné než dynamické programování. Konkrétní volba metody k nasazení tedy záleží na vlastnostech instancí, které chceme řešit (resp. dalších omezeních, které jsme zde neanalyzovali, např. na paměť).
   
   Hladová heuristika vycházející z prázdného batohu není citlivá co do počtu testovaných konfigurací, což nepřekvapí. Její analogie, která odebírá věci z plného batohu takovou citlivost vykazuje a testuje tedy vždy neostře menší počet konfigurací. Vykazuje však zhruba 2x větší relativní chybu a vzhledem k tomu, že počet testovaných konfigurací nijak nezohledňuje režii nutnou na počáteční řazení věcí podle výhodnosti, takže celková operační složitost obou heuristik bude velice podobná, je celkově spíše horší než původní přidávající heuristika. Můžeme ji však preferovat pokud chceme počítat co nejrychleji a pole věcí obdržíme již správně seřazené.
   
   

7. Odkazy

   Zdrojový kód programu batoh zde
   Makefile zde
   Vygenerované soubory instancí zde
   Výstupy 4 použitých algoritmů zde
   Výsledky seskupené do statistik zde
   bash skript pro výrobu statistik zde
   Zdrojové soubory grafů pro GLE zde

1. Zadání

   • Zvolte si heuristiku, kterou budete řešit problém vážené splnitelnosti booleovské formule (simulované ochlazování, simulovaná evoluce, tabu prohledávání).
   • Tuto heuristiku použijte pro řešení problému batohu. Můžete použít dostupné instance problému, anebo si vygenerujte své instance pomocí generátoru. Používejte instance s větším počtem věcí (>30).
   • Hlavním cílem domácí práce je seznámit se s danou heuristikou, zejména se způsobem, jakým se nastavují její parametry (rozvrh ochlazování, selekční tlak, tabu lhůta...) a modifikace (zjištění počáteční teploty, mechanismus selekce, tabu atributy...). Není-li Vám cokoli jasné, prosíme ptejte se na cvičeních.
   • Problém batohu není příliš obtížný, většinou budete mít k dispozici globální maxima (exaktní řešení) z předchozích prací, například z dynamického programování.
   
   

2. Platforma

   Úloha byla řešena programem napsaným v jazyce C (ansi). Program "batoh-ga" je konzolová realizace genetického algoritmu na problému batohu s množstvím parametrů a na standardním vstupu očekává instance problému ve "školním" formátu. Na standardím výstupu se objevují řešení ve "školním" formátu. Aplikace je nezávislá na host OS a parametrem --help zobrazí návod k použití.
   
   

3. Heuristika

   Jako pokročilá heuristika byl zvolen genetický algoritmus. Jedná se randomizovanou lokální iterativní metodu prohledávání stavového prostoru, při které probíhá diskrétní simulace procesu evoluce (simulovaná evoluce je nadmnožinou GA). Prohledávaný prostor je pokrýván množinou jedinců, kteří reprezentují možná řešení a existují operátory, které z existujících jedinců generují nové. Ve standardním GA je v populaci s konstantní velikostí prováděna selekce rodičovských jedinců, reprodukce generující potomstvo a nahrazení původní generace.
   
   Každý jedinec je reprezentován genotypem, což je zakódovaná informace o podobě jedince. Podoba jedince - fenotyp, je řešením problému (obecně nepřípustným) a zobrazení genotypu na fenotyp provedeme jeho dekódováním. Kódování do genotypu linearizuje informaci o podobě a transformuje ji do binární podoby, nad kterou lze provádět reprodukční operace - křížení, mutace. Genotyp se skládá z genů, což jsou jednotky pro uložení informace o řešení a manipulaci s ní při běhu algoritmu. Kvalita jedince je kvalita řešení, které odpovídá jeho genotypu a toto zobrazení je funkce "fitness" (zdatnost/vhodnost). Kvalita jedince je kritériem při výběru jedinců vhodných k reprodukci.
   
   Genetický algoritmus pracuje iterativně v následujících fázích:
   
   
   1. počáteční populace
   2. vyhodnocení fitness
   3. test ukončení
   4. reprodukce
   • selekce rodičů
   • křížení
   • mutace potomků
   5. nahrazení populace
   6. (návrat do bodu 2)
   
   
   Počáteční populaci je nutné vybrat s ohledem na rovnoměrné pokrytí stavového prostoru, např. náhodně (v případě absence omezujících podmínek a binární reprezentace genotypů jsou to náhodné řetězce 1/0). Při řešení problému s omezující podmínkou (zde nepřetíženost batohu), je nutné toto zohlednit buď při výpočtu fitness nebo při činnosti reprodukčních operátorů a generování počáteční populace. Řešení přizpůsobením informovaných operátorů negeneruje jedince s nepřípustnými řešeními, ale může snižovat dostupnost ve stavovém prostoru. Slepé operátory křížení (např. jednobodové křížení) a mutace (záměna bitu) vyžadují řešení nepřípustných genotypů zohledněním ve fitness (penalizace) nebo jednoduchou úpravou nepřípustného řešení na blízké přípustné, což je vlastně úprava dekódování na fenotyp. Ukončení algoritmu je dáno buď dosažením požadované kvality řešení nebo příznaky konvergence.
   
   Selekce zohledňuje monotónně hodnotu fitness funkce a existuje více možností její implementace (turnaj několika jedinců, ruletový výběr - úměrnost pravděpodobnosti aj.). Převod fitness na pravděpodobnost výběru zavádí prvek náhody. Selekční tlak (pravdepodobnost výberu nejlepších jedinců) lze ovlinit transformací fitness, např. lineárním škálováním do intervalu nebo zohledněním pořadí místo hodnot (ranking). Při turnajové selekci je hlavním činitelem selekčního tlaku velikost turnaje. Křížení (2 rodičů) mohou být z hlediska významu genů slepá (jednobodové, uniformní), která vkládají náhodné části genotypů rodičů do potomků nebo přizpůsobená konkrétnímu druhu problémů (např. permutační OX, PMX nebo hranová rekombinace). Slepá mutace je náhodná záměna bitu. Mutace je obecně prvek, který působí diversifikaci při prohledávání a snaží se tak kompenzovat ztrátu informace způsobenou selekčním tlakem. Pokud nemáme explicitní mechanismus, který udržuje diverzitu populace, pak nízká úroveň mutace působí degeneraci populace (zahlcení jedním, v daný okamžik, nejlepším řešením nebo několika blízkými) a přílišná intenzifikace tak způsobí uváznutí v lokálním extrému. Velká mutace působí divergenčně a algoritmus má vlastnosti náhodného prohledávání, proto je nutné nastavit vhodnou úroveň mutace (pravděpodobnost, že k ní dojde).
   
   V poslední fázi je populací potomků nahrazena celá nebo část původní populace. Způsobů řízení nahrazení populace je více. Technika, která v populaci zanechává malý počet nejlepších jedinců se nazývá "elitismus", což mimojiné zajistí monotónnost konvergence k optimálnímu řešení. Opakem k blokovému nahrazení celé původní populace potomky je "ustálená populace" (steady), při které je nahrazeno určité procento nejhorších starých jedinců nejlepšími novými. Mezi těmito krajními případy existují další přechodové formy, např. mí/lambda řízení populace.
   
   

4. Algoritmus

   Moje implementace GA k řešení batohu umožňuje většinu z výše zmíněných technik, celkově lze volit:
   
   
   • velikost populace
   • počet generací (nebo nekonečno)
   • podmínku na ukončeni hodnotou dosažené kvality
   • transormaci fitness - lineární škálování, ranking, mocnění plovoucím exponentem
   • algoritmus selekce - turnajová selekce, ruletový výběr, stochastické vzorkování
   • algoritmus křížení - jednobodové křížení, uniformní křížení
   • řízení populace - en-blok, ustálená populace
   • pravděpodobnost křížení
   • pravděpodobnost mutace
   • velikost turnaje pro turnajovou selekci (plovoucí hodnota - střídání menších a větších)
   • procento populace k nahrazení pro ustálenou populaci
   • velikost elity
   
   
   Hodnotou fitness funkce je cena věcí v batohu. Genotyp je pole genů, které kódují přítomnost/nepřítomnost věci v batohu. Kódování, která by vedla na přetížený batoh jsou interpretována jako po odebrání věcí v pořadí rostoucí výhodnosti (poměru cena/váha), až do dosažení přípustného řešení. Tato možnost dovoluje použití slepých operátorů křížení a mutace a nepotřebuje zavádět do fitness funkce penalizaci. Výchozí hodnoty všech parametrů vycházejí z provedených experimentů a u žadných testovacích dat nebylo třeba k dosažení dobrých výsledků jejich hodnoty měnit výrazně.
   
   

5. Experimenty

   Ukázalo se, že menší instance řeší vhodně nastavený GA bez problému s průměrnou kvalitou blížící se exaktním algoritmům. Neporadí si pouze s klamnými instancemi, které každý balík školních instancí jednou obsahoval. Je to proto, že takováto evoluce si neporadí s problémy typu "jehla v kupce sena"; jde o lokální metodu, takže potřebuje "vidět" směr cesty k cíli, avšak klamná funkce ji svádí po celou dobu jinam. Žádnou z klamných instancí se nepodařilo vyřešit a kdyby tomu tak bylo, šlo by o pouze náhodu. Další experimenty jsem prováděl na instancích o velikosti 40.
   
   

   Doba běhu

   Doba běhu algoritmu je přímo úměrná počtu generací a mírně superlineární k velikosti populace (některé minoritní operace s populací mají lineárně-logaritmickou složitost). Pro velikost populace 100 a 100 iterací trvá výpočet (stejný stroj jako v úloze 1) cca 4.5 sec, což je o 2 řády více než dynamické programování (při použité maximální ceně) a o 4 více než metoda větví a hranic pro balík 50 instancí s jednou klamnou, která je neprořezatelná (její řešení trvá zhruba stejně dlouho jako řešení hrubou silou). Pro ořezatelné instance je rychost srovnatelná s takto nastaveným GA. Ořezávání pracuje jako algoritmus Las Vegas, GA je zde spouštěn jako algoritmus Monte Carlo (přístup Las Vegas bychom získali použitím podmínky pro ukončení).
   
   

   Chyby

   Narozdíl od exaktních metod, u GA pozorujeme na větších instancích nenulovou průměrnou relativní chybu. Dosažená kvalita (i rychlost) řešení závisí na parametrech algoritmu. Použitelné výsledky obdržíme již od velikosti populace 10 (100 generací), jejím zvětšováním se kvalita zlepšuje, pro 100 (výchozí hodnota) nalezne v cca 90% případů GA optimální řešení a ve zbytku případů se od něj liší do cca 0.25 %. Se zvyšujícím počtem generací se situace zlepšuje (rychleji pro menší populace, které měli původně větší chybu) tak, že od cca 500 (100 jedinců) pozorujeme chybu takřka výhradně jen na klamných instancích (na zbytku se jedná o setiny % v jednotkovém počtu případů a v některých případech by tyto rozdíly šly odstranit pouze pokusem o přidání zbylých předmětů). Přesný průběh průběh průměrné chyby na balíku testovacích instancí je v grafu níže.
   
   

   Ostatní parametry

   Jako nejlepší algoritmus výběru se zde ukázalo stochastické vzorkování s fitness přepočtenou na pořadí (ranking). Srovnatelné výsledky na testovaných instancí dávala i turnajová selekce, ale až pro velké turnaje a velký selekční tlak by se mohl negativně projevit na instancích s jinými vlastnostmi než na testovacích. Ranking udržuje selekční tlak konstantní. Stochastické vzorkování je vylepšený ruletový výběr, kdyje zaručena selekce nejlepšího jedince a menší rozptyl v rozdělení náhodného výběru. Vyžaduje sice alokaci paměti, ale narozdíl od rulety lze spočítat v jednom průchodu pro celou populaci. Křížení jsem použil jednobodové i uniformní s náhodnou volbou. Volba pouze jednoho z nich nevedla k pozorovatelným změnám ve kvalitě řešení. Pravděpodobnost křížení 90 % se ukázala jako vhodná pro nahrazování celé populace, ale nakonec byla jako výchozí použita ustálená, která zde lépe konverguje a u ní není pravděpodobnost křížení tolik rozhodující jako když se nahrazuje všemi potomky. Pravděpodobnost mutace se v programu nastavuje inverzní hodnotou (statistický počet bitů na 1 změněný) a jako použitelný se jevil interval 10 - 20. Menši inverzní pravděpodobnost mutace vedla na příliš náhodné prohledávání a tím i větší chyby. Naopak při vyplé mutaci se projevila ztráta informace vlivem selekčního tlaku a algoritmus ve většině případů optimální konfiguraci nenalezl. Všechno ostatní zde uvedené platí pro hodnotu 15. S velikostí elity jsem experimentoval do doby, než jsem přešel k řízení ustálenou populací, kde explicitní elitismus není třeba. Při nahrazování celé populace zajišťoval elitismus velikosti 2 monotónnost konvergence k optimu a její celkově výrazně lepší průběh.
   
   Následující obrázky ukazují průběhy kovergence a relativních chyb GA s výchozím nastavením a -pm=15:
   
   

   Obr 5.1 Průběhy konvergence řešení pro některé známé instance - instance velikosti 40	Obr 5.2 Průběhy chyb v závislosti na velikosti populace - instance velikosti 40

   
   
   

6. Závěr

   Zevrubně jsme se seznámili s genetickým algoritmem nasazeném na problému batohu. Podařilo se ho implementovat a úspěšně použít k řešení větších instancí.
   
   

7. Odkazy

   Zdrojový kód programu batoh-ga zde
   Makefile zde
   Výsledky seskupené do statistik zde
   bash skript pro výrobu statistik zde
   Zdrojové soubory grafů pro GLE zde

1. Zadání

   Je dána booleovská formule F proměnnných X=(x₁, x₂, ... , x_n) v konjunktivní normální formě (tj. součin součtů). Dále jsou dány celočíselné kladné váhy W=(w₁, w₂, ... , w_n).  Najděte ohodnocení Y=(y₁, y₂, ... , y_n) proměnných x₁, x₂, ... , x_n 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).
   

   Poznámka

   Obdobný problém, který má optimalizační kritérium ve tvaru "aby počet splněných klausulí byl maximální" a kde váhy se týkají klausulí, se také nazývá problém vážené splnitelnosti booleovské formule. Tento problém je lehčí a lépe aproximovatelný. Oba problémy se často zaměňují i v seriózní literatuře.
   
   

2. Platforma

   Úloha byla řešena programem napsaným v jazyce C (ansi). Program "sat-ga" je konzolová realizace genetického algoritmu na problému vážené splnitelnosti booleovské formule s množstvím parametrů a na standardním vstupu očekává instance problému ve formátu DIMACS. Aplikace je nezávislá na host OS a parametrem --help zobrazí návod k použití.
   
   

3. Heuristika

   Jako pokročilá heuristika byl zvolen genetický algoritmus. Jedná se randomizovanou lokální iterativní metodu prohledávání stavového prostoru, při které probíhá diskrétní simulace procesu evoluce. Vzhledem k flexibilitě kódu z úlohy 5 je výpočetní jádro algoritmu stejné (viz. úloha 5. S tímto bylo počítano a program pro SAT se liší v načítání dat a definici fitness funkce. Vstupem do programu je zápis formulí ve formátu DIMACS, vylepšeném o možnost definice vah proměnných direktivou "w 1 2 3 4". Zápis nemusí být ve formátu 3-SAT, ale v libovolné konjunktivní formě (cnf).
   
   

   Fitness funkce

   Fitness funkce musí zohledňovat kritéria zadání. Vzhledem k tomu, že primární kritérium je nalézt připustné řešení a legalita řešení spočívá ve splňení všech uvedených klauzulí, je jednou složkou hodnocení počet splňených klauzulí. Strategie nejmenší opravy jedinců, jako v řešení batohu, zde nelze použít, protože samotná slpnitelnost je těžký problém. Zároveň se zdá, že omezení se na manipulaci pouze s legálními konfiguracemi by rapidně omezilo dostupnost stavového prostoru při použití slepých operátorů. Strategie zahazování nepřípustných jedinců je zde zcela nepoužitelná. Rověž návrh problémově závislých operátorů naráží na složitost splnitelnosti a nesouvislost takto vzniklého prohledávacího prostoru. Proto volíme relaxaci/penalizaci na úrovni hodnotící funkce jako techniku poskytující konvergenci k požadovaným výsledkům.
   
   Sekundární kritérium problému je součet vah nastavených proměnných. Toto je rozhodující, pokud porovnáváme ohodnocení se stejným počtem splněných klauzulí, zejm. pokud je splněna celá formule. Není přesně zřejmé, jak uspořádat nesplněné formule s různou sumou vah, pokud se počet jejich splněných klauzulí blíží. Je ovšem zcela zřejmé, že všechny splněné formule by měly dominovat nesplněným. Návrh konkrétní fitness prošel sérií experimentů na instancích s odlišnými parametrami (poměr klauzulí a proměnných, velikost instance, náhodné váhy) a jako základ pro další experimenty byla zvolena penalizace za nesplněnou klauzuli (vzhledem k požadavku na kladnou fitness v algoritmu jde o bonifikaci opaku) a bonifikace úměrná sumě vah nastavených proměnných, která zároveň splňuje výše úvedené monotoity (konkr. uspořádání je primárně podle splněnosti a sekundárně podle vah). Uvedené monotoity je vhodné dodržet zcela, vzhledem k tomu, že některé techniky selekce se dotazují pouze na uspořádání zdatností a nikoliv konkrétní hodnoty (turnajová selekce). Je možné bonifikovat skutečnost, že byla splněna celá formule, ale toto má vliv pouze, pokud jsou použity konkrétní techniky selekce a nahrazování populace.
   
   

   Řízení populace

   Lze se domnívat, že počáteční (náhodná) populace bude obecně prosta splněných formulí a zpočátku bude nutné pracovat s formulemi nesplněnými a diverzifikací získat nějaké splněné, které by se daly dále šlechtit na maximalizaci vah. Oba problémy spolu ale souvisí, protože maximalizace vah nám může splněnost porušit, ale i naopak zajistit. Nemá tedy cenu splněné klauzule favorizovat příliš, spíše je vhodné použít elitismus, který nám nejlepší dosud nalezené řešení v populaci udrží a navíc zajistí i nadprůměrnou selekci splněné klauzule v rámci generace. Při volbě výchozího řízení populace, resp. nahrazovací strategii, bylo nejprve experimentováno s blokovým nahrazováním. Průběhy konvergence a dosahované výsledky však nasvědčovaly tomu, že dochází k příliš velké ztrátě informace o dobrých jedincích nebo těch, kteří jsou blízko dobrých výsledků. Díky tomu průběhy často stagnovaly a legální konfigurace se vyskytovaly prakticky pouze v elitě. Toto pozorování mě vedlo k aplikace ustálené populace (steady-state).
   
   Ustálená populace má na tomto problému výhodu v tom, že udržuje dostatečné množství dobrých jedinců, které jsme někdy nalezli a zde jsou to díky volbě fitness zejm. ty konfigurace, které tvoří přípustná řešení (forumle je splněna). Taková populace poskytuje dobrý základ pro reprodukci za účelem nalezení legálních konfigurací s maximálním sekundárním kritériem - váhami. Zároveň však udržuje oběh informace minimálně v té části populace, která je nahrazována (zde 10 %). Odpadá pak nutnost bonifikovat splněnost na úrovni formulí, protože toto řízení jich samo o sobě udržuje dostatečně na možnost volby správného selekčního tlaku. Zároveň se zde uplatní to, že zpočátku, kdy je populace v průměru špátná, provádí algoritmus spíše diverzifikaci (neupíná se ke splněným nebo téměr splněným ohodnocením, protože je dosud nezná) a po nalezení legálních konfigurací provádí spíše intenzifikaci v okolí legálních konfigurací, které zná. V těchto místech lze očekávat největší pravděpodobnost nalezení něčeho zajímavého. Jde zde vlastně o jednoduchou adaptaci obsahu populace jejím použitým řízením.
   
   

   Vliv vah, operátory

   Výše zmíněná definice fitness funkce má však jednu nevýhodu. Splněné formule mají vysokou zdatnost a jednoduché vyjádření s dodržením výše zmíněného uspořádání zapříčiní, že nastavené vahy ji už příliš nezmění. Nemuselo by pak nedocházet k adekvátní selekci při intenzifikaci (pro techniky pracující s hodnotami). Proto jsem zvýšil vliv sekundárního kritéria v případě že primární bylo splněno. Tato úprava je počítána relativně - poměr maximálních hodnot těch dvou složek je konstantní (narozdíl od nesplněných formulí, zde mohou váhy ovlivnit výslednou fitness ještě další poloviční hodnotou fitness splněné formule), takže by neměla existovat závislost na parametrech instance. Zároveň jsme tím neporušili stanovené uspořádání, protože se úprava týkala okraje oboru hodnot zdatnosti.
   
   Operátory křížení jsou slepé, jednobodové a uniformní (jedno náhodně zvolené), mutace je inverze bitu. Optimalizace parametrů pravděpodobnosti křížení a mutace byla provádněna slepě s apriorní informací ze zkušeností u GA na jiných problémech. Jako výchozí hodnoty pro experimentování byly zvoleny 0.95 pro křížení a 0.067 (každý 15.) pro mutaci.
   
   

4. Experimenty

   Nejprve zkusíme menší problémy bez použití vah, abychom se přesvědčíli, zda-li algoritmus nastavený dle výše uvedených úvah (a pro velikost populace 100, pokud není uvedeno jinak) konverguje k uspokojené formuli. Instance byly vybrány z balíků splnitelných formulí zde. Tyto instance mají poměr klauzulí a proměnných 4.3, což je hodnota považovaná za hranici fázového přechodu splnitelnosti a takové instance jsou nejhůř rozhodnutelné, tudíž nalezení optima by mělo být náročnější než jindy. Na obr. 6.1 vidíme, že nalezení globálního optima pro menší instance nečiní algoritmu problémy a všech 7 testovacích instancí o 50 proměnných dokonvergovalo ještě před dosažením 50. generace.
   
   

   Obr 6.1 Průběhy konvergence řešení pro nevážený 3-SAT, 100 jedinců v populaci

   
   
   Nyní zkusíme větší instance. Obr. 6.2 ukazuje, že pro 50 proměnných bude zapotřebí více než 100 generací. Na obr. 6.3 vidíme situaci pro 500 generací. Zde již bylo pro 5 ze 7 instancí nalezeno globální optimum, 2 formule zůstaly ve stavu s jednou nesplněnou klauzulí z 218. To je poměrně slušný výsledek.
   
   

   Obr 6.2 Průběhy konvergence řešení pro nevážený 3-SAT, 100 jedinců v populaci	Obr 6.3 Průběhy konvergence řešení pro nevážený 3-SAT, 100 jedinců v populaci

   
   
   Zkusme ještě instance velikosti 100, tozn. 430 klauzulí ke splnění. Opět ale budeme muset zvednout počet generací, protože obtížnost problému roste, viz obrázky 6.4 a 6.5 (obrázek pro větší počet generací má logaritmickou osu x !}. Konvergenční tendence je zřetelná a při větším počtu generací jsme docílili jedné úplně splněné formule a ostatním chyběly 1-2 klauzule. Z logaritmického zobrazení je vidět že k optimu se blížíme exponenciálně (zobrazený průběh je zhruba lineární).
   
   

   Obr 6.2 Průběhy konvergence řešení pro nevážený 3-SAT, 200 jedinců v populaci	Obr 6.3 Průběhy konvergence řešení pro nevážený 3-SAT, 200 jedinců v populaci

   
   
   

   Optimalizace parametrů GA

   Z prvních měření se zdá, že algoritmus dokáže splnitelnost optimalizovat uspokojivě. Zatím jsme se ovšem omezili na jeden konkrétní poměr počtu klauzulí a proměnných (a na 3-SAT, což je předpoklad zadání). Jiné poměry nám poskytnou náhodně vygenerované instance, ke kterým můžeme přidat i váhové ohodnocení proměnných. Na těchto instancích zkusíme optimalizovat parametry GA. Je třeba zohlednit randomizovaný způsob práce algoritmu, a tak bude vhodné na každé hodnocení při jistém nastavení parametrů provést více měření (5x pro každou instanci z balíku a počítá se průměr). Zároveň je nutné pokrýt prohledávací prostor parametrů dostatečně, takže budeme odezvu na parametry GA měřit pro balík instancí s různým poměrem počtu klauzulí a proměnných (konkr. 8 od 1 do 7 se zhruba normálním rozdělením okolo 4.3) a s různým počtem klauzulí (50 - 350). Váhy proměnných jsou vygenerovány náhodně (s rovnoměrným rozdělením).
   
   Vzhledem k tomu, že optimální řešení instancí nebudeme znát a instance s různými parametry budou mít různé zdatnosti globálních optim, nelze jejich výsledky přímo sčítat nebo počítat jejich průměr. Hodnotící funkce je však navržena tak, že tato hodnota by měla být v asymptotě úměrná počtu klauzulí (i příspěvek váhové složka se odvíjí od tohoto čísla), což nás opravňuje (pokud dáváme všem možným instancím stejný význam) k vážení výsledků hodnotou úměrnou počtu klauzulí instance (event. ku celkovému počtu klauzulí v balíku pro normalizaci k 1). Tato lineární kombinace nejlepších nalezených zdatností jednotlivých "trénovacích" instancí bude hodnocením pro aktuální nastavení parametrů. Aktuální parametry mají jako základ jisté výchozí parametry (jinak by se muselo optimalizovat ve velkém počtu dimenzí, často pro nesmyslné kombinace a celková optimalizace by nebyla příliš efektivní vzhledem k její pracnosti, takto optimalizuje hladově), určené na základě úvah v části o heuristice a předchozích měření. Soubor optimalizovaných parametrů GA a jejich výchozí hodnoty (také defaultní parametry programu) jsou:
   
   
   • velikost populace: 100
   • počet generací: 500
   • algoritmus selekce: stochastické vzorkování
   • pravděpodobnost křížení: 0.95
   • pravděpodobnost mutace: 0.067
   • nahrazovací strategie: ustálená populace, 10 %
   
   
   Následující obrázky zachycují citlivost dosažených výsledků na parametrech GA:
   
   

   Obr 6.4 Hodnocení výsledků v závislosti na velikosti populace	Obr 6.5 Hodnocení výsledků v závislosti na počtu generací

   
   
   

   Obr 6.6 Hodnocení výsledků v závislosti na pravděpodobnosti křížení	Obr 6.7 Hodnocení výsledků v závislosti na pravděpodobnosti mutace

   
   
   

   Obr 6.8 Hodnocení výsledků v závislosti na algoritmu selekce	Obr 6.9 Hodnocení výsledků v závislosti na nahrazování populace

   
   
   Výsledky grafů na obr. 6.4 - 6.9 jsou vážené součty nejlepších nalezených zdatností na instancích z testovacího balíku (viz. výše), navíc zprůměrované přes více spuštění. Pokud bychom nepoužili váhy, měly by splnitelné formule max. fitness 1.0, dalších max. 0.5 může být příspěvek od vah (to pokud by bylo možno nastavit všechny proměnné). Zlepšující závislost na velikosti populace (obr. 6.4) nepřekvapí, ale dává představu o minimální použitelné velikosti populace - 50. Výchozích 100 nechává rezervu i pro složitější instance. Zdá se, že použití větších populací se příliš nevyplatí (výpočetní sílu bychom měli orientovat spíše na počet iterací). Závislost na počtu generací (obr. 6.5) je zcela jistě rostoucí (pouze s vypnutým elitismem při blokovém nahrazování by mohla i klesat) a jak je vidět, tyto instance se dají dobře uspokojit (příznaky konvergence) od cca 500, kdy na grafu zůstávají spíše fluktuance randomizace. 100 bych považoval za minimum.
   
   Poněkud překvapující je poměrně rovná závislost výsledků na pravděpodobnosti křížení (i pro < 50, což není zobrazeno, obr. 6.6), pouze blízko před 1 (mezi 95 % a 100 %) se objevuje významnější bod. Při nižších hodnotách se křížení prakticky neprojevuje, resp. zdá se, že nepřináší užitečnou informaci v porovnání s expanzí stavového prostoru, kterou provádí operátor mutace. Při dodatečném pokusu se křížení začlo opět projevovat až při dostatečném snížení vlivu mutace, což zde není znázorněno. Slepé křížení se tedy neukazuje jako příliš silné pro SAT, zde můžeme použít hodnotu z intervalu 95 % - 99 %. Pravděpodobnost mutace (obr. 6.7) má výraznější vliv a průběh grafu je typický - začátek (5) je zobrazení situace s příliš velkou mutací, kdy prohledávání ztrácí systematičnost a konec (cca 50+) je situace, kdy šum mutace nestačí kompenzovat ztrátu informace selekčním tlakem. Rozumná hodnota bude mezi 10 a 20 (jde o invertovanou hodnotu vlastní pravděpodobnosti), a proto výchozích 15 můžeme akceptovat.
   
   Různé algoritmy selekce spolu s jejich parametry ukazuje obr. 6.8. Pokud bychom chtěli použít turnajovou selekci, měla by se velikost turnaje (pro 100 jedinců) pohybovat okolo 6. Tento údaj je však třeba brát s rezervou, protože tento parametr by bylo nejlépe adaptovat s časem a tak, abychom nevyvíjeli přehnaný selekční tlak velkými hodnotami. Takovou adaptaci zde neřešíme, ale dozvědeli jsme se alespoň, jakou hodnotu použít jako vodítko, pokud bychom ji chtěli implementovat. Ruletový výběr dává poněkud horší výsledky než univerzální stochastické vzorkování, což odpovídá tomu, jak obě techniky fungují. Použití rankingu nám výsledky nezlepšilo, což znamená, že hodnoty fitness funkce nejsou navrženy nevhodně, což je potěšující informace. Jelikož nejlepší a zhruba stejné výsledky dává turnaj o velikosti 6 a stochastické vzorkování s původní hodnotou fitness, volíme jako vhodnou metodu stochastické vzorkování, protože odpadá nutnost určovat velikost turnaje a selekční tlak se řídí hodnotami fitness funkce, o které si myslíme, že je navržena použitelně. Strategie nahrazování (řízení populace) máme zobrazeny na obr. 6.9. Zcela nevhodné je nahrázování en-blok bez použití elitismu. Jeho použití situaci zlepšuje, avšak jako nejvhodnější se jeví použít ustálenou populaci (steady-state). Velikost nahrazované části (nejhorší jedinci) se může pohybovat v okolí 10 %, jiné hodnoty jsme netestovali, protože nejsou typické. Výsledky z posledního grafu dávají za pravdu úvahám z části o heuristice.
   
   

   Testy na jiných datech

   S optimalizovanými hodnotami heuristiky bychom měli vyzkoušet činnost algoritmu na dalších datech. Použijeme náhodně vygenerované 3-SAT vážené instance s proměnným počtem proměnných (10 - 90} a s oblíbeným poměrem počtu klauzulí a proměnných 4.3. Dopředu o nich nevíme, zda-li jsou splnitelné (u instancí s více proměnnými volíme tedy raději více generací). Nyní nás zajímá, jak si algoritmus poradí s optimalizacemi, které by měl provádět. Zde jsou výsledky (přesné aktuální hodnoty parametrů algoritmu viz helpscreen --help):

   
   $ ./sat-ga.exe <inst/weighted/vars_10.cnf -i=500 -v
   best fitness found: 54.72
   phenotype: clauses satisfied: 43 (100.00%), sum of weights: 53 (55.79%)
   genotype: 0101001110
   
   $ ./sat-ga.exe <inst/weighted/vars_30.cnf -v -i=1000
   best fitness found: 161.86
   phenotype: clauses satisfied: 129 (100.00%), sum of weights: 171 (51.35%)
   genotype: 101111100010111001000011001011
   
   $ ./sat-ga.exe <inst/weighted/vars_50.cnf -v -i=2000
   best fitness found: 275.39
   phenotype: clauses satisfied: 215 (100.00%), sum of weights: 298 (56.44%)
   genotype: 10001111111100101010111111100010100111110010010011
   
   $ ./sat-ga.exe <inst/weighted/vars_70.cnf -v -i=2000
   best fitness found: 300.66
   phenotype: clauses satisfied: 300 (99.67%), sum of weights: 501 (65.58%)
   genotype: 0101011101100111000011111001110001110110101011101101111111011100000110
   
   $ ./sat-ga.exe <inst/weighted/vars_90.cnf -v -i=5000
   best fitness found: 386.66
   phenotype: clauses satisfied: 386 (99.74%), sum of weights: 639 (65.54%)
   genotype: 000011101111001001111101111100111111101010111100101111100101110011111011101111010011010001
   
   

   U prvních třech instancí jsme splnili všechny klauzule a konfrontace genotypu s váhami ze souborů dává představu o snaze optimalizovat součet vah. U 2 instancí s větším počtem proměnných se nám podařilo splnit všechny klauzule až na jednu pro 70 proměnných a 2 pro 90. Vzhledem k tomu, že nezafungovalo použití větší populace, spuštění jako Las Vegas, jiná selekce/nahrazování ani upravování jiných parametrů (pravděpodobnost mutace), je možné, že formule absolutně splnitelné nejsou (leč dokázat to lokální metodou nikdy nemůžeme). K optimalizaci součtu vah však dochází i tak (i když ne se stejným selekčním tlakem, jako pokud by se formuli podařilo splnit, protože v tom případě by získala tato složka fitness větší vliv). Celkově se zdá, že algoritmus poskytuje dobré výsledky. Bylo by zajímavé konfrontovat tyto konkrétní výsledky s někým, kdo řešil úlohu pomocí SA nebo Tabu search.

5. Závěr

   Bylo implementováno řešení problému vážené splnitelnosti booleovské formule heuristikou používající genetický algoritmus. Experimentálním vyhodnocením na známých DIMACS instancích se podařilo ověrit prvotní fuknčnost a dále pak najít vhodné parametry heuristiky. Hledání vhodných parametrů bylo prováděno na balíku náhodných instancí s různými poměry počtu klauzulí a proměnných ve snaze pokrýt prostor instancí. Potvrdily se některé úvahami získané odhady vhodných parametrů a použitých technik. Vhodně se jevící parametry jsou nastaveny jako výchozí parametry programu a dají se upravovat argumenty. Vyladěná heuristika byla testována na několika dalších náhodných instancích s různým počtem proměnných, z nichž u většiny byla schopna najít konfiguraci úplně splněných formulí, dále prováděla maximalizaci součtu vah, což je druhým kritériem úlohy. Dosažené výsledky považuji za dobré, avšak objektivní hodnocení na konkrétních instancích by vyžadovalo nějakou referenci pro absolutní či relativní srovnání.
   
   

6. Odkazy

   Zdrojový kód programu sat-ga zde
   Makefile zde
   Soubory splnitelných instancí bez vah zde
   Soubory náhodných instancí s váhami zde
   Výsledky seskupené do statistik zde
   bash skript pro výrobu statistik zde
   Zdrojové soubory grafů pro GLE zde
   bash skript pro výrobu grafů zde

© 1997-2008 Jan Skalicky
cz (dot) skalda (at) seznam (dot) cz