Seznámení se se zvolenou pokročilou iterativní metodou na problému batohu

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.
  • 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 slekce, 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í.
  • Zpráva z tohoto úkolu má být co nejstručnější: použitá metoda, způsob nastavení parametrů, výsledky.

Použité algoritmy

V rámci této úlohy jsem implementoval 2 různé algoritmy z oblasti pokročilých iterativních metod.
Jedná se o mravence a genetický algoritmus.

Mravenci

Tato metoda pracuje na jednoduchém principu. Jsou vytvořeni mravenci a ti se snaží nandat do batohu co nejvíce věcí. Po každí iteraci zůstává na každé věci pach a to tak silný, v jak dobrém řešení byl použit. Tyto iterrace se opakují dokud není v několika po sobě následujících iterací nalezeno lepší řešení.
Konkrétní implementace vybírání věcí do batohu pracuje ve 2 fázích. V první provede mravenec předvýběr. Podle pachu s určitou pradněpodobností vybere podmnožinu věcí. V druhé fázi, pokud tato podmnožina není řešením (celková hmotnost je vyšší než nosnost batohu) náhodně mravenec odebírá věci, dokud nezíská řešení.
Po provedení všech pokusů (všemi mravenci) zanechá každý mravenec na každé věci pach odpovídající právě tomu, v jak dobré konfiguraci se nacházel.
V průběhu implementace jsem zjistil, že pokud je počet mravenců stálý, stopá rel. chyba s počtem věcí, proto se v konečné implementaci používají tyto konstanty.
Počet marvenců věcí X 2
počet nenalených zlepšení pro konec algoritmu 20

Genetický algoritmus

Genetický algoritmus pracuje na několik fází. V první fázi přidává do různých chromzonů náhodně věci tak dlouho dokud by nedošlo k přeplnění, tzn. že se nesnaží doplňovat malými věcmi poté.
Tím je vytvořena první generace a je možné spustit hlavní smyčku, která opět jako u mravenců je ukončena sérií iterací, kdy se nenajdou lepší řešení.
V každé takové iteraci dochází ke křížení. Každý jedinec si náhodně vyběre partnera a s ním se skříží (jeden jedinec si volí jen jednou za iteraci). To probíhá tak že jejich potomek má jejich společné věci a poté získá všechny co se vejdou z těch které má jen jeden z rodičů. Toto pořadí (ve kterém dochází k pokusu vložit) je určeno náhodně.
Do další generace se dostanou i mutanti. Z každého může během jedné iterace vzniknout maxilně jeden. To probíhá tak, že se náhodně vybere věc, a pokud jí půdodní jedinec neměl a vejde se do batohu alespoň samotná mutant vznikne. Dále je nutné uvolnit případné místo takové věci. To se děje tak, se náhodně odebírají věci, dokud není místo dostatečné
Do nové generace, mohou postoupit i nejlepší ze současné, tzv. TOP-10.
Tyto tři způsoby generování nové generace by ale značně zatěžovali, a tak se ze vzniklé generace zachová jen TOP-X.
Počet nejlepších přežívající zkrz generace 10
Počet hledání partnerů na iteraci 1
Maximum mutanců z jedince 1
Maximum jedinců v jedné generaci 32
 
Ani jeden z algoritmů nenajde s jistotou optimální řešení, proto jsem pro porovnání použil heuristiky a tabulku zniklou jejich chybami v závislosti na testovacích datech v souborech pro 1. úlohu.

Výsledky

Získání rel. a abs. chyb na testovacích datech.
prům. rel. prům. abs. max. rel. max. abs.
Heuristika podle klesající ceny 1 48 24 421
Heuristika podle rostoucí hmotnosti 8 258 65 938
Heuristika podle poměru cena/hmotnost 0 10 36 121
Heuristika podle klesající ceny (s testem) 1 48 24 421
Heuristika podle rostoucí hmotnosti (s testem) 8 257 46 938
Heuristika podle poměru cena/hmotnost (s testem) 0 9 24 121
Metoda mravenčí kolonie 4 167 43 709
Genetický algoritmus 0 8 2 100

Program

Aplikace je psaná v Javě 1.5 (JBuilder 2006). Pro spuštění bude možná nutné upravit cestu k interpretu v souboru run.bat.

Závěr

Z naměřených dat je patrné, že nejlepším z měřených byl genetický algoritmus. Díky své podstatě je ale také nejnáročnější z vybraných algoritmů.
Metoda mravenců poskytuje také dobré výsledky ale ve srovnání s heuristikou cena/hmotnost (s testem) se nejedná o přínost, zvláštně s ohledem na vyšší složitost.
Tato naměřená data je nutné brát s rezervou, protože jsou z velké míry zatíženy náhodným elemenentem (např. v jednom měření byla max. rel. chyba metody mravenců 12%. zde je 43%. Z toho je patrné že může dojít k velmi rozdílným výsledkům. U genetické algoritmu nebyly takto velké rozdíly spatřeny)