Úloha 4 - Experimentální hodnocení kvality algoritmů

• MI-PAA, ZS 2011/12
• Autor: Jaroslav Fibichr (fibicjar)

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
• Pozorujte zejména závislosti výpočetního času (B&B, DP, heuristika) a rel. chyby (heuristika) na:
  • maximální váze věcí
  • maximální ceně věcí
  • poměru kapacity batohu k sumární váze
  • granularitě (pozor - zde si uvědomte smysl exponentu granularity)
• Doporučuje se zafixovat všechny parametry na konstantní hodnotu a vždy plynule měnit jeden parametr

Podle zadání jsem změřil a vyhodnotil kvalitu řešení a výpočetní náročnost algoritmů řešících problém batohu, které jsem naimplementoval v předchozích úlohách:

• Jednoduchá heuristika (předtřídění podle cena/váha)
• Metoda větví a řezů (Branch and Bound, B&B)
• Dynamické programování
• FPTAS, s parametrem 2

Vstupní data byla vygenerována poskytnutým nástrojem knapgen. Podle zvolené závislosti, kterou chceme pozorovat, jsem fixoval jednotlivé parametry. Následující tabulka shrnuje fixované/generované parametry:

Pro vygenerování byl použit následující batch skript:

FOR %%i IN (25 40 60 80 100 150 200 250 300 400 500) DO (
    knapgen.exe -n 22 -N 30 -m 0.5 -W %%i -C 100 -k 1 -d 0 >> i1/maxW_%%i.dat
)

Z výsledků měřění lze sledovat jednoznačné tendence:

• Heuristika, BF, B&B - výpočetní čas není závislý na maximální váze (W). To je patrně způsobeno tím, že změnou W se nemění počet prošlých stavů, pouze se mění “jemnost” hodnot vah.
• DP, FPTAS - zde s rostoucím W lze pozorovat i růst času. To lze přisoudit faktu, že algoritmy jsou implementovány ve verzi s dekompozicí podle kapacity. Tím se tabulka pro podproblémy se zjemňující celkovou váhou zvětšuje a tím se zvyšuje i počet stavů pro průchod.

Na kvalitu heuristiky nemělo zvyšování W žádný vliv. Pro všechny instance byl průměr chyby pod 1%. Naopak, na kvalitě výsledků algoritmu FPTAS se projevilo, že zanedbává poslední bity. Tyto dva bity se se zvyšujícím se W stávají méně důležité pro konečný výsledek. Pro W = 200 a více je již relativní chyba menší než 1%.

Pro vygenerování byl použit následující batch skript:

FOR %%i IN (25 40 60 80 100 150 200 250 300 400 500) DO (
  knapgen.exe -n 22 -N 30 -m 0.5 -W 100 -C %%i -k 1 -d 0 >> i2/maxC_%%i.dat
)

Z hodnot i grafu můžeme pozorovat, že maximální cena pozorovatelným způsobem neovlivňuje dobu výpočtu algoritmu. Rozdíl oproti předchozímu případu (tedy závislost na W) pro DP a FPTAS je zřejmý - dekompozice je provedena podle kapacity. Změna max. ceny tedy neovlivňuje výpočetní čas žádného z algoritmů.

Na kvalitu heuristiky nemělo zvyšování W žádný vliv. Pro všechny instance byl průměr chyby pod 1%. Naopak, na kvalitě výsledků algoritmu FPTAS se projevilo, že zanedbává poslední bity. Tyto dva bity se se zvyšujícím se W stávají méně důležité pro konečný výsledek. Pro W = 200 a více je již relativní chyba menší než 1%.

Pro vygenerování byl použit následující batch skript:

FOR %%i IN (0.05 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.95) DO (
  knapgen.exe -n 22 -N 30 -m %%i -W 100 -C 150 -k 1 -d 0 >> i3/m_%%i.dat
)

Z měřění lze opět pozorovat rostoucí trend výpočetního času v závislosti na poměru kapacita/celková váha. Jediná pozorovatelná výjimka se objevuje u metody Branch and Bound. Zde od cca m = 0.5 nastává mírný sestupný trend patrně způsobený ořezáváním stavového prostoru zdola.

Obě heuristiky mají se zvyšujícím se poměrem kapacity a sumární váhy sestupnou tendenci relativní chyby.

Pro vygenerování byl použit následující batch skript:

FOR %%i IN (0.1 0.3 0.5 0.75 1 2.5 5 8) DO (
  knapgen.exe -n 22 -N 30 -m 0.5 -W 100 -C 150 -k %%i -d 0 >> i4/gr0_%%i.dat
  knapgen.exe -n 22 -N 30 -m 0.5 -W 100 -C 150 -k %%i -d -1 >> i4/gr-1_%%i.dat
  knapgen.exe -n 22 -N 30 -m 0.5 -W 100 -C 150 -k %%i -d 1 >> i4/gr1_%%i.dat
)

Granularitu ovlivňují především 2 parametry:

• -d * -1..více malých věcí, 1..více velkých věcí, 0..rovnováha
  • Při volbě parametru d=0 se granularita neměnila, parametr -k
  • Při volbě parametru d=1 a d=-1 se granularita měnila symetricky (tedy velikosti vah věcí měli stejnou vzdálenost od 0, resp. maximální w)
• -k - exponent k ve vzorci p = 1 / w^k pro pravděpodobnost výskytu věci s váhou w (při převaze malých věcí)

Se změnou granularity se pohybovaly pouze časy DP a FPTAS. Měly mírnou vzestupnou tendenci pro d=1 (a sestupnou pro d=-1). Výpočetní čas ostatních algoritmů změna granularity neovlivnila.

Z měření vyplynulo, že jednoduchá heuristika cena/váha není na změny parametrů citlivá, u FPTAS tomu tak je. Se zvyšováním exponentu k pro d=1 se zvyšovala hmotnost věcí a relativní chyba se zmenšovala. To je opět dáno tím, že pro větší čísla již nejsou poslední dva bity tolik důležité. Při jejich zanedbání se nesníží přesnost řešení.

Provedl jsem sadu měření pro posouzení citlivosti naprogramovaných přístupů k jednotlivým parametrům vstupních dat. Výsledky vcelku potvrzovaly očekávání.

Pozn.: Ačkoliv se dalo očekávat, že výsledky z měření kvality jednoduché heuristiky (podle poměru cena/váha) by mohly být více ovlivněny v prvních třech testech, není tomu tak. Patrně je to způsobeno tím, že byly zvoleny dostatečně vysoké ostatní (fixované) parametry a zárověň je v Javě dostatečně vysoká přesnost reprezentace čísel s plovoucí desetinnou čárkou typu double. Tím byla dosažena vysoká jemnost při dělení cena/váha a další ovlivnění nedostatenou jemností nemohly být pozorovány.