15. tétel - Genetikus algoritmus I.

Mutassa be az evolúciós módszerek jellegzetességeit és alapvető lépéseit! Részletesen ismertesse a reprezentációs lehetőségeket (kromoszóma, populáció jellemzők)! Milyen fitnesz hozzárendelési módokat ismerünk (egyszerű fitnesz, rangsor, verseny)? Mik a kombinatorikai feladatok specialitásai?

Evolúciós módszerek jellegzetességei

  • Alapelvüket a természetes szelekcióból (evolúció) merítik.
  • Alapvető mechanizmusai:
    • természetes kiválasztás: a jobb képességű elemek
      • nagyobb eséllyel maradnak életben
      • nagyobb eséllyel szaporodnak
    • keresztezés: az új egyedek a kiválasztott szülők tulajdonságait öröklik valamilyen kombinációban
    • mutáció: a leszármazottak nem mindig öröklik teljes egészében a szülők tulajdonságait, a tulajdonságaik bizonyos valószínűséggel véletlenszerűen megváltoznak
    • legjobbak túlélése: a legjobb elemek jó eséllyel túlélnek
  • A keresési tér (\(𝕊\)) tartalmazza a megoldásjelölteket, amiket egyedeknek vagy kromoszómáknak nevezünk.
  • Többdimenziós tér esetén több paraméter értékét keressük, ezek a gének.
  • A módszer egyszerre több megoldásjelölttel dolgozik, ezeket nevezzük populációnak (\(P\)).
  • A módszer egy véletlenszerű állapotból indul.
  • Több iteráción keresztül finomítja az egyes egyedek paramétereit
  • Leállításkor azt várjuk, hogy a populáció egyedei jó fitnesz értékű megoldásjelöltek legyenek

Evolúciós módszerek alapvető lépései

Genetikus algoritmus

  1. InitializePopulation(): létrehozza a véletlen populációt
  2. Evaluation(): kiértékeli a populáció minden egyedét az átadott fitnesz függvény alapján, és minden egyed kap egy p.fitness értéket a saját jóságával.
  3. Kiválasztjuk a populáció legjobb fitneszű elemét, és eltároljuk egy pbest változóban
  4. Fő ciklus futtatása a megállási feltételig
  5. A kilépési feltétel után a legjobb egyed lesz a visszatérési érték

A fő ciklus felépítése

  1. Selection(): leendő szülők kiválasztása (\(M\) halmazba)
    • általában megengedett, hogy egy egyed többször is belekerüljön
  2. Létrehozunk egy \(P'\) halmazt, ide fognak kerülni a szülőkkel generált gyermek egyedek
  3. A belső ciklus addig tölti a \(P'\) halmazt, amíg az el nem éri a szükséges elemszámot
    • kiválaszt k darab szülőt az \(M\) halmazból (k tetszőlegesen beállítható)
    • ezekből lesz egy új egyed a CrossOver() függvény meghívásával
    • a Mutate() függvény meghívásával mutálódik az elem
    • elhelyezi az elemet a \(P'\) halmazban
  4. Reinsertion(): \(P\) és \(P'\) valamilyen kombinálásával előáll az új \(P\) halmaz
  5. Kiértékeljük az egyedeket, és kiválasztjuk a legjobbat

Folyamatábra

Folyamatábra 
flowchart TB

IP[Populáció létrehozása] --> EV[Kiértékelés] --> BEST[Legjobb elem mentése] --> S
subgraph MAIN[Fő ciklus]
    S[Szelekció M-be] --> CREATE_P
    CREATE_P["P' létrehozása"] --> PARENTS
    subgraph INNER["Belső ciklus: Populáció feltöltése"]
        PARENTS[k darab szülő választása M-ből] --> CROSS[Keresztezés] --> MUT[Mutáció]
        MUT --> ADD["Hozzáadás P'-hez"] -->ISFULL
        ISFULL{"P' tele van?"}
        ISFULL--"nem"-->PARENTS
        
    end
    ISFULL--"igen"-->REINS
    REINS["`Új *P* populáció készítése *P* és *P'* halmazokból`"] --> MAIN_EV
    MAIN_EV[Kiértékelés] --> MAIN_BEST[Legjobb elem mentése]
    MAIN_BEST --> STOPCOND{Megállási feltétel teljesül?}
    STOPCOND--"nem"-->S

end
STOPCOND--"igen"--> STOP["Leállás, legjobb elem vissza"]

Kromoszóma reprezentáció

flowchart TB
KR["Kromoszóma reprezentáció"]

J["Gén reprezentáció"]
Geno["Genotípus jellegű"]
Feno["Fenotípus jellegű"]
Perm["Permutációs"]

H[Kromoszóma hossza]
FH[Fix hosszúságú]
VH[Változó hosszúságú]

KR --> J & H
J --> Geno & Feno & Perm
H --> FH & VH

Gén reprezentáció

Milyen formában szeretnénk a kromoszómák adatait tárolni?

  1. Genotípus jellegű tárolás: a kromoszómát egy bitsorozatként írjuk le
    • legegyszerűbb a számértékek tárolása bináris formában
      • de ennek van egy hátránya: az egymás melletti számok Haming-távolsága különböző, így egy bit megváltoztatása lehet kicsi vagy nagy változás is
      • ezért jobb a Gray-kódolás, ahol a számok Haming távolsága 1.
  2. Fenotípus jellegű tárolás: a kromoszóma közvetlenül a megoldás adatait tartalmazza
    • a kereső algoritmus feladata, hogy a vektor elemeinek lehetséges intervallumait figyelembe vegye
  3. Permutációs ábrázolás: az egyes gének itt nem függetlenek egymástól, hanem mindig egy adott készlet elemeit tartalmazzák különféle sorrendben

Milyen legyen a kromoszóma hossza?

  1. Fix hosszúságú: egyszerű, az egyedekkel végzett műveletek ugyanolyan hosszú egyedet fognak eredményezni
  2. Változó hosszúságú:
    • pl. útkeresési problémánál nem tudjuk előre, hogy milyen hosszú utat keresünk
    • keresztezésnél a szülő kromoszómák hossza eltérhet
    • mutációnál változhat a kromoszóma hossza

Fitnesz-hozzárendelési módok

  1. Egyszerű fitnesz hozzárendelés:
    • egy darab fitnesz függvény van, ami minden egyedhez tud rendelni egy számot
    • a fitnesz érték jelentéssel bírhat, pl. két elem között nagy a fitnesz különbség => az egyik sokkal jobb mint a másik
    • nem mindig használható
  2. Rangsor alapú:
    • ha nem tudunk pontos értéket rendelni az elemekhez, de össze tudjuk őket hasonlítani
    • a rendezettséget használjuk fitnesz értékként
    • pl. pareto dominanciával is meg lehet adni a fitnesz értéket
  3. Verseny alapú:
    • a rangsor alapú hozzárendelés számításigénye nagy, ehelyett használhatunk közelítő számításokat
    • \(t\) szintű bináris verseny: minden elem lejátszik \(t\) darab versenyt, és megszámoljuk, ki hányszor győzött

Kombinatorikai feladatok sajátosságai

A kromoszómák permutációs ábrázolása

A kombinatorikai feladatoknál a permutációs kormoszóma reprezentáció használható. Lásd a Gén reprezentáció részben.

Keresztezés kombinatorikai feladatokban

  1. Uniform sorrend alapú keresztezés
    • két szülőből egy utód, megtartva a gének szülőkön belüli relatív sorrendjét
    • lépések (példa a jegyzetben):
      1. egy véletlen bitmaszkot állít elő, ami ugyanolyan hosszú, mint az egyes kromoszómák
      2. ahol a bitmaszk értéke 1, oda átmásolja az egyik szülő génjeit
      3. a második szülő alapján tölti fel a maradék géneket
        • sorbaveszi a második szülő azon génjeit, amik még hiányoznak a gyerekből
        • ezeket olyan sorrendben tölti fel, ahogy a 2. szülőben vannak
  2. Edge rekombináció
    • a szülőkben a gének szomszédsági viszonyait vizsgálja, ezeket igyekszik átvinni a gyerekbe
    • picit hosszú és példa nélkül nehezen érthető, itt van a jegyzetben

Mutáció kombinatorikai feladatokban

  • korlátozottabban működnek a mutációs műveletek
  1. Csere: a kromoszóma két tetszőleges génjét megcseréljük
  2. Invertálás: kiválasztunk egy szakaszt a kromoszómán belül, és ebben a gének sorrendjét megfordítjuk