Paralelní genetické algoritmy

Semestrální práce z předmětu Programovací jazyky pro WWW

Petr Pošík, 5/18
xposik@rtime.felk.cvut.cz, posa@volny.cz

28.6.2000

Katedra kybernetiky
Fakulta elektrotechnická
České vysoké učení technické v Praze


Pro nováčky na poli genetických algoritmů doporučuji předem se podívat na některou z následujících stránek:

  1. Marek Obítko: GA - komplex velice pěkně udělaných stránek vysvětlujících na rozsáhlé sadě Java appletů koncepty a funkce jednoduchých GA. Jsou sice v angličtině, ale vřele doporučuji.

  2. Jednoduché genetické algoritmy - obsáhlý přehled principů a postupů používaných v GA. Text.

  3. Paralelení genetické algoritmy - přehled a rozdělení PGA, motivace k jejich užívání, výhody, nevýhody. Text.

  4. Programátorká dokumentace - popis tříd a appletu vygenerovaný programem JavaDoc


Porovnání SGA a PGA na problému obchodního cestujícího

Níže uvedený applet prezentuje rozdíly v běhu jednoduchého a paralelního genetického algoritmu. Zobrazuje zároveň řešení problému obchodního cestujícího nalezeného pomocí SGA (vpravo nahoře) a pomocí PGA (vpravo dole). Parametry nalezeného řešení jsou uvedeny vždy vlevo od jeho grafického znázornění (tedy uprostřed nahoře a dole). V levé dolní části je navíc vizualizován průběh migrace jedinců mezi jednotlivými populacemi. Nastavení parametrů obou GA spolu s ovládacími tlačítky se nachází v levé horní části appletu.

Oba algoritmy užívají stejné parametry (celková velikost populace, pravděpodobnost mutace, atd.), aby mělo smysl jejich běh vůbec porovnávat.

Java applet předvádějící rozdíly v běhu jednoduchého a paralelního GA na problému obchodního cestujícího

Některé části programu jsou adaptovány ze zdrojových kódů Marka Obítka


Na appletu je vidět síla PGA. V okamžiku, kdy GA začne docházet dech (dojde ke značné konvergenci populace k jedinému suboptimálnímu řešení), SGA už není schopno se vymanit ze sevření tohoto lokálního extrému (může pomoci zvýšení pravděpodobnosti mutace, ale pak se celý algoritmus značně přibližuje náhodnému prohledávání). Ve stejný okamžik ale PGA vytahuje z rukávu své tajné eso - migraci - a jednotlivé subpopulace zkonvergované k různým lokálním řešením si mezi sebou začnou vyměňovat genetické informace, takže běh PGA v lokálním optimu neuvázne a pokračuje dál ve vývoji.