Kde se vzaly?
Původ genetických algoritmů musíme hledat již v minulém století, kdy přední vědci a přírodovědci postupně zformulovali zákony klasické genetiky a objevili základní principy reprodukce. Zjistilo se, že hnacím faktorem evoluce je přirozený výběr, který posiluje nejlépe adaptované jedince a naopak vyřazuje nejméně adaptované jedince. Dále bylo zjištěno, že rozmanitost v genetické výbavě nových potomků zajišťují procesy křížení a mutace. Křížení spočívá v tom, že ze dvou rodičovských chromozomů vzniká vzájemnou kombinací chromozom nový, nesoucí jejich genetickou výbavu. Mutace způsobuje nenadálé změny v genetické výbavě, které jsou zapříčiněny silným vnějším nebo vnitřním vlivem.

Nejen Mendel
V tomto století další osvícení vědci a badatelé dokázali přenést tyto principy do zcela odlišných oblastí, než je botanika. Byl vytvořen umělý model vývoje organismu a začala éra tzv. genetických nebo evolučních algoritmů. Vědci si byli vědomi síly a robustnosti této metody a tušili její možnosti v řešení různých problémů. Postupem času se genetický algoritmus zdokonaloval a rozvíjel. V dnešní době můžeme říci, že snad neexistuje oblast, kde by nebyl jako výpočetní metoda použit. Byl aplikován na řešení velmi složitých problémů, přičemž byla získána často nečekaná a pozoruhodná řešení, klasickými metodami nedostupná.

V čem je podstata
Základním principem genetického algoritmu je postupné přizpůsobování řešení okrajovým podmínkám. Jedná se o analogii s přírodou, kde tytéž algoritmy zajišťují adaptaci na okolní prostředí. Nositelem genetické výbavy každého živého organismu je chromozom, který se skládá z mnoha molekul DNA. 

Základním stavebním prvkem genetického algoritmu je rovněž chromozom. Zde se však jedná o souhrn základních znaků umělého systému, který představuje řešený problém. Systémem rozumíme množinu základních veličin (např. rozměry, finanční údaje, různá množství, doby trvání atd.), ze kterých je možné odvodit veličiny další. Požadavky kladené na tyto základní nebo odvozené veličiny (např. požadavky rovnosti, nerovnosti, dosažení konkrétní hodnoty nebo intervalu hodnot, …) tvoří okolní prostředí, kterému se algoritmus snaží přizpůsobit. 

Chromozóm, jedinec, generace
K pochopení problematiky genetických algoritmů je nutné vysvětlit několik základních pojmů. Co je chromozom, víme. Dalším pojmem je jedinec, který představuje jeden konkrétní stav systému vycházející z vygenerovaných hodnot základních veličin. Takže je-li chromozom tvořen např. šířkou, délkou a hloubkou nějakého objektu, pak jedinec je konkrétním stavem - tedy např. 10, 12 a 2. 

Množina různých jedinců tvoří populaci nebo generaci. Velikost populace může být různá a závisí na druhu řešeného problému.

Proces genetického algoritmu probíhá v několika krocích. Na počátku vždy stojí vygenerování prvotní generace jedinců, která je většinou malého rozsahu a inicializuje celý systém. Pak následuje vytvoření nové generace jedinců, kde se aplikují výše zmíněné metody křížení a mutace. Abychom zjistili, kteří noví jedinci jsou nejlépe přizpůsobení okolním podmínkám a požadavkům, je nutné provést vyhodnocení. K tomu slouží sestavení tzv. fitness funkce, která oceňuje každého nového jedince a vyjadřuje míru splnění požadavků. Pak dojde k seřazení od nejlepšího jedince k nejhoršímu a provede se úzký výběr rodičovské generace, která se stane vzorem pro vytváření další generace. Tento cyklus se neustále opakuje, řešení systému se přibližuje až nakonec dojde k jeho nalezení.
Proč používat genetické algoritmy

Genetické algoritmy náleží do kategorie alternativních metod, kam patří např. metoda Monte Carlo, fuzzy logika, neuronové sítě, metoda simulovaného žíhání apod. Důvodem vzniku a rozšíření těchto metod byla stále vzrůstající složitost řešených úloh. Do praktických problémů vnikla nelinearita, náhodnost, velké množství vzájemných vztahů a začaly ubývat metody, které by dokázaly tyto problémy vyřešit. Klasické matematické metody, jako jsou např. lineární programování, statistika nebo regresní a korelační analýza, jsou omezené různými požadavky, jako linearita, počet vzájemných vztahů, rozsah hodnot apod. Navíc existují problémy, kde vůbec není možné tyto metody použít, protože je nelze popsat tradičními způsoby. Existence zpětných vazeb, skokové závislosti, náhodné rozhodování, to vše jsou aspekty, které naplňují praktické problémy stále více, a které způsobují selhání klasických metod.

Naproti tomu genetické algoritmy představují univerzální výpočetní systém, který je velmi robustní a nezávislý na množství parametrů, vztahů a druhu závislostí. Rozsah řešitelnosti problémů pomocí genetických algoritmů je oproti klasickým metodám mnohem větší. Důvodem takové výkonnosti je fakt, že řešení systému se postupně vyvíjí a algoritmus díky zpětné vazbě získané z velikosti hodnoty fitness funkce jednotlivých jedinců přesně "ví, co dělá" a dokáže se přizpůsobit. Genetické algoritmy se používají k nalézání průchodných řešení různě složitých systémů, nebo k hledání suboptimálních a optimálních řešení. Stávají se tak mocným nástrojem v oblasti, která je velmi populární a zároveň problematická.

Kde klasické metody selhávají
Genetické algoritmy lze využít v řízení výroby, řešení problémů v průmyslu, dopravě a logistice, finančnictví, matematice a mnoha dalších oborech. Zaměřme se na úlohy, kde klasické metody zcela určitě selhávají. Jedná se např. o řízení výrobního procesu. Genetický algoritmus dokáže optimálně navrhnout výrobní linku a zahrnout přitom do řešení spoustu okolních parametrů, jakými jsou např. možnost provedení dané operace na více strojích, libovolné následnosti v technologickém postupu, výpadek některého z pracovišť nebo jednotlivé operace, zahrnutí časových prodlev a nákladů spojených s přechodem od jednoho pracoviště k druhému, definice maximální délky fronty každého pracoviště atd. Podobnou úlohou je sestavení a optimalizace logistických řetězců, opět se zahrnutím mnoha doprovodných parametrů nebo optimalizace obslužných systémů spočívající v nalezení optimálního počtu jednotlivých kanálů systému, nebo vytvoření různých variant reagujících na různou úroveň přísunu požadavků.

Moderní doba s sebou přináší stále nové a nové problémy k řešení. Protože se jedná o problémy z praxe, jsou velmi složité. K jejich řešení je nutné využít co nejlepších metod. A jednou z nich jsou určitě i genetické algoritmy. Zakladatelé klasické genetiky v minulém století sotva tušili, kam až se jejich poznatky a objevy rozšíří. Nezbývá, než jim za jejich objevy poděkovat.

Vzhledem k velkému zájmu o tuto problematiku mezi firmami se budeme podrobnému popisu řízení výroby s využitím genetických algoritmů věnovat i v dalším čísle.

Pozn.: autor pracuje jako analytik firmy Janouch a.s.