Úkol 1 - problém batohu (knapsack problem)

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

Zadání

• Naprogramujte řešení problému batohu hrubou silou. Na zkušebních datech pozorujte závislost výpočetního času na n.
• Naprogramujte řešení problému batohu heuristikou podle poměru hmotnost/cena. Pozorujte:
  • závislost výpočetního času na n. Grafy jsou vítány (i pro exaktní metodu).
  • průměrnou a maximální *relativní chybu* (tj. zhoršení proti exaktní metodě)

Je dán batoh s kapacitou W a monožina předmětů N, kde každý předmět má svou váhu w_i a cenu v_i. Úkolem je najít takovou podmonožinu N, která maximalizuje cenu předmětů v batohu a nepřesáhne svou vahou kapacitu batohu W. Problém batohu je kombinatorický optimalizační problém spadající do třídy NP úplných problémů.

Vytvořil jsem dvě řešení - hrubou silou a řešení s využitím jednoduché heuristiky.

Při řešení hrubou silou procházíme všechny možná řešení problému a hledáme optimální řešení. Algoritmus rekurzivně generuje všechny možné kombinace věcí, které můžeme vložit do batohu, aniž bychom ho přetížili, a hledá optimální řešení. Složitost tohoto algoritmu je 2^|N|.

       public Solution SolveBruteForce(Instance instance, Solution solution, int idx)
        {
            if (idx < 0) return solution;
 
            if(solution.ResCapacity < instance.Items[idx].Weight) 
                return SolveBruteForce(instance, solution, idx-1);
 
            Solution s1 = solution;
            Solution s2 = solution.Clone();
 
            s2.Value += instance.Items[idx].Value;
            s2.ResCapacity -= instance.Items[idx].Weight;
 
            s1 = SolveBruteForce(instance, s1, idx-1);
            s2 = SolveBruteForce(instance, s2, idx-1);
 
            solution = s1.Value > s2.Value ? s1 : s2;
 
            return solution;
        }

Další řešení je s využitím jednoduché heuristiky. Heuristika spočívá v seřazení věcí podle poměru cena/váha. Následně do batohu vkládáme věci s nejvyšším poměrem cena/váha, dokud batoh zcela nezaplníme. Výpočetní složitost je značně redukována na cenu řazení + O(|N|).

        public Solution SolveWithHeuristic(Instance instance)
        {
 
            instance.SortItems(new ItemByValueWeightComparer());
            var solution = new Solution(instance);
 
            for (int idx = solution.Count-1; idx >=0 ; idx--)
            {
                if (solution.ResCapacity < instance.Items[idx].Weight) continue;
 
                solution.Value += instance.Items[idx].Value;
                solution.ResCapacity -= instance.Items[idx].Weight;
            }

Windows Server 2008 EE x64, Intel Core2 Duo E8500@3.16GHz, 8 GB DDR2

Platforma .NET nabízí několik možností jak měřit čas vykonávání algoritmu:

• DateTime.UtcNow
  • velmi rychlé volání,
  • špatná rozlišovací schopnost (10 milliseconds),
• Stopwatch
  • pomalejší než UtcNow,
  • nespolehlivé chování na vícejádrových počítačích, nebo počítačích s pohyblivou frekvencí,
• Process.TotalProcessorTime
  • měří pouze procesorový čas,
  • pokud problém zpracovává více jader, čas se sčítá,
  • výrazně pomalejší volání než u UtcNow.

Nejvýhodnější pro měření výkonnosti algoritmu je bezpochyby měření pomocí Process.TotalProcessorTime, které měří pouze procesorový čas, který nás zajímá. Bohužel i při využití Process.TotalProcessorTime nebyla rozlišovací schopnost pro malé instance a heuristiku dostatečná. Bylo nutné opakovat volání algoritmu ve smyčce a výsledný čas podělit počtem opakování. Ilustrace použití v následujícíh částech zdrojového kódu.

TimeSpan begin = Process.GetCurrentProcess().TotalProcessorTime;
...
TimeSpan end = Process.GetCurrentProcess().TotalProcessorTime;
Console.WriteLine("Execution time: " + (end - begin).TotalMilliseconds + " ms.");

begin = Process.GetCurrentProcess().TotalProcessorTime;
for (int i = 0; i < 100000; i++)
{
     solutionH = solver.SolveWithHeuristic(instance.Value);                        
}
end = Process.GetCurrentProcess().TotalProcessorTime;

Z tabulky a grafu 1 (v logaritmickém měřítku) je vidět exponenciálně rostoucí čas řešení hrubou silou. Naopak u řešení pomocí heuristiky je vidět lineární nárůst viz graf 2. Obrovský rozdíl ve výpočetním čase nám může přiblížit pohled na graf 3. Problémy s 32,35 a 37 předměty jsem řešil pouze pro dvě instance, jelikož jsou jejich nároky na čas příliš vysoké.

Graf 1

Graf 2

Graf 3

Pro každou instanci jsem spočetl relativní chybu a udělal průměr této chyby přes počet předmětů v instanci a zároveň zaznamenal maximální chybu. Nakonec jsem spočetl celkovou průměrnou relativní odchylku. Data můžeme vidět v tabulce, relativní chybu v grafu 4 a maximální chybu v grafu 5.

Relativní chybu spočteme jako ε = ( C(OPT)-C(APX) ) / C(OPT),

• kde C(OPT) je cena optima,
• a C(APX) je cena přibližného řešení.

Relativní chyba se pohybovala do 2%, i když průměrnou hodnotu ovlivnila jedna odlehlá hodnota pro instanci se 4 předměty, byl průměr na 1%, což je velmi dobrý výsledek.

Graf 4

Maximální chyba se pohybovala v rozmezí 0-10%, pouze jedna hodnota u instance s 4 předměty byla velmi vysoká a to 78%. To bylo nejspíš způsobeno netestováním vložení do batohu pouze nejdražšího předmětu.

Graf 5

Naměřené hodnoty naplnily očekávání a potvrdily, že řešení hrubou silou je pro svou výpočetní složitost u většího počtu předmětů nepoužitelné. Naopak řešení s využitím jednoduché heuristiky dává velmi dobré výsledky (průměrná relativní chyba 1,12%) při výrazně nižší výpočetní složitosti. Pokud je řešen optimalizační problém, je nutné znát cenu optimálního řešení a zhodnotit, zda není výhodnější využít heuristiky s výrazně nižší cenou, avšak s nejistotou nejlepšího optimálního řešení.

• http://en.wikipedia.org/wiki/Knapsack_problem
• http://rosettacode.org/wiki/Knapsack_problem/0-1