Experimentální hodnocení kvality algoritmů

• CTU Prague, MI-PAA, ZS 2011
• Autor: Tomáš Borovička (borovto1)

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

Úkolem je zhodnotit kvalitu řešení a výpočetní náročnost implementovaných algoritmů pro problém batohu v závislosti na parametrech řešených instancí.

V práci hodnotím výpočetní náročnost a kvalitu v závislosti na parametrech řešených instancí u následujícíh algoritmů pro řešení problému batohu:

• B&B branch and bound
• Heuristika (cena/váha)
• Dynamické programování
• FTPAS

#!/bin/bash
for i in 40 60 80 100 150 200 300 400 500
do
./knapgen -n 25 -N 40 -m 0.5 -W $i -C 200 -k 1 -d 0 >> instances/W/knap_W$i.inst.dat
done

Závislost výpočetního času můžeme pozorovat u všech algoritmů krom heuristiky, kde je vliv jen minimální. U ostatních je vidět rostoucí tendence výpočetního času s maximální vahou.

S rostoucí vahou výrazně roste průměrná chyba u řešení pomocí heuristiky (cena/váha). Naopak při řešení FPTAS průměrná chyba klasá - což je logické, víme-li, že u FPTAS dekomponujeme podle váhy věcí, neboli “zaokrouhluje” posledních x (2) bitů. Chyba u FTPAS klesala od 5% pri maximální váze 40 až pod 0,5% při maximální váze 500. Naopak relativní chyba u řešení pomocí heuristiky rostla s maximální vahou od 1,3% při maximální váze 40 až k 20% při maximální váze 500.

#!/bin/bash
for i in 40 60 80 100 150 200 300 400 500
do
./knapgen -n 25 -N 40 -m 0.5 -W 100 -C $i -k 1 -d 0 >> instances/C/knap_C$i.inst.dat
done

Z grafu lze vypozorovat snižující se tendence při rostoucí maximální ceně. Tento trend lze pozorovat u šech algoritmů. Nejméně výrazný je opět u heuristiky, kde je na hranici signifikance.

S grafu je vidět výrazné relativní chyba heuristiky, která se snižuje s rostoucí maximální cenou. To je opět očekávaný trend, vzhledem k logice heuristiky cena/váha. Naopak algoritmus založený na FTPAS není ovlivněn vůbec, jelikož je problém dekomponován podle váhy věcí.

#!/bin/bash
for i in 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
do
./knapgen -n 25 -N 40 -m $i -W 100 -C 200 -k 1 -d 0 >> instances/m/knap_m$i.inst.dat
done

U všech algoritmů, opět kromě heuristiky, je vidět výrazná závislost výpočetního času na poměru kapacity batuhu k sumární váze. U Dynamického programování a FTPAS je rostoucí trend výpočetního času s rostoucím poměrem. U řešení branch and bound můžeme pozorovat největší výpočetní složitost při poměru 0.5, při ostatních poměrech, když se sumární váha blíží kapacitě batohu, nebo je výrazně větší, dokáže B&B velice efektivně ořezat stavový prostor.

Relativní chyba heuristiky je nejvyšší při poměru 0.5. Chyba FTPAS klesá s rostoucím poměrem, neboli klesající sumární váhou.

#!/bin/bash
for i in 0.1 0.2 0.5 0.8 1 2 5 8
do
./knapgen -n 25 -N 40 -m 0.5 -W 100 -C 200 -k $i -d 0 >> instances/k/knap_k$i.inst.dat
done

Závislost výpočetního času na granularitě je na hranici signifikance, spíše můžeme řici, že při nastavených parametrech neměla granularita vliv na výpočetní čas a to u všech testovaných algoritmů.

Stejně jako výpočetní čas, ani relativní chyba při nastavených parametrech nekoreluje s granularitou testovaných instancí.

Experimentálně jsem zkoumal chování čtyř implementovaných algoritmů v závislosti na parametrech řešených instancí a zhodnotil jejich kvalitu a závislost výpočetního času na těchto parametech.

• Úkol 1 - problém batohu
• Úkol 3 - problému batohu 2: dynamické programování, metoda větví a hranic a aproximativní algoritmus