ČVUT – FEL X36PAA - Problémy a algoritmy
4. úloha - Experimentální hodnocení algoritmů pro řešení problému batohu Jméno: Marek Handl Datum: 3. 2. 2009 Cvičení: Pondělí 9:00
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.
Úvod Ve všech provedených měřeních vždy pozorujeme vztah jedné veličiny k počtu stavů, které je nutné projít pro výpočet. Všechny ostatní možnosti nastavení generátoru instancí zůstavají fixní. Velikost instance Počet instancí Maximální Maximální cena Poměr kapacity k Granularita hmotnost věci věci hmotnosti 20 40 100 Tab 1 – standardní nastavení generátoru instancí
250
0,6
nerozlišovat
Jsou porovnávány tři algoritmy výpočtu problému: metoda větví a hranic, dynamické programování a heuristika podle poměru cena/hmotnost s testem nejcennější věci. Heuristika obecně nenalézá optimální řešení, a proto také sledujeme průměrnou odchylku heuristického řešení od optimálního. K výpočtu odchylky se používá vzorec: chyba = (cenaOptimum – cenaHeuristika) / cenaOptimum. Metoda větví a hranic se chová obdobně jako hrubá síla, jen s tím rozdílem, že se počítají pouze stavy, které mají naději zlepšit dosavadní nejlepší nalezené řešení. Počet stavů, které bude nutné pro výpočet projít, se nedá odhadnout. V nejhorším případě se z toho stane hrubá síla. Dynamické programování těží z faktu, že existuje značně omezené množství možných součtů cen věcí, které jsou do batohu dávány. Tímto přístupem je možné si ukládat již zjištěné výsledky a neopakovat některé výsledky. Počet stavů je tedy v tomto případě roven počtu věcí násobeno součtem cen věcí. Heuristika nejprve seřadí věci podle poměru cena/hmotnost a pak přidává nejvýhodnější věci do batohu, dokud se tam hmotnostně vejdou. Na závěr se ještě řešení porovná se situací, kdy se do batohu vloží jen ta nejcennější věc, a vezme se lepší řešení. Výpočetně nejnáročnější je v tomto případě seřazení věcí. Počet stavů je tedy roven N*log(N)+X+1, kde N je počet věcí, X je počet věcí které do batohu opravdu dáme a jednička symbolizuje porovnání s nejcennější věcí.
Maximální hmotnost Toto měření zkoumá vliv maximální možné hmotnosti věci na počet stavů, které se projdou při výpočtu, a na kvalitu řešení dosaženého heuristikou. Max hmotnost 50 100 150 200 250
Větve a hranice 5624 5391 5382 4444 5836
Dynamické programování 49319 50382 51112 49889 50993
Heuristika 101 101 101 101 101
300 5332 51177 350 7237 52063 400 4827 50171 450 6886 51679 500 6696 51102 Tab 2 – počet stavů prošlých při výpočtu v závislosti na maximální hmotnosti věci
101 101 101 101 101
60000
Po čet stavů
50000 40000
Větve a hranice
30000
Dynamické programování Heuristika
20000 10000 0 0
100
200
300
400
500
600
Maximální hmotnost Graf 1 – počet stavů prošlých při výpočtu v závislosti na maximální hmotnosti věci
2,5
2
2,01
1,95
Průměrná chyba (%)
1,83 1,52
1,5
1,62
1,53
1,51 1,36
1,59
1,39
1
0,5
0 0
100
200
300
400
500
600
Maximální hmotnost
Graf 2 – procentní průměrná chyba heuristického řešení vzhledem k optimálnímu Zhodnocení V tomto měření se nepodařilo vypozorovat žádnou závislost mezi maximální hmotností věcí a počtem propočítaných stavů. U heuristického řešení a u dynamického programování ani nelze předpokládat, že
by se nějaká závislost projevila, jelikož jsou tyto metody na maximální hmotnosti nezávislé. U průměrné chyby heuristického řešení je zřejmé, že chyba kolísá mezi 1,3% a 2%, ale nelze vypozorovat žádný trend.
Maximální cena Měření zkoumá vliv maximální možné ceny věci na počet stavů prošlých při výpočtu a na kvalitu řešení dosaženého heuristikou. Max cena
Větve a hranice
Dynamické programování
Heuristika
50
5450
10436
101
100
5852
19860
101
150
5276
30808
101
200
5681
39531
101
250
5034
51410
101
300
5169
57700
101
350
4338
68111
101
400
5660
79684
101
450
5442
87514
101
500 3806 99539 Tab 3 – počet stavů prošlých při výpočtu v závislosti na maximální ceně věci
101
120000
Počet stavů
100000 80000 Větve a hranice 60000
Dynamické programování Heuristika
40000 20000 0 0
100
200
300
400
500
600
Maxim ální cena Graf 3 – procentní průměrná chyba heuristického řešení vzhledem k optimálnímu
2,50
Průměrná chyba (%)
2,03
2,01
2,00
1,75
1,88 1,67
1,56
1,50
1,52
1,00
1,41
1,40
0,98
0,50
0,00 0
100
200
300
400
500
600
Maxim ální cena
Graf 4 – procentní průměrná chyba heuristického řešení vzhledem k optimálnímu Zhodnocení Z grafu 3 je zřejmé, jak je metoda dynamického programování lineárně závislá na součtu cen věcí, resp. na maximální ceně věci. U průměrné chyby heuristického řešení není vidět žádný trend.
Více malých (lehkých) věcí Měření zkoumá vliv převažujícího výskytu lehkých věcí na počet stavů potřebných pro výpočet a na kvalitu řešení dosaženého heuristikou. Pravděpodobnost výskytu věci s hmotností w je (1/w)^koef. Koeficient
Větve a hranice
Dynamické programování
Heuristika
0,5
3196
50754
102
1,0
1025
49865
104
1,5
1261
52118
105
2,0
1535
48850
104
2,5
4155
51094
102
3,0
10263
52640
101
3,5
10433
50666
100
4,0
10942
49454
100
4,5
13682
51940
100
5,0 12340 50293 100 Tab 4 – počet stavů prošlých při výpočtu v závislosti na tom, jak moc převažují věci s nižší váhou
60000
Po čet stavů
50000 40000
Větve a hranice
30000
Dynamické programování Heuristika
20000 10000 0 0,0
1,0
2,0
3,0
4,0
5,0
6,0
Hmotnost Graf 5 – procentní průměrná chyba heuristického řešení vzhledem k optimálnímu
1,8 Průměrná chyba (%)
1,6
1,54
1,4
1,29
1,2
1,38
1,28
1,36
1,32
1 0,8
0,73
0,6
0,55
0,4 0,2
0,19 0,07
0 0,0
1,0
2,0
3,0
4,0
5,0
6,0
Koeficient Graf 6 – procentní průměrná chyba heuristického řešení vzhledem k optimálnímu Zhodnocení Z měření se zdá, že metoda větví a hranic je na koeficientu zastoupení lehkých věcí závislá. S větším koeficientem roste počet prošlých stavů. Největší nárůst je patrný pro rozmezí hodnot koeficientu 2 a 3. Průměrná chyba heuristického řešení značně klesá se vzrůstajícím koeficientem. Pro koeficient s hodnoutou 5, je chyba již pouhých 7 setin procenta, tedy řešení je velmi blízké k optimu.
Více velkých (těžkých) věcí Měření zkoumá vliv převažujícího výskytu těžkých věcí na počet stavů potřebných pro výpočet a na kvalitu řešení dosaženého heuristikou. Pravděpodobnost výskytu věci s hmotností w je (1/(wmaxw))^koef.
Koeficient
Větve a hranice
Dynamické programování
Heuristika
0,5
7079
49316
100
1,0
10358
51130
100
1,5
13718
52159
99
2,0
12969
51017
99
2,5
16149
53626
99
3,0
13934
51272
99
3,5
11500
49787
99
4,0
11595
48824
99
4,5
12508
50317
99
5,0 12974 49848 99 Tab 5 – počet stavů prošlých při výpočtu v závislosti na tom, jak moc převažují věci s vyšší váhou
60000
Počet stavů
50000 40000 Větve a hranice Dynamické programování
30000
Heuristika 20000 10000 0 0,0
1,0
2,0
3,0
4,0
5,0
6,0
Hm otnost Graf 7 – procentní průměrná chyba heuristického řešení vzhledem k optimálnímu
1,60
Průměrná chyba (%)
1,40
1,40 1,25
1,20 1,10 1,00
0,97
0,85
0,81
0,80
1,02
0,68
0,60
0,58
0,40
0,34
0,20 0,00 0,0
1,0
2,0
3,0
4,0
5,0
6,0
Koeficient Graf 8 – procentní průměrná chyba heuristického řešení vzhledem k optimálnímu Zhodnocení Metoda větví a hranic vykazuje mírně rostoucí trend počtu propočítaných stavů pro zvyšující se hodnotu koeficientu. Průměrná chyba má složitější průběh, ale zdá se, že celkově má klesající trend.
Závěr Z provedených měření se podařilo vypozorovat náznaky některých závislostí. Zcela jasná je závislost metody dynamického programování na maximální ceně, ale to byl očekáváný výsledek jelikož vyplývá z povahy metody. Ostatní závislosti již nejsou tak zřejmé, ale o to jsou zajímavější. Pozoruhodné jsou výsledky vlivu granularity. Měření ukazují, že pokud se zvyšuje koeficient ovlivňující zastoupení lehkých (resp. těžkých) věcí, průměrná chyba heuristického řešení znatelně klesá. Přitom heuristické řešení je v porovnání s ostatními metodami rychlejší o několik řádů.
Výpočetní sestava Výpočty byly prováděny v prostředí Windows Vista Business 32bit na stroji s procesorem Intel Core 2 Duo T7700 2,4 GHz a 3GB paměti.
Podpůrné programy Programy byly napsány v jazyce C++, kompilovány ve Visual C++ 2005. Zdrojové kódy knapsack_bb.cpp - branch&bound knapsack_dynamic.cpp - dynamické programování knapsack_mostvalued.cpp - heuristika s testem nejcennější věci knapsackCompare.cpp - pomocný program pro porovnání heuristických řešení a hrubé síly knapsack, knapsack_bb, knapsack_dynamic, knapsack_mostvalued: Použití: program.exe input_file [output_file1 [output_file2] Formát input_file: každá instance na jednom řádku, na řádku jen celá čísla v tomto formátu ID n M váha cena váha cena ... Formát output_file: každá instance na jednom řádku, na řádku jen celá čísla
ID n cena řešení 0/1 0/1 ... Program zpracovává input_file, řešení zaznamenává do output_file a na standardní výstup vypíše časy výpočtu, maximální a průměrnou relativní chybu heuristiky. knapsackCompare.cpp: Použití: knapsackCompare.exe input_optimal input_heuristic Formáty vstupních souborů viz výše. Program vypíše na standardní výstup průměrnou a relativní chybu heuristiky.
