4. úloha - experimentální hodnocení algoritmů pro řešení problému batohu

Tomáš Kubeš - kubest1
FEL-ČVUT PAA (Problémy a algoritmy) LS 2005

Úvod

Pro řešení problému batohu existuje mnoho algoritmů jak exaktních, tak přibližných. O jejich vlastnostech toho není mnoho známo, pouze pro kombinované heuristiky byla dokázána maximální chyba. Chceme-li vědět více, musíme vyhodnocovat experimentálně.

Zadání

Cílem je prozkoumat citlivost metod řešení problému batohu na parametry instancí, konkrétně na maximální cenu resp. váhu, poměr nosnosti batohu a celkové váhy věcí.

Popis úlohy

Budeme sledovat dva podstatné parametry - kvalitu řešení a výpočetní náročnost. Tyto parametry budou posuzovány u těchto metod (implementovaných ve 3. úloze):

• metoda větví a hranic
• dynamické programování
• heuristika podle poměru cena/hmotnost (s kontrolou nejcennější věci)

Nemá smysl sledovat všechny parametry u všech metod. Kvalita řešení bude sledována u heuristiky, naopak výpočetní náročnost bude sledována u druhých dvou metod (výpočetní náročnost heuristiky je známá).

Ke generování instancí byl užit náhodný generátor dodaný na webu předmětu. Nastavení generátoru instancí, není-li řečeno jinak, je následující: m=0,5; W_max=300; C_max=300; d=0; k=1

Výsledky a komentáře

Závislost na m - (poměr nosnosti batohu a celkové váhy věcí)

Závislost počtu navštívených stavů na m (poměr nosnosti batohu a celkové váhy věcí)
 

Komentář

Můžeme vidět, že pro metodu větví a hranic je nejsnazší buď hodně velký nebo hodně malý batoh. To je dáno tím, že u malého batohu mnohem dříve dochází k zamítnutí rozvíjené větve jakožto neperspektivní, naopak když je batoh hodně velký, tak se tam téměř všechny věci vejdou. Dynamické programování roste lineárně, protože obsahuje smyčku od 0 do nosnosti batohu. Kromě případu, kdy poměr překračuje 0,7, v. h. provádí mnohonásobně víc operací než d. p.

Závislost chyby ceny řešení heuristikou na m (poměr nosnosti batohu a celkové váhy věcí)
 

Komentář

Odchylka heuristiky od optimálního řešení se s rostoucí velikosti batohu zvyšuje, a pak se opět snižuje. Ačkoliv bylo otestováno mnoho instancí nelze obecně tvrdit, že batohy do kterých se vejdou skoro všechny nebo skoro žádné věci jsou pro heuristiku lepší. Je to však pravděpodobné. Zde by ovšem bylo potřeba blíže prozkoumat také spojení s vlivem rozmanitosti věcí, který bude velmi významný pro nízká m.

Závislost na maximální hmotnosti W

Rozmezí pro maximální hmotnost jsem zvolil s ohledem na propagované rovnoměrné rozložení vah věcí v rozsahu 31 až 600, tzn. počet věcí (+ 1) až dvacetinásobek.

Závislost počtu navštívených stavů na max. hmotnosti W_max
 

Komentář

Z grafu se zdá, že maximální váha věci nemá na metoda větví a hranic žádný vliv. Dynamické programování mírně lineárně roste, protože W_max rovněž určuje nosnost batohu (nosnost = m*W_max).

Závislost chyby ceny řešení heuristikou na max. hmotnosti W_max
 

Komentář

Tento graf jasně ilustruje hlavní slabinu heuristiky. Prohrává na úlohách, kde se vyskytují předměty s vyšší rozmanitostí cen a vah, může se snadno stát, že pár malých předmětů s dobrým poměrem cena/váha znemožní vložení většího předmětu s horším poměrem, ale díky vysoké váze zároveň lepší celkovou cenou. Naopak v úlohách, kde je rozdíl vah nízký (pro W=31 je každá váha zastoupená 1), pracuje heuristika téměř bezchybně.

Závislost na maximální ceně C

Závislost počtu navštívených stavů na max. ceně C_max
 

Komentář

Z grafu se zdá, že maximální cena věci nemá na metodu větví a hranic i dynamické programování žádný vliv. Můžeme však vypozorovat, že zatímco rychlost d. p. je víceméně konstantní, u v. h. je značně nepravidelná (jak ukazuje i měření závislosti na W_max).

Závislost chyby ceny řešení heuristikou na max. ceně C
 

Komentář

Chyba ceny heuristiky s C_max klesá, zvláště od 0 do 330. Příčinou je, že při velké C_maxje snazší vybrat ty nejcennější věci do řešení, které pak představují velkou část řešení. Pokud se ceny věcí pohybují zhruba v kolem téže hodnoty, je úkol vybrat ty nejvhodnější kombinačně náročný. Zde by bylo zajímavé sledovat chování v závislosti na zvolené váze.

Závěr

Test ukázal, že každá metoda má své silnější a své slabší stránky. Ve většině případů podává heuristika přijatelné výsledky s chybou v řádu procent. Pro některé batohy s předměty jejichž váha je řádově srovnatelná s nosností batohu však může být chyba znatelně vyšší. Stejně tak dělají problém instance, kde se vyskytuje hodně předmětů s podobnými a nízkými cenami. Problém je, že velikost chyby nelze dopředu nějak jednoduše zjistit.

Naopak pokročilejší metody podávají vždy přesná řešení. Jejich výpočetní náročnost bohužel není shora omezená (exponenciální omezení není akceptovatelné), průměrné chování závisí na typu úlohy. Pokud je charakter úlohy znám dopředu je možné vybrat vhodnější algoritmus. Jisté omezení přináší fakt, že metoda dynamického programování je efektivně použitelná pouze pokud je možné hmotnosti věcí v batohu převést na celočíselné a zároveň tyto jsou malé.