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):

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; Wmax=300; Cmax=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í)
 

m metoda větví a hranic dynamické programování
0,1 62572 13486
0,2 855056 26910
0,3 3774713 40628
0,4 3484917 53847
0,5 2428540 68380
0,6 593864 80124
0,7 84695 95371
0,8 10001 106371
0,9 739 121099

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í)
 

m odchylka od optima
0,1 3,21%
0,2 4,54%
0,3 3,82%
0,4 4,98%
0,5 6,65%
0,6 8,78%
0,7 8,30%
0,8 6,77%
0,9 4,35%

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 Wmax
 

Wmax metoda větví a hranic dynamické programování
31 2513631 6960
60 2235911 13527
90 1943607 20145
120 1657329 27141
150 2048331 33675
180 2607335 40672
210 3523451 47589
240 2025606 54277
270 2637518 60678
300 2629382 66534
330 1698373 74044
360 2763215 81258
390 1939966 86593
420 1900321 97191
450 2967573 101223
480 2788828 109962
510 2869162 116992
540 2068680 120156
570 1654920 133079
600 2892008 136248

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 Wmax rovněž určuje nosnost batohu (nosnost = m*Wmax).

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

Wmax odchylka od optima
31 0,67%
60 0,69%
90 1,37%
120 1,64%
150 1,55%
180 2,40%
210 2,56%
240 2,71%
270 4,10%
300 6,31%
330 8,81%
360 11,40%
390 13,27%
420 16,12%
450 16,19%
480 17,79%
510 19,56%
540 18,23%
570 23,43%
600 20,72%

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ě Cmax
 

Cmax metoda větví a hranic dynamické programování
30 3409839 66285
60 1628137 69082
90 3274375 67354
120 1963898 67135
150 2335052 68002
180 1985827 69086
210 2250712 69093
240 2668862 68105
270 2306236 69747
300 3223225 67403
330 1807276 67281
360 2202767 67545
390 2164388 66777
420 2395362 68425
450 2492475 69694
480 1849777 67848
510 2363729 66375
540 2743233 66735
570 2718265 66594
600 1496576 68225

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 Wmax).

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

Cmax odchylka od optima
30 28,26%
60 27,47%
90 25,18%
120 23,03%
150 21,35%
180 17,14%
210 15,61%
240 11,47%
270 10,03%
300 5,56%
330 4,50%
360 3,19%
390 2,91%
420 2,71%
450 2,66%
480 2,98%
510 2,85%
540 2,65%
570 2,61%
600 2,03%

Komentář

Chyba ceny heuristiky s Cmax klesá, zvláště od 0 do 330. Příčinou je, že při velké Cmaxje 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é.

Metoda Rychlost Kvalita řešení Hodnocení

Hrubá síla

neakceptovatelná
(exponenciální)

absolutní

pro: není závislá na parametrech úlohy
proti:
nejpomalejší
vhodné: malé instance úlohy

Metoda větví a hranic

rychlé

absolutní

pro: rychlé pro malé nebo naopak velké poměry sumární ceny věcí ke kapacitě
proti: není nejrychlejší
vhodné: pro speciální batohy

Dynamické programování
(podle kapacity batohu)

rychlé

absolutní

pro: rychlé
proti: závislé na hmotnostech předmětů, velká spotřeba paměti (největší z algoritmů)
vhodné: pro obecné batohy s co nejmenšími celočíselnými váhami

Heuristika
cena/váha

neměřitelná

dostatečná

pro: nejrychlejší
proti: možnost větší chyby u speciálních úloh
vhodné: pro obecné batohy s větším počtem spíše podobných a lehčích věcí (v poměru k nosnosti)