Potíže s genetickým programováním

Základní myšlenka genetického programování byla vysvětlována již mnohokrát, proto ji nyní popíšeme pouze stručně. Podobně jako v biologické evoluci i v její počítačové obdobě využíváme stejné principy: mutaci, křížení a přírodní výběr (selekci). Vycházíme z toho, že i mezi programy přežijí ty „nejschopnější“ – tedy ty, které nejlépe řeší námi zadanou úlohu. Na začátku vezmeme nějaké zdrojové kódy, obvykle takové, které mají již k řešení úlohy nějaký vztah. Uděláme mezi nimi první výběr. Máme například zajistit, aby se virtuální mravenec naučil hledat potravu. Srovnáme tedy programy podle toho, jak je který úspěšný (tj. žebříček bude třeba seřazen podle množství jídla, které sesbírá mravenec za několik kol). Ty nejlepší v populaci „namnožíme“, ty nejhorší smažeme. Následně spolu programy náhodně „zkřížíme“, tj. funkčně si odpovídající bloky kódu nějak proházíme (z programů A1A2 a B1B2 dostaneme třeba kombinace A1B2 a B1A2). Tento postup celkem odpovídá tomu, co se děje při pohlavním rozmnožování s jednotlivými geny.
Máme potomstvo. Jako další krok nyní necháme u určité části programů proběhnout mutaci, tj. náhodnou změnu. Mutace se může týkat třeba řídicí proměnné cyklu (změna hodnoty, nebo změna proměnné jako takové), podmiňovacího příkazu apod. Může také docházet k deleci (vypadnutí kusu programu) či inserci (kus kódu je kopírován na další místo).
Nyní testujeme, jak nové programy řeší danou úlohu. Většina změn bude zřejmě k horšímu, řada programů vůbec nepůjde spustit či budou vykazovat jiné zásadní chyby. To nám ovšem nevadí, slabé programy vyřadíme, ty úspěšné naopak propustíme do dalšího kola opět ve více kopiích.
Pokud v nové generaci nedostaneme program řešící danou úlohu lépe než v předešlém kole, můžeme buď pokračovat dále, a nebo se vrátíme ke generaci minulé.

Způsoby křížení můžeme samozřejmě definovat nějak přesněji, taktéž je záhodno upřesnit, co všechno může mutovat a samozřejmě jak často. Taktéž můžeme změnit pořadí kroků, tj. nejprve nechat programy mutovat a až pak je křížit. (Poznámka: autor tohoto článku je pouze svátečním programátorem a omlouvá se za možná přílišné zjednodušení v textu výše.)

Jaký je z toho závěr? Genetickým programování lze vyvinout určitý software často bez toho, abychom rozuměli „podstatě“ řešeného problému a museli se nějak namáhat s vymýšlením algoritmické reprezentace. Tato skutečnost má kromě výhod samozřejmě i určité nevýhody, mj. i estetickou – není to prostě tak elegantní jako dokonale promyšlený a zdůvodněný algoritmus, nemusí se dostavit „radost z úspěchu“. Existují však i další potíže. Aby „selekce“ mohla vůbec nějak smysluplně začít, potřebujeme programy, které už úlohu alespoň nějak řeší. Pokud vložené programy dělají něco úplně jiného, není moc mezi čím vybírat (museli bychom čekat, až mutacemi náhodně vznikne nějaký alespoň „trochu-řešící“ program, a toho bychom se nemuseli v reálném čase vůbec dočkat). Naopak v případě, že se řešení výsledku už nějak blíží, bývá kumulovaná selekce často velmi efektivní. Může se nám také stát, že během vývoje dostaneme algoritmus, který by geniálně řešil jiný problém, avšak samozřejmě to nemáme možnost zjistit (to ovšem víceméně platí i pro jiné metody programování). Taktéž musíme umět včas skončit, tj. zjistit, kdy už mutace pouze „rozhazují“ obstojné řešení.
Zatím se ale jedná skutečně o pouhé vady na kráse. S dostatečně výkonným hardwarem bychom mohli zdánlivě složit ruce v klín a vše nechat na samovolně probíhající evoluci.
Pak je zde ale jeden zásadní problém, kterému bychom mohli učeně říkat „falešný atraktor“. Atraktor (ze slovesa přitahovat – to attract) není kosmetický doplněk, ale stav, kam směřuje určitý fyzikální (či jiný) systém. Pro teplotu konvice s horkou kávou ponechanou v místnosti je například atraktorem teplota místnosti. Pro pohybující se kyvadélko zpomalované třením je to nehybná svislá poloha.
Kromě atraktoru bychom problém také mohli označit za problém lokálních minim. Potřebujeme se dostat k nejlepšímu řešení úlohy, tj. k extrému globálnímu. Jestliže však řešení úlohy, které si můžeme představit jako kuličku, jednou spadne do určitého důlku, je velmi obtížné jej z něj mírným potřásáním dostat, i když někde dále se nachází důlek hlubší. Kulička se prostě vždy skutálí zpátky do důlku, který si vyhlédla jako první.
Protože v genetickém programování ovšem „mapu krajiny“ neznáte (jinak byste měli i řešení, tj. nejhlubší důlek, a nepotřebovali byste nic programovat), často si nemůžete být jisti, zda jste dosáhli skutečného řešení, nebo pouze řešení falešného – falešného atraktoru.
Tady by snad byla na místě jistá odbočka do biologie. Jak to, že biologická evoluce potom vůbec probíhá a už dávno nezatuhla ve svých lokálních extrémech-důlcích? Často k zatuhnutí skutečně dochází. Nějaká změna se prostě nemůže uplatnit, protože „mezipřechod“ k ní je nevýhodný. Zmutovaní jedinci jsou z populace eliminováni dříve, než by mohlo dojít k další, už zvýhodňující mutaci. Jenomže na rozdíl od genetického programování není biologická krajina konstantní. Struktura maxim a minim se neustále mění s tím, jak se mění třeba teplota, hladiny moří a koneckonců i další organismy. Abychom se vyhnuli problému falešných atraktorů, měli bychom tyto změny nějakým způsobem zahrnout i do genetického programování. Jenže jak? Chceme přece vyřešit určitou konkrétní úlohu. Když zahýbáme s „krajinou“, evoluce sice nikde nezatuhne, jenže výsledkem bude řešení jiné úlohy, než o jakou nám šlo. My jsme dnes také výsledkem řešení jiné úlohy, než jaká byla „formulována“ v prvohorách.

S problémem genetického programování úzce souvisí otázka tzv. biomorf (metoda modelování biologické evoluce, kdy lze z jednoduchých prvků a jednoduché sady operací velmi rychle postavit složité útvary) a teorie buněčných automatů. Těm se podrobněji věnují například následující články.

       

Svět podle Stephena Wolframa – výklad řady jevů na základě principů buněčných automatů

Jak pracují buněčné automaty – včetně problematiky generování biomorf evolučním biologem Richardem Dawkinsem