Experimentální hodnocení algoritmů pro řešení problému batohu
Zadání
- Prozkoumejte citlivost metod řešení problému batohu na parametry instancí generovaných generátorem náhodných instancí. 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.
Přehled hodnocených algoritmů
V této úloze byly pro měření použity všechny algoritmy implementované pro problém batohu v předchozích úlohách.
- Hrubá síla
- Heuristika podle klesající ceny
- Heuristika podle rostoucí hmotnosti
- Heuristika podle poměru cena/hmotnost
- Heuristika podle klesající ceny (s testem)
- Heuristika podle rostoucí hmotnosti (s testem)
- Heuristika podle poměru cena/hmotnost (s testem)
- Metoda větví a hranic
- Dynamické programování: s dopřednou fází
- Dynamické programování: bez dopředné fáze
- Dynamické programování: cena x věci
Použítá měření
V aplikaci bylo implementováno rozhraní pro tvorbu testů, které se skládá z volby algoritmu(ů), veličiny, která má být měřena (čas, počet operací nebo relativní chyba), a volby jedné z proměných při generování instancí, která má být měněna.
možné proměné pro testování
- velikost instance
- maximální hmotnost Wmax
- maximální cena Cmax
- poměr m
- granularita
|
velikost instance |
maximální hmotnost Wmax |
maximální cena Cmax |
poměr m |
granularita |
| defaultní hodnoty |
20 |
100 |
200 |
0.5 |
0 |
| počáteční hodnoty |
4 |
50 |
50 |
0.1 |
-2 |
| krok |
2 |
50 |
50 |
0.05 |
0.1 |
| počet kroků |
20 |
10 |
10 |
20 |
40 |
V této úloze jsem se již nezabýval měřením v závislosti na velikosti instance, protože tím jsem se již zabíval pro všechny metody v minulé úloze.
Dále je z předchozích úloh patrné že měření relativní chyby na jiných metodách než heuristikách nemá smysl, protože vždy dávají optimální řešení.
Posledním znížením počtu měření je fakt, že je výhodnější měřit počet provedených operací než čas. Čas je totiž funkcí počtu operací. Je ale navíc zatížen jinými rušícími faktory, jakými jsou jiná vlákna a procesy, které odebírají výkon a tím nestejnoměrně zvyšují čas potřebný k provedení měření.
Výsledky měření
počet operací X maximální hmotnost Wmax
Na těchto měřeních byly zjištěny očkávané vlastnosti DP a sice při DP, kde rozměr pole je určen maximální hmotností a počtem věcí je přímo úměrná (počet operací).
Dále je zde patrné že metoda větví a hranic potřebuje méně operací při nižší maximální váze. To je zřejmě způsobeno prořezáváním v grafu, kdy je již v menší hloubce větev zavržena a nedochází k prohledávání.
U brutální síly je vidět nižší počet operací v začátku grafu, tedy při nižší maximální hmotnosti. To je dáno tím, že tato metoda přeskočí více možných konfigurací, ale není příliž výrazný.
U dalších metod je možné konstatovat, že změna maximální hmotnosti nemá podle tohoto měření žádný vliv.
relativní chyba X maximální hmotnost Wmax
Podle tohoto měření nemá maximální hmotnost vliv na relativní chybu. Je to dáno tím, že průběh je totožný, jen je limitován jiným místem.
počet operací X maximální cena Cmax
V této sérii měření jsou zjevně zajímavé jen metody hrubé síly a DP ceny/počet věcí.
U zmíněného DP je průběh očekáváný a nijak překvapivý, je dán tím, že maximální cena je jedním z rozměrů pole.
Hrubá síla vykazuje velké rozdíly a graf je příliž ovlivněn náhodným generováním instancí. Dá se zde pouze usuzovat, že v závislosti na vyšší maximální ceně klesá složitost. To ovšem z teoretického hlediska není možné, protože průběh prohledávání je určen jen a poze hmotností (věcí a maximální). Proto usuzuji, že se jedná o průběh jen ovlivněný náhodným generováním, které by se jistě při vyšším počtu měření více eliminovalo. K těmto závěrům docházím jsem došel s ohledem k tomu že zmíněný rozdíl je menší než zjevný vliv náhodných generovaných instancí a na základě velkém počtu měření.
relativní chyba X maximální cena Cmax
Toto měření prokazuje, že maximální cena nemá vliv na relativní chybu. Příčina je obdobná jako u maximální hmotnosti.
počet operací X poměr m
Toto měření zjevně objevilo závislost hrubé síly. Zde je vidět že se zvyšíjícím se poměrem těžších věcí se znišuje složitost. Jde o rychlejší/pravděpodobnější zamítnutí větve.
Dále byla zjistěna závislost DP cena/věci, kde velikost pole při generovaných instancích implementovaného generátoru s velikostí klesá i složitost.
Metoda větví a hranic ukázala na možnou závislost, proto bylo pro tuto metodu měření opakováno na mnohem více instancích:
Tím jsem s jistoutou objevil závislost, u které je dá říci, že metoda pracuje nejlépe při mimumu a maximu v proměné poměr m. Okolo 0,4 je složitost nejvyšší.
relativní chyba X poměr m
Relativní chyba odhaluje , že se zvyšujícím se m, klesá chyba heuristik, ač s různým průběhem. To je způsobeno zřejmě tím, že s dostatečným pčtem malých věcí, může heuristika mnohem lépe vyplnit batoh.
počet operací X granulita
Granulita má vliv na 3 metody: DP cena/věcí, větve a hranice a hrubá síla.
Na metody hrubé síly a větví a hranic má vliv podobný se zvyšující se granulitou roste i složitost. Podobnost nárustu je způsobena podobnou způsobem, tedy, že obě metody jsou si velmi blízké.
U DP programování je průběh v první polovině grafu (g<0) nezajímavá (nemá vliv). V druhé části je ovšem vidět, že dochází ke snižování složitosti a tedy i rozměrům pole.
relativní chyba X granulita
Poslední měření ukázalo, že heuristiky klesající ceny a rostoucí hmotnosti mají relativní chybu závislou na granulitě.
Obě metody jsou závislé opět jen pro g>0, přičemž podle rostoucí ceny se chyba zvyšuje a podle kledající ceny snižuje.
Je to způsebo tím, že rozložení hmotností a cen věcí je opačný a tedy se lépe, resp. hůře vyplňuje zbylá kapacita batohu.
Data
Data byla změřena aplikací a zpracována v MS Excel.
Program
Aplikace je psaná v Javě 1.5 (JBuilder 2006). Pro spuštění bude možná nutné upravit cestu k interpretu v souboru run.bat.
U aplikace je možnost měřit i časovou složist, u té je důležité si uvědomit vnější vlivy, přičemž velký vliv může mít i průběžné vykreslování. Proto při měření časové složitosti je nutné brát výsledky s rezervou a spíše orientační (předevšim při průběžném vykreslování).
Závěr
Ve všech měřeních byly nalezeny závislosti na rozných veličinách, většina byla známá již z teorie a předchozích úloh. Zajímavými byly závislosti na granulitě a poměru m, které nebyly tak zřejmé před samotným měřením.
Dále je z měření dobře viditelné, že zlepšení heuristik o test, neměl žádný velký vliv na měření 4. úlohy i složitost. Patrné je to z toho, že je podobné heuristiky (s/bez testu) se liší ve všech grafech jen nepatrně.
