Evolution with Open Dynamics Engine (Bečvarová Ľuboslava)

Úvod

Mojou úlohou bolo vytvoriť simuláciu evolúcie, kde genotypom je tvar. ten sa mal postupne vyvíjať tak, aby robot pri pohybe dosahoval čo najväčšiu rýchlosť.

ODE

Pri svojej práci som použila ODE. Je to open-source knižnica, ktorá slúži na simuláciu dynamiky pevných predmetov. Knižnica je plne funkčná, stabilná, vyspelá a platformovo nezávislá, ktorá je jednoducho použiteľná s C/C++ API. Má pokročilé kĺby a integrovanú detekciu kolízií s trením. Kĺbové konštrukcia sa vytvorí, keď sú telesá rôznych tvarov spojené s kĺbmi z rôznych druhov. Príklady sú pozemné vozidlá (ak sú kolesá zapojený na kostru), bytosti s nohami (kde nohy sú pripojené k telu). ODE má zabudovaný systém detekcie kolízií. Avšak ten môžete ignorovať a robiť si vlastné detekciu kolízií, ak chcete. ODE je užitočné pre simuláciu vozidiel, objektov vo virtuálnych prostrediach alebo virtuálnych bytostí. V súčastnosti sa používa v mnohých počítačových hrách, 3D nástrojoch pre tvorbu a v simulačných nástrojoch. ODE je určený pre použitie v interaktívnych simuláciách alebo v simulácií v reálnom čase. Je zvlášť vhodná pre simuláciu pohybujúcich sa objektov v premenlivých virtuálnej realite.

GAlib

GAlib je C++ knižnica komponentov genetických algoritmov. GAlib obsahuje sadu C++ objektov genetických algoritmov. Knižnica obsahuje nástroje pre používanie genetických algoritmov na optimalizáciu v ľubovoľnom C++ programe použitím ľubovoľnej reprezentácie a genetických operátorov. Dokumentácia obsahuje rozsiahly prehľad o tom, ako realizovať genetický algoritmus, rovnako ako príklady ilustrujúce úpravy na GAlib triedy. GAlib bol postavený na rôznych platformách UNIX (Linux, MacOSX, SGI, Sun, HP, DEC, IBM), ako aj MacOS a DOS / Windows systémov. GAlib obsahuje príklady, ktoré používajú PVM pre distribuované paralelné, implementácie.

Postup

V hlavnej časti programu - vo funkcií int main(int argc, char **argv) sa na začiatku nachádzajú nastavenia veľkosti populácie, počtu generácií, pravdepodobnosť mutácie a pravdepodobnosť kríženia. Tu sa využíva knižnica GAlib. ďalej sa vytvorí genóm. Knižnica GAlib ponúka na výber z ôsmych základných typov genómov. Niektoré z nich sa ešte delia na ďalšie typy genómov. Ja som si pre svoj projekt vybrala GARealGenome. Pri tomto type genóme je potrebné nastaviť najskôr množinu alel, teda GARealAlleleSet. Táto množina alel definuje možné hodnoty, ktoré každý prvok genómu môže predpokladať. Genómu nastavíme aj jeho Objecive funkciu. Potom si konečne vytvoríme genetický algoritmus, ktorý použijeme. Pre tento projekt som zvolila GASimpleGA. Ide o "jednoduchý" genetický algoritmus, ktorý popisuje pán Goldberg vo svojej knihe. Algoritmus používa neprekrývajúce sa populácie. Pri vytváraní jednoduchého genetického algoritmu je potrebné špecifikovať buď jedinca alebo populáciu jedincov. Nový genetický algoritmus bude klonovať jedincov podľa predchádzajúcej špecifikácie na vytvorenie vlastnej populácie. Do tohto genetického algoritmu priradíme všetko, čo sme už definovali, teda o aký genóm ide, veľkosť populácie, počet generácií, pravdepodobnosť mutácie, pravdepodobnosť kríženia. Je potrebné nastaviť aj to, podľa čoho bude vyberať vhodných kandidátov. Preto si vytvoríme objekt typu GATournamentSelector. Volič na základe turnaju používa metódu, kde si pomocou rulety vyberie dvoch jedincov a vyberie toho s vyšším skóre. Tento volič častejšie vyberá vyššie ohodnotených jedincov ako RouletteWheelSelector. Toto teda tiež priradíme do genetického algoritmu a ten môžme konečne spustiť. Pre každý genóm zbehne funkcia Objective, kde voláme funkciu Evaluate s hodnotami, ktoré sme získlai z genómu. Funkcia Evaluate je funkcia, ktorá využíva ODE. V tejto funkcií sa spustí simulácia. Výsledkom tejto funkcie je fitness, ktoré priradíme na základe toho, ako ďaleko robot došiel. V tejto funkcií si vytvoríme premennú typu dsFunctions, ktorej ako jeden krok nastavíme funkciu simLoop. Funkcia simLoop vytvorí robota a simuluje jeho pohyb. Zároveň sa v nej počíta počet "tikov", teda ako dlho má jedna simulácia bežať. Ak sa tento počet už prekročí, simulácia bude zastavená a vyráta sa fitness pre robota s aktuálnymi parametrami. Táto fitness je výstupom funkcie Evaluate.