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       10 613×

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 NVIDIA shrnuje přehled novinek na E3 2018

NVIDIA shrnuje přehled novinek na E3 2018

Společnost NVIDIA si u příležitosti E3 2018 připravila řadu novinek, které uvádí v kompletním přehledu, Například nové hry s podporou NVIDIA Highlights, která je součástí aplikace GeForce Experience, i nadále nabírá na obrátkách. Kromě výše zmíněné Shadow of the Tomb Raider získaly podporu také hry Dirty Bomb a Switchblade.

Reklama
Reklama
Obrázek ke článku SODAT vidí budoucnost datové bezpečnosti ve strojovém učení

SODAT vidí budoucnost datové bezpečnosti ve strojovém učení

Firmy chrání svá citlivá data často nedostatečně. Podle průzkumu společnosti SODAT se v minulém roce setkalo až 80 % z nich s bezpečnostním incidentem ztráty nebo úniku dat. Jedna z pilotních firem, která testovala novou verzi řešení SODAT Protection & Analytics 2.0pro bezpečností analýzu a monitoring dat díky novince zjistila, kdo z disku smazal důležité výkresy a mohla na incident včas reagovat.

Obrázek ke článku Kontrolujete pracovní emaily i na dovolené? 7 tipů odborníka, jak nepřijít o data

Kontrolujete pracovní emaily i na dovolené? 7 tipů odborníka, jak nepřijít o data

Letní měsíce jsou pro většinu zaměstnanců spojené s každoroční dovolenou. Z údajů Českého statistického úřadu vyplývá, že v roce 2017 podnikli Češi přes 13 milionů delších cest (tzn. s více než čtyřmi noclehy). Přitom právě na období července, srpna a září připadá více než 7,5 milionů z nich. Nicméně tradiční představu o dovolené jako o čase, kdy má práci na starost někdo jiný, Češi boří. 

Obrázek ke článku 10 SEO mýtů, které už nemusíte v roce 2018 řešit

10 SEO mýtů, které už nemusíte v roce 2018 řešit

„Kolik má být na stránce klíčových slov?“, „Nemáš vyplněný meta tag keywords, to nebude fungovat.“, „Katalogy jsou mrtvý“. Také jste už slyšeli některé z těchto otázek? Pojďme si na ně konečně jednou provždy odpovědět.

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