Zvolená metoda: Genetický algoritmus (dále GA)
Princip:
1) Vygenerovat dva jedince - rodiče
2) Křížením vytvořit další dva jedince - potomky
3) Mutace rodičů
4) Selekce - vyberou se dva nejlepší jedinci a použijí se jako rodiče
- každá další iterace opakuje body 2 až 4.
Podrobný princip
1) Vygenerovat dva jedince - rodiče
a) generování je náhodné
b) generování je založeno na plnění batohu z leva do maximální kapacity pro
jednoho rodiče a zprava pro druhého
2) Křížením vytvořit další dva jedince - potomky
Křížení je uniformní - použije se náhodně vygenerovaný vektor
(byl-li náhodný vektor generován jednou na počátku, nebo při každé iteraci,
nedocházelo k žádné razantní změně, pouze se navýšil výpočetní čas takřka o 1/3)
3) Mutace rodičů
Náhodně zvolený gen se invertuje
4) Selekce - vyberou se dva nejlepší jedinci a použijí se jako rodiče
a) Z rodičů je vybrán jeden lepší a v případě že splňuje omezující podmínky
je použit jako rodič, jinak je generován nový jedinec. To samé se provede pro
potomky.
b) Z rodičů je vybrán jeden lepší a v případě že splňuje omezující podmínky je
použit jako rodič, jinak jsou mu z leva nulovány geny, dokud není omezující
podmínka splněna. To samé se provede pro potomky.
c) Jde o zkřížení obou variant. Tedy varianta B, kde je výběr nulovaných
genů určen náhodně.
Testy GA byly porovnávány s nejlepším použitým algoritmem, který nacházel
optimální řešení a to s algoritmem pracujícím s metodou větví a mezí.
Algoritmus GA nebyl z hlediska potřebného výpočetního času navrhován co
nejoptimálněji, proto by zřejmě šlo výsledky tohoto algoritmu ještě o něco
vylepšit.
Společný jev pro všechny testy
- při zvyšování počtu iteraci docházelo ke zlepšování výsledku
- při zvyšování složitosti instancí při zachování počtu iterací se kvalita
zhoršovala
Generováni jedince variant A či B:
Při vyšším počtu interaci dávaly obě varianty podobný výsledek (pro cca
500). Pro menší počet interací (cca 10) varianta B dávala podstatně lepší
výsledky. Proto byla pro následující testy vybrána už jen varianta B.
Selekce:
Varianta A: U této varianty nebyl vždy zaručen dobrý výsledek. Došlo zde k
extrémně špatnému výsledku při konfiguraci s koeficientem granularity 1,6 a
důrazem na obsah velkých věcí (test G1), který se při zvyšování počtu interaci
mnoho nezlepšoval.
Varianta B: Zde se již kvalita pohybovala u všech testů v rozumných hodnotách, viz tabulka 1 - test G1.
Varianta C: Tato varianta dávala stejné výsledky jako varianta B, proto jsem jí do výsledné tabulky již nezahrnul.
Tento test dosahoval nejhorších výsledků, proto jsem jej použil pro výsledné shrnutí výsledků. Parametry pro tento test jsou:
Maximální cena = 250; velikost instance = 20; poměr váhy ke kapacitě = 0,6; počet instancí = 50; maximální váha věci = 100; více velkých věcí s koeficientem granularity 1.6;
Dosažená kvalita pro varianty selekce A a B v závislosti na počtu instancí:
interce | selekce | |
A | B | |
1 | (0.08) | 0.07 |
10 | (0.08) | 0.53 |
100 | (0.08) | 0.65 |
500 | 0.1 | 0.71 |
1000 | 0.12 | 0.74 |
10000 | 0.41 | 0.79 |
Výsledek konkrétního testu a pohled na aplikaci je na následujícím obrázku:
Veliké plus genetického algoritmu vidím v možnosti předem vymezit čas pro výpočet, určením počtu interací. Algoritmus lze také modifikovat, tak, aby při malé či žádné změně zlepšování sám sebe zastavil a vyobrazil vypočtené výsledky. Vliv jednotlivých variant je popsán výše. Při měření bylo zjištěno, že generování náhodné veličiny zabere poměrné hodně výpočetního času, proto je vhodné toto generování používat co nejméně.
Zdrojový a zkompilovaný kód vytvořený ve Visual Studiu C++ je zde:
uloha5.zip
Samostatný genetický algoritmus: GA.cpp
Autor: Jaroslav Nušl