XIII. Doporučení

Parametry GA

Tato kapitola by vám měla dát některá základní doporučení, pokud jste se rozhodli implementovat vlastní genetický algoritmus. Tato doporučení jsou velmi obecná. Pravděpodobně budete chtít s vlastním GA pro konkrétní problém experimentovat, protože stále neexistuje obecná teorie, která by popisovala parametry GA pro libovolný problém.

Tato doporučení často vycházejí z empirických studií GA, z nichž mnoho bylo provedeno pouze s binárním kódováním.

  • Pravděpodobnost křížení
    Pravděpodobnost křížení by měla být obecně vysoká, zhruba 80 %-95 %. (Některé výsledky ale ukazují, že pro určité problémy je nejlepší pravděpodobnost křížení okolo 60 %.)
  • Pravděpodobnost mutace
    Naopak pravděpodobnost mutace by měla být velmi nízká. Nejlepší uváděné hodnoty jsou asi 0,5 %-1 %.
  • Velikost populace
    Možná je překvapivé, že velmi velká populace obvykle nezlepšuje výkonnost GA, pokud jde o rychlost nalezení řešení. Dobrá velikost populace bývá často asi 20-30, i když někdy se jako nejlepší uvádí velikost 50-100. Některý výzkum také ukazuje, že nejlepší velikost populace závisí na kódování a na délce zakódovaného řetězce. To znamená, že pokud máte chromozom o 32 bitech, velikost populace může být okolo 32 a určitě bude větší než nejlepší velikost populace pro chromozom o 16 bitech.
  • Selekce
    Lze použít základní ruletovou selekci, ale někdy může být lepší selekce podle pořadí. Podívejte se do kapitoly o selekci, kde jsou uvedeny výhody a nevýhody. Existují také složitější metody, které mění parametry selekce během běhu GA. V principu se chovají trochu podobně jako simulované žíhání. Skoro vždy by se měl ale použít elitismus (pokud nepoužíváte jinou metodu uchování nejlepšího nalezeného řešení). Můžete také vyzkoušet selekci se stálou populací.
  • Kódování
    Kódování závisí na problému a také na velikosti instance problému. Podívejte se do kapitoly o kódování pro některé nápady nebo se podívejte do dalších zdrojů.
  • Typ křížení a mutace
    Operátory závisí na kódování a na problému. Podívejte se do kapitoly o operátorech pro některé návrhy. Můžete také využít další zdroje.

Aplikace GA

Genetické algoritmy byly použity pro obtížné problémy (např. NP-hard problémy), pro strojové učení a také pro evoluci jednoduchých programů. Byly také použity v umění, např. pro evoluci obrázků a hudby.

Jednou z výhod GA je jejich paralelnost. GA prohledává prohledávací prostor pomocí více jedinců (a pracuje s genotypem místo fenotypu), a proto u něj hrozí menší riziko uvíznutí v lokálním optimu než u některých jiných metod.

Jsou také poměrně snadné na implementaci. Jakmile máte připravený rámec GA, často stačí definovat nové zobrazení chromozomu a můžete řešit další problém. Při stejném kódování často stačí změnit pouze účelovou funkci. Na druhou stranu může být obtížné navrhnout dobré kódování a vhodnou účelovou funkci.

Jednou z nevýhod GA je výpočetní náročnost. Mohou být pomalejší než některé jiné metody. S dnešními počítači to ale často není tak velký problém.

Aby bylo jasné, jaké typy problémů se pomocí GA řeší, uvádíme krátký seznam aplikací:

  • Nelineární dynamické systémy - predikce, analýza dat
  • Návrh neuronových sítí, a to jak architektury, tak vah
  • Trajektorie robota
  • Evoluce programů v LISP (genetické programování)
  • Plánování strategie
  • Hledání tvaru molekul proteinů
  • TSP a plánování posloupnosti
  • Funkce pro vytváření obrázků

O projektu

První verze demonstrace, původně jako interaktivní ukázka, vznikla v letním semestru roku 1998 na Českém vysokém učení technickém (pod vedením prof. Pavla Slavíka). Projekt pak pokračoval v létě 1998 na Hochschule für Technik und Wirtschaft Dresden (FH) (pod vedením prof. Waltera Pätzolda). Začal jako malý letní studentský projekt, když jsem se učil programování a genetické algoritmy, ale postupně vyrostl ve velmi používaný tutorial a dostal jsem na něj mnoho pozitivních reakcí (děkuji!). Když interaktivní ukázky přestaly v prohlížečích fungovat, staly se tyto stránky méně populární. V roce 2026 byly ukázky převedeny pro web s pomocí LLM, takže jsou demonstrace znovu dostupné.