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.
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 |
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í.
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 |
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.
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).
Zpráva by měla obsahovat:
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.
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);
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]); }
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 }
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
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).
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.
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ší.
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 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.
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.
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ů.
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 |
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 |
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
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.
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 |
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ě.
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 |
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.
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
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:
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).
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.
..., ž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č! ;-)
tlw
OMG! jeste ze uz jsem to cet pred rokem a nemusel jsem ted :D