Projekt 2019

CGP - Kartezijsko genetsko programiranje

Mentor: prof. dr. sc. Domagoj Jakobović


Zadatak

Cilj projekta bio je kreirati funkcionalnu implementaciju kartezijskog genetskog programiranja (CGP) i implementirati ju u sustav ECF. Napravljena je i evaluacija i vizualizacija konačnog algoritma na grafički jasan i interesantan način u obliku igrice.


Što je CGP?

CGP (Cartesian Genetic Programming) odnosno kartezijsko geentsko programiranje oblik je genetskog programiranja razvijen na temelju reprezentacije korištene za evoluciju digitalnih sklopova. Bazira se na kodiranju grafa (kartezijska mreža čvorova) kao slijeda cijelih brojeva koji predstavljaju funkcije te veze između čvorova grafa i ulaza/izlaza programa.


Implementacija

Na početku same implementacije CGP-a u ECF implementirali smo odabrane funkcijske operatore, operatore križanja i operatore mutacije. Osim operatora ostvareno je i svojstvo povratnog odnosno rekurentnog CGP-a. Nakon uspješnog parsiranja generacije iz XML-a i generacije u XML, implementirano rješenje se evaluiralo i na kraju vizualiziralo spajanjem ulaza mreže čvorova CGP-a s igrom napravljenom posebno za ovaj projekt. U završnoj fazi testira se uspješnost i efikasnost implementacije te različiti ishodi ovisno o ulaznim parametrima koji definiraju mrežu CGP-a.


Funkcijski operatori

Od funkcijskih operatora korištene su osnovne aritmetičke funkcije. Konkretno:

  • Zbrajanje
  • Oduzimanje
  • Množenje
  • Dijeljenje
  • Eksponencijalna (e^x)
  • Korjenovanje
  • Sinus
  • Kosinus
  • Step
  • Logaritam prirodnog broja

Operatori križanja

  • Single-Point Crossover
  • Pri ovom križanju oba roditeljska genotipa se dijele na nasumično određenom mjestu križanja. Naposljetku, novi genotip stvara se spajanjem prvog dijela prvog roditeljskog genotipa i drugog dijela drugog roditeljskog gentipa. Kao rezultat imamo genotip koji nosi genetsku informaciju oba roditelja.

  • Two-Point Crossover
  • Pri ovom križanju oba se roditeljska genotipa dijele na dva nasumično određena mjesta stvarajući novi genotip koristeći prvi i treći dio prvog roditeljskog genotipa i središnji dio drugog roditeljskog genootipa. Korištenjem ovog operatora križanja omogućuje se temeljitija pretraga područja problema. Two-Point crossover ekvivalentan je izvođenju dva single-point crossover-a na različitim mjestima križanja.

  • Uniform Crossover
  • Za razliku od single-point i two-point križanja koji definiraju mjesta križanja, uniform crossover generalizira genotip i svaki gen čini potencijalnim mjestom križanja. Osnovni princip uniformnog križanja je maska križanja. Ona je iste duljine kao i individualna struktura i stvara se slučajno, odnosno paritet maskirajućih bitova određuje koji će roditelj predati koje gene novostvorenom čvoru. Izbor roditelja čiji gen će biti odabran bira se jednakom vjerojatnošću. Za uniform crossover nije određen efektivan broj mjesta križanja, no u prosjeku taj će iznositi l/2 gdje je l veličina genotipa.

  • Half-Uniform Crossover
  • Sličan je uniform crossover-u. Jedina je razlika što se samo pola razlikujućih bitova među dva roditeljska genotipa zamjenjuju.


Operatori mutacije

  • One Point Mutation
  • Ova mutacija nasumično bira gen u genotipu koji će mutirati. Ukoliko odabere funkcijski gen ovaj operator mutira gen slučajnim odabirom neke od funkcija iz skupa funkcijskih operatora. U slučaju nasumičnog odabira gena koji je ulaz u neki čvor slučajno odabire jedan od ulaza nekog čvora, a u slučaju odabira gena koji je izlazni mutira ga slučajnim odabirom jednog od izlaza nasumičnog čvora genotipa.

  • Parameter Less Mutation
  • Točno jedan aktivni gen se mutira u cijelom genotipu. Mutacija se obavlja istim algoritmom kao i u One Point Mutation sve dok se ne mutira jedan aktivni gen. U međuvremenu moguće je da će biti mutirano nula ili više neaktivnih gena. Za ovaj postupak nije potrebno definirati mutation rate (stopu mutiranja).

  • Silent Mutation
  • Ovaj operator karakterizira mutacija koja se izvršava nad jednim od neaktivnih gena iz genotipa. Slučajno odabranom neaktivnom genu na neki od njegovih ulaza dovodi se jedan od izlaza čvorova genotipa. Ova mutacija nema nikakvog efekta na fenotip, već samo na genotip.

  • Non-Silent Mutation
  • Algoritam je vrlo sličan algoritmu Silent Mutation operatora. Također se odabire jedan od neakitvnih gena iz genotipa, međutim taj će se mutirati u aktivni gen. Potom, nalazimo sve aktivne i neaktivne čvorove koji mogu imati neaktivni čvor kao ulaz. Ti čvorovi mogu sadržavati i indekse izlaznih čvorova. Nakon pronalaska svih takvih čvorova izbacujemo one neaktivne među njima i slučajno odabiremo aktivan čvor koji će se mutirati. Ukoliko je taj čvor izlazni na njega se dovodi izlaz neaktivnog čvora odabranog na početku, a u slučaju da nije izlazni na jedan od njegovih ulaza dovodimo onaj neaktivni čvor s početka postupka.


Povratni (recurrent) CGP

U rekurentnom CGP-u nema ograničenja na veze među čvorovima. Ulaz čvora može biti ulazni parametar ili izlaz bilo kojeg čvora, uključujući i njegov vlastiti izlaz. Izlazi se povezuju s ulazima čak i prije nego što su i sami poprimili vrijednost. Ovime su omogućene povratne veze među čvorovima i mogu se stvoriti rekurzivne strukture. Postupak izvođenja rekurentnog CGP-a malo se razlikuje od običnog CGP-a jer izlaz određenog čvora može biti zahtijevan prije nego što je zapravo izračunat.

Ovo su koraci dekodiranja takvog programa:

  1. Izlazi svih aktivnih čvorova postave se na 0 prije svake evaluacije fitnessa.
  2. Primjeni se sljedeći set ulaznih parametara programa.
  3. Ažuriraju se vrijednosti svih aktivnih čvorova počevši od ulaznih parametara progra-ma pa do izlaza programa. Izlazi svih čvorova računaju se samo jednom.
  4. Čita se izlaz programa.
  5. Ponavlja se od točke 2 dok se ne primijene svi setovi ulazni parametara.

Evaluacija i vizualizacija rješenja

Evaluirali smo svaku jedinku pojedinačno kako bi odlučili koje jedinke imaju prednost pri križanju i mutaciji. Naravno, najbolje jedinke imaju prednost pred istima. U našem slučaju, evaluacija se bazirala na udaljenosti od cilja, količini goriva i prijeđenom putu. Za puno preciznije izračune više parametara se moglo ubaciti kao što su vidljivost cilja i kutevi prema preprekama i cilju. No, za naš proof-of-concept spomenuta tri ulaza bila su dovoljna za uspješan dolazak do cilja. Prednost CGP-a je ta što uzima par ključnih stvari od neuronskih mreža. Jedna od tih je što ima više izlaza što smo iskoristili u ovom primjeru. Naša mreža koristi pet izlaza, svaki predstavlja smjer kretnje: gore, dolje, lijevo, desno i ništa.


  • "raketa" na početnoj poziciji



  • "raketa" na putu prema cilju



  • "raketa" trenutak prije stizanja na cilj



Članovi projektnog tima

  • Mile Čarić
  • Ivica Duspara
  • Ante Gazibarić
  • Jelena Nemčić
  • Lukas Šestić
  • Jakov Vidulić
  • Ante Žužul