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

Úloha z předmětu 36PAA

Martin Tůma

Zadání

  1. Prozkoumejte citlivost metod řešení problému batohu na parametry instancí generovaných generátorem náhodných instancí [1]. Máte-li podezření na další závislosti, modifikujte zdrojový tvar generátoru.
  2. Na základě zjištění navrhněte a proveďte experimentální vyhodnocení kvality řešení a výpočetní náročnosti.
  3. Pokud možno, prezentujte algoritmy jako body v ploše, jejíž souřadnice jsou výše uvedená kritéria.

Řešení

U jednotlivých metod byly odhadnuty následující závislosti a provedena příslušná měření:

Řešení metodou "hrubé síly"

Použitá implementace metody hrubé síly [2] prochází vždy všechny možné stavy stavového prostoru, není tedy ani teoreticky možné, aby výpočetní složitost byla závislá na jiném paramatru než velikosti instance. Dále se jedná, stejně jako u B&B a dynamického programování, o "exaktní" metodu (tzn. metoda najde vždy optimální řešení) z čehož plyne, že je zbytečné provádět jakákoliv měření kvality/relativní chyby algoritmu.

Řešení metodou větví a hranic

Zde lze předpokládat, že algoritmus je citlivý na poměr sumární váhy ke kapacitě batohu (m/M). Pro velmi málo zaplňený batoh lze předpokládat účiné ořezávání zespoda (tzn. v dalších větvích již nelze očekávat lepší výsledek), pro téměř plný batoh pak naopak účinné ořezávání zezhora (přidání dalších věcí by vedlo k přeplnění batohu).

Algoritmus B&B dále může být citlivý na granularitu věcí v batohu.

Řešení metodou dynamického programování

Řešení metodou dynamického programování má složitost O(mmax·n), musí tedy lineárně záviset na parametru maximální váhy věci. Jiné závislosti nelze předpokládat.

Řešení heuristikou podle poměru C/m s testem Cmax

Výpočetní složitost kombinované heuristiky by měla být ke všem parametrům, invariantní, závislosti lze ovšem očekávat u kvality/relativní chyby metody, a to na poměru sumární váhy ke kapacitě batohu (m/M) - s rostoucím zaplněním batohu je méně kritické nevložení některé věci - a granularitě obsahu.

Naměřené hodnoty

Výchozí konfigurace generátoru pro všechna měření:

Naměřené výsledky jsou vždy průměry (na jednu instanci) ze všech instancí ve vstupním souboru při změně zkoumaného parametru.

Metoda větví a hranic

m/M 0.10.20.30.40.5 0.60.70.80.9
Navštívených stavů 25591212984368107287676 151114313707629925166

Graf 1: Závislost výpočetní složitosti metody B&B na poměru sumární váhy ke kapacitě batohu.

n Navštívených stavů
(Více malých věcí)
Navštívených stavů
(Více velkých věcí)
20533 4555
251059 21819
301952 89142
353911 663775
40110132303979

Graf 2: Výpočetní složitosti metody B&B při velké a malé granularitě věcí v batohu. (k=1)

Dynamické programování

Maximální váha věci 1005001000500010000 20000
Navštívených stavů 444362116424287512069822 42946688414791

Graf 3: Závislost výpočetní složitosti metody dynamického programování na maximální váze věci.

Heuristika dle poměru C/m s testem Cmax

m/M ηø [%] ηmax [%]
0.11.295.39
0.21.305.23
0.30.763.75
0.40.663.66
0.50.534.56
0.60.221.46
0.70.231.46
0.80.171.26
0.90.091.33

Graf 4: Závislost relativní chyby řešení kombinované heuristiky na poměru sumární váhy ke kapacitě batohu.

n v.m.v.
ηø [%]
v.m.v.
ηmax [%]
v.v.v.
ηø [%]
v.v.v.
ηmax [%]
200.855.420.402.99
250.614.230.261.65
300.412.200.242.29
350.211.390.231.57
400.282.260.291.57

Graf 5: Relativní chyba řešení kombinované heuristiky při velké a malé granularitě věcí v batohu.

Závěr

Výpočetní složitost metody B&B v závislosti na na poměru sumární váhy ke kapacitě batohu potvrdila doměnky, že směrem ke "kraji" grafu nabývá na účinnosti vždy jedno z obou ořezávání stavového prostoru. Zajímavá je poloha maxima grafu, které je posunuto směrem k počátku (m/M = 0.3), což svědčí o vyšší účinosti ořezávání zezhora.

Mnohem překvapivější je vysoký rozdíl výpočetní složitosti pro různou granularitu věcí v batohu, která je pro převahu velkých věcí v batohu řádově vyšší, než pro batoh složený z více malých věcí. Pro tento jev jsem však bohužel žádné věrohodné vysvětlení nenašel.

Test pro metodu dynamického programování zcela potvrdil lineární závislost výpočetní složitosti na maximální váze věci, i, což z grafu patrné není, rostoucí paměťovou náročnost algoritmu v závislosti na max. váze. Pro řešení instancí s max. váhou 20000 jsou již třeba desítky MB RAM.

Experimenty zaměřené na kvalitu řešení heuristiky prokázaly závislost relativní chyby na poměru sumární váhy ke kapacitě batohu i mírnou závislost na granularitě věcí v batohu. Rozhodujícím kritériem pro kvalitu řešení je však velikost instance - pro velká n klesá i vliv závislostí na parametrech na kvalitu/relativní chybu řešení.

Reference

[1] http://service.felk.cvut.cz/courses/36PAA/wknapgen.html
[2] http://tumic.wz.cz/fel/online/36PAA/1

Přílohy

1. batoh_bb.c - Program pro řešení metodou B&B.
2. batoh_dyn.c - Program pro řešení dynamickým programováním.
3. batoh_h2.c - Program pro řešení heuristikou podle poměru C/m s testem Cmax
4. stats.sh - Script na výpočet relativní chyby heuristiky