Genetické algoritmy aneb matrice života v počítačích

Evoluční výpočetní techniky Možná jste již někdy slyšeli výraz genetické programovaní, ale co se vlastně za tí...


Evoluční výpočetní techniky
Možná jste již někdy slyšeli výraz genetické programovaní, ale co se vlastně za
tímto názvem skrývá jde opravdu o geny zapřažené vedle elektronů a nebo nás
zase počítačoví vědci mystifikují? Vlastně obojí je pravda, samozřejmě o žádnou
kyselinu, kterou byste museli nalévat do počítače nejde, ale přesto mají
genetické algoritmy s vývojem života velice mnoho společného.
Oblast genetických algoritmů (GA) je zařazována do evolučních výpočetních
technik, kde mimo genetické algoritmy tvoří velkou část neuronové sítě. Všechny
tyto techniky a jim podobné patří do oboru umělé inteligence.
Jak již název napovídá, genetické algoritmy jsou inspirovány myšlenkami
převzatými z biologie a souvisejících věd. Genetický algoritmus může být použit
k řešení problému tak, že použije vyjádření problému ve formě chromozomu a
snaží se "vypěstovat" optimální řešení za pomoci vyvíjející se populace.
Existují problémy, které se dají řešit pomocí genetických algoritmů velmi
dobře. Stejně tak je ovšem plno jiných problémů, které je vhodnější řešit
jinými způsoby. Genetický algoritmus může však dát řešení i v případech, kde
ostatní metody selhaly. Asi nejčastější oblastí aplikací GA je optimalizace a
strojové učení. GA byly použity pro řešení problémů z technických oborů,
chemie, ekonomie a dalších. Je namístě říci, že GA nejsou zamýšleny jako
pomůcka pro simulaci přírody, přestože byly použity pro modelování přírodních
pochodů (např. pro studie otázek z genetiky nebo pro modelování ekosystému).
Problémy pro genetický algoritmus
Co to tedy genetický algoritmus je? Předtím, než ho podrobněji popíši, musím se
zmínit o problémech, které mohou být pomocí GA řešeny. Problém můžeme
specifikovat takto: vyber z nějakých přípustných řešení to nejlepší. Takto to
zní velmi jednoduše, ovšem pokud si uvědomíme, že u praktických problémů může
být počet přípustných řešení velmi velký, stává se situace složitější. Tento
počet bývá tak velký, že ani při použití toho nejrychlejšího počítače
nestihneme všechna přípustná řešení vygenerovat během našeho života, natož z
nich vybrat to nejlepší.
Ilustrujme si vše na příkladě známého problému obchodního cestujícího: obchodní
cestující má navštívit několik měst, ale nechce se mu strávit na cestách moc
času. Přesněji tedy musí navštívit všechna města, vrátit se domů (tj. do města,
ze kterého vyjel) a přitom urazit co nejkratší vzdálenost. Problém je zde tedy
nalezení takové posloupnosti měst, kde cesta mezi nimi bude nejkratší možná.
Pokud máme nějakou posloupnost, můžeme velmi rychle určit celkovou délku trasy
(umět určit rychle tzv. cenu řešení je velmi důležité, jak uvidíme níže).
Zaručeně nejlepší řešení umíme nalézt pouze tak, že probereme všechny možnosti
(posloupnosti) a z nich vybereme tu nejlepší. Ohodnocení řešení (vzdálenost)
umíme spočítat rychle. Problém je pouze v počtu řešení. Počet všech permutací
pro n měst je tedy n!=1*2*3*.*n. Pro 5 měst dostáváme 120 možností, což je
počítačem snadno zvládnutelné. Již pro 20 měst však dostáváme
2432902008176640000, což by počítač ohodnocující miliardu permutací za vteřinu
počítal přes 77 let. I jen malým zvýšením tohoto počtu se dostáváme za hranice
času předpokládané existence vesmíru.
Musíme se tedy spokojit s tím, že optimální řešení nenalezneme. Člověk však je
schopen nalézt dobré řešení v mnohem kratším čase. Není sice zaručené, že je to
řešení optimální, ale pro praktické účely může být dostačující. A proč by něco
takového nemohl umět i počítač? Ukážeme si, že nalézt poměrně rychle dobré (ale
suboptimální) řešení pomocí počítače je možné např. pomocí genetických
algoritmů.
Pro použití genetických algoritmů (ale i jiných optimalizačních metod) musíme v
první řadě být schopni vygenerovat nějaká přípustná řešení daného problému, tj.
řešení, která neporušují dané omezující podmínky. Na kvalitu těchto řešení
nejsou kladeny žádné požadavky. Dále musíme být schopni umět ke každému řešení
určit jeho ohodnocení, podle kterého můžeme všechna řešení uspořádat a tak
nalézt to nejlepší. Optimalizace pak probíhá tak, že nějak prohledáváme prostor
všech řešení s tím, že chceme najít to nejlepší. Jednotlivé optimalizační
metody se liší v podstatě pouze tím, jak chytře tento prostor řešení
prohledávají.
Trocha biologie
Genetický algoritmus používá pro reprezentaci řešení speciální tvar inspirovaný
biologickými chromozomy a pro generování nových řešení křížení a mutaci. Před
detailním popisem genetického algoritmu proto připomenu několik známých
poznatků ze souvisejících oblastí. V každé buňce živého organismu je sada
chromozomů skládajících se z DNA. Chromozomy tvoří model celého organismu a
skládají se z genů (bloků DNA). Velmi zjednodušeně se dá říci, že každý gen
reprezentuje nějakou vlastnost nebo rys, např. barvu očí. Možné stavy genu se
nazývají alely, tj. například barva očí může být modrá, hnědá atd. Každý gen má
svou pevnou pozici v chromozomu. Celý genetický materiál organismu se nazývá
genom. Konkrétní "nastavení" genů v genomu se nazývá genotyp. Genotyp určuje
tzv. fenotyp, což je vnější charakteristika organismu (fyzická i mentální barva
očí i inteligence).
Během reprodukce organismů dochází ke křížení (rekombinaci), při kterém se
vybírají geny převzaté od rodičů a jejich kombinací se vytvoří genotyp potomka.
Při nebo po reprodukci může dojít k mutaci náhodné změně nepatrné části
genotypu. Úspěšnost organismu (fitness jeho ohodnocení) se v biologii udává
jako pravděpodobnost, že organismus přežije do své reprodukce, nebo jako počet
jeho potomků. Evoluční teorie pak říká, že pouze některé organismy přežijí a
budou se reprodukovat, přičemž s větší pravděpodobností se to podaří těm lepším.
Genetický algoritmus
Vše výše uvedené používá genetický algoritmus. Přípustné řešení problému, který
GA řeší, je reprezentováno pomocí genomu, tj. nějakého souboru genů. Konkrétní
stav souboru genů je genotyp a reprezentuje tak fenotyp, což je konkrétní
řešení. Na základě fenotypu se tedy určí ohodnocení řešení a tak vlastně i
ohodnocení genotypu. Křížení a mutace však probíhá pouze na úrovni genotypu.
Genetický algoritmus si udržuje populaci řešení ve formě genotypů (chromozomů),
které kříží a mutuje s tím, že preferuje genotypy s vyšším ohodnocením, a tak
se snaží "vypěstovat" dobré řešení. Na začátku svého běhu vytvoří náhodnou
populaci (první generaci) a uvedeným způsobem vytváří nové potomky (další
generace) dokud není splněna nějaká ukončující podmínka (např. počet generací,
čas, nelepšící se nejlepší fitness apod.).
Genetický algoritmus lze tedy popsat zhruba takto:
1.(Start) Vygeneruj náhodnou populaci chromozomů
2.(Výpočet fitness) Ohodnoť každý chromozom x, tj. vyhodnoť fitness funkci f(x)
3.(Test konce) Jestliže je splněna ukončovací podmínka, ukonči běh algoritmu a
vrať nejlepší nalezené řešení
4.(Nová populace) Vytvoř novou populaci opakováním následujících kroků
A.(Selekce) Vyber náhodně 2 rodiče z populace dle jejich ohodnocení (čím vyšší
f(x), tím vyšší šance k výběru)
B.(Křížení) S danou pravděpodobností křížení proveď křížení pro vytvoření
potomka (potomků) pokud nedojde ke křížení, potomek je přesnou kopií rodiče
C.(Mutace) S danou pravděpodobností mutace proveď mutaci každého genu potomka
D.(Vložení) Vlož vytvořeného potomka (potomky) do nové populace
5.(Nahrazení) Nahraď starou populaci novou populací (nová generace)
6.(Opakování) Opakuj od bodu 2
Hlavní síla genetického algoritmu je v jeho paralelismu, tzn. že prohledává
více bodů prostoru řešení najednou (celou populací). Z toho vyplývá hlavně jeho
odolnost proti uváznutí v nějakém lokálním extrému (představme si, že hledáme
nejvyšší bod v horách pokud se budeme dívat pouze na jedno místo blízko kolem
sebe, stejně jako velká část jiných optimalizačních metod, a pouze podle toho
se budeme rozhodovat o další cestě, může se nám stát, že najdeme pouze lokální
vrchol (extrém) a z něj se již tímto postupem nehneme). Genetický algoritmus je
tak schopen pracovat bez zvláštních požadavků na prohledávaný prostor (např.
jeho spojitost) a umí na rozdíl od jiných metod nalézt dobré řešení i když je
prohledávaný prostor velmi "divoký". Další významnou odlišností od ostatních
optimalizačních metod je oddělení genotypu a tvorby nových řešení (postupu v
prostoru řešení) od fenotypu a ohodnocení vhodnosti řešení.
Příklad maximum funkce
Ukažme si práci genetického algoritmu a reprezentaci chromozomů na klasickém
příkladu hledání maxima funkce. Tento problém je sice v základní podobě spíše
akademický, ale slouží jako základ pro úpravu na praktické úlohy. Je však velmi
jednoduchý a ilustrativní. Mějme nějakou funkci, např. tu na obrázku 1. Máme
najít její maximum na intervalu 0..255. Znamená to tedy hledat v daném
intervalu takové x, kde bude f(x) nejvyšší funkce f(x) tedy vyjadřuje fitness
funkci. Fenotyp zde bude vyjadřovat konkrétní hodnotu x. Genotyp bude vyjádřen
chromozomem, který má 8 genů nabývajících hodnot 0 nebo 1 bude se jednat o
binární vyjádření čísla x. Příklad s uvedeným genotypem, fenotypem a hodnotou
fitness funkce je v tabulce 1.
Křížení bude probíhat výběrem genů z rodičů a jejich kopií do chromozomu
potomka. Výběr může probíhat tímto způsobem: Zvolíme náhodně nějaký bod mezi
geny v chromozomu. Všechny geny potomka až do tohoto bodu budou převzaty z
prvního rodiče, zbytek genů bude převzatý z druhého rodiče. Tento způsob,
ilustrovaný v tabulce 2, se nazývá jednobodové křížení. Jak již bylo uvedeno,
křížení probíhá při vytváření nové generace s určitou pravděpodobností, tzn. je
předem daná pravděpodobnost křížení, která určuje, kolik potomků bude vytvořeno
křížením (ostatní potomci budou přesnými kopiemi rodičů). Mutace probíhá tak,
že každý gen (bit) je s danou pravděpodobností mutace zinvertován viz tabulka 3.
Tato pravidla křížení a mutace a dané pravděpodobnosti křížení a mutace určují
do jisté míry úspěšnost genetického algoritmu. Závisí ovšem také na konkrétním
řešeném problému. Uvedené možnosti křížení a mutace nejsou samozřejmě jediné.
Navíc i reprezentace řešení, tedy tvar chromozomu, může vypadat různě, např.
lze použít řetězec reálných čísel nebo znaků. Velmi zajímavá reprezentace je
použita u tzv. genetického programování, kde chromozom představuje program a
genetickým algoritmem lze vypěstovat program řešící zadaný problém. Binární
reprezentace je však nejznámější, nejjednodušší a také nejprobádanější. Zatím
pouze pro tuto reprezentaci existuje rozšířenější matematická teorie, která se
snaží vysvětlit chování genetického algoritmu tzv. teorie schémat. Tato teorie
vysvětluje, že genetický algoritmus se snaží hledat řešení pomocí schémat,
jakýchsi stavebních bloků.
Jiné způsoby kódování
Ve výše uvedeném příkladu hledání extrému funkce bylo použito tzv. binární
kódování (binární reprezentace) řešení. Každý chromozom je v tomto případě
zakódován řetězcem binárních čísel. Jiným příkladem problému, kde lze použít
binární reprezentaci, je tzv. problém batohu: Máme batoh a věci, které chceme
do batohu naskládat. Problém je v tom, že se nám do batohu všechny věci
nevejdou. U každé věci máme danou její velikost a cenu. Za úkol máme vybrat
věci, které se nám vejdou do batohu a přitom mají dohromady nejvyšší možnou
cenu (ať už z finančního nebo jiného hlediska). Tento problém, který už určitě
nejednou řešil každý z nás, se dá řešit pomocí genetických algoritmů s binární
reprezentací řešení. Každý bit v reprezentaci odpovídá jedné věci a jeho
hodnota v daném řešení určuje, zda se příslušná věc do batohu dá, nebo nedá.
Binární reprezentace však samozřejmě není jediná možná. V podstatě si můžeme
zvolit jakékoliv zakódování řešení, pokud jsme schopni k němu nalézt příslušné
operace křížení a mutace. Mimo řetězec bitů lze použít například řetězec
reálných čísel, znaků nebo jakýchkoliv symbolů. Pro křížení můžeme použít
stejný postup jako u binární reprezentace (viz tab. 2). Mutace se může u
řetězce reálných čísel provést třeba náhodným přičtením nebo odečtením malého
čísla k vybraným hodnotám. Reprezentace řetězcem reálných čísel se dá použít
kdekoliv, kde hledáme více parametrů nějakého systému s pevně danou strukturou,
například pro trénování neuronových sítí, kde se jedná o nalezení parametrů
všech neuronů.
Další možností je permutační kódování. V tomto případě je řešení reprezentováno
permutací několika čísel, například (2,3,5,4,1) pro 5 čísel. Každé číslo pak
udává pořadí v sekvenci. Například při řešení výše uvedeného problému
obchodního cestujícího takovéto kódování přímo udává pořadí měst v řešení.
Operátor křížení může vypadat tak, že určíme bod křížení, posloupnost do tohoto
bodu zkopírujeme do chromozomu potomka a zbytek doplníme nepoužitými čísly v
pořadí stejném jako ve druhém rodičovi. Mutaci lze provést prohozením vybraných
čísel. Tuto reprezentaci lze použít pro jakýkoliv problém, kde má být výsledkem
posloupnost, což je mimo problém obchodního cestujícího v podstatě jakýkoliv
plánovací problém.
Velmi zajímavá reprezentace je použita u tzv. genetického programování, kde
chromozom představuje program a genetickým algoritmem lze vypěstovat program
řešící zadaný problém pouze na základě sady vstupů a požadovaných výstupů.
Například lze takto nalézt obecný předpis funkce na základě naměřených hodnot.
Výběr rodičů
Nyní již umíme vytvořit potomky, zbývá nám pouze vybírat rodiče. Jak již bylo
řečeno, rodiče se vybírají dle jejich ohodnocení, podle hodnoty fitness funkce.
Je totiž pravděpodobné, že lepší rodiče (s vyšším ohodnocením) budou mít lepší
potomky. Nelze však omezit výběr pouze na ty nejlepší. Pokud by se tak stalo,
mohla by celá populace uváznout v lokálním extrému bez možnosti dalšího
zlepšování. Jinými slovy zdegenerovala by. Hodnota fitness funkce tedy udává
pouze výši pravděpodobnosti vybrání chromozomu. Používaný způsob výběru se dá
přirovnat k ruletě. Představme si, že máme ruletové kolo rozdělené na různě
velké části, přičemž každá část odpovídá jednomu chromozomu v populaci.
Velikost každé části odpovídá velikosti ohodnocení tohoto chromozomu, jak je
zobrazeno na grafu č. 1. Roztočíme ruletu a vhodíme kuličku. Po zastavení
rulety vidíme, ve které části se kulička zastavila, a dle toho určíme, jaký
chromozom máme vybrat. Tímto způsobem preferujeme lepší chromozomy, ale
nevylučujeme ani ty nejhorší.
Uvedený způsob lze různě modifikovat, například lze vhodně upravit velikosti
částí ruletového kola. Jedna z možností je použít ohodnocení podle pořadí. Ta
pomůže zejména v případě, že je v populaci jeden nebo několik málo chromozomů,
které mají výrazně vyšší fitness než zbytek populace. V tomto případě by se do
dalších generací dostávaly pouze prozatímní nejlepší řešení a zbytek populace,
který zajišťuje rozmanitost, by neměl šanci přežít, čímž by mohlo dojít k
uváznutí v lokálním extrému. Řešním je použít pro výběr ruletovým kolem místo
hodnoty fitness funkce hodnotu odpovídající pořadí chromozomu dle fitness
funkce, tak jak je znázorněno na grafu č. 2. Oproti grafu č. 1 je vidět, že
všechny chromozomy mají šanci se dostat do další generace.
K jakémukoliv způsobu selekce by měla být doplněna strategie, která zajistí
přežití alespoň jednoho nejlepšího jedince do další generace, abychom
neztratili nejlepší dosud nalezené řešení (pokud toto řešení neuchováváme
jinak). Tato strategie se nazývá elitismus a spočívá jednoduše v tom, že se
nejlepší jedinec (nebo několik málo nejlepších jedinců) přesně zkopíruje do
nové populace.
Aplikace a shrnutí
Genetické algoritmy byly úspěšně použity v několika praktických aplikacích. Asi
nejpoužívanější jsou pro optimalizační úlohy (např. plánování, navrhování
obvodů VLSI), a pro strojové učení (klasifikace, predikce, učení neuronových
sítí). Byly použity pro "automatické programování" (např. vývoj buněčných
automatů, genetické programování). Mimo technické obory jsou genetické
algoritmy používány např. v chemii (určování struktury složitých molekul), v
ekonomii (predikce, hledání parametrů ekonomických modelů), v biologii a
medicíně (modelování imunitního systému, modelování ekologického systému) a v
sociologii (modelování sociálního systému).
Uvedený popis genetických algoritmů není ani zdaleka vyčerpávající. Více
informací lze nalézt např. na Internetu. Existuje i několik stránek s Java
applety, kde si lze pohrát s genetickým algoritmem řešícím nějakou jednoduchou
úlohu, například http:// cs.felk.cvut.cz/~xobitko/ga/index.html na této stránce
lze nalézt spolu s dalšími informacemi i odkazy na další stránky.
0 2202 / alsn
Genotyp1Ę1Ę0Ę1Ę0Ę0Ę1Ę0
Fenotyp210
Fitnessf(210)=10,79
Rodič 11Ę1Ę0ĘĘ1Ę0Ę0Ę1Ę0
Rodič 21Ę0Ę1ĘĘ1Ę0Ę1Ę1Ę1
Potomek 11Ę1Ę0ĘĘ1Ę0Ę1Ę1Ę1
Potomek 21Ę0Ę1ĘĘ1Ę0Ę0Ę1Ę0
Potomek vzniklý křížením1Ę1Ę0ĘĘ1Ę0Ę1Ę1Ę1
Zmutovaný potomek1Ę1Ę0ĘĘ0Ę0Ę1Ę1Ę1









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.