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

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

 
Hledat
Moderní platforma pro vytvoření vašeho nového webu – Wix.com.
Nyní už můžete mít web zdarma.
Vybavení pro Laser Game
Spuštěn Filmový magazín
Laser Game Brno

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

Google       Google       8. 10. 2006       10 437×

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. 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.

×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

Obrázek ke článku Konference: Kvalitní informační systém roste spolu se svými uživateli

Konference: Kvalitní informační systém roste spolu se svými uživateli

Informační systémy, které rostou spolu s požadavky svých uživatelů, efektivní uchování důležitých dokumentů nebo moderní uživatelská rozhraní, která maximálně zjednodušují práci s informacemi - to je jen několik z řady aktuálních trendů v oblasti podnikových informačních systémů, kterým se bude věnovat konference Firemní informační systémy, která se koná 31.5.2018 v pražském Kongresovém centru Vavruška na Karlově náměstí.

Reklama
Reklama
Obrázek ke článku Bezrealitky.cz na novém webu rychleji propojí vážné zájemce s majiteli nemovitostí

Bezrealitky.cz na novém webu rychleji propojí vážné zájemce s majiteli nemovitostí

Největší platforma pro přímý prodej a pronájem domů a bytů Bezrealitky.cz představila novou podobu svého portálu. Redesign zásadně zjednodušuje všechny transakce, mění způsob, jakým zájemci o bydlení komunikují s majiteli nemovitostí, přináší nejpřesnější filtrování nabídek na trhu, ale také umožňuje prověřovat důvěryhodnost zájemců. 

Obrázek ke článku Samba.ai: Personalizační nástroje hlásí připravenost na GDPR

Samba.ai: Personalizační nástroje hlásí připravenost na GDPR

Do ostrého nasazení nařízení GDPR, které upravuje nakládání s osobními údaji, zbývá pár dní, a vzbuzuje vrásky u řady provozovatelů služeb, které pracují s profilací návštěvníků na stránkách a personalizací obsahu. Český personalizační nástroj Samba.ai(dříve Yottly) zajišťující personalizaci webu a prediktivní automatizaci email marketingu je však slovy svého CEO Davida Vyskočila na GDPR plně připraveno. 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032018 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý