Problém batohu

Sat, 17 Jan 09 17:07:44 +0100

Obsah

  1. Obsah
  2. Hrubou silou a heristikou podle poměru cena/váha
    1. Zadání
    2. Specifikace problému
      1. Zadáno je
      2. Cílem je
    3. Řešení hrubou silou
    4. Řešení heuristikou podle poměru cena/váha
    5. Závěr
  3. Metodou větví a hranic, dynamickým programováním a heuristikou
    1. Zadání
    2. Specifikace problému
      1. Zadáno je
      2. Cílem je
    3. Řešení metodou větví a hranic
    4. Řešení dynamickým programováním
    5. Řešení heuristikou podle poměru cena/váha s testem nejcennější věci
    6. Měření
    7. Závěr
  4. Experimentální hodnocení algoritmů pro problém batohu
    1. Zadání
    2. Úvod
      1. Kvalita řešení
      2. Výpočetní náročnost
    3. Kvalita řešení
    4. Výpočetní náročnost
      1. Základní konfigurace generátoru instancí
      2. Závislost počtu stavů na velikosti instance
      3. Závislost počtu stavů na poměru kapacity batohu k sumární váze věcí
      4. Závislost počtu stavů na velikosti batohu (dynamické programování)
      5. Závislost počtu stavů na charakteru granularity
      6. Závislost počtu stavů na maximální ceně věci
    5. Závěr
  5. Genetickými algoritmy
    1. Zadání
    2. Popis implementovaného genetického algoritmu
    3. Měření
    4. Závěr
  6. A z toho všeho plyne...

Hrubou silou a heristikou podle poměru cena/váha

Zadání

Specifikace problému

Zadáno je

Cílem je

Najít takovou podmnožinu množiny věcí, která se ještě vejde do batohu, a zároveň je její cena nejvyšší možná. Řečeno formálněji: Najít množinu X = {x1, x2, ..., xn}, xi = {0, 1}, tak, aby platilo:

(tj. batoh nebyl přetížen) a aby výraz

nabýval maximální hodnoty pro všechny takové množiny.

Řešení hrubou silou

Algoritmus iteruje přes všechny kombinace věcí, v každém průchodu se vypočte jejich celková hmotnost a hodnota. Pokud je hmotnost nižší než nosnost batohu a zároveň jejich cena vyšší než dosud nejvyšší nalezená, označí se dané řešení jako řešení problému, které je po průchodu všemi kombinacemi vypsáno.

Knapsack()
{
	opt = 0;					// Nulové optimální řešení
	for (i = 0; i < 2^n; i++)			// Všechny kombinace
	{
		cur = {x1, x2, ..., xn}			// Další kombinace
		if (hm(cur) <= M)			// Vejde se do batohu?
			if (cena(cur) >= cena(opt))	// Dosud nejlepší?
				opt = cur;		// Označí jako dosud nejlepší
	}
	print(opt);					// Zobrazí výsledek
}
Po spouštění programu byly získány očekávané výsledky. Rychle rostoucí čas potřebný k výpočtu a jeho trend je zřejmý už při n = 25. Naměřené hodnoty jsou zaneseny do tabulky a rovněž do grafu, jedná se vždy o sumu časů všech padesáti datových sad.
n čas [s]
4 0.000292
10 0.03996
15 1.6481
20 66.412
22 286.350
25 2583.32

Graf pro řešení hrubou silou

Algoritmus má složitost O(2n), což je počet všech možných stavů, ve kterých se může batoh nacházet. Exponenciální doba trvání je jasná i z grafu. Jedinou výhodou tohoto algoritmu je, že vždy vypočítá optimální řešení.

Řešení heuristikou podle poměru cena/váha

Heuristika nejdříve seřadí věci sestupně podle poměru cena/hmotnost. V další fázi se postupně zkouší přidávat jednotlivé věci do batohu (ty s nejvyšším poměrem nejdříve). Poté, co se projdou všechny věci, je obnoveno jejich původní pořadí v datové struktuře a vypsán výsledek.

Knapsack()
{
	T = {t1, t2, ..., tn};			// Seznam věcí
	sort(T);				// Řazení podle cena/hmotnost sestupně
	ret = 0;				// Nulování řešení
	for(i = 0; i < n; i++)			// Všechny věci
	{
		if(hm(cur) + hm(ret) <= M)	// Vejde se ještě?
			batoh.add(cur);		// Vložit do batohu
	}
	print(batoh);				// Zobrazí výsledek
}

Heuristiky nezajišťují vždy stoprocentně správné vyřešení daného problému, nicméně přinášejí obrovské časové úspory. Aby byla doba trvání vůbec měřitelná, byl výpočet prováděn tisíckrát a získaná hodnota poté vydělena. V tabulce jsou taktéž uvedeny průměrné a maximální relativní odchylky od optima pro jednotlivá n. Je patrné, že pro malá n se heuristikou dopouštíme relativně velké chyby, s rostoucím n však tato chyba postupně klesá.

n čas [ms] Prům. rel. odchylka Max. rel. odchylka
4 0.252 2.175 36.364
10 0.496 1.104 11.480
15 0.768 0.305 2.770
20 1.044 0.449 4.079
22 1.096 0.542 3.018
25 1.208 0.425 2.588
27 1.416 0.289 1.845
30 1.524 0.383 1.749
32 1.648 0.274 2.278
35 1.824 0.188 1.817
37 1.940 0.181 1.176
40 2.112 0.153 0.946

Graf pro heuristiku cena/váha

Pokud není uvažována složitost řazení, má tento algoritmus (heuristika) lineární složitost, ne vždy se však nalezne optimální řešení problému.

Závěr

Každý další předmět, který se uvažuje při vkládání do batohu při řešení hrubou silou, extrémně zvyšuje výpočetní čas. Heuristika tuto dobu výrazně snižuje, nicméně ne vždy nalézá optimální řešení problému.

Oba programy byly napsány v jazyce C++ s použitím šablon ze standardní knihovny STL. Programy byl spouštěny na počítači s procesorem AMD Atlon XP 1800+ pod operačním systému Debian Etch GNU/Linux. Doba jejich trvání byla pro jednotlivé datové soubory měřena pomocí standardního programu time (položka user).

Metodou větví a hranic, dynamickým programováním a heuristikou

Zadání

Zpráva by měla obsahovat:

Specifikace problému

Zadáno je

Cílem je

Najít takovou podmnožinu množiny věcí, která se ještě vejde do batohu, a zároveň je její cena nejvyšší možná. Řečeno formálněji: Najít množinu X = {x1, x2, ..., xn}, xi = {0, 1}, tak, aby platilo:

(tj. batoh nebyl přetížen) a aby výraz

nabýval maximální hodnoty pro všechny takové množiny.

Řešení metodou větví a hranic

Algoritmus rekurzivně prochází všechny zadané věci, v každém zanoření se rozhoduje, zda určitá věc bude ve výsledném množině, či ne. Ořezávání se provádí podle dvou jednoduchých pravidel. 1) Rekurze se v dané větvi ukončí, když přidání aktuální věci přetíží batoh. 2) Do batohu se fiktivně přidají všechny zbývající/neprověřené věci a pokud je celková cena tohoto fiktivního řešení menší než cena dosud nejlepšího nalezeného, tak se rekurze v dané větvi opět ukončí.

Knapsack(index, cost, weight, things)
{
	// End of recursion?
	if(index >= n)
		return;

	// Actual thing won't be there
	if(cost + remaining_costs > currently_the_best)
		SolveKnapsack(index + 1, cost, weight, things);

	// Actual thing will be there
	if(weight + actual_thing.weight <= M)
	{
		if(cost + remaining_costs > currently_the_best)
		{
			// Update the best solution
			if(cost + actual_thing.cost > currently_the_best)
			{
				currently_the_best = cost + actual_thing.cost;
				things[index] = true;
				resolution_things = things;
			}

			things[index] = true;

			SolveKnapsack(index + 1,
				cost + actual_thing.cost,
				weight + actual_thing.weight,
				things);
		}
	}
}

Knapsack(0, 0, 0, 0);

Řešení dynamickým programováním

Algoritmus si v pseudopolynomiálním čase vygeneruje dvourozměrnou tabulku s výsledky řešení jednotlivých podproblémů a poté pouze zobrazí výsledek na požadovaném indexu tabulky.

void Knapsack(ID, n, M, data)
{
	ZeroFirstRow(table);
	ZeroFirstColumn(table);

	// Calculate table items
	for(i = 1; i <= M; i++)
	{
		for(j = 1; j <= n; j++)
		{
			if(cur.weight > i)
			{
				table(actual).cost = table(left).cost;
				table(actual).weight = table(left).weight;
				table(actual).things = table(left).things;
			}
			else
			{
				if(table(left).cost > table(down).cost + cur.cost)
				{
					table(actual).cost = table(left).cost;
					table(actual).weight = table(left).weight;
					table(actual).things = table(left).things;
				}
				else
				{
					table(actual).cost = table(down).cost + cur.cost;
					table(actual).weight = table(down).weight + cur.weight;
					table(actual).things = table(down).things;
					table(actual).things[j-1] = true;
				}
			}
		}
	}

	DisplaySolution(table[n, M]);
}

Řešení heuristikou podle poměru cena/váha s testem nejcennější věci

Výsledek původní heuristiky podle poměru cena/váha z první úlohy je srovnán s řešením, kdy obsahem batohu bude pouze nejcennější věc. Jako výsledek se vezme to řešení, které vychází lépe.

Knapsack(ID, n, M, data)
{
	T = {t1, t2, ..., tn};			// Seznam věcí
	sort(T);				// Řazení podle cena/hmotnost sestupně
	ret = 0;				// Nulování řešení
	for(i = 0; i < n; i++)			// Všechny věci
	{
		if(hm(cur) + hm(ret) <= M)	// Vejde se ještě?
			knapsack.add(cur);	// Vložit do batohu
	}

	thing = FindMostValuableThing();	// Nejhodnotnější věc

	if(thing.cost > knapsack.sumOfCosts())	// Je dražší než původní řešení?
	{
		knapsack.removeAllThings();	// Odstraní všechny věci
		knapsack.add(thing);		// Vloží pouze nejcennější věc
	}

	print(knapsack);			// Zobrazí výsledek
}

Měření

Následující tabulka obsahuje dobu trvání spuštění programu vždy pro padesát testovacích instancí problému batohu, které jsou uvedené na webu předmětu.

čas [s]
n Hrubá síla B&B Dyn. prog.
4 0.000292 0.005 0.003
10 0.03996 0.008 0.004
15 1.6481 0.013 0.012
20 66.412 0.073 0.021
22 286.350 0.259 0.022
25 2583.32 1.720 0.028
27 - 6.609 0.037
30 - 52.371 0.049
32 - 0.910 * 0.051
35 - 2.339 * 0.064
37 - 2.522 * 0.069
40 - 18.719 * 0.082

Ze souborů instancí označených hvězdičkou byla odstraněna konfigurace, která způsobovala, že se metoda B&B chovala téměř jako metoda hrubou silou, a tudíž nebylo možné získat výsledky během relativně krátkého času. V příkladu níže jsou hodnoty hmotností takové, že se batoh hned ze začátku nepřetíží, cena poslední věci způsobí, že prořezávání nezafunguje ani podle ceny. Z tohoto příkladu je vidět, že B&B může být výrazně závislá na složení vstupních dat problému a v nejhorším případě může dosahovat původní exponenciální složitosti.

9405 32 450 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14
14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14
14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 450 449

Graf pro dynamické programování

Graf pro metodu B&B

Společný graf pro dynamické programování a B&B

Porovnají-li se výstupy z programů a správné výsledky uváděné na webu předmětu v diffovacím nástroji (diff, Meld, Araxis Merge...), je vidět, že některé z uvedených instancí mají více optimálních řešení. Protože je výsledná cena všech věcí v batohu v obou případech stejná, nejedná se o chybu v programu.

Horní řádek: výsledky z webu předmětu
Dolní řádek: výsledky získané metodou dynamického programování

9588 40 4805  1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 1 1 0 0 1
9588 40 4805  1 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 1 0 1

9596 40 4244  1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 0 1
9596 40 4244  1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 1 1 0 1 0 1 0 1 1 1 1 0 1 1 1 0 1 1 1

Všechny programy byly napsány v jazyce C++ s použitím šablon ze standardní knihovny STL. Programy byly spouštěny na počítači s procesorem Intel Celeron 1,7 GHz pod operačním systémem Debian Sarge GNU/Linux. Doba jejich trvání byla pro jednotlivé datové soubory (tedy vždy 50 různých instancí problému) měřena pomocí standardního programu time (položka user).

Závěr

Srovná-li se heuristika z první úlohy s kombinovanou heuristiou, že vidět, že porovnání výsledků a zvolení lepší hodnoty, opravdu pomáhá. U malých instací je to více zřetelné než u velkých. Nevyžadují-li se naprosto přesné výsledky je implementovaná heuristika vhodným řešením. Odchylka od optimálního řešení je poté maximálně 50% (důkaz na stránkách předmětu).

Pokud je nutné přesné řešení, vychází nejlépe dynamické programování. To ale může být na druhou stranu limitováno velikostí dostupné paměti použité pro cachování mezivýsledků.

U většiny instancí problému se bude velice dobře chovat i metoda větví a hranic. Doba hledání řešení je však závislá i na vlastních hodnotách v zadání problému a za určitých okolností může dokonce narůst na původní exponenciální složitost metody hrubé síly.

Experimentální hodnocení algoritmů pro problém batohu

Zadání

Úvod

Pro řešení problému batohu existuje mnoho algoritmů jak exaktních, tak přibližných. O jejich vlastnostech toho není mnoho známo, pouze pro kombinované heuristiky byla dokázána maximální chyba. Chceme-li vědět více, musíme vyhodnocovat experimentálně.

Budeme sledovat dva podstatné parametry - kvalitu řešení a výpočetní náročnost. Uvedeme-li obě tyto veličiny do vztahu, dozvíme se, pro které kombinace nároků na čas a kvalitu je ten který algoritmus nejvýhodnější.

Kvalita řešení

Pro instance, kde známe exaktní řešení, se kvalita dá měřit absolutně. Tam, kde srovnáváme heuristiky mezi sebou, můžeme srovnávat pouze relativně. Tyto dva způsoby hodnocení je potřeba rozlišovat a konzistentně mezi nimi volit.

Výpočetní náročnost

Výpočetní náročnost se měří ještě hůře. Celkový čas výpočtu zahrnuje všechny vlivy, selhává však při porovnání výsledků z různých strojů. Zahrnuje také vlivy, které nejsou důležité - například způsob implementace datových struktur. Proto jako měřítko výpočetní složitosti volíme počet testovaných stavů. Poněvadž celkové počty stavů instancí lze snadno odvodit, máme měřítko účinnosti dané výpočetní metody.

Kvalita řešení

Problém batohu jsme řešili pouze dvěma heuristikami - heuristikou podle poměru cena/hmotnost a heuristikou podle poměru cena/hmotnost s testem nejcennější věci. Chování obou heuristik byla podrobně rozebrána už při minulých úlohách, a proto na tomto místě budou pouze ve stručnosti okomentovány výsledky.

Heuristika podle poměru cena/váha má polynomiální časovou složitost, a proto přináší obrovské časové úspory. Na druhou stranu je patrné, že pro malé počty věcí se dopouští relativně velké chyby, s jejich rostoucím počtem však tato chyba postupně klesá. Chyba je v principu způsobena postupným vkládáním jednotlivých věcí podle nejvyššího poměru cena/váha, kdy se už netestuje, zda by některá kombinace odstatních věcí byla výhodnější.

Druhá z heuristik je kombinací předchozí metody a testu na vložení pouze nejcennější věci. Jelikož vybírá lepší z obou řešení, bude její kvalita, vzhledem k první metodě, vždy lepší, náročnost výpočtu se však nijak výrazně nezvýší a stále bude polynomiální. Je dokonce dokázáno, že odchylka od optimálního řešení může být maximálně 50%.

Metody hrubé síly, dynamického programování i metoda větví a hranic vracejí vždy optimální řešení, a proto je zbytečné, o kvalitě jimi vrácených řešení, jakkoli diskutovat.

Výpočetní náročnost

Základní konfigurace generátoru instancí

Metoda hrubé síly prochází všechny možné kombinace jednotlivých věcí v batohu, a proto je její složitost vždy exponenciální (2n) a nezávisí na žádném z parametrů uvedených v tabulce. Podobně se chovají obě heuristiky, pracují však s polynomiální složitostí. Vzhledem k výše uvedeným důvodům nebudou tyto tři metody z hlediska výpočetní složitosti dále uvažovány.

Následující tabulka definuje implicitní nastavení generátoru instancí, při jednotlivých testech se bude hýbat vždy pouze s jedním parametrem. Pokud by se hýbalo více parametry najednou, daly by se možná najít i jiné závislosti, nicméně by to bylo časově velice náročné.

Parametr Hodnota
Velikost instance 20
Počet instancí  50
Maximální váha věci 100
Maximální cena věci 250
Poměr kapacity batohu k sumární váze 0.6
Charakter granularity Nerozlišovat
Exponent závislosti granularity 1

Aby byly výsledky více vypovídající, je pro každé nastavení konfigurace generováno vždy padesát různých instancí problému (viz parametr Počet instancí), získané hodnoty jsou průměrovány a následně zanášeny do grafu.

Pro měření byly použity implementace jednotlivých metod ze třetí úlohy. Byly upraveny, aby nevypisovaly jednotlivá řešení, ale pouze hodnoty počtu navštívených stavů.

Závislost počtu stavů na velikosti instance

Jak bylo zjištěno už v úloze číslo tři, dynamické programování vychází při vyšších hodnotách počtu instancí mnohem lépe než metoda B&B. Ta se může v nejhorším případě chovat téměř jako metoda hrubou silou, nicméně v praxi se nejhorší konfigurace vyskytují spíše zřídka. Dynamické programování, na druhou stranu, závisí nejen na počtu věcí, ale také na velikosti batohu (pseudopolynomiální složitost).

Počet stavů
n Dynamické programování B&B
05 924 24
10 3324 253
15 7161 1429
20 12392 9890
25 19853 69985
30 28052 638518
35 37512 5009287
40 48343 26312804

Graf závislosti počtu navštívených stavů na velikosti instance

Závislost počtu stavů na poměru kapacity batohu k sumární váze věcí

Optimální řešení se může skládat z několika málo věcí nebo z téměř všech věcí. Podle toho, "z které strany" řešení hledáme, můžeme prozkoumat větší nebo menší část stavů. Pro poměr větší než jedna je pochopitelně řešením soubor všech věcí. Zadáme-li maximální váhu věci a rozložení (granularitu), je tím (statisticky) určena i sumární váha. Proto kapacitu batohu určujeme nepřímo, poměrem k sumární váze.

Počet stavů
kapacita / ∑ váha Dynamické programování B&B
0.1 2174 1463
0.2 4263 9806
0.3 6602 27432
0.4 8364 32352
0.5 10728 16280
0.6 12582 10549
0.7 14601 4446
0.8 17023 2151
0.9 18402 1514
1.0 20907 1272

Graf závislosti počtu navštívených stavů na poměru kapacity batohu k sumární váze

Z grafu je jasně patrné, že u dynamického programování je křivka rovnoměrně rostoucí. Zajímavější je však metoda větví a hranic, přibližně do hodnoty poměru 0.4 je křivka rostoucí a poté postupně klesá.

Pokud je sumární váha věcí výrazně vyšší, než je kapacita batohu (hodnotou poměru je nízké číslo), zafunguje ořezávání shora, protože se již velice brzy detekuje překročení kapacity batohu. V opačném případě dochází zase spíše k ořezávání zdola - některé z již nalezených řešení je lepší než aktuálně prověřované. Při poměru jedna a vyšší se do batohu vejdou úplně všechny věci. Zdá se, že nejhorší možný poměr je okolo hodnoty 0.4, kdy pořádně nepracuje ani jedno z prořezávání, a kvůli tomu se prověřuje mnohem více stavů, než v ostatních případech.

Například v ukázce konfigurace níže jsou hodnoty hmotností takové, že se batoh hned ze začátku nepřetíží a cena poslední věci způsobí, že prořezávání nezafunguje ani podle ceny. Z tohoto příkladu je vidět, že metoda B&B může být výrazně závislá na složení vstupních dat problému a v nejhorším případě může dosahovat původní exponenciální složitosti metody hrubé síly. V dalším textu bude pro toto používáno označení "vhodnost instance".

9405 32 450 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14
14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14
14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 450 449

Závislost počtu stavů na velikosti batohu (dynamické programování)

Program s dynamickým programováním byl napsán nerekurzivně, tj. počítá se celá tabulka se všemi stavy a poté se vybírá hodnota v pravém horním rohu, a proto by měl být průběh v minulé kapitole (Závislost počtu stavů na poměru kapacity batohu k sumární váze) přímkou rovnoběžnou s osou x. Nicméně při inspekci jednotlivých instancí problému, začínají kapacity cca. u hodnoty 100 (~0.1) a poté postupně rostou až do 1000 (~1.0). Tímto způsobem tedy generátor nastavoval požadovaný poměr.

Kdyby byl program napsán rekurzivně, nepočítaly by se vždy všechny stavy a nejednalo by se o přímku - křivka by se s většími kapacitami batohu postupně zakřivovala do vodorovnějšího stavu.


Graf závislosti počtu navštívených stavů na kapacitě batohu (dynamické programování)

Závislost počtu stavů na charakteru granularity

Podle vyneseného grafu se zdá, že granularita (převaha malých či velkých věcí) na počet kroků k řešení má v případě dynamického programování vliv. Je to zejména patrné u vyššího počtu věcí, trojce křivek se zřetelně rozbíhá.

Počet stavů
Dynamické programování B&B
n malé nerozl. velké malé nerozl. velké
05 393 924 1501 23 24 24
10 1251 3324 5388 224 253 286
15 2652 7161 11783 1496 1429 17561
20 4968 12392 20576 4760 9890 17561
25 7719 19853 31561 21305 69985 137054
30 10866 28052 45479 122636 638518 982906
35 15370 37512 61134 396766 5009287 6875663
40 19546 48343 79869 2271841 26312804 23822808

Graf závislosti počtu navštívených stavů na charakteru granularity (dynamické programování)

U metody větví a hranic tak jasný vliv granularity vidět není. Do počtu věcí 35 je situace podobná, jako u dynamického programování, ale celou situaci nabourává hodnota 40. Toto chování si vysvětluji nevhodným složením jednotlivých věcí v batohu, pravděpodobně byly vygenerovány instance, pro které není tato metoda až tak vhodná. Odhadoval bych, že výkonnost algoritmu bude spíše záviset na "vhodnosti instance" pro tuto metodu, než na granularitě.


Graf závislosti počtu navštívených stavů na charakteru granularity (B&B)

Závislost počtu stavů na maximální ceně věci

Zdá se, že ani jedna z metod není závislá na maximální ceně věcí, měření bylo pro obě metody provedeno dvakrát s různými instancemi. U dynamického programování je kolísání pravděpodobně způsobeno ne vždy stejnými kapacitami batohu. Metodu větví a hranic spíše ovlivňuje "vhodnost instance" než maximální cena věci. Pokud by mezi těmito parametry i byly nějaké závislosti, nemáme moc velkou šanci je z testovacích dat zjistit.

Počet stavů
Dynamické programování B&B
max. cena #1 #2 #1 #2
250 12481 12647 8279 11777
500 12816 12561 11479 12281
750 12874 13064 10329 15424
1000 13001 12540 10464 8343
1250 13058 12973 13633 9234
1500 12690 12301 12232 11484
1750 12398 12780 9837 9693
2000 12778 12341 10629 10250
2250 12742 12906 10491 11619
2500 12914 12453 9428 12088
2750 12698 12875 10853 11449
3000 12874 12747 11509 12085

Graf závislosti počtu navštívených stavů na maximální ceně

Závěr

V této úloze bylo prakticky ověřeno chování jednotlivých algoritmů pro řešení problému batohu. Výsledky - ve formě tabulek, grafů a komentářů - lze najít přímo u textů zabývajících se daným parametrem.

Genetickými algoritmy

Zadání

Popis implementovaného genetického algoritmu

Vlastní genetický algoritmus je relativně jednoduchý. Na začátku se inicializuje populace na náhodné hodnoty a poté se vstoupí do while cyklu. V něm se postupně kopírují nejlepší jedinci z předchozí populace, provádějí se rekombinace s mutacemi a z nejlepších výsledků se vytvoří nová populace. Cyklus se zastaví poté, co se určitý počet generací nemění nejlepší známé řešení problému. Aby se výsledek ještě vylepšil, je celý algoritmus spuštěn několikrát nezávisle na sobě a vybírá se nejlepší z nalezených lokálních maxim.

SolveKnapsack()
{
	for(SeveralSeparateRuns)
	{
		InitializePopulation();

		while(BestSolutionIsChanging())
		{
			CopyBestFromPreviousPopulation();
			Recombinations();
			Mutations();
			Selection();
		}
	}

	DisplayBest();
}

Přesné chování genetického algoritmu lze upravit následujícími konstantami.

NUM_SEPARATE_RUNS definuje počet nezávislých spuštění genetického algoritmu nad danými daty, které jsou přidány kvůli alespoň částečnému odstranění problémů s lokálními maximy, přesnost výsledku se výrazně zvyšuje. Pokud se přesáhne STOP_BEST_NOT_CHANGED populací a nejlepší známé řešení se už dále nemění, je algoritmus ukončen.

NUM_COPIED_BEST_PARRENTS definuje, kolik nejlepších rodičů se automaticky zkopíruje do nově vytvářené populace. Mohli bychom se ocitnout v situaci, že po aplikování rekombinací a mutací získáme horší výsledek, než byl ten, ze kterého jsme vyšli. Zkopírování nejlepších rodičů zajistí, že v takovém případě populace tolik nezdegraduje.

POPULATION_SIZE udává velikost populace, nad kterou se provádí rekombinace a mutace, které se ukládají do pomocné populace o velikosti NEW_POPULATION_SIZE. Po aplikaci genetických operátorů se z ní vybírají nejlepší jedinci a vytváří se nová populace o původní velikosti.

NUM_MUTATIONS_IN_POPULATION obsahuje počet náhodných mutací, které se provedou při vytváření nové populace.

#define NUM_SEPARATE_RUNS		5
#define STOP_BEST_NOT_CHANGED		20
#define NUM_COPIED_BEST_PARRENTS	3
#define POPULATION_SIZE			20
#define NEW_POPULATION_SIZE		50
#define NUM_MUTATIONS_IN_POPULATION	5

Měření

Jistým problémem GA je, že i pro stejná vstupní data vrací při opakovaných spuštěních odlišná řešení, která mohou být i výrazně odlišná. Je to způsobeno tím, že se výchozí populace inicializuje na náhodné hodnoty a i selekce spolu s mutacemi se provádějí náhodně. Nemáme proto naprosto žádnou záruku, že se výsledné řešení bude blížit k optimálnímu nebo že se bude pohybovat v určitém rozsahu. Na druhou stranu níže uvedený graf nejlepší dosažené ceny v závislosti na vytvářených populacích ukazuje, že se ceny postupně vyvíjejí ke stále lepším. Pro výpočty a vynesení grafu byla použita následující instance problému:


Vývoj cen pro jednotlivá spuštění

Pozn.: Jsem si vědom toho, že linky nejsou v tomto grafu zrovna nejvhodnější, ale při vynášení jednotlivých bodů je výstup z gnuplotu hodně nepřehledný.

Jelikož je GA pro podobné instance problému velice rychlou metodou, je možné algoritmus spouštět vícekrát po sobě a poté uživateli zobrazit nejlepší z dosažených řešení. Jeden průchod pro výše uvedená nastavení a instanci problému, který se ukončil po 35. generaci, trval 4 ms (měřeno pomocí standardního programu time, položka user).

Závěr

Při vypracovávání této práce jsem s překvapením zjistil, že naprogramovat si vlastní genetický algoritmus není vůbec složité. Velice mi při tom pomohl naprosto skvělý popis genetických algoritmů od Marka Obitka (http://cs.felk.cvut.cz/~xobitko/ga/), který jsem náhodou objevil při pročítání prezentace o genetických algoritmech z University of Extremadura (Spain).

Hlavním problémem při programování GA je správné nastavení konfiguračních parametrů tak, aby algoritmus pracoval co nejlépe. Popravdě jsem nenašel žádný zaručený způsob, jak toho dosáhnout a po určitém čase jsem se jednoduše spokojil s hodnotami, které fungují celkem dobře, ale optimální asi nebudou. Jelikož se v GA používá funkce random() v podstatě všude, je velice obtížné (rychle a jednoznačně) určit, zda je určitá změna daného parametru prospěšná, či nikoliv. Vždy je nutné nad danými daty spustit program vícekrát, průměrovat výsledky a donekonečna porovnávat. A ani poté si člověk nemůže být úplně jistý.

Hodně dobrým příkladem může být parametr NUM_MUTATIONS_IN_POPULATION, který určuje kolik mutací se provede při vytváření každé populace. Na jednu stranu by to mělo být relativně vysoké číslo, abychom se dokázali dostat z lokálního maxima, ale na druhou stranu naprostá většina mutací způsobuje zhoršení a degradaci populace a jen několik málo z nich může být přínosem. Ten se ale opět - kvůli náhodnému výběru rodičů pro rekombinaci - nemusí vůbec projevit. V limitním případě se při příliš vysokém počtu mutací může z GA stát spíše random search, při příliš nízkém se běh zastaví v lokálním maximu.

Jiným parametrem může být velikost populace POPULATION_SIZE. Při čtení různých materiálů o GA, kdy jsem teprve zjišťoval, jak vlastně fungují, jsem několikrát viděl zmíněno, že základní populace by měla být spíše malá cca. 20 až 50 jedinců. To je sice pravda, ale velikost pomocného bufferu NEW_POPULATION_SIZE, do kterého se generují rekombinace a mutace a z nichž se poté selekcí vybírají jedinci nové populace, tak jednoznačná není. Čím bude menší, tím méně kombinací budeme generovat a naopak čím bude větší, tím bude program pomalejší. Opět je nutné najít rozumné optimum.

A z toho všeho plyne...

..., že nemá cenu se příliš pokoušet přeskládávat věci, stejně se do těch 20 kil povolených v letadle s věcma na půl roku není šance vejít. Optimální řešení existuje, nicméně Problém batohu je NP-úplný. Tohle všechno jsme se učili na FELu, heč! ;-)

Fri, 30 Jan 09 15:10:24 +0100

tlw

OMG! jeste ze uz jsem to cet pred rokem a nemusel jsem ted :D