Letos mě na škole zdaleka nejvíce baví předmět A4B33FLP, který, jak jste si již někteří mohli všimnout, jsem si zapsal dobrovolně. Je to předmět primárně určený pro studenty OI (A4), což ve mně opět vzbuzuje přesvědčení, že jsem měl jít raději tam, než na STM, kde mají lidé běžně velký problém s Karlem v Javě.

K věci. Probíráme různé exotické jazyky, jako je Scheme (dialekt Lispu), Haskell nebo Prolog. Právě Schemu jsme věnovali nejvíce času a právě v něm jsme tvořili semestrální projekt sestávající ze tří nezávisle bodovaných navazujících částí, které měly zdůraznit použití funkcionálních jazyků v oblasti umělé inteligence.

V první části (která mi zabrala celkem 9 hodin) jsme tvořili interpret programu pro robota pohybujího se v dvojrozměrném poli plném zdí a značek. Programovací jazyk robota je pro zjednodušení velmi podobný Schemu, ale z větší části nekompatibilní. Jazyk obsahuje několik atomických příkazů:

• turn-left – robot se otočí doleva,
• step – robot provede krok pokud před ním není zeď, jinak skončí,
• get-mark – robot sebere značku ze země a pokud tam není, skončí,
• put-mark – robot pod sebe položí značku,
• ([...]) – seznam příkazů,
• () – nic,

několik složitějších konstrukcí:

• procedure [jméno] ([tělo]) – definice procedury,
• if [bool] [tělo-true] [tělo-false] – podmínka,
• [jméno_procedury] – volání procedury,

a funkce vracející booleovské hodnoty:

• wall? – je před robotem zeď?
• mark? – je pod robotem alespoň jedna značka?
• north? – míří robot na sever?

Robot se pohybuje v bludišti, které je definováno jako seznam seznamů.

((w w w w)
 (w 0 1 w)
 (w 2 0 w)
 (w w w w))

Program robota je seznam seznamů procedur, kde v každém seznamu musí být procedura start, která je vstupní procedurou. Program může vypadat nějak takto:

(((procedure a (step a)) (procedure start (if wall?
turn-left a)))(...))

Ve druhé části (která mi zabrala 4 hodiny) jsme vytvářeli ohodnocovací (fitness) funkci pro robotovy programy. Nyní jsme narazili na termín z genetického programování, které raději nejprve povrchně popíšu.

------

Genetický algoritmus je algoritmus, který se, inspirován evoluční teorií, snaží vyšlechtit požadovaného jedince z náhodně generované počáteční populace. Zná přitom pouze hodnotu fitness (tj. jak by měl být dobrý) požadovaného jedince. Jedinec je jedno konkrétní řešení problému a disponuje vlastním genotypem, fenotypem a ohodnocením (fitness). V případě, že řešení problému je program, jedná se o genetické programování. Genotyp je v tomto případě syntaktický strom programu a fenotyp je tento strom zapsán jako vnořené seznamy.

Proces evoluce v genetickém programování sestává z následujích kroků:

• Generování populace
• Selekce
• Rekombinace
• Mutace

opakovaných v n iteracích (tzv. generacích).

V procesu selekce se jistým chytrým způsobem (uveďme napříkad ruletovou selekci (kterou používám ve svém programu), turnajovou selekci nebo fitness-proporcionální selekci) zvolí dva jedinci (zpravidla jedinci s větší fitness budou mít větší šanci na zvolení) a aplikuje se na ně rekombinace.

V procesu rekombinace (křížení) se vezmou dva vybraní jedinci, určí se náhodný bod křížení ve fenotypu a jeho příslušné části se vymění. V případě genetického programování se vyberou určité uzly syntaktických stromů a odpovídající podstromy se vymění. Pozor! Tento proces musí zajistit, že jeho aplikací vzniká platný jedinec (nemůžeme například místo "procedure" vložit "wall?" a podobně). Následuje mutace.

V procesu mutace se ve fenotypech nově vzniklých jedinců zvolí náhodné listy (tj. atomické příkazy) a ty se náhodně změní.

Dále následuje stěžejní operace - generování nové populace. Pro různé typy problémů se hodí různé způsoby. Můžete například vyměnit dva nejhorší jedince z populace a nahradit je novými (což jsem si osobně pojmenoval jako božská metoda - většina populace žije po mnoho generací). Mně se osvědčila metoda, kdy nechám ze staré populace postupně vygenerovat úplně novou, kterou tu původní nahradím až na dva nejlepší jedince z předchozí populace. Zkoušel jsem i úplně přirozenou metodu - nahrazovat populaci úplně, ale při ní nedochází ke šlechtění - dobří jedinci umírají i se svým dobrým genotypem a nahrazují je jiní.

Metoda selekce zaručuje, že příležitost zachovat svůj genotyp dostanou občas i horší jedinci, čímž se vyhneme uváznutí v lokálním extrému (problémy greedy algoritmů - např. hill climber).

------

Fitness programu je seznam o čtyřech číselných prvcích:

(A B C D)

kde A je manhattanská vzdálenost robota po spuštění programu od kýženého stavu, B rozdíl bludišť co do počtu značek, C je délka programu a D je počet vykonaných atomických příkazů při jednom běhu (nebo naopak). Každému programu lze nastavit i práh maximálních vnořených volání procedur (což bude mít za následek jiné výsledky - například program ((procedure start (step start))) půjde s robotem přesně tolik kroků, kolik je velikost tohoto prahu).

Ve třetí části (která mi zabrala 8 hodin) jsme měli implementovat samotnou automatickou syntézu kódu. Měli jsme napsat proceduru, která přijímá výchozí bludiště a stav robota, cílové bludiště a stav robota (těchto párů může být několik - fitness funkce je navržena tak, že se počítá pro všechny páry), práh fitness (A B C D), který označuje jak špatné programy můžeme ihned zahazovat a práh pro vnořené procedury. Výsledkem měl být program, který má fitness (0 0 x x), tedy takový, který dostal robota do správné pozice a se všemi políčky udělal to, co měl (sebral značku atp...).

Protože jako studenti píšící ve funkcionálním jazyce poprvé, jsme ještě neměli dostatečné zkušenosti na to, abychom psali optimální kód, byly nám přiděleny pro každou evoluci relativně velké časy v automatickém hodnotícím systému, kde byly úlohy rozděleny na level easy, medium a hard. Easy úlohy měly limit 10 vtěřin a hard úlohy 3 minuty. Protože čtenář se pravděpodobně s funkcionálními jazyky nesetkal, povrchně přiblížím Scheme.

------

Scheme je dialekt jazyka Lisp, což je zkratka pro "LISt Processing", tedy zpracování seznamů. V postatě se ve Schemu nedělá nic jiného než zpracovávání seznamů. V čistě funkcionálních jazycích neexistují proměnné ani smyčky. Pouze funkce, parametry a rekurze. Rekurze je základní stavební kámen každého funkcionálního programovacího jazyka. Téměř každá funkce, kterou napíšete, bude rekurzivní. Ve výsledku máte elegantní krátký kód, který je navíc rychlý.

Dvě nejpoužívanější funkce Schemu (a kteréhokoliv FJ) jsou car a cdr. car bere první prvek seznamu, cdr bere celý seznam bez prvního prvku. Pomocí těchto dvou příkazů, rekurze a něco málo aritmetických operátorů a podmínek, lze naprogramovat vše. Dokonce i tyto příkazy se dají zjednodušit na tzv. lambda funkci, se kterou samotnou lze vystavět vpodstatě jakýkoliv program (pokud vás to zajímá, vizte Lambda Kalkulus). Následují nějaké ukázky.

(define (take n list)
  (if (= n 0) '()
      (cons (car list) (take (- n 1) (cdr list)))
  )
)

Tato funkce take bere dva argumenty n a list. n je nějaké číslo a list je nějaký seznam. Následuje ukončovací podmínka (každá pořádná rekurzivní funkce by měla začínat ukončovací podmínkou) - pokud je n rovno 0, vrať prázdný seznam (proč, to se dozvíte dále). Pokud není rovno 0, vrať seznam takový, že vezmi první prvek ze seznamu list a připoj ho k seznamu, který vrátí funkce take, když ji zavoláme s o jedno nižším n a zbytkem seznamu.

Základním datovým typem Schemu je tzv. tečkový pár (A . B). Pokud A bude cokoliv a B bude prázdný seznam '(), potom výsledkem bude seznam s jediným prvkem A. Například toto spojení - '(1 . (2 . ())) - vytvoří seznam (1 2). Tečky si můžete představit jako uzly stromu. Funkce cons v naší funkci take připojí jeden prvek k seznamu, a proto potřebujeme seznam vytvořit, když doejdeme na konec rekurze - připojíme k poslední hodnotě prázdný seznam a máme seznam o jednom (právě n-tém prvku). Při zpětném postupu rekuze potom připojujeme všechna předešlá čísla. Funkce take vezme ze seznamu podseznam o n prvcích.

------

Moje úloha dopadla na 9/10 bodů - u jednoho z level:hard příkladů překročila časový limit.

Ale abych o tom jenom nepsal, mám i praktickou ukázku. Svůj program jsem trochu poupravil a zkompiloval do nativního binárního souboru systému Windows (exe). Tento program bere jako parametr řetězec, který obsahuje libovolný příkaz Schemu, který vykoná nad mým programem. Můžete tedy z něho volat i potřebnou funkce (evolve ...). Připravil jsem pár command skriptů, které za vás obstarají i volání, takže jen můžete sledovat evoluci.

První program má úplně volné bludiště 5x5 a uprostřed něj je značka. Cílem je sebrat značku.

Druhý program má dvě verze. Bludiště je tentokrát jenom čtvercová cestička kolem středu. Úkolem je vydláždit cestu značkami a vrátit se zpět na začátek. Rozdíl mezi verzemi je ten, že první má limit vnoření 20 (program bude vyvíjet spíše povrchní a dlouhé programy a bude mu to trvat relativně dlouho) a druhý má limit 100 (bude rychlejší, vyvine kratší "rekurzivní" program).

Třetí program. Je jenom chodba, na které jsou střídavě vysázeny značky... úkolem robota je značky invertovat (tam kde, jsou, je sebere, a tam, kde nejsou, je položí).

Zde je možné stáhnout program a sadu těchto testovacích bludišť.

Program nejprve zobrazí vygenerovanou počáteční populaci a potom pokaždé, když se v nějaké generaci vyskytne jedinec lepší, než prozatím nejlepší, vypíše ho.

Když pochopíte, jak programu zadávat parametry, můžete vytvářet i vlastní situace.

Jen pro představu: Program má 960 řádků a je v něm nespočet dlouhých neoptimálních zel, hrubě porušujících zásady funkcionálního programování - imperativní kontrukty. Je v něm vidět, jak moc jsem byl při psaní té které části unavený.