Jaká je jeho idea a k čemu lze použít

Na světě existuje mnoho úloh a problémů, jejichž vyřešení by nám výrazně zjednodušilo život. Některé problémy vyřešit dokážeme, ale ne dost rychle. U jiných nedokážeme navrhnout ani správný postup k řešení. Když už tedy sami nedokážeme nalézt uspokojivý výsledek, nastupují univerzální solvery, tedy “řešiče” problémů, kterým předložíme precizně popsaný problém a oni postupně dospějí k hledanému řešení. Jedním z nich je genetický algoritmus. Pojďme se tedy velice laicky podívat na myšlenku, která je za tímto solverem skryta.

které úlohy nám dělají problém?

Uveďme si nejprve pár příkladů úloh, které nejsme schopni vyřešit optimálně v rozumném čase. Mám tím na mysli to, že pokud bychom chtěli vypočítat skutečně nejlep39 řešení těchto problémů, tak i dnešním superpočítačům by tento úkon trval mnoho dní, né-li roků. Dejme tomu, že potřebujeme naplnit kontajnery do nákladní lodi. Máme tedy seznam objektů s rozměry (pro jednoduchost krabice), které potřebujeme převézt a chceme objednat co nejméně kontajnerů tak, aby se všechny krabice do nich vešly. Jak něco takového vyřešit, když převážených krabic je velice mnoho a odhad požadovaných kontajnerů se pohybuje v řádu stovek? Nechceme však plýtvat finance za zbytečně poloprázdné kontajnery a záleží nám na tom zda jich objednáme 200 nebo 190.

Nebo mějme seznam různých přísad a látek, ze kterých chceme namíchat látku určitých vlastností. Přísad je však tolik, že nemůžeme vyzkoušet všechny možnosti smíchání.

Dalším příkladem může být silniční doprava. Které kamiony mají vzít jakou zakázku, aby celkově firma spotřebovala nejméně paliva? Pokud je však řidičů mnoho a chceme zakázky plánovat měsíce dopředu, snadno se dostaneme do obrovských hodnot a propočítat veškeré kombinace řidičů, měst, kamionů a zakázek by trvalo počítači roky.

primitivní myšlenka

Jak je vidět tak nároky na optimální řešení těchto úloh necháme stranou. Jak tedy dospět alespoň k dostatečně přijatelnému řešení?

Všechny tyto příklady měly něco společného. Dostaneme-li k nim nějaká řešení, umíme říci, které je lepší. U kontajnerů bude lepší řešení takové, které jich využije méně. U přísad vyhraje například řešení s běžnějšími, méně vzácnými látkami. Dopravní firma naopak ocení co nejmenší spotřebu paliva. Představte si tedy nějaký vcelku jednoduchý program, který vám náhodně předloží několik možných a platných řešení. Vy je poté mezi sebou všechny porovnáte a vyberete to nejlepší. Už toto je základní idea primitivního genetického algoritmu. Pojďme se však podívat na to, jak dosáhnout lepších výsledků.

idea mutace

Nyní se pro jednoduchost budu držet pouze příkladu s kontajnery. Představme si, že máme počítačový program, který nám vypíše seznamy věcí, které se mají dát do daného kontajneru. Zkrátka nám tu množinu všech předmětů, rozdělí na menší množiny podle toho, jak se do jednotlivých kontajnerů vejdou. Program by však poté mohl zkusit náhodně vybrat jeden či více předmětů a přemístit je do jiných kontajnerů, do kterých se ještě vejdou. Se štěstím bude naše výsledné řešení vyžadovat třeba o jeden kontajner méně. Pokud ano, zkusíme znovu náhodně přerozdělit nějaké předměty. Pokud ne, pak se vrátíme k řešení původnímu a zkusíme přerozdělit věci na něm. Tomuto principu se v genetickém algoritmu říká mutace. Neboli dochází s určitou malou pravděpodobností k mutování částí řešení, a tato změna nás může přivést k řešení lepšímu. Je třeba si uvědomit, že se stále pohybujeme v obrovských hodnotách, proto počet mutací nutných alespoň k drobnému vylepšení řešení může být v řádu tisíců.

idea křížení

Co nyní zkusit vygenerovat dvě řešení a poté vzít část jednoho a vyměnit ji s částí druhého. U příkladu výše by to bylo tak, že vezmeme seznamy věcí několika kontajnerů a vyměníme je s několika kontajnery druhého řešení. U tohoto příkladu musíme tedy ještě ošetřit, zda v obou řešeních počítáme se všemi předměty k převozu a naopak nepočítáme žádný předmět dvakrát. I po této změně však můžeme nalézt řešení, které bude validní a bude vyžadovat méně kontajnerů. Tomuto principu se říká křížení. Neboli vyměníme určitý úsek jednoho řešení s řešením jiným a naopak a vzniknou nám tak dvě nová řešení..

Generační cyklus

Jak jste již asi pochopily, tak k dosáhnutí uspokojivého výsledku bychom musely tyto operace provézt mnohokrát, a třeba i na více potenciálních řešeních najednou. A přesně to genetický algoritmus děla.

Vygenerujme si tedy na začátku náhodně několik desítek různých řešení. Tuto skupinu budeme nazývat populace a každé její řešení nazveme jedincem v dané populaci. Proveďme nyní na všech jedincích s určitou nízkou pravděpodobností nějaké mutace. Poté vyberme pár dvojic jedinců a proveďme u nich křížení. Následně seřaďme jedince podle toho jak jsou úspěšní (V našem případě, kolik využívají kontajnerů). Nyní vyberme polovinu těch nejlepších jedinců a vložme jejich kopie do nové populace. Tuto novou populaci doplňme nově náhodně vygenerovanými jedinci, aby měla stejnou velikost jako populace původní. Následně můžeme nahradit původní populaci touto nově vytvořenou a opakovat na ní stále tentýž princip. Přechod mezi starou a novou populací se nazývá přechod mezi dvěma generacemi. Genetickým algoritmem běžícím N generací se tedy rozumí N-krát probíhající cyklus:

Proběhne-li tento cyklus mnohokrát (řádově tisíce), máme šanci k nalezení lepšího než náhodně vygenerovaného řešení. To se však ve většině případů zdaleka neblíží řešení uspokojivému natož optimálnímu. Existují však techniky, které základní mechanismus GA obohacují a s důmyslným nastavením mohou nalézt řešení blížící se hledanému optimu. Pro zájemce tedy doporučuji prostudovat techniky iterativního ořezávání listů, hill climbing, metodu ostrovů a jíné. Více se můžete dočíst v mé bakalářské práci.