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

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.

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