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.

 

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

Google       Google       8. 10. 2006       9 604×

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

Obrázek ke článku Blockchain & Bitcoin konference

Blockchain & Bitcoin konference

V pátek 19. 5. 2017 se v pražském konferenčním centru Andel’s konala Blockchain & Bitcoin konference. Řada odborníků a podnikatelů v oboru blockchainu a kryptoměn představila možnosti budoucího směřování tohoto oboru. Speakeři většinou rusky mluvící provenience prezentovali řešení svých firem založená na technologii blockchainu.

Reklama
Reklama
Obrázek ke článku Malware KONNI se úspěšně skrýval 3 roky. Odhalil ho bezpečnostní tým Cisco Talos

Malware KONNI se úspěšně skrýval 3 roky. Odhalil ho bezpečnostní tým Cisco Talos

Bezpečnostní tým Cisco Talos odhalil celkem 4 kampaně dosud neobjeveného malwaru, který dostal jméno KONNI. Ten se dokázal úspěšně maskovat od roku 2014. Zpočátku se malware zaměřoval pouze na krádeže citlivých dat. Za 3 roky se ale několikrát vyvinul, přičemž jeho současná verze umožňuje útočníkovi z infikovaného počítače nejenom krást data, ale i mapovat stisky na klávesnici, pořizovat screenshoty obrazovky či v zařízení spustit libovolný kód. Pro odvedení pozornosti oběti zasílali útočníci v příloze také obrázek, zprávu a výhružkách severokorejského režimu či kontakty na členy mezinárodních organizací.

Obrázek ke článku Pouze jedna z deseti lokálních firem ví o pokutách plynoucích z GDPR

Pouze jedna z deseti lokálních firem ví o pokutách plynoucích z GDPR

Trend Micro, celosvětový lídr v oblasti bezpečnostních řešení a VMware, přední světový dodavatel cloudové infrastruktury a řešení pro podnikovou mobilitu, oznámily výsledky výzkumu mezi českými a slovenskými manažery zodpovědnými za ochranu osobních údajů, který zjišťoval, jak jsou připraveni na nové nařízení o ochraně osobních údajů (GDPR). Většina firem v České republice a na Slovensku nad 100 zaměstnanců je již s novým nařízením GDPR obeznámena. Výzkum provedený ve spolupráci s agenturou Ipsos ukázal, že téměř 8 firem z 10 o nařízení ví, přičemž jeho znalost je o něco vyšší na Slovensku (89 %) než v České republice (69 %).

Obrázek ke článku Vyděračský software Locky se vrací, tváří se jako potvrzení platby, odhalil tým Cisco Talos

Vyděračský software Locky se vrací, tváří se jako potvrzení platby, odhalil tým Cisco Talos

Jeden z nejznámějších ransomwarů, Locky, se vrací. Po většinu roku 2016 patřil mezi nejrozšířenější vyděračské softwary. Ke svému šíření využíval emailové kampaně s infikovanými přílohami. Ransomware Locky byl rozesílán prostřednictvím botnetu (internetový robot zasílající spamy) Necurs. Jeho aktivita na konci roku 2016 téměř upadla a spolu s ní i šíření ransomwaru Locky. Před několika týdny se Necurs opět probudil a začal posílat spamy nabízející výhodný nákup akcií. Dne 21. dubna zaznamenal bezpečnostní tým Cisco Talos první velkou kampaň ransomwaru Locky prostřednictvím botnetu Necurs za posledních několik měsíců.

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ý