19. tétel - Raj alapú módszerek

Mutassa be a raj alapú módszerek jellemzőit! Részleteiben ismertesse a Particle Swarm Optimization eljárást! Milyen jellemzőik vannak az egyes egyedeknek és a populációnak? Mi történik az egyes iterációkban? Értékelje a módszert!

Alapelv

  • Biológiailag inspirált algoritmusok, a madár- és hajrajok mozgásán alapulnak.
  • Ezek az állatok képesek a hatékony együtt mozgásra, pedig nincs kitüntetett vezető, aki irányítana
  • Minden pozícióhoz hozzárendelünk egy fitnesz értéket
  • A raj célja, hogy minél közelebb kerüljenek az alacsonyabb fitneszű területekhez az alábbi szabályok betartásával:
    1. az egyedek között nincs kitüntetett vezető
    2. mindenki ismeri a raj által eddig elért legjobb pontot (globális optimum)
    3. mindenki ismeri az önmaga által eddig elért legjobb pontot (lokális optimum)
  • Tehát itt a globális és lokális optimum mást jelent, mint ahogy eddig használtuk.
  • Egy véletlen kiindulópont és kiértékelés után az egyedek mozogni kezdenek.
    • Ehhez súlyozottan figyelembe veszik:
      1. az eddigi mozgási irányukat,
      2. a globális optimum helyét, és
      3. a lokális optimum helyét,
    • ezek alapján állapítják meg a pillanatnyi sebességüket.

Megvalósítás

Particle Swarm Optimization

Particle Swarm Optimization kiértékelő része

A rendszer lépései

Folyamatábra 
flowchart TB
IN["`**Inicializálás**
*(kezdőpontok, kezdősebességek)*`"] --> EV
EV["`**Kiértékelés**
*(optimumok esetleges módosítása itt történik)*`"]
STOPCOND{"Megállási feltétel teljesül?"}--"igen"-->STOP
V["Sebességek meghatározása"] --> M
M["Mozgatás"] --> EV --> STOPCOND --"nem"--> V
STOP["Leállás, vissza gpm(g_opt)"]

  1. Inicializálás: A keresési térben véletlenszerűen kiválasztjuk a kezdőpozíciókat és kezdősebességeket.

  2. Kiértékelés:: Minden egyed megállaptíja a saját fitneszét, majd ennek megfelelően módosítja a globális és lokális optimumok értékét

  3. Sebességek meghatározása: Minden egyed megállapítja a saját sebességvektorát. Ehhez figyelembe tudja venni az aktuális pozícióját, sebességét, illetve a globális és lokális optimumokat.

  4. Mozgatás: A sebességnek megfelelően módosítjuka pozíciót

  5. Kiértékelés: Újra kiértékeljük az egyedeket, szükség esetén módosítva a globális és lokális optimumok értékét.

  6. A fenti lépéseket addig ismételjük, amíg nem teljesül valamelyik megállási feltétel.

A függvény visszatérési értéke a globális optimumhoz tartozó problématérbeli megoldás lesz.

A sebesség meghatározása

A sebesség fogalom bármi lehet, de támogatnia kell az alábbi követelményeket:

  1. két pozíció különbsége egy sebesség legyen
  2. sebességet meg lehessen szorozni egy skalár értékkel
  3. össze lehessen adni két sebességet
  4. egy pozícióhoz hozzá lehessen adni egy sebességet

Az új sebesség megállapítás jellemzően az alábbiakon alapul:

  1. jelenlegi sebesség
  2. globális optimum iránya az aktuális pozíciótól
  3. lokális optimum iránya az aktuális pozíciótól

Ezeket a tényezőket súlyozzuk, esetleg véletlen számokkal kombináljuk.

Sebesség meghatározása a PSO-ban

Értékelés

Előnyök

  • Nagy keresési tereknél jó, jól át tudja fésülni
  • Amikor közelít a globális optimumhoz, lassulnak az egyedek (az átlagszámításnak megfelelően)
  • Jól párhuzamosítható

Hátrányok

  • Sok paramétere van, nehezen konfigurálható
  • Csak szám keresési terekben működik