Problémy a algoritmy
Experimentální hodnocení algoritmů pro řešení problému batohu
(4. úloha)

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.

Sledované závislosti

Zpracování této úlohy jsem se rozhodl rozdělit na dvě části. Část první bude věnována srovnání kvality řešení obou heuristických metod, ve druhé části se zaměřím na porovnání výpočetní náročnosti algoritmů, především metody Větví a hranic a Dynamického programování.

Obě části, jak již bylo uvedeno v zadání, budou popisovat nalezené závislosti na parametrech instancí generovaných generátorem instancí. Generátor instancí má mnoho vstupních parametrů, má měření sledovaly závislosti na nastavení většiny z nich. Předem musím upozornit, že výsledky měření nebyly nijak překvapivé, v podstatě utvrdily předpoklady z úloh předchozích. Z tohoto důvodu je zpracování této úlohy možná poněkud chudší, než by se dalo očekávat, zpracování všech naměřených údajů mi nepřišlo zas tak podstatné, pokud měření nepřináší zajímavé skutečnosti.

Předem chci též podotknout, že bližší informace o algoritmech jednotlivých metod naleznete ve zpracování první a třetí úlohy.

Kvalita řešení

O kvalitě řešení má smysl se bavit pouze u heuristických metod, v mém případě tedy Heuristikou dle poměru cena/váha a Heuristikou dle cena/váha s testem nejtěžší věci. Výhodou pro určování kvality řešení je existence exaktního algoritmu s relativně slušnou složitostí ("nejlepší" algoritmus pro metodu Větví a hranic), kterým je možno zjistit přesné řešení i pro velké instance. Proto lze přesnost řešení určovat absolutně vůči výsledku tohoto algoritmu.

Srovnání heuristik, závislost chyby na velikosti instance
Jak již bylo uvedeno v předchozí úloze, druhá metoda má zaručenou cenu minimálně 50% optimálního řešení (ovšem pouze za předpokladu, že se nejtěžší věc do batohu vejde!!!), což u úlohy první samozřejmě neplatí. Rozdíly však nastanou pouze u speciálních instancí, které se v náhodně generovaných instancích pro větší počet věcí bohužel nevyskytují. Proto metody pro větší počty věcí dávají shodné výsledky, což mě vedlo k omezení velikosti testovaných instancí.

Pro zajímavost uvádím příklad instance, kdy metoda bez testu nejtěžší věci dává špatné výsledky:
    věc1: hmotnost=1, cena=1   věc2: hmotnost=M, cena=M-1   batoh: kapacita=M
Pro tuto instanci metoda zvolí věc1, která má lepší poměr cena/hmotnost a na věc druhou již nezbyde v batohu místo. Ideální řešení tedy dosáhne ceny M-1, kdežto heuristika pouze 1. Relativní chyba je tedy (M-2)/(M-1), což umožňuje dosáhnout libovolně velké chyby.

Následující tabulka ukazuje srovnání kvality řešení na náhodně generovaných instancí. Průměrná hodnota je vždy pro 50 instancí pro každý počet věcí.

Jak je z hodnot patrné, s rostoucím počtem věcí se chyby heuristických metod (maximální i průměrné) snižují. Ale je to především tím, že s rostoucím počtem věcí se snižuje pravděpodobnost "nevhodných" instancí a pokud se již tyto instance vyskytnou, je jejich chyba nižší než než u malého počtu věcí.
Vzhledem k malé průměrné složitosti metody Větví a hranic, která nalezne vždy exaktní řešení, je dle mého názoru výhodnější použít tuto metodu a heuristiky použít pouze pro ty instance, kde ořezání metody větví a hranic není dostatečné.

Velmi zajímavé jsou chyby algoritmu pro instance, kdy se alespoň jedna z věcí do batohu nevejde. Tato věc je samozřejmě věcí nejtěžší a proto test nejtěžší věci selže a obě heuristiky dávají stejné výsledky, tedy až 100% chybu. Chyba 100% je dosažena, pokud je tato nejtěžší věc zároveň věcí s nejlepším poměrem cena/váha (což při její velké hmotnosti je snadno dosažitelné) a do batohu tedy není přidána žádná věc.

Závislost chyby na poměru kapacity a celkové hmotnosti věcí
Tato závislost je zřejmá již z podstaty heuristických algoritmů - čím větší počet věcí je možno do batohu přidat, tím menší je význam chyba případné špatné volby, ostatní věci tuto chybu alespoň částečně napraví. Výsledky měření naleznete v následující tabulce.

Tabulka zachycuje velikost maximální a průměrné relativní chyby řešení v závislosti na poměru celkové hmotnosti věcí a kapacity batohu (parametr m generátoru). Průměrné hodnoty byly získány z měření padesáti instancí, velikost všech instancí byla 30 věcí.

Výpočetní složitost algoritmů

Pro srovnání složitosti algoritmů jsem se rozhodl do této úlohy zahrnout pouze (výpočetně) lepší varianty metod, metody hrubou silou již vůbec nebudu uvažovat, jejich složitost je příliš veliká. Podrobnosti k principu jednotlivých algoritmů nalezenete ve zpracování první a třetí úlohy.

Metody budou, podobně jako v předchozí úloze, porovnávány podle počtu kroků, které jsou třeba k dosažení řešení. Pro zjednodušení značení jsem pro metody opěr zvolil "kódová jména". Tato jména spolu s vysvětlením významu počtu kroků pro jednotlivé srovnávané metody jsou uvedeny v následující tabulce.

Nárůst složitosti v závislosti na velikosti instance
Až překvapivě malá složitost metody Větví a hranic mě vedla k testu možností jednotlivých metod - pro jak velké instance je ještě ten který algoritmus použitelný. Výsledky byly velmi překvapivé.

Použitelnost metody Dynamického programování je velmi závislá na velikosti paměti počítače - jakmile velikost pole pro ukládání mezivýsledků překročí její velikost, potřeba častého swapování paměti absolutně znemožní použití algoritmu - asi po deseti minutách úpěnlivého blikání kontrolky disku jsem se nad diskem a v té době již stejně zborcenými Windows slitoval a počítač jsem natvrdo resetoval.
Jak jsem již uvedl, použitelnost metody závisí na velikosti paměti počítače, lze tedy jen těžko uvádět obecné závěry. Je však nutno si uvědomit, že velikost alokovaného pole závisí na součinu count*capacity, tedy nejen na počtu věcí. O výpočetní složitosti algoritmu je těžko dělat jakékoliv závěry, jelikož není počítán obsah celého pole, ale jen skutečně potřebných hodnot, jejichž počet je velmi závislý na všech parametrech dané instance, které však není možno obecně podchytit nastavením parametrů generátoru instancí. Je však důležité si uvědomit, že pokud kapacita batohu je velmi velká, značnou část doby výpočtu zabere počáteční iniciace pole, která není do počtu kroků započítávána.
Pokud by vás zajímalo obecné zjištění, na PC s Win98 a 128MB paměti byla velikost poslední akceptovatelné instance 250 věcí (s max. hmotností věci 1000, tedy kapacitami batohu kolem 850 000), pro instanci o velikosti 300 věcí (a kapacitami kolem 1E+6) již cýsledek nebyl dosažen.

Velkým překvapením pro mě byly výsledky algoritmu metody Větví a hranic, která byla snadno použitelná i pro instance s 10 000 věcmi. Srovnání této metody s metodou heuristickou pro velké počty věcí naleznete v následující tabulce a grafu.

Tabulka uvádí srovnání výsledků Heuristiky a metody Větví a hranic pro velké instance. Jsou uvedeny průměrné hodnoty z měření výsledků pro pět instancí, "vetve_max" je maximální hodnota metody Větví a hranic.
Přehlednější zobrazení naleznete v grafech, které se nachází pod tabulkou.

V druhém grafu jsem by hodnota rozdílu obou metod měla představovat složitost samotné metody Větví a hranic bez počátečního řazení (obě metody totiž používají stejné řazení). Jak je vidět, závislost není lineární, ale lze jen těžko usuzovat, zda je kvadratická či exponenciální.

Srovnání průměrné a maximální složitosti algoritmů
Následující tabulka reprezentuje základní rozdíl ve složitosti algoritmů, kterým je poměr mezi nejhorším a průměrným počtem kroků. Průměrná hodnota je průměrem z 50-ti instancí pro daný počet věcí, instance byly standardními instancemi bez speciálních nastavení. Vyhodnocení výsledků naleznete pod tabulkou.

Z tabulky je jasně patrná větší závislost algoritmu pro metodu Větví a hranic na konkrétní instanci - její hodnota poměru maximální a průměrné složitosti je jednoznačně největší, a to přibližně dvojnásobně oproti ostatním metodám. Z tohoto srovnání lze vysledovat skutečnost, že metoda Větví a hranic má základní složitost exponenciální a teprve na konkrétním "stromu" instance závisí, jak moc bude možné ho "prořezat".

Další závislosti
Přes celkem velkou snahu se mi nepodařilo nalézt další závislosti mezi parametry generátoru instancí a výsledcích jednotlivých metod. Nalezené a prezentované závislosti budou shrnuty v následující kapitole

Závěr - vyhodnocení metod

Na závěrem jsem se rozhodl stručně shrnout vlastnosti jednotlivých metod, které byly uvedeny v této nebo předchozích úlohách.

Heurisitika dle poměru cena/váha
je nejrychlejší metodou pro řešení batohu, její složitost závisí na složitosti použitého řazení. Kvalita řešení je závislá na konkrétní instanci, obecně může být libovolně velká, ale v normálních případech pro větší počet věcí není nikterak kritická.

Heurisitika cena/váha s testem nejtěžší věci
je vylepšením předchozí heuristiky, zaručuje dosažení minimálně 50% ceny optimálního řešení (pokud se všechny věci vejdou do batohu). Její složitost je opět závislá na použitém řazení.

Řešení hrubou silou
nalezne vždy optimální řešení, složitost je však exponenciální a proto není prakticky použitelné

Dynamické programování
je metodou s relativně dobrou složitostí, ale vysokou paměťovou náročností, která znemožňuje řešení rozsáhlých instancí. Maximální složitost algoritmu je závislá na součinu count*capacity, řešení je tedy závislé na celkové kapacitě batohu (a tím i poměru hmotnosti věcí ku kapacitě batohu).

Metoda větví a hranic
je dle mého názoru ideální metodou pro řešení problému batohu, ale výpočetní složitost je velmi závislá na konkrétní implementaci "ořezávání" stavového prostoru. Metoda vychází z řešení hrubou silou, z čehož vyplývá její exponenciální maximální složitost - důkazem toho je podstatně větší rozdíl mezi průměrnou a maximální hodnotou při řešení více instancí.
Můj algoritmus je velmi citlivý na instance s věcmi s podobným poměrem cena/váha, kde optimalizační kritérium stavový prostor prořezává nedostatečně a složitost velmi rychle roste.