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

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

 

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

Google       Google       18. 7. 2006       12 905×

Při vytváření informačních systémů se někdy setkáváme s problémy, pro které neexistuje algoritmus řešení. Častým případem jsou optimalizační úlohy, kdy je třeba vybrat nejvhodnější z velkého množství možností, přitom neexistuje návod, jak takový výběr provést. Každou již nalezenou alternativu však musíme umět ohodnotit. Přehled několika takových úloh s nástinem řešení jsem již podal v článku Genetické algoritmy a jejich aplikace v praxi, v tomto seriálu bych se chtěl touto problematikou zabývat podrobněji.

Reklama
Reklama

Evoluce v přírodě a její počítačový model

Vzorem pro genetické algoritmy jako jednoho z nejvýznamnějších reprezentantů evolučních optimalizačních systémů byly principy vývoje v přírodě. Autorem principu přírodního výběru (selekce) je anglický vědec Charles Robert Darwin. Jeho teorie je všeobecně známá, v následujícím přehledu bych chtěl na několika příkladech zdůraznit základní principy, které mají význam pro projektování genetických systémů na počítači.

Příklad 1 – ochranné zbarvení

Některá zvířata nebo ptáci mají takové zbarvení, že je v přírodě přehlédneme. U toho jedince, který méně splýval s okolím, byla větší pravděpodobnost, že jej dravec spatří a uloví. Naopak ti jedinci, kteří lépe splývali s okolím, měli větší pravděpodobnost přežití a měli potomstvo. Nakonec se vyvinula taková zvířata nebo ptáci, kteří splývají s okolím dokonale.

Příklad 2 – kritériem přežití je rychlost

Některá menší zvířata se před dravci zachrání útěkem. To zvíře, které dravci uteče, přežije a má potomstvo, méně vybavení jedinci jsou uloveni. Do jisté míry záleží také na náhodě, mohou se však objevit jedinci, kteří utečou dravci vždy.

Příklad 3 – kritérium stanoví člověk

Lidé po celé generace vybírali do dalšího chovu ta hospodářská zvířata, která měla požadované vlastnosti – krávy co nejvíce mléka, ovce co nejlepší vlnu a slepice co největší vejce. Na rozdíl od předchozích případů zde zasáhl člověk, je jasné, že hospodářská zvířata nemají vlastnosti, které by jim umožnily ve volné přírodě přežít.

Možnosti využití principu evoluce v informatice

Zamyslíme-li se nad uvedenými příklady, vidíme některé základní principy, kterými se při modelování těchto procesů na počítači musíme řídit:

  1. Každý jedinec je částí určitého druhu, smečky – obecně populace, má různý počet potomků, jedinci se navzájem liší
  2. Každý jedinec je definován jistým souborem vlastností – genů sdružených v řetězcích – chromozomech
  3. V těchto vlastnostech dochází čas od času k náhodným změnám – mutaci
  4. Jedinci mají potomky, kteří náhodně převzali část vlastností od jednoho rodiče a část od druhého – křížení
  5. Ti jedinci, kteří mají vhodnější vlastnosti, mají větší pravděpodobnost přežití a předání těchto vlastností potomkům
  6. Někteří jedinci jsou tak dokonale vybavení, že jejich přežití a potomstvo není otázkou náhody
  7. Kritérium hodnocení stanoví zpravidla příroda, v některých případech také člověk.

Konstrukce genetických systémů

Při návrhu genetického systému vycházíme z výše uvedených pravidel.

  1. Definujeme vlastnosti populace jako skupiny jedinců, počet členů, potomků, četnost změn a další skutečnosti
  2. Přesně popíšeme vlastnosti objektů, které nás zajímají. Každá vlastnost je definována ve struktuře, kterou nazýváme gen, popis všech vlastností jednoho objektu bude tvořit řetězec genů – chromozom.
  3. Určíme způsob změny každé vlastnosti – mutaci genů
  4. Popíšeme, jak se z vlastností rodičovských jedinců budou odvozovat vlastnosti jejich potomků – křížení chromozomů
  5. Popíšeme způsob hodnocení vhodnosti jedince pro kopírování do další generace – tj. definujeme tzv. fitness funkci
  6. Určíme, jaký počet nejlepších jedinců přechází do další populace vždy. Tento princip se nazývá elitářský algoritmus.
  7. Kritérium hodnocení stanoví vždy autor inteligentního systému ve spolupráci s uživatelem, musí přitom respektovat priority uživatele

V průběhu analýzy genetického systému je nutno věnovat pozornost všem těmto bodům jak ze strany dodavatele, tak i uživatele, rád bych se zastavil u hodnotící fitness funkce. Jde o to, že genetický systém dělá spoustu úkonů automaticky, navrhuje různé alternativy řešení a evolucí a vybírá tu nejlepší, avšak to, která alternativa je nejlepší, stanoví uživatel. To znamená, že nemusí existovat algoritmus, jak nalézt nejlepší alternativu (ani nesmí, jinak není důvod vytvářet genetický systém), ale když už je nějaká alternativa navržena, musí existovat předpis pro číselné hodnocení, zda je „lepší“, nebo „horší“.

Nalezení takové funkce zpravidla není problém, spočítá se například ekonomický zisk nebo ztráta, musí se však stanovit po dohodě s uživatelem, protože jen on může stanovit, jaké kritérium je pro něj rozhodující.

Ještě poznámka k elitářskému algoritmu. Tento systém je v praktických úlohách velmi užitečný, v nepříznivém případě by se mohlo stát, že v průběhu vývoje dojde ke krátkodobému zhoršení výsledku. Dokonce je lepší jej ještě zpřísnit, nalezené řešení se ponechává tak dlouho, dokud se nenalezne lepší bez ohledu na to, kolik je v populaci stejně dobrých řešení. Neustálé střídání dvou a více stejně dobrých řešení vnáší do informačního systému zbytečný zmatek.

Jednoduchý příklad genetického algoritmu

Uveďme si velmi jednoduchý příklad, který uvedené principy vysvětlí. Budeme modelovat výše uvedený princip ochranného zbarvení jedinců v přírodě. Tento příklad nemá samozřejmě praktický význam, obecné principy, které použijeme, nám však pomohou pochopit způsob konstrukce skutečných optimalizačních systémů.

  1. Populace se bude (např.) skládat z 10 jedinců, v každé generaci se provede 5 mutací a vytvoří se 10 potomků
  2. Vlastnosti jedince bude popisovat řetězec 5 znaků, „R“ = red (červená), „G“ = green (zelená) a „B“ = blue (modrá), charakterizujících barvu jednotlivých částí zvířecího těla
  3. Mutace znamená: náhodně zvolíme číslo i z intervalu <1,10> a číslo j z intervalu <1,5>, vybereme i-tého jedince z populace a barvu na j-tém místě změníme na jinou
  4. Vytvoření potomků znamená: zvolíme náhodně dva rodiče a číslo k z intervalu <2,4>. Do prvního potomka zkopírujeme barvy 1 až k z prvního rodiče a k + 1 až 5 z druhého rodiče. Do druhého potomka barvy 1 až k z druhého rodiče a k + 1 až 5 z prvního rodiče.
  5. Pro stanovení fitness funkce musíme znát barvu prostředí. Pak stačí u každého jedince spočítat barvy, které jsou stejné jako prostředí, a vydělit celkovým počtem barev, tj. 5. Dostaneme hodnotu z intervalu <0,1>, přičemž 1 znamená dokonalé splynutí s prostředím.

Jestliže realizujeme výše uvedený algoritmus, po nějaké době se objeví jedinec, který dokonale splyne s prostředím.

V příští kapitole si probereme podrobněji realizaci tohoto příkladu na počítači.

Literatura

  • J. Šíma, R. Neruda: Teoretické otázky neuronových sítí, Praha, MATFYZPRESS, 1996
  • J. Teda: Nové možnosti informačních systémů s využitím inteligentních modulů, Sborník přednášek z mezinárodní konference Svět informačních systémů 2006, Zlín 2006, str. 202–208
  • I. Vondrák: Umělá inteligence a neuronové sítě, Ostrava, VŠB TU, 1994

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

1 názor  —  1 nový  
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ý