Evoluční optimalizační systémy II.

V minulé kapitole jsme odvodili základní pravidla, kterými se řídíme při navrhování evolučních systémů v souladu se zákony vývoje, které platí v přírodě. V této kapitole si předvedeme, jak takový jednoduchý genetický algoritmus na počítači skutečně pracuje. Seznámíme se také s některými riziky, se kterými se při navrhování těchto systémů můžeme setkat.

Jednoduchý genetický systém

Genetický algoritmus předvedeme na jednoduchém příkladě vývoje ochranného zbarvení, jehož slovní podobu jsme popsali v minulé kapitole. Výukový program najdete na www.optiintelligent.cz v sekci Pro školy pod názvem Barvy.zip. Rozbalte si jej do vhodného adresáře na svém počítači. Odstartujte program barvy.exe a zvolte funkci Program Start.

Zopakujme si, v čem spočíval závěrečný příklad minulé lekce. Představme si hejno pěti papoušků – populaci, jejichž barva je definována řetězcem pěti znaků – chromozomem. Každý znak znamená barvu jedné části těla – první například hlavy, druhý levého křídla, třetí levé části trupu, čtvrtý pravého křídla a pátý pravé části trupu. Pro jednoduchost jsme zvolili jen základní barvy – R = červená, G = zelená, B = modrá. Přežijí ti jedinci, kteří co nedokonaleji splynou s okolím. Barva okolí je definována tlačítky R, G a B vlevo uprostřed obrazovky.

Klikněte myší na tlačítko Krok. Náhodně vytvořené chromozomy všech pěti jedinců se objeví v okénku vlevo nahoře. Je to v našem případě původní populace. Pro názornost jsou jedinci vlevo očíslování, aby bylo možno lépe sledovat průběh evoluce.

Průběh evolučního procesu.

1. krok – kopírování původní populace

Klikněte znovu na tlačítko Krok. Všichni jedinci se zkopírují do okénka vpravo a vstupují do soutěže o výběr do další generace.

2. krok – mutace

Klikněte znovu na tlačítko Krok. V dalším okénku se objeví průběh mutace. Vlevo před šipkou je vždy původní chromozom, číslo vlevo identifikuje vzor. Mutovaný gen je mezi znaky | a |. Za šipkou je nový chromozom, opět mutovaný gen mezi znaky | a |. Všimněte si, že někdy mutace zlepší kvalitu jedince – více znaků odpovídajících prostředí, zpočátku znaků R. Někdy je ovšem mutace nepříznivá, jedinec je více nápadný. To však vůbec nevadí, méně příznivý jedinec se do další generace nedostane, jak uvidíme za chvíli.

3. krok – křížení

Klikněte znovu na tlačítko Krok. Nyní se opět objeví průběh další genetické operace křížení. Kříží se vždy náhodně zvolené dvojice chromozomů vlevo od složeného znaku X, opět číslo vlevo odkazuje na chromozom původní populace. Vpravo jsou potomci, každý má část chromozomu od jednoho rodiče a část od druhého, oba chromozomy každé dvojice opačně. Bod řezu je opět označen |.

4. krok – selekce

Klikněte znovu na tlačítko Krok. Do nové populace se zkopíruje část chromozomů ze všech polí vpravo, tj. ze staré generace, výsledků mutace i křížení. Všimněte si, že s větší pravděpodobnosti se do nové populace kopírují ty chromozomy, které odpovídají barvě prostředí, tj. které původně mají více znaků R.

Opakování evolučního cyklu

Po dalším stisknutí tlačítka Krok se přesunou jedinci nové generace do staré generace, ostatní okénka se vymažou a celý proces se může opakovat. Vyzkoušejte si opakovanou evoluci – stiskněte klávesu Enter a držte ji, až se objeví jedinci, kteří dokonale splývají s prostředím – v řádku je samé R.

Evoluční cyklus v jiném prostředí

Změňte prostředí na G nebo B, stiskněte Krok a držte klávesu Enter. Jedinci opět splynou po nějaké době s prostředím.

Výhody a rizika evolučních systémů

Genetické evoluční systémy mají řadu nesporných výhod:

• Minimální požadavky na popis algoritmů ze strany uživatele. Uživatel musí definovat:
  • Obecný popis vlastností objektů daného prostředí – v našem případě jsme museli předem vědět, že budeme sledovat u každého jedince 5 barev, barvy budou R, G a B.
  • Předpis hodnocení pro již nalezenou alternativu
    • V našem případě je to součet takových barev, které odpovídají prostředí, např. pro prostředí R a jedince RRGRB je kritérium 3.
    • V praktických úlohách je stanovení hodnotící funkce pro uživatele také zpravidla jednoduché, odvíjí se buď od celkových nákladů (minimalizujeme je), nebo celkového zisku (snažíme se dosáhnout maximální).
  • Řešení, jež nalezne systém sám
• Minimální zásah v případě změny, pokud ovšem nezasahuje do podstaty algoritmu. Kritérium se zpravidla odvíjí od určitých parametrů, při změně těchto parametrů si systém sám nalezne vhodné řešení. Srovnejte, jak se náš program dokázal snadno vyrovnat se změnou barvy prostředí.

Existují však závažná rizika, která není dobré podceňovat:

Rizika pro projektanty

Největším rizikem těchto algoritmů je, že jsou obecně dost pomalé. Na rozdíl od Darwinovy teorie požaduje uživatel oprávněně přiměřenou odezvu, v případě technologických procesů i v reálném čase. Srovnejte si to s naším, velmi jednoduchým programem vývoje jedinců s pouhými pěti geny, jak dlouho někdy trvá nalezení toho nejlepšího. Přitom v praxi optimalizujeme stovky položek v reálném čase, desetitisíce v řádu několika minut.

Výše uvedený problém se nemusí projevit již při ladění. Protože program ladíme často na menším vzorku dat, může se stát, že při ladění se zdá být vše v pořádku, až při zpracování reálných dat se ukáže odezva, kterou uživatel není ochoten přijmout.

Evoluční programy využívají až 100 % procesoru, je nutno počítat s tím, že ostatní programy se během jejich výpočtu mohou výrazně zpomalit, pokud jedou na tomtéž počítači.

Rizika pro vývojáře

Programy tohoto typu se velmi obtížně ladí. Používat debug je téměř nemožné, při protokolování se vytvářejí megabajtové soubory, není snadné se v nich orientovat.

Při stále se opakujících cyklech se musí důsledně uvolňovat každý bajt paměti. Stačí zapomenout uvolnit malý úsek paměti ve vnitřním cyklu, a požadavky na paměť tak narůstají, že po krátké době dojde k vyčerpání operační paměti a program je ukončen s chybou.

Závěr

V této kapitole jsme si předvedli jednoduchý evoluční proces na počítači a seznámili jsme se se základními výhodami i riziky evolučních systémů. Příští kapitoly budou pojednávat o skutečných evolučních systémech používaných v praxi.