ČVUT – FEL X36PAA - Problémy a algoritmy
5. úloha - Seznámení se se zvolenou pokročilou iterativní metodou na problému batohu Jméno: Marek Handl Datum: 4. 2. 2009 Cvičení: Pondělí 9:00
Zadání Zvolte si heuristiku, kterou budete řešit problém vážené splnitelnosti booleovské formule (simulované ochlazování, simulovaná evoluce, tabu prohledávání) Tuto heuristiku použijte pro řešení problému batohu. Můžete použít dostupné instance problému (zde), anebo si vygenerujte své instance pomocí generátoru. Používejte instance s větším počtem věcí (>30). Hlavním cílem domácí práce je seznámit se s danou heuristikou, zejména se způsobem, jakým se nastavují její parametry (rozvrh ochlazování, selekční tlak, tabu lhůta...) a modifikace (zjištění počáteční teploty, mechanismus slekce, tabu atributy...). Není-li Vám cokoli jasné, prosíme ptejte se na cvičeních. Problém batohu není příliš obtížný, většinou budete mít k dispozici globální maxima (exaktní řešení) z předchozích prací, například z dynamického programování.
Simulované ochlazování Použitého algoritmus lze popsat následujícím pseudokódem. temperature = initialTempFactor * bestPrice / log(2); // set initial temperature to a factor of best valued item that fits in the sack state = putFirstPossibleItemInSack(); while (temperature > minTemperature) { // i.e. while not frozen steps = 0; while (steps < stepsCount*count) { // i.e. while not equilibrium ++steps; state = changeState(state); if (state.getPrice() > best.getPrice()) { // find a new state or keep the same best = state; } } temperature *= cooldownFactor; // i.e. cool down statesTested += steps; } changeState(state) { newState = getRandomNeighbor(state); if (newState.getPrice() > state.getPrice()) { return newState; } delta = state.getPrice() – newState.getPrice(); if (random() < exp(-delta/temperature)) { return newState; } // keep the old state return state; } getRandomNeighbor(state) { index = randomItemNumber(); if (index not in state sack) { state = addItemToSack(index, state); } else { state = removeItemFromSack(index, state); }
return state; }
Chování algoritmu je možné ovlivňovat nastavením hodnot parametrů: o initialTempFactor – určuje velikost prvotní teploty (v násobcích hodnoty nejcennější věci, která se vejde do batohu) o minTemperature – určuje minimální teplotu, pro nižší teplotu se algoritmus ukončí o stepsCount – určuje počet průchodů vnořeného while-cyklu v násobcích počtu věcí o cooldownFactor – určuje ochlazovací faktor
Měření Byla provedena měření sledující vliv jednotlivých parametrů na chování a výsledky výpočtu. Je sledován počet stavů, které se při výpočtu projdou a relativní odchylka výsledku vzhledem k optimálnímu řešení. K výpočtu odchylky se používá vzorec: chyba = (cenaOptimum – cenaHeuristika) / cenaOptimum. U grafů odchylek je zobrazen i trend vypočtený standardní funkcionalitou MS Excel 2003 – Power Trendline. Jeho vzorec následuje. Equation: y=c*x^b c: =EXP(INDEX(LINEST(LN(y),LN(x),,),1,2)) b: =INDEX(LINEST(LN(y),LN(x),,),1) Každé měření bylo prováděno na 40 různých instancích a výsledky zprůměrovány. Ve všech provedených měřeních vždy měníme pouze jeden parametr, ostatní zůstavají fixní. V následující tabulce jsou uvedeny standardní hodnoty parametrů. initialTemp minTemperature stepsCount cooldownFactor 1 0,01 Tab 1 – standardní hodnoty parametrů algoritmu
2
0,9
Počáteční teplota - initialTempFactor 2,90
5000
P o čet stavů
4500
2,50 2,30
4000 2,10 1,90
3500
Prů m ěrná chyba (% )
2,70
Počet stavů Průměrná chyba (%) Pow er (Průměrná chyba (%))
1,70 3000 0,0
1,0
2,0
3,0
4,0
5,0
1,50 6,0
Počáteční teplota Graf 1 – počet stavů prošlých při výpočtu a průměrná odchylka řešení od optima vzhledem k hodnotě počáteční teploty Zhodnocení Zvyšováním počáteční teploty dáváme algoritmu větší šanci opustit oblast lokálního minima. Je zřejmé, že počet prozkoumaných stavů s vyšší počáteční teplotou roste, ale snižování průměrné chyby tak přesvědčivé není. Je patrný klesající trend, takže lze tvrdit, že zvyšováním původní teploty dosahujeme lepších výsledků, ale je nutné počítat s výkyvy výkonnosti.
Minimální teplota - minTemperature 5000
3,10 2,90 2,70 2,50
4000
2,30 2,10
3500
Prům ěrná ch yba (% )
Počet stavů
4500
Počet stavů Průměrná chyba (%) Pow er (Průměrná chyba (%))
1,90 1,70
3000 0,000
0,010
0,020
0,030
0,040
1,50 0,050
Minimální teplota
Graf 2 – počet stavů prošlých při výpočtu a průměrná odchylka řešení od optima vzhledem k hodnotě teploty, kdy se algoritmus ukončuje Zhodnocení Zvyšováním minimální teploty zastavíme algoritmus dříve. Dosáhneme tak zkrácení výpočtu. Z měření vyplývá, že ve zkoumaném rozmezí nemá minimální teplota vliv na kvalitu výsledku. Dokonce se zdá, že průměrná chyba klesá společně s nárůstem minimální teploty, což je přesně opak očekávaného chování.
Počet průchodů - stepsCount 25000
4,50 4,00
20000
P oč e t s ta vů
3,00 15000 2,50 2,00 10000 1,50
P rům ěrná c hy ba (% )
3,50
Počet stavů Průměrná chyba (%) Pow er (Průměrná chyba (%))
1,00
5000
0,50 0
0,00 0
2
4
6
8
10
12
Počet průchodů Graf 3 – počet stavů prošlých při výpočtu a průměrná odchylka řešení od optima vzhledem k faktoru, který ovlivňuje kolikrát se provede vnitřní cyklus algoritmu před ochlazením Zhodnocení Počet stavů, které se při výpočtu prozkoumají lineárně roste s počtem provedení vnitřního cyklu (než se dosáhne equilibria). Tato závislost je přirozená. Je patrné, že tento parametr má značný vliv na průměrnou chybu řešení. Pro hodnoty 1 až 4 klesá chyba velmi znatelně.
Parametr ochlazování – cooldownFactor 25000
5,00 4,50 4,00
P oč e t s ta v ů
3,50 15000
3,00 2,50
10000
2,00 1,50
5000
P rům ě rná c hy ba (% )
20000
Počet stavů Průměrná chyba (%) Pow er (Průměrná chyba (%))
1,00 0,50
0 0,77
0,00 0,87
0,97
Parametr ochlazování Graf 4 – počet stavů prošlých při výpočtu a průměrná odchylka řešení od optima vzhledem k rychlosti ochlazování Zhodnocení Nárůst počtu zkoumaných stavů vzhledem k hodnotě parametru ochlazování má polynomiální průběh. Pro hodnoty velmi blízké 1 je ale nárůst počtu stavů enormní. Souběžně s tím klesá průměrná chyba výsledku, zdá se že lineárně.
Závěr Z provedených měření lze vidět vliv parametrů algoritmu na výpočetní čas a na kvalitu nalezeného řešení. Ukázalo se, že nemá cenu nastavovat příliš vysokou počáteční teplotu. Taková hodnota pouze vede k prodlužování výpočtu s minimálním pozitivním vlivem na kvalitu výsledku. Jako vhodná hodnota se jeví číslo 2. Parametr minimální teploty, se zdá, také nemá cenu nastavovat příliš nízko. Hodnota 0,04 vedla k rychlému výpočtu s malou chybou. Další dva parametry se ukázaly jako důležitější. Je nutné zvolit kompromis mezi časem výpočtu a požadovanou kvalitou. Jako vhodné se jeví hodnoty 6 pro počet provedení vnitřního cyklu a 0,96 pro parametr ochlazování.
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 annealing.cpp knapsackCompare.cpp řešení
- pomocný program pro porovnání heuristických a optimálních
annealing: Použití: program.exe annealing.exe input_file initial_temperature min_temperature steps_count cooldown_factor 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 „v_“+input_file a na standardní výstup vypíše počet prošlých stavů. 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.
