4. domácí úloha z předmětu PAA

Experimentální hodnocení algoritmů pro řešení problému batohu

Oto Válek

Problém batohu je řešen hrubou sílou s detekcí přetížení (1), heuristikou cena/váha (2), metodou větví a hranic (3), dynamickým programováním (4) a heuristikou podle poměru cena/váha s testem nejdražší věci (5). Bližší popis metod viz řešení 1.úlohy a 3.úlohy Sledována byla výpočetní náročnost a chyba řešení podle zadání.

Čítač kroků řešení byl zvyšován na vhodném místě v hlavní rekurzivní funkci algoritmu. U heuristik vybírajících nejvyšší poměr cena/váha byl navíc umístěn do cyklu příslušné funkce, aby se projevila O(n) složitost pro každý navštívený stav. U metody hrubé síly, dyn. programování a metody větví a hranic však počet kroků zhruba odpovídá počtu navštívených stavů stavového prostoru.

Čas byl měřen funkcí ftime() ze std. C knihovny v prostředí WinNT. Byl použit kompilátor z MS VC 5.0 s defaultním nastavením a procesor Intel Pentium 100 Mhz.

Pro generování instancí byl použit zkompilovaný připravený generátor. Defaultní hodnoty parametrů byly zvoleny podle WWW formuláře:

 -n  20 Velikost instance [10,15,20,25,30]
 -N  50 Počet instancí 
 -W 100 Maximální váha věci
 -C 250 Maximální cena věci [50,150,250,350,450]
 -m 0.6 Poměr sumární váhy ke kapacitě batohu [0.2,0.4,0.6,0.8,1]
 -d   0 Charakter granularity (-1 více malých, 1 více velkých) [-1,0,1]
 -k   1 Exponent závislosti granularity
 -I   0 Základní ID

Sledována byla závislost na vybraných parametrech, které nabývají následujích hodnot (ostatní parametry na defaultních hodnotách) :

 -n [10,15,20,25,30]     Velikost instance
 -C [50,150,250,350,450] Maximální cena věci
 -m [0.2,0.4,0.6,0.8,1]  Poměr sumární váhy ke kapacitě batohu
 -d [-1,0,1]             Charakter granularity (-1 více malých, 1 více velkých)

Každé hodnotě parametru odpovídá vygenerovaných 50 instancí, v úvahu je brán aritmetický průměr.

Měřen byl reálný čas, počet kroků řešení, a relativní chyba proti nejlepší nalezené ceně, kterou zde představuje výsledek metody dynamického programování. U metody hrubé síly byl test ukončen pro n=20.

Následuje srovnání algoritmů podle výpočetní náročnosti a chyby řešení. Každé měřené kombinaci parametrů generátoru odpovídá jeden bod v ploše - průměr z 50 instancí. Čas je vynesen v logaritmickém měřítku.

Změna maximální ceny věci činnost algoritmů v podstatě neovlivňuje. S vyššími hodnotami cen se jen zvyšuje jakási "inflace" v úloze - i výsledná max. cena je vyšší. Růst ceny (a tím především relativní zjemňování intervalu) prospívá jen v malé míře metodě větví a hranic, jelikož ořezání podle optimalizačního kritéria nastává dříve.

Chyba heuristických metod nabývá nevýrazného maxima pro C=250, pro což jsem nenalezl vhodné vysvětlení.

Překvapivé zjištění je, v žádném případě nehraje roli, zda převažují věci malé nebo velké, podstatný je jen rozdíl mezi rovnoměrným a nerovnoměrným rozložením vah věcí.

Ve výpočetní náročnosti výraznější rozdíly nejsou, heuristika se doupuší na nerovnoměrně rozložených vahách věci menší chyby.

Tento parametr má na průběh algoritmů velmi podstatný vliv. Menší hodnoty parametru (tj. "hodně věcí na výběr a malý batoh") vyhovují hrubé síle a dynamickému programování. U těchto metod se dříve prosadí kontrola přetížení batohu, která stavový prostor ořeže více právě v případě, kdy je věcí o hodně více, než se jich do batohu vejde.

Metodě větví a hranic naopak vyhovuje případ, kdy se do batohu vejde většina věcí. Vzhledem k tomu, že moje implementace v každém kroku nejprve věc přidává je velmi brzy nastavena ořezávací hodnota opt. kritéria blízko max. ceny a většina stavového prostoru se pak neprohledává.

Heuristika cena/váha má s rostoucí hodnotou parametru "stále méně na výběr" a tedy "stále méně co zkazit" a tak relativní chyba klesá.

Tato závislost je už podrobněji rozebrána ve 3. úloze. Výpočetní náročnost hrubé síly je exponenciální. Totéž lze říci i o metodě větví a hranic, i přes značné snížení počtu kroků. Přesto je v mé implementaci výhodnější než dynamické programování pro instance menší než cca 22-33 věcí.

Metoda dynamického programování se ukázala nejvýhodnější pro vyšší n. S rostoucím n se počet kroků blíží lineární závislosti.

Chyba heuristiky cena/váha s rostoucím počtem věcí klesá. Ubývá totiž zastoupení "výjimek", které kazí zjednodušený pohled heuristiky na problém.