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

Úloha z předmětu 36PAA

Martin Tůma

Zadání

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.
Na základě zjištění navrhněte a proveďte experimentální vyhodnocení kvality řešení a výpočetní náročnosti.
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(m_max·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 C_max

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

Velikost instance (n): 30
Počet instancí: 50
Maximální váha věci: 100
Maximální cena věci: 250
Poměr sumární váhy ke kapacitě batohu (m/M): 0,6
Charakter granularity: Nerozlišovat
Exponent závislosti granularity (k): 1

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.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
Navštívených stavů	25591	212984	368107	287676	151114	31370	7629	925	166

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í)
20	533	4555
25	1059	21819
30	1952	89142
35	3911	663775
40	11013	2303979

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	100	500	1000	5000	10000	20000
Navštívených stavů	44436	211642	428751	2069822	4294668	8414791

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 C_max

m/M	η_ø [%]	η_max [%]
0.1	1.29	5.39
0.2	1.30	5.23
0.3	0.76	3.75
0.4	0.66	3.66
0.5	0.53	4.56
0.6	0.22	1.46
0.7	0.23	1.46
0.8	0.17	1.26
0.9	0.09	1.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 [%]
20	0.85	5.42	0.40	2.99
25	0.61	4.23	0.26	1.65
30	0.41	2.20	0.24	2.29
35	0.21	1.39	0.23	1.57
40	0.28	2.26	0.29	1.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 C_max
4. stats.sh - Script na výpočet relativní chyby heuristiky