Mobil robotok szimulációja speci 7. óra

Az evolúciós algoritmusok jelentõsége

• az eddigi algoritmusok többsége biológiai alapokra épül
• evolúció esetén a kapcsolat nyilvánvaló: a C. Darwin által felfedezett modell matematikai absztrakciója
• az evolúcióban részt vevõ egyedek valamilyen módon a feladat megoldásait reprezentálják
• eljárás kiszelektálja a jobb egyedeket (gazda haszonállatokkal)
• jellemzõi: bonyolult eljárástér, melyben kis hatósugarú, lokális szabályok mûködnek; nagyfokú párhuzamosság
• lehetséges megoldások egész halmazával dolgoznak az eddigi egy megoldás folyamatos javítása helyett
• evolúciós eljárással meghatározható egy robot felépítése és viselkedése is
• evolúció és a tanulás kapcsolata
• evolúció: napszakok, évszakok változása, éghajlat, fajtársak, ellenségek, táplálékok alakja és viselkedése
• tanulás: egyed szempontjából fontos események, tárgyak, élõlények felismerése, élõhelyének megismerése

Az alapok

Az általános eljárás

• egyedek állandóan változó populációja, melyek a feladat szempontjainak megfelelõ megoldásokat reprezentálják
• sikeresség mérõje: fitneszfüggvény
• sikeres egyedek szaporodhatnak, kevésbé sikeresek elpusztulnak
• szaporodás során történhetnek változások, ez javít(hat)ja a populációt
• az általános algoritmus

  Algoritmus EA {
      t := 0
      initpopuláció(P(t))
      fitneszszámítás(P(t))
      Ciklus(amíg nincs kész) {
          P'(t) := szülõválasztás(P(t))
          keresztezés(P'(t))
          mutáció(P'(t))
          fitneszszámítás(P'(t))
          P(t+1) := túlélõ(P(t),P'(t))
          t := t + 1
      }
  }

• kezdõ populáció, ciklus, fitnesz, genetikai operátorok (keresztezés, mutáció), halál

Az algoritmus típusai

• vázolt általános végrehajtási forma specializációi
• genetikus algoritmus
  • minden egyed a megoldandó probléma egy lehetséges megoldása
  • génkészletre, kromoszómára képezõdés
  • gyakran nullákból és egyesekbõl álló bitvektor
  • genetikai operátorok a kromoszómán dolgoznak
  • fitnesz megállapításához, a gyõztes felhasználásához a génkészletet vissza kell transzformálni a feladat terébe
  • generációváltás: feleannyi szülõpár alakul ki, mint a populáció mérete
  • minden pár két egyedet hoz létre
  • az elõálló új egyedek alkotják a következõ generációt
• evolúciós stratégia
  • egyedek nem a megoldásokat reprezentálják
  • számszerû, valós értékû paraméterek
  • a paraméterek helyettesítõdnek
  • lineáris függvény együtthatói, neurális háló súlyai
• evolúciós programozás
  • populáció egyedei a probléma megoldásait elõállító programok
  • kifejezésfa, LISP-szerû nyelv
  • robotika

A reprezentáció

• reprezentáció megválasztása meghatározza a keresési teret
• genetikus algoritmus
• háromjegyû Fibonacci-számok, 1000 hosszú bitvektorok az egyedek, sorszámnak megfelelõ szám a Fibonacci számsor eleme-e
• evolúciós programozás: kifejezésfák

  

  

Genetikai operátorok

• mutáció: új egyedek elõállítása
• génkészlet véletlenszerû megváltozása
• 0.01 és 0.001 körüli érték (általában hátrányos)
• bitvektorokon a nullák és egyesek ellentétes értékbe billentése
• távolság-eltérés: 8 (1000), 0 (0000), 7 (0111)
• +/- epszilon módszer
• fáknál a fában szereplõ értékek módosítása vagy egy részfa cseréje
• keresztezés bitvektorokon legegyszerûbb esetben azt jelenti, hogy egy meghatározott ponttól kezdve a két kromoszóma felcserélõdik

  

• többpontos és uniform keresztezés
• kifejezésfáknál két részfa cseréje

  

A fitneszfüggvény

• mely egyedek és leszármazottaik kerülnek a következõ populációba
• jól számítható függvény maximalizálásakor a közelítendõ függvény a fitneszfüggvény
• függvény-approximáció: mintavételi pontokban mért különbségek összege alkotja a fitneszfüggvényt
• idõigény miatt esetleg közelítõ függvény: trigonometrikus függvény közelítésekor Taylor-polinomja
• evolúciós programozásnál a fitnesz közvetlen meghatározására nincsen lehetõség
• a kialakult programot mindig le kell futtatni, és az elõállt eredményt kell megítélni
• büntetõfüggvény
• egyedek kiválasztása módjai
• fitnesz arányában
• a sikeresek túl gyors vagy túl lassú eluralkodása -> rangsor
• bajnokság: könnyen összehasonlítható egyedeknél

Robotirányítás evolúciós programozással

• W. Lee, J. Hallam, H. Lund cikkükben evolúciós algoritmust használnak egy Khepera robotot irányító program elõállítására
• a robotnak egy tárgyat kell a környezetben felfüggesztett fényforrás alá tolnia
• három irányító modul
• elsõ modul: a tárgy megközelítése és mozgatása
• második: tárgy körül haladás
• harmadik: koordinál
• reaktív kontroller
• Khepera 55 milliméter átmérõjû, 3 centiméter magas kétkerû robot
• infravörös szenzorokkal akadályok és fény érzékelésére

A genetikai kód felépítése

• adott környezet, modulonként meghatározott fitneszfüggvény, kezdeti véletlen populáció
• fitnesz, genetikai operátorok, bajnokság
• mutáció: részfa törlése és létrehozása
• keresztezés: kompatibilis részfák cseréje, átlagolás
• populáció szigetekre osztása
• a programok logikai kifejezések
• szenzorok és értékeik, AND, OR, NOT, XOR, >=
• részfák a szenzorok értékeire alapozva gyökerüknél nulla vagy egy értéket adnak vissza
• a részfa a motor bekapcsolási irányát és a motor hatóerejét definiálja 200 ms-onként
• egy jellemzõ program

  (PROG
    (NOT (>= IR6 IR1))
    (>=IR1 0.78)
    (OR (>= IR5 IR1) (>= IR3 IR3))
    (OR (>= 0.32 IR3) (>= IR5 IR4))
    (>=IR4 IR3)
    (OR (>= IR5 IR1) (>= IR6 IR3))
  )

A viselkedésmodulok létrehozása

• a három részfeladat megoldása három teljesen különálló evolúciós programozási eljárás eredménye
• véletlenszerûen kiválasztott tesztelési feladatok a tesztkörnyezetben
• a fitnesz büntetõfüggvény alapján
• az utolsó generáció legjobb egyede a gyõztes
• dobozeltolás: elülsõ akadályszenzorok értéke folyamatosan magas, nagy sebesség, kicsi sebességkülönbség

  

• a futás során két, 50 egyedbõl álló populáció minden példánya tehetett meg 150 lépést 50 generáción keresztül

  

• doboz körvonalának követése: sebesség tartása, a robot bal oldalától a doboz fix távol tartása (IR1)

  

• a futás hasonló, és itt is van eredmény (program)

  

• harmadik modul: a fényforrás irányára és helyzetére alapozva el tudja dönteni, hogy a két alprogram közül melyiket kell érvényre juttatni
• a fitneszfüggvény a doboz és a fényforrás távolságát összegzi

  

• 4 populáció változott 40 egyeddel összesen 600 lépésnyi ideig

  

Evolúciós algoritmusok neuronhálóval

A háló kódolása

• csótány-animat járásmódjának megvalósítása
• sejtkódolás és axonnövelés kombinációja
• minden egyes neuron egy fix, meghatározott pozíciót foglal el egy kétdimenziós szubsztrátban
• neuronok axonokat, kimeneteket növeszthetnek más neuronok irányába és más neuronoktól fogadhatnak bejövõ axonokat
• szenzorok és az aktorok helyet foglalnak a kétdimenziós térben
• minden sejt tartalmazza a kromoszómába kódolt fastruktúrájú programot
• a csúcsok a háló kialakulását befolyásoló paraméteres utasítások
• lehetséges utasítások

  

• kezdetben szubsztrát méretének meghatározása, szenzorok és motorneuronok elhelyezése
• minden lábhoz tartozik egy prekurzor sejt, amiben az evolúciós program fut
• a DIVIDE utasítás hatására létrejön egy új sejt, ami örökli az eredeti programot és futtatni kezdi a DIVIDE alatti jobb oldali csúcson, a szülõ sejt a bal ágon folytatja a futást.
• a GROW vagy a DRAW hatására új kapcsolat keletkezik a megadott irányban

  

• a SETBIAS és a SETTAU utasítások a neuron funkcionális paramétereit határozzák meg
• neurondinamika: szivárgó összegzés modell (leaky integrator)

  

  

• bemenetek folyamatosan növelik, saját potenciájával arányosan folyamatosan veszít értékébõl
• a folyamat eléggé idõigényes: szintaktikai megszorítások, csak a nyelvtannak megfelelõ programok alakulhatnak ki, lábanként nyolc neuron és harminckét kapcsolat, a hat lábhoz ugyanaz a program tartozik

Az evolúciós folyamat

• szintaktikailag helyes programok gyûrûje
• tetszõleges pozíció kiválasztása, kettõ méretû környezetbõl a legjobb egyedet egy bajnokság során határozták meg
• 60 százalék a valószínûsége a keresztezõdésnek egy szomszéddal
• 20 százalék a valószínûsége a részfa elhagyásának és generálásának
• konstansok módosítása binomiális eloszlás alapján
• új egyed fitnesze a környezetbe helyezve derül ki
• populációba illesztéshez egy negatív bajnokság nyújt segítséget

Eredmények

• a láb mozgásának paraméterei

  

• fitneszfüggvény a megtett úttól és a láb mozgásának frekvenciájától függ, elesés nincs explicit módon büntetve

  

• a kísérlet: 100 ezer egyed kicserélése, 200 egyedet tartalmazó populációban
• öt futtatás, az egyik esetben a már ismert háromlábú járásmód alakult ki

  

• bal oldalán lévõ öt neuron a láb ritmikus felemelését végzi
• jobb oldal a hat láb egyesített mûködésének egy részletet tárja fel
• kiterjesztés egy újabb szubsztrát bevezetésével, mely serkenti és gátolja az eddigi neuronokat
• feladatok: elindulás, megállás, célkövetés, akadálykikerülés

Fejlõdõ ideghálózat

A hálózat kialakulása

• hagyományos és fejlõdõ hálózat
• genetikus kód mindkét esetben a neuronok fizikai elhelyezkedését és a kapcsolódások létrejöttét specifikálja
• fejlõdés során minden neuron meghatározott szögben, meghatározott mennyiségû axont növeszt

  

• az axonok nem minden esetben találnak neuronra

  

• hálónak lehetnek olyan neuronjai, melyek sem közvetve, sem közvetlenül nem kapcsolódnak szenzor- és motorneuronokhoz, ezek elhagyhatók

  

• érdekesség: a kromoszóma közvetlen vizsgálatával a kódolt egyed tulajdonságait nem lehet megállapítani

Az evolúciós eljárás

• a feladat 10 ételegység megtalálása egy kétdimenziós négyzetrácson
• szenzorok: legközelebbi étel iránya és távolsága
• motorok elfordulás szöge (-90,90), haladás sebessége (0-5)
• három neurontípus: szenzor, belsõ, motor
• A genotípus:
  • neuron kifejezõdése
  • neuron x koordinátája
  • neuron y koordinátája
  • elágazások szöge
  • szegmensek hossza
  • szinaptikus súlyok az axonokra (egységes)
  • küszöb
  • neuron típusa (irány/távolság, szenzor/motor)
• a futás során 100 egyed, 20 életciklus 250 lépéssel, 5 különbözõ környezetben
• a legjobb 20 szaporodhat, 5 utódot létrehozva
• összesen 25000 lépés 150 generáción át

A kontroller tulajdonságai

• a generációk legjobb egyedei:

  

• egyszerûek
• eleinte csak az étel és a haladás iránya számít, késõbb belép a haladási sebesség, majd az étel távolságának érzékelése
• logikus a szelekciós elõnyök ismeretében
• modulok felbukkanása szintén evolúciós elõny

Az egyedfejlõdés hatása

• génstruktúra módosítása: kifejezõdés helyett aktiválódási idõ
• a futtatás paraméterei változatlanok, kivéve, hogy csak 10 életciklus élhetnek az egyedek
• a generációk legjobb egyedei az elõzõhöz hasonlóak:

  

• moduláris felépítés, irány és sebesség csak késõbbi generációkban válik fontossá
• ismert biológiai szabály alátámasztása: az egyedek fejlõdése a faj fejlõdéséhez hasonlóan zajlik
• modulok jelentkeznek, az elõzõeknek megfelelõ módon és sorrendben
• minden komponensnek helyt kell állnia magában és a rendszer részeként is
• az ételek megtalálásának képessége az egyedfejlõdés során nõ
• az egyedek átlagosan az ötödik generációig változnak
• miért nem születnek rögtön felnõtt egyedek?
• az új hálózati elemek megjelenése egyformán jó és rossz lehet, az egyednek születéskor életképesnek kell lennie, kísérletezni szaporodás után kevésbé veszélyes
• az eredmények igazán látványosak, de a nagyon egyszerû neurális hálókból levont következtetések kissé nagyratörõek