17. tétel - Genetikus programozás

Milyen esetekben célszerű használni a genetikus programozást? Miként építhető fel a programfa, milyen követelményeknek kell teljesülniük? A módszer miben különbözik a klasszikus genetikus algoritmusoktól (reprezentáció, fitnesz számítás, mutáció)? Milyen genotípus-fenotípus leképezéseket ismer?

Alapelv

  • Automatikus programkészítő módszer
  • Olyan programot akarunk készíteni, ami a lehető legkisebb hibával tudja megoldani a kitűzött feladatot
  • Hasonló a genetikus algoritmushoz
    • annyi, hogy itt a keresési tér a lehetséges programok tere

A programfa felépítése

  • Az összetett kifejezéseket általában jól lehet reprezentálni egy fával
  • A fa levélelemei önmagukban kértékelhető elemek (terminális elemek) lehetnek:
    • konstansok,
    • változók
    • input értékek
    • paraméter nélküli függvények
  • A fa belső pontjai mindig műveletek
    • az alattuk lévő egy vagy több elemmel végeznek el valamilyen műveletet
    • az eredményt továbbítják a szülőjük irányába
    • a műveletek lehetnek:
      • aritmetikai műveletek,
      • logikai műveletek,
      • vezérlési szerkezetek (if, for, stb.)
      • egyéb saját függvények
  • A fa gyökérpontja kitüntetett szerepű, ez adja meg a teljes program kimenetét
  • a bemeneteket tehát rákapcsoljuk a levélpontokra, majd kiértékeljük a teljes fát
  • a terminális elemek a \(T\) halmaz elemei, míg a műveletek az \(F\) halmaz elemei.

Validációs követelmények

\(T\) és \(F\) halmaznak teljesítenie kell az alábbi követelményeket:

  1. Zártság:
    • az egyes műveletek eredménye bemenete lehet bármelyik másik műveletnek
    • ez azért fontos, hogy a keresztezés/mutáció során ne álljanak elő szintaktikailag helytelen megoldásjelöltek
  2. Elegendőség:
    • a problémának megoldhatónak kell lennie \(T\) és \(F\) halmaz elemeiből építkezve

Azt is garantálni kell, hogy a programfa kiértékelhető, az általa képviselt program futtatható legyen.

  • Célszerű alapból úgy megadni az utasításokat, hogy azok teljesen hibatűrőek legyenek
    • tehát egy utasítás ne akadjon el azon, hogy eggyel több vagy kevesebb operandust kapott
    • célszerű értelmet adni a valóságban értelmezhetetlen műveleteknek
      • pl. 0-val osztás
    • a módosított fákat grammatikai elemzésnek vethetjük alá, majd javíthatjuk a hibákat automatikusan
    • eleve úgy készíthetjük el a keresztezés és mutáció műveleteket, hogy azok csak szintaktikailag helyes fákat tudjanak létrehozni
    • egy másik lehetőség, hogy a kereső algoritmus nem látja közvetlenül a fát, csak egy alacsonyabb szintű reprezentációját
      • pl egy bitsorozatot
      • a kifejezésfa fenotípus, a genotípus ennek a reprezentációja
        • a kettő között megfelelő gpm-mel elérhető, hogy mindig helyes fát kapjunk

Fitnesz

Definiálnunk kell valamilyen formában a fitneszt.

Lehet pl:

  • boolean: jól működik / nem működik jól a program
    • ennél célszerűbb valami árnyaltabb, hogy a fitnesz arányok felhasználhatóak legyenek
  • tanítási minta:
    • megadunk egy vagy több elvárt bemenet-kimenet párt
    • a feladat olyan program összeállítása, ami a megadott bemenetekre a megadott kimeneteket adja
    • a fitnesz ekkor a program által készített kimenetek és a referenciakimenetek távolságainak összege
  • szabályok meghatározása:
    • megadunk egy szabályt, hogy mit tartunk jó megoldásnak
    • pl. útkereső algoritmusnál megadjuk, hogy milyen közelre kell jusson a célponthoz

További részcél lehet, hogy az algoritmus legyen minél rövidebb, futásideje legyen minél kevesebb (ezek csak másodlagos célok általában).

Megvalósítás

Alapvetően teljesen azonos a genetikus algoritmussal, gyakorlatilag ez is egy evolúciós módszer.

Milyen eltérések vannak ahhoz képest?

Kezdőpopuláció létrehozása

Itt is megadott számú véletlen elemet hozunk létre, de általában változó hosszúságú a kromoszóma.

A hosszúságot korlátozhatjuk:

  • megadjuk a maximális műveleti darabszámot
  • megadjuk a fa maximális mélységét (\(d\))
    • ennek megfelelő generálási módszerek:
      1. full: minden gyökér → levél út hossza legyen \(d\)
      2. grow: minden gyökér → levél út hossza legyen maximum \(d\)
      3. ramped half-and-half: a populáció egyik része full, a másik része grow módon lesz generálva

Keresztezés

  1. Mindkét fát elvágjuk egy ponton
  2. Az egyik fának megtartjuk a gyökérből kiinduló részét
  3. A vágási pontra ráillesztjük a másik fa vágás alatti részét

Ez gyakorlatilag a genetikus algoritmusoknál megismert egypontos keresztezés.

Mutáció

Nem fix a kromoszóma méret → sok féle mutációs lehetőség

  • Csomópont cseréje egy újra
    • \(T\)-beli elemet csak \(T\)-belire, \(F\)-belit csak \(F\)-belire lehet cserélni
  • Új csomópontok, részfák beszúrása
    • levélből nem lehet belső pontot csinálni, szóval csak a fa belsejébe lehet beszúrni
  • Csomópontok, részfadarabok törlése
    • belső pontok nem kerülhetnek levél szerepbe
  • Művelet gyerekeinek sorrendjének megváltoztatása

Speciális műveletek

Ilyenek nem voltak a genetikus algoritmusnál.

  1. Fa egyszerűsítése: ugyanazon eredmény elérése kevesebb csomóponttal
  2. Részfák rögzítése: egy részfa elemeit egységként kezeljük, ekkor terminálisként viselkedik

Genotípus-fenotípus leképezések

JB mapping

  • a kromoszóma egész számokból álló tömb
  • hagyományosan ezen belül minden utasítás egy számhármas (opcode, operandus1, operandus2)
  • előzetesen készítünk egy kódtáblát, hogy melyik azonosító melyik művelethez tartozik, és hogyan használják az operandusokat
  • gépi kódhoz hasonlít

Gene Expression Programming

A kromoszóma kupacszerűen tárolja el az adatokat, de a szekvenciálisan tárolt megoldás egy fát reprezentál

  1. az adatok első fele a fejléc
    • ebben lehetnek műveletek és terminálisok is
  2. a másik fele a farok rész
    • ebben már csak terminális lehet

A fa így biztosan valid lesz.

  • a műveletek megadják a fa alakját
  • a farokrészből csak annyi operandust használ fel, amennyire szüksége van