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

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

Obrázek ke článku Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Delphi 10.1.2 (Berlin Update 2) – na co se můžeme těšit

Touto roční dobou, kdy je zem pokrytá barevným listím a prsty křehnou v mrazivých ránech, se obvykle těšíme na zbrusu novou verzi RAD Studia. Letos si však ale budeme muset počkat na Godzillu a Linux až do jara. Vezměme tedy za vděk alespoň updatem 2 a jelikož dle vyjádření pánů z Embarcadero se budou nové věci objevovat průběžně, pojďme se na to tedy podívat.

Reklama
Reklama
Obrázek ke článku Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Konference: Moderní datová centra pro byznys dneška se koná už 24. 11.

Stále rostoucí zájem o cloudové služby i maximální důraz na pružnost, spolehlivost a bezpečnost IT vedou k výrazným inovacím v datových centrech. V infrastruktuře datových center hraje stále významnější roli software a stále častěji se lze setkat s hybridními přístupy k jejich budování i provozu.

Obrázek ke článku Konference: Mobilní technologie mají velký potenciál pro byznys

Konference: Mobilní technologie mají velký potenciál pro byznys

Firmy by se podle analytiků společnosti Gartner měly  rychle přizpůsobit skutečnosti, že mobilní technologie už zdaleka nejsou horkou novinkou, ale standardní součástí byznysu. I přesto - nebo možná právě proto - tu nabízejí velký potenciál. Kde tedy jsou ty největší příležitosti? I tomu se bude věnovat již čtvrtý ročník úspěšné konference Mobilní řešení pro business.

Obrázek ke článku Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres přiveze v září do Prahy špičky světové kryptoanarchie

Hackerský kongres HCPP16 pořádá od 30. září do 2. října nezisková organizace Paralelní Polis již potřetí, a to ve stejnojmenném bitcoinovém prostoru v pražských Holešovicích. Letos přiveze na třídenní konferenci přes 40 většinou zahraničních speakerů – lídrů z oblastí technologií, decentralizované ekonomiky, politických umění a aktivismu. Náměty jejich přednášek budou také hacking, kryptoměny, věda, svoboda nebo kryptoanarchie.

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 © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý