Seznámení se se zvolenou pokročilou iterativní metodou na problému batohu

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

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
 

Vliv jednotlivých variant:

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.

Test G1

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í:

Výsledek konkrétního testu a pohled na aplikaci je na následujícím obrázku:

Závěr

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ě.

Ke stažení

Zdrojový a zkompilovaný kód vytvořený ve Visual Studiu C++ je zde: uloha5.zip
Samostatný genetický algoritmus: GA.cpp

Autor: Jaroslav Nušl