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

1. Úkol

2. Rešení

Problém batohu lze slovně popsat jako úlohu, kdy máme předměty různých hodnot a hmotností zabalit do batohu tak, aby jeho hodnota byla co možná nejvyšší a nebyla překročena jeho nosnost.

2.1 Měření

Jako statistiky jsou určeny výpočetní náročnost a kvalita řešení. Výpočetní náročnost v experimentu byla měřena počtem prohledaných konfigurací batohu. Kvalita řešení je absolutní pro metody hledající optimální výsledky, pro heuristické metody byla sledována jako relativní chyba ceny k ceně batohu sbaleného optimálně.

Sledované algoritmy jsou použití hrubé síly, heuristiky podle poměru i podle poměru s testem nejcennější věci, dynamické programování a metoda větví a hranic. Rozdělíme je do dvou skupin podle toho, zda hledají optimální nebo suboptimální řešení. Pro každou skupinu přichystáme stejnou sadu testů pro určení výpočetní náročnosti.

Pro heuristické metody navíc vytvoříme test ke stanovení kvality řešení.

Různé testy mají jednu společnou charakteristiku: počet instací problému je vždy 50.

2.2 Výsledky

2.2.1 Skupina optimálních algoritmů

Proměnné parametry testu Průměrný počet prohledávacích kroků pro 50 instancí
Počet věcí Maximální váha Maximální cena Hrubá síla Větve a hranice Dynamicky podle kapacity batohu
10 100 250 1023,00 256,84 1064,84
10 100 500 1023,00 260,84 1064,84
10 100 1000 1023,00 237,58 1064,84
10 300 250 1023,00 249,68 1341,52
10 300 500 1023,00 257,34 1341,52
10 300 1000 1023,00 241,80 1341,52
20 100 250 1048575,00 19926,44 11922,16
20 100 500 1048575,00 19438,32 11922,16
20 100 1000 1048575,00 24209,86 11922,16
20 300 250 1048575,00 22528,70 19180,76
20 300 500 1048575,00 22091,48 19180,76
20 300 1000 1048575,00 21765,58 19180,76
25 100 250 33554431,00 135741,66 20849,44
25 100 500 33554431,00 132408,40 20849,44
25 100 1000 33554431,00 156521,96 20849,44
25 300 250 33554431,00 214068,12 28980,78
25 300 500 33554431,00 166229,16 28980,78
25 300 1000 33554431,00 158224,48 28980,78

Tabuka 1. Výpočetní náročnost pro test 1.

Pro metodu hrubé síly žádné závislosti nejsou, prohledává všechen stavový prostor. Větve a hranice také nejsou nijak závislé, rozdíly je možno přičíst náhodě. Jiné je to u dynamického programování, zde je závislost jasná na maximální hmotnosti. Je to dáno algoritmem, jde o dekompozici podle kapacity batohu.



Proměnné parametry testu Průměrný počet prohledávacích kroků pro 50 instancí
Charakter granuality Exponent závislosti granuality Hrubá síla Větve a hranice Dynamicky podle kapacity batohu
více malých věcí 1 1048575,00 9673,12 7348,42
více malých věcí 2 1048575,00 11635,66 4845,62
více malých věcí 3 1048575,00 9600,70 4012,88
více větších věcí 1 1048575,00 32463,50 14789,66
více větších věcí 2 1048575,00 40428,66 16022,54
více větších věcí 3 1048575,00 43640,84 16033,58

Tabuka 2. Výpočetní náročnost pro test 2.

U metody větví a hranic je pro těžší přeměty výpočetní náročnost větší - předměty se často do batohu nevejdou a začne tak další rekruze bez snížení volného prostoru v batohu. Podobné je to u dynamického programu.



Proměnné parametry testu Průměrný počet prohledávacích kroků pro 50 instancí
Poměr sumární váhy věcí k nosnosti batohu Hrubá síla Větve a hranice Dynamicky podle kapacity batohu
0,1 1048575,00 1650,44 964,60
0,3 1048575,00 42148,46 5686,96
0,5 1048575,00 47234,52 9833,04
0,7 1048575,00 8732,20 12692,62
0,9 1048575,00 619,00 14027,96

Tabuka 3. Výpočetní náročnost pro test 3.

Při výpočtu podle větví a hranic dochází u větších poměrů ke kapacitě batohu k prořezávání neperspektivních větví, u velkých poměrů jde o výbornou metodu. U dynamického programování opět záleží na hmotnostech.

2.2.1 Skupina heuristických algoritmů

V této části je počet prohledávaných konfigurací vlastně zhruba počet vkládaných předmětů. To zkresluje výsledky, kdybychom tato čísla vzali a porovnali je s metodami optimálními. Takové porovnání je zavádějící.

Proměnné parametry testu Průměrný počet prohledávacích kroků pro 50 instancí
Počet věcí Maximální váha Maximální cena Heuristika cena/váha Heuristika cena/váha s testem nejcennější věci
10 100 250 6,78 6,78
10 100 500 6,84 6,84
10 100 1000 6,82 6,82
10 300 250 6,70 6,70
10 300 500 6,78 6,78
10 300 1000 6,76 6,76
20 100 250 13,92 13,92
20 100 500 13,94 13,94
20 100 1000 13,78 13,78
20 300 250 13,94 13,94
20 300 500 14,04 14,04
20 300 1000 14,12 14,12
25 100 250 17,50 17,50
25 100 500 17,58 17,58
25 100 1000 17,38 17,38
25 300 250 17,64 17,64
25 300 500 17,54 17,54
25 300 1000 17,50 17,50

Tabuka 4. Výpočetní náročnost pro test 1.

Podle výsledků můžeme usuzovat, že změna maximálních cen a vah neměla, i podle předpokladů, na rychlost algoritmu vliv. Jediným rozhodujícím činitelem je počet věcí k naskládání do batohu, který ovlivnuje nejdelší část algoritmu - řazení.



Proměnné parametry testu Průměrný počet prohledávacích kroků pro 50 instancí
Charakter granuality Exponent závislosti granuality Heuristika cena/váha Heuristika cena/váha s testem nejcennější věci
více malých věcí 1 16,06 16,06
více malých věcí 2 16,40 16,40
více malých věcí 3 15,72 15,72
více větších věcí 1 12,90 12,90
více větších věcí 2 12,18 12,18
více větších věcí 3 12,02 12,02

Tabuka 5. Výpočetní náročnost pro test 2.

Je vidět, že s převahou větších věcí se batoh plní rychleji, probádaných stavů je méně.



Proměnné parametry testu Průměrný počet prohledávacích kroků pro 50 instancí
Poměr sumární váhy věcí k nosnosti batohu Heuristika cena/váha Heuristika cena/váha s testem nejcennější věci
0,1 5,08 5,08
0,3 9,44 9,44
0,5 12,56 12,56
0,7 15,36 15,36
0,9 18,04 18,04

Tabuka 6. Výpočetní náročnost pro test 3.

Batoh se pro mnoho předmětů vzhledem k jeho nosnosti plní rychle, heuristika si seřadila předměty od nejlepších k nejhorším. V opačném případě jí nezbývá než vložit skoro všechny předměty z nabídky.

Metoda testu nejcennější věci nebyla vůbec použita. Výsledky dokládají, že u všech kombinací byla v činnosti pouze část vkládaní podle poměru cena/váha. Všechny tři testy ale potvrzují, že heuristická metoda je velmi rychlá. Jak je to s její kvalitou ukáže až následující.



Proměnné parametry testu Relativní chyba k optimální metodě [%]
Počet věcí Heuristika cena/váha Heuristika cena/váha s testem nejcennější věci
5 2,68 2,68
10 1,08 1,08
15 0,39 0,39
20 0,36 0,36
25 0,40 0,40
30 0,35 0,35
35 0,51 0,51
40 0,42 0,42

Tabuka 7. Kvalita řešení pro test 4.

Bez nadsázky se dá uvést, že kvalita řešení je velmi rozumná vzhledem k času, které metody spotřebují. Ani zde se neuplatnil test nejcennější věci.

3. Závěr

Porovnání nalezneme v přehledné tabulce. Pokud bychom výsledky zanesly do grafu, měli bychom na ose s kvalitou metody heuristické se skoro nulovou náročností a na ose s náročností vysoku metody optimální s nulovou chybou. To je zbytečné.

Test Výpočetní náročnost Kvalita řešení Hodnocení
Hrubá síla velmi pomalé, exponenciálně s počtem předmětů absolutní pro: není závislá na ždáných parametrech
proti: nejpomalejší
vhodné: nevhodné
Větve a hranice celkem 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
Dynamicky podle kapacity batohu rychlé absolutní pro: rychlé
proti: příliš závislé na hmotnostech předmětů, velká spotřeba paměti
vhodné: pro obecné batohy bez těžkých předmětů
Heuristika cena/váha nejrychlejší dobrá pro: nejrychlejší a přesné
proti: prakticky žádné proti
vhodné: pro obecné batohy
Heuristika cena/váha s testem nejrychlejší dobrá pro: nejrychlejší a přesné, oproti předchozí může mít ještě zlepšení pro malé batohy (kolem 5 předmětů), nikdy však zhoršení
proti: prakticky žádné proti
vhodné: test vhodný pro malé batohy, pro obecné batohy

Tabuka 8. Kvalita a náročnost.

Dodatek

Kompletní balíček se zdroji a výsledky testů.