Představte si, že potřebujete optimalizovat nějakou cílovou funkci na nějaké množině přípustných řešení, přitom ale o této funkci moc nevíte. Nedokážete třeba říct ani jak se na dané množině chová, neumíte zjisitit jestli je vůbec spojitá, natož jestli má v daném bodě gradient a jaký. Předpokládejte také, že množina všech přípustných řešení je obecně velmi rozsáhlá a nepřipadají tedy v úvahu metody ve stylu backtrackingu apod. To je situace, ve které většina konvenčních optimalizačních technik, jako je např. metoda gradientu nebo lineární programování, prostě selhává. Zároveň je to situace, ve které byste měli pomalu začít uvažovat o nasazení genetických algoritmů.
To zázračné, co genetické aloritmy nabízí, je v podstatě aplikace principů, které příroda úspěšně používá již po tisíciletí. Hlavní myšlenka spočívá v tom, že na jednotlivé prvky množiny přípustných řešení pohlížíme jako na nějaké živé organismy v nějakém umělém životním prostředí. Přitom to, jak si tyto organismy v tomto postředí vedou, tj. jejich schopnost přežít a schopnost reprodukce, odpovídá tomu, o jak "dobrá" řešení se jedná. Vlastní hledání pak spočívá ve výběru nějaké počáteční populace těchto organismů a v následné simulaci jejího vývoje pod kontrolou evolučních mechanismů, zahrnující přirozený výběr, reprodukci, atd. Jak se tato populace od generace ke generaci vyvýjí, "špatná" řešení mají tendenci vymírat, a naopak "dobrá" řešení se mezi sebou hojně kříží a produkují řešení ještě lepší.
Genetické algoritmy jsou poměrně mladá disciplína a i v současnoti jsou předmětem intenzivního studia. Jejich zrod je datován do roku 1975 a je spojen zejména se jménem John Holland, který se v té době věnoval studiu buněčných automatů na Michiganské Univerzitě.
Nejprve je třeba vybrat nějakou počáteční populaci přípustných řešení. To se děje většinou náhodně, ale máme-li k dispozici nějaké heuristiky, můžeme je uplatnit právě v tomto kroku.
Dále, protože budeme chtít na tyto řešení uplatňovat genetické operátory, jako je kříženi a mutace, potřebujeme je mít k tomuto účelu reprezentované v nějaké vhodné podobě. Jako dostatečně obecné se jeví kódování ve formě řetězce či pole hodnot. V praxi se přitom velmi často používají binární řetězce. Kódování řetězci má také svou analogii v gentice, kdy v podstatě řetězce odpovídají chromozómům, jednotlivé pozice v řetězci jednotlivým genům a konkrétní hodnoty na těchto pozicích pak alelám.
Dobře. Máme tedy nějakou počáteční populaci organismů (kde každý organismus odpovídá jednomu chromozómu) a zápas o život může začít.
První na řadu přichází výběr jedinců, kteří se budou podílet na vzniku nové generace. Klasický přístup k tomuto problému obnáší ohodnocení jedinců aktuální populace na základě cílové funkce a následný výběr, kdy pravděpodobnost výběru daného jedince je úměrná jeho relativnímu ohodnocení. Názorně si to můžete představit na příkladu rulety, kdy se každému jedinci přiřadí výseč velikosti úměrné jeho relativnímu ohodnocení, a při každém pokusu je vybrán ten jedinec, v jehož výseči se kulička zastaví. Standartní genetický algoritmus pracuje s populací konstantní velikosti, takže se vybírá přesně tolik jedinců, kolik činí tato velikost.
Samotný výběr ještě ovšem samozřejmě nemůže dát vznik žádným novým strukturám. Od toho jsou tu genetcké operátory křížení a mutace.
Za účelem křížení je nejprve nutné vybrané jedince spárovat (je přirozené tedy za velikost populace volit sudé číslo). Na každý pár je pak aplikováno křížení s nějakou předem stanovenou pravděpodobností (obvykle velmi vysokou, např. 0,95). Křížení samo o sobě znamená výměnu genetického materiálu, tedy částí řetězců mezi oběma jedinci. V nejjednodušším případě se může jednat např. o to, že se náhodně určí pozice a od této pozice si oba řetězce vymění konce. Vždy je však třeba volit takový mechanismus, aby křížením vznikl opět řetězec, který reprezentuje nějaké přípustné řešení.
Nakonec je každý kandidát předmětem mutace. Mutace slouží k udržování genetické variace v populaci a tím brání, aby proces hledání skouznul jen do oblasti nějakého lokálního optima. U binárních řetězců se může jednat např. o prohození 0 za 1 na nějaké náhodně vybrané pozici. Protože však významně narušuje genetickou informaci, mělo by být její uplatňování omezeno nějakou poměrně malou pravděpodobností (ve většině aplikací se pro představu tato pravděpodobnost pohybuje mezi 0,001 a 0,1). I zde, podobně jako u křížení, je třeba dbát na to, aby mutací narušený řetězec opět reprezentoval nějaké přípustné řešení.
Takto jsme tedy získali novou generaci řešení a proces opakujeme tak dlouho, dokud není splněna nějaká ukončovací podmínka, která může být dána např. ve formě maximálního počtu generací nebo ve formě nějakého přijatelného limitu.
Zapsáno formou pseudo-kódu by standartní genetický algoritmus vypadal následovně:
|
t := 0 Initialize G(0) Evaluate G(0) do while not Done t := t + 1 Select G(t) from G(t-1) Crossover G(t) Mutate G(t) Evaluate G(t) loop |
/ inicializuj počáteční generaci / proveď ohodnocení / dokud není splněna ukončovací podmínka / proveď přirozený výběr / aplikuj křížení / aplikuj mutaci / proveď ohodnocení |
Pro ilustraci uvádím následující jednoduchý příklad:
Uvažujme populaci o 4 jedincích ve formě binárních řetězců délky 8 a nechť ohodnocovací funkce je rovna počtu 1 v řetězci. Počáteční populace by mohla vypadat např. takto:
| jedinec | ohodnocení |
|---|---|
| A 00010000 | 1 |
| B 11011101 | 6 |
| C 10000100 | 2 |
| D 01100001 | 3 |
Roztočíme-li čtyřikrát ruletu, mohl by náš výběr dopadnout např. jako B,D,B,C. V tuto chvíli již tedy jedinec A vypadá ze hry. Dále budeme aplikovat křížení. To se děje podle nějaké předem dané pravděpodobnosti. Pro jednoduchost předpokládejme, že se uplatní u páru B,D a u páru B,C nikoliv. Pro pár B,D tedy určíme náhodně pozici. Nechť je to např. hned první pozice. Provedeme výměnu konců řetězců a dostaneme tak dva nové jedince E=11100001 a F=01011101. Nyní na každý z jedinců E,F,B,C může být aplikována mutace. Předpokládejme, že se tak stane u jedince B, a to např. na páté pozici. Dostaneme tedy B'=11010101. Nová generace bude vypadat takto:
| jedinec | ohodnocení |
|---|---|
| E 11100001 | 4 |
| F 01011101 | 5 |
| B'11010101 | 5 |
| C 10000100 | 2 |
Můžete si povšimnout, že maximální ohodnocení v nové generaci je menší (klesnulo ze 6 na 5), průměrné ohodnocení se však zvýšilo.
Pro matematický popis a analýzu genetických algoritmů je klíčovým pojmem pojem tzv. schématu. Schéma je v podstatě šablona, jež slouží k popisu podmnožiny řetězců (chromozómů), které obsahují jisté podobné sekce. Pro binární řetězce je schéma řetezcem znaků 0,1 a metaznaku #. Přitom symbol # znamená, že se na jeho místě může vyskytovat jak 0, tak 1. Takto např. schéma #0000 popisuje množinu řetězců 00000, 10000, oba řetězce pak tvoří instance tohoto schématu.
Holland odvodil pro případ reprezentace binárními řetězci a dříve zmíněných mechanismů křížení a mutace následující stěžejní vztah pro počet instancí daného schématu S v generaci t:
| kde |
m(S,t) je počet instancí schématu S v generaci t, m(S,t+1) je očekácaný počet instancí schématu S v generaci t+1, f(S) je průměrné ohodnocení instancí schématu S v generaci t, f je průměrné ohodnocení všech řetězců generace t a a<1 je faktor zastupující vliv křížení a mutace. |
Z tohoto vztahu můžeme učinit základní závěr, že počet instancí schémat, která se těší naprůměrnému ohodnocení, s časem roste, a to přibližně exponencielně rychle, zatímco počet instancí schémat podprůměrného ohodnocení přibližně exponencielně klesá.
D.E. Goldberg Genetic Algorithms in Search, Optimization, and Machine Learning
B.P. Buckles, F.E. Petry Genetic Algorithms