Evoluční optimalizační systémy II.
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

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

Google       Google       8. 10. 2006       9 427×

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.

Reklama
Reklama

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. Zkopírujte si z downloadu na tomto serveru soubor tga.zip a rozbalte do vhodného adresáře na svém počítači. Odstartujte program ga.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.

×Odeslání článku na tvůj Kindle

Zadej svůj Kindle e-mail a my ti pošleme článek na tvůj Kindle.
Musíš mít povolený příjem obsahu do svého Kindle z naší e-mailové adresy kindle@programujte.com.

E-mailová adresa (např. novak@kindle.com):

TIP: Pokud chceš dostávat naše články každé ráno do svého Kindle, koukni do sekce Články do Kindle.

Hlasování bylo ukončeno    
0 hlasů
Google
(fotka) Jaroslav TedaAutor se zabývá vývojem inteligentních softwarových systémů ve firmě OPTI Intelligent s.r.o. Publikoval na seminářích včetně mezinárodních i zahraničních a v časopise Automatizace.
Web    

Nové články

Reklama
Reklama
Obrázek ke článku Nový IT hráč na českém trhu

Nový IT hráč na českém trhu

V roce 2015 otevřela v Praze na Pankráci v budově City Tower své kanceláře společnost EPAM Systems (NYSE:EPAM), jejíž centrála se nachází v USA. Společnost byla založená v roce 1993 a od té doby prošla velkým vývojem a stále roste.

Obrázek ke článku České Radiokomunikace opět hledají nejlepší nápady pro internet věcí

České Radiokomunikace opět hledají nejlepší nápady pro internet věcí

České Radiokomunikace (CRA) pořádají druhý ročník CRA IoT Hackathonů. Zájemci z řad vývojářů a fanoušků moderních technologií mohou změřit své síly a během jediného dne sestrojit co nejzajímavější funkční prototyp zařízení, které bude komunikovat prostřednictvím sítě LoRa. CRA IoT Hackathony se letos uskuteční ve dvou fázích, na jaře a na podzim, v různých městech České republiky. Jarní běh se odstartuje 31. března v Brně a 7. dubna v Praze.

Obrázek ke článku Cloud computing je využíván stále intenzivněji

Cloud computing je využíván stále intenzivněji

Využívání cloud computingu nabývá na intenzitě. Jen v letošním roce vzroste podle analytiků trh se službami veřejného cloudu o 18 %, přičemž o téměř 37 % vzrostou služby typu IaaS. Růst o více než pětinu pak čeká služby poskytování softwaru formou služby, tedy SaaS. Aktuálním trendům v oblasti využívání cloudu se bude věnovat konference Cloud computing v praxi, která se koná 23. března. 2017 v pražském Kongresovém centru Vavruška na Karlově náměstí 5.

loadingtransparent (function() { var po = document.createElement('script'); po.type = 'text/javascript'; po.async = true; po.src = 'https://apis.google.com/js/plusone.js'; var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(po, s); })();
Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032017 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý