Evoluce Turingova stroje

Předmluva

Tímto článkem začíná konec :-) anonymity mého blogu. Protože konferenční příspěvek o mých experimentech na téma "evoluce" musím nejpozději do února 2011 dopsat a odeslat na nějakou tematickou konferenci, snadno si pak dohledáte, kdo tento blog píše.

Úvod

Poslední dva měsíce jsem strávil implementací evoluce Turingova stroje.

Stručné vysvětlení pro ne-ajťáky: Turingův stroj je asi nejjednodušší možný stroj s výpočetní schopností ekvivalentní běžným počítačům. Pro představu, kompletní simulátor Turingova stroje mi v programovacím jazyce ANSI C zabírá pouze 20 řádků kódu, a to nejsem žádný geniální programátor.

Proč se pokouším na Turingův stroj nasadit evoluci?

Chci si na tomto jednoduchém modelu sám vyzkoušet zodpovědět několik otázek, o kterých se bez experimentu dá pouze spekulovat:

1. Může nemyslící entita (např. stroj) vytvořit funkční algoritmus? Toto je jedna ze základních otázek oboru "umělá inteligence"
2. Jaké schopnosti má evoluce?
3. Co je to "přirozený výběr"?
4. Zůstalo ještě v Darwinově teorii něco, co je ve světle dnešní vědy obecně platné?

Výsledky

1. Podařilo se mi pomocí evoluce vytvořit funkční algoritmus, který je stejně efektivní, jako ten, který jsem vymyslel sám. Samozřejmě, výsledný algoritmus nevymyslel počítač uplně sám, ale vytvořil ho na základě popisu správného řešení, který jsem mu zadal. Detaily popíšu v konferečním článku.
    
2. Evoluční algoritmy fungují.
   
   Základním předpokladem dobrých výsledků je ale dobře vymyšlená účelová funkce a dobře vymyšlená "evoluční strategie" - tyto dvě komponenty určují, které jedince necháme rozmnožovat a jak.
   
   Na implementaci těchto dvou komponent jsem strávil velmi mnoho času - řádově víc, než kolik mi trvalo vymyšlení optimálního "lidského řešení" Turingova stroje řešícího daný vzorový problém. 
   
   Ale pro složitější problémy, kde se "lidské řešení" vymýšlí těžko nebo příliš dlouho, může být implementace evoluce naopak mnohem jednodušší.
   
   Co z toho vyplývá: evoluční algoritmy v informatice fungují proto, že do nich vkládáme svoji inteligenci a obraz správného výsledného řešení.
   To je naprosto jiný přístup, než materialistický (Darwinův) model "evoluce bez záměru"  ("evolution without purpose").
   
   U materialistického modelu evoluce je účelovou funkcí evoluce "přežití organismu". Modelováním v tomto smyslu se zabývá jiná oblast informatiky - "Umělý život" (artificial life). Narozdíl od evolučních algoritmů, které fungují a už nějakou dobu přináší lidstvu užitek, výzkumníci v oblasti umělého života naráží na to, že jimi modelované životní formy se po nějaké době přestávají vyvíjet, stagnují, degenerují nebo zanikají.
   
   
3. "Přirozený výběr": Darwin věřil, že přirozený výběr v přírodě probíhá algoritmem "přežití nejlepších". Tato evoluční strategie ale v evolučních algoritmech nefunguje a nemůže fungovat ani u živých organismů. Proč?
   
   Představte si obrovský prostor všech možných "jedinců", který je tvořen všemi možnými kombinacemi jejich kódu (je jedno, jestli je to kód DNA nebo počítačový).
   
   V případě mého experimentu jsem vyvíjel jedince - Turingovy stroje, kteří měli max. 20 stavů, zpracovávali max. 5 znaků a na pásce mohli dělat 4 různé posuvy (nic, L, R, RR).  Kód Turingova stroje je přechodová funkce, tj. tabulka, která v mém případě má 20*5 = 100 řádků a v každém řádku může být jedna z 20*5*4=400 kombinací trojic (stav, znak, posuv). Počet všech možných jedinců = počet všech možných tabulek = 400¹⁰⁰=1,6 * 10²⁶⁰.
   
   To je ovšem ohromné číslo. Jen pro představu: I kdybych měl scifi super počítač a vytvořil v něm populaci o velikosti 10³⁰ jedinců (tj. odhadovaný počet nejpočetnější živé formy na Zemi - bakterie SAR11) a mohl bych nové mutace z každého jedince tvořit každou sekundu (scifi super počítač to stihne), pak by každý jedinec vytvořil 86400 mutací denně = 31.536 milionů ročně a já mohu za 1 rok vyzkoušet pouze 31 * 10³⁶ mutací. Abych tímto způsobem prošel celý stavový prostor, bude můj výpočet trvat cca  10^260-37 = 10²²³ let. Je pro srovnání, stáří sluneční soustavy se odhaduje na 4.5 * 10⁹ let :-)
   
   Podotýkám, že prostor o velikosti 10²⁶⁰  Turingových strojů  je stále mikroskopický ve srovnání s prostorem všech možných živých organismů, které definuje řetězec bázových párů DNA. Např. výše uvedená bakterie SAR11 má 1 308 759 párů DNA, což je nejkratší DNA ze všech dnes známých volně žijících organismů. Jeden pár může nabývat 4 hodnot (G-C, C-G, A-T, T-A), takže to máme 4^1308759 =   2.7 * 10⁷⁸⁷⁹⁵¹ možných kombinací. Wow...
   
   Představte si tento ohromný prostor raději jako obrovskou krajinu s nížinami, propastmi a horami. Vaším úkolem je najít nejvyšší horu, což  obnáší i to, že musíte nejdřív nalézt její vrchol.
   
   Jediné možné řešení tohoto problému je takové, že budete testovat náhodné body v celé krajině a pokud nějaký bod bude mít dobrou výšku, začnete ohmatávat jeho okolí.
   
   Takto nějak funguje evoluční algoritmus: jedinec=bod v krajině, výška bodu=fitness jedince.
   
   V čem je problém algoritmu "přežití nejlepších" ? V dané chvíli hledání se nějaký jedinec může nacházet na vrcholu, který je sice momentálně nejvyšší nalezený, ale rozhodně není nejvyšší. Pokud byste nechali rozmnožovat pouze tohoto jedince, pak všichni jeho potomci (ať už nemodifikovaní, nebo modifikovaní mutací) se budou nacházet již pod vrcholem a vy nikdy nenajdete žádnou vyšší horu. Přitom o kus dál jste měli jedince, který stál na úpatí hory, která skutečně nejvyšší byla. Máte ale smůlu, protože jste ho nenechali se rozmnožovat  a další jedinec se na jeho pozici dostane .. třeba až za 10¹⁰⁰ let :-)
   
   Darwin nic z tohoto nemohl vědět. Nevěděl nic o DNA, nevěděl nic o dědičnosti, neměl k dispozici počítače, na kterých by mohl nechat běžet modely evoluce a zkoumat, čeho je a čeho není schopna. Nemohu mu vyčítat, že na základě tehdejších znalostí o přírodě vytvořil teorii, která obsahuje tolik chyb, že není použitelná.
   
   Co mu ale musím vyčítat je to, že o svojí teorii neměl žádné pochybnosti a postavil ji tím na úroveň víry. Víry, která se stala velmi úspěšná. Co tato víra ovšem implikuje si můžete přečíst na straně 134 jeho pozdní práce "THE DESCENT OF MAN,AND SELECTION IN RELATION TO SEX".
   
   Pokud nevládnete dobře angličtinou, přeložil jsem pro vás aspoň kousek tohoto pamfletu v příspěvku The descent of man.