====== Ú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

===== Řešení =====
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:

^ parametr ^ testované parametry ^ fixované ^
| maximální váha | W | n, N, m, C, k, d |
| maximální cena | C | n, N, m, W, k, d |
| poměr kapacity batohu k sumární váze | m | n, N, C, W, k, d |
| granularita | k, d | n, N, m, W, C |

==== Maximální váha věcí ====

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

<code winbatch>
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
)
</code>


=== Výpočetní čas ===
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.

{{:school:fit:miric:jaramipaa:r1_time.png|}}

=== Kvalita řešení ===
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%.

{{:school:fit:miric:jaramipaa:r1_err.png|}}

==== Maximální cena věcí ====

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

<code winbatch>
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
)
</code>


=== Výpočetní čas ===
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ů.


{{:school:fit:miric:jaramipaa:r2_time.png|}}

=== Kvalita řešení ===
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%.

{{:school:fit:miric:jaramipaa:r2_err.png|}}

==== Poměr kapacity batohu k sumární váze ====

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

<code winbatch>
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
)
</code>

=== Výpočetní čas ===
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.

{{:school:fit:miric:jaramipaa:r3_time.png|}}

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

{{:school:fit:miric:jaramipaa:r3_err.png|}}

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

<code winbatch>
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
)
</code>

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<sup>k</sup>// pro pravděpodobnost výskytu věci s váhou //w// (při převaze malých věcí)


=== Výpočetní čas ===
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.

{{:school:fit:miric:jaramipaa:r4_time_pos.png|}}
{{:school:fit:miric:jaramipaa:r4_time_neg.png|}}

=== Relativní chyba ===
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í.

{{:school:fit:miric:jaramipaa:r4_err_pos.png|}}
{{:school:fit:miric:jaramipaa:r4_err_neg.png|}}

===== Závěr =====
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.