Ugrás a tartalomhoz

Alkalmazott Mesterséges Intelligencia

Dudás László (2011)

Kempelen Farkas Hallgatói Információs Központ

Részecske-raj alapú optimálás (Particle swarm optimization, PSO)

Részecske-raj alapú optimálás (Particle swarm optimization, PSO)

Forrás: Particle swarm optimization - Wikipedia

A számítástudományban a részecske-raj alapú optimálás egy számítási módszer, mely iteratív módon optimalizál, megpróbálva egy megoldásjelölt minőségét fejleszteni, javítani. Ezek a technikák általánosságban metaheurisztikaként ismertek, mivel kevés, vagy semmi követelményt nem támasztanak az optimálandó feladattal szemben és a megoldásjelöltek hatalmas terében képesek keresni. Azonban, a metaheurisztikák, mint a részecske-raj alapú optimálás is, nem garantálják, hogy valaha is megtalálják az optimális megoldást.

Még konkrétabban, a részecske-raj optimálás nem használ gradienst az optimálandó problémában, ami egyúttal azt is jelenti, hogy nem igényli, hogy az optimálandó jellemző az állapottéren differenciálható legyen, mint ahogy az elvárás a gradiens módszer, vagy a kvázi-Newton módszerek esetében. A részecske-raj alapú optimálás emiatt olyan problémák esetén is alkalmazható, melyek részben szabálytalanok, hibákkal terheltek – zajosak –, időben változnak, stb. (Ebben hasonlítanak a Tabu keresésre, vagy a genetikus algoritmusra.)

A részecske-raj alapú optimálás a problémát a megoldásjelöltek, azaz részecskék populációján keresztül optimálja (v.ö. evolúciós algoritmusok), egyszerű matematikai formulák segítségével mozgatva ezeket a részecskéket a keresési térben. A részecskék mozgását a legjobb megtalált keresési tér pozíciók vezetik, amelyek frissítődnek, amint jobb pontokat találnak a részecskék.

A részecske-raj alapú optimálást eredetileg Kennedynek, Eberhartnak és Shinek tulajdonítják, és legelőször szociális viselkedés szimulálására szánták (Kennedy, J.; Eberhart, R. , 1995; Shi, Y.; Eberhart, R.C. , 1998). Az algoritmust egyszerűsítették és optimálásra alkalmasnak találták. Kennedy és Eberhart könyve (Kennedy, J.; Eberhart, R.C. , 2001) számtalan filozófiai aspektusát leírja a részecske-raj alapú optimálásnak és a raj-intelligenciának. A részecske-rajon alapuló optimálást használó alkalmazások kiterjedt áttekintését találjuk Poli műveiben (Poli 2007, 2008).

A részecske-raj alapú optimálás algoritmusa

Az algoritmus alapvariációja a megoldásjelöltek (részecskék) egy populációjával (nevezzük rajnak) dolgozik. Ezek a részecskék a keresési térben néhány egyszerű matematikai formulának megfelelően mozognak. A részecskék mozgását a keresési térben a saját ismert legjobb pozíciójuk, valamint a teljes raj ismert legjobb pozíciója határozza meg. Amikor jobb pontokat találnak ezek veszik át a raj vezérlő szerepét.

Formálisan, legyen f(p) a tér p pontjához tartozó, n dimenzióról 1 dimenzióra leképező fitness, vagy költségfüggvény, melyet minimalizálni kell. A függvény az n dimenziós, valós elemekből álló p argumentum alapján egyetlen valós függvényértéket ad, mely jelzi a p megoldásjelölt jóságát. Az f() függvény gradiense nem ismert. A cél egy a pont megtalálása a keresési térben, melyre f(a) ≤ f(b), ahol b a keresési tér bármely pontja lehet, magyarul az a pont globális minimumhely. Maximálás hasonlóan végezhető, ha f() ellentettjével dolgozunk.

Legyen N a részecskék száma a rajban. Minden i. részecskét (i = 1,…,N) jellemez az xi helye és a vi sebessége. Legyen továbbá pi az i. részecske (particle) eddigi legjobb értéket adó pozíciója a keresési térben, g pedig a raj (group, global) eddigi legjobb pozíciója. Ezekkel az alapalgoritmus:

  • Inicializálás minden egyes i = 1,…,N részecskére:

    • Inicializáld a részecske pozícióját a keresési téren egyenletes eloszlású véletlen vektorral: xi ← RandomPozició();

    • Inicializáld a részecskék eddigi legjobb pozícióját a kezdő pozíciójukkal: pixi

    • Ha i = 1, gp1, egyébként ha f(pi) < f(g), akkor frissítsd a raj legjobb pozícióját: gpi

    • Inicializáld a részecskék sebességvektorát (elmozdulásvektorát) a keresési térben elférő nagyságú, de ezen belül tetszőleges, egyenletes eloszlású véletlen értékű és véletlen előjelű komponensekből álló elmozdulásvektorokkal: vi ← RandomElmozdulásvektor();

  • Ismételd, amíg a leállási kritérium nem teljesül:

    • Minden egyes i = 1,…,N részecskére:

      • Végy a 0,…,1 valós tartományból két egyenletes eloszlású valós véletlenszámot: rp, rg

      • Frissítsd a részecskék sebességét (elmozdulásvektorát): vi ← ωvi + φprp(pi - xi) + φgrg(g - xi)

      • Frissítsd a részecskék pozícióját: xixi + vi

      • Ha a részecske jobb pontba került, azaz f(xi) < f(pi), jegyezd meg:

        • A részecske talált új jobb pozícióját: pixi

        • Ha ez jobb, mint a raj eddigi legjobbja (f(pi) < f(g)), akkor a raj legjobbját is: gpi

  • Ha a leállás bekövetkezett, g megadja a megtalált addigi legjobb, szerencsés esetben kvázioptimális minimumpontot.

Leállási kritérium lehet az iterációk számára megadott korlát teljesülése, vagy megfelelő fitnessérték elérése. Az ω, φp és φg paramétereket gyakorlati tapasztalatok alapján választjuk, ezekkel lehet kontrollálni az algoritmus viselkedését és változtatni a hatékonyságát.

Paraméterválasztás

Az ω, φp és φg paraméterek helyes megválasztása erőteljes kihatással bír a részecske-raj alapú optimálás hatékonyságára. (Egy másodlagos belső optimálási feladat…) A megfelelő paraméterértékek megválasztásával ezért sok kutatás foglalkozott, lásd pl. (Shi és Eberhart , 1998b), (Eberhart és Shi, 2000). A paramétereket egy másodlagos optimálóval is hangolhatjuk, ezt az elvet meta-optimálásként ismerik (Meissner és társai, 2006).

Belső működés

Többféle iskola létezik aszerint, hogy vajon milyen módon hajtja végre az optimálást a részecske-raj alapú módszer?

Minden kutató egyetért abban, hogy a raj viselkedése felfedező és hasznosító szakaszokra bomlik. Míg az első a keresési tartomány minél szélesebb tartományának feltárását jelenti, a másodikban egy lokális jellegű folyamatban határolja be pontosabban a (feltehetően lokális) optimumhelyet. Ezt az iskolát képviselik a módszer felfedezői is. Véleményük szerint az algoritmus paramétereinek megfelelő megválasztásával a keresés ezen két szakasza között egyensúlyozhatunk, megakadályozva a korai lokális optimumba ragadást. A paraméterek megválasztásából többféle algoritmus-variáció ered.

A másik iskola úgy képzeli, hogy az algoritmus viselkedését nem értjük olyan jól abban az értelemben, hogy a paraméterek megválasztása hogyan hat az aktuális eredményességére, különösen nem magasabb dimenziójú állapotterek és nemfolytonos, zajos és időben változó optimálási problémák esetén. Ez az iskola egyszerűen megpróbál olyan algoritmusokat és paramétereket találni, amely jó hatékonyságot eredményez függetlenül attól, hogy a raj viselkedése felfedezőnek, vagy hasznosítónak minősíthető-e. Ezek a tanulmányok vezettek az algoritmus egyszerűsítéséhez.

Konvergencia

Az algoritmus esetében a konvergencia kétféle dolgot is jelenthet, bár gyakran nem tisztázott, hogy melyiket értik és hibásan gondolják azonosaknak.

  • A konvergencia vonatkozhat a raj g legjobb ismert pozíciójának a probléma optimumához való tartására, a raj viselkedésétől függően.

  • A konvergencia vonatkozhat a raj összehúzódására, amelyben az összes részecske tart a keresési tér egy pontja felé, mely egyaránt lehet az optimum, vagy más pont.

Bár történtek próbálkozások a konvergencia egzakt matematikai leírására, lásd a Forrást, az eredmények nem egyértelműek és az algoritmus sokszínűsége miatt változatosak. Mindenesetre, a paraméterek okozhatnak konvergenciát, divergenciát és oszcillálást is a raj részecskéinél.

Variánsok

Még az alap algoritmusnak is számtalan variációja lehetséges, pl. az inicializálás variálásával. Új és finomított variációk folyamatosan jelennek meg a hatékonyság növelésének célzatával. Jelen van a hibrid optimálás irányába ható irányzat is. Több módszer, mint pl. a paraméterek keresés közbeni dinamikus változtatása jól ismertek pl. a szimulált lehűtés, vagy a mesterséges neurális hálók tanulási algoritmusaiból. Valószínűleg az algoritmus alkalmazása inkább problémaspecifikus, és a tapasztalat a próbák fontosságát emeli ki.

Egyszerűsítések

Egy másik irányzat a sokszínűség helyett az algoritmus anélküli egyszerűsítését célozza, hogy a hatékonysága jelentősen csökkenne, ehhez gyakran Occam borotvája elvét hivatkozva.

Kapcsolódó témakörök

A részecske-raj alapú optimálás alkalmazása előtt célszerű tanulmányozni a

  • Raj intelligencia és a

  • Méhecske/ Mesterséges méhecske kolóniák, hangyakolóniák

algoritmusait.

A következőkben a részecske-raj alapú optimálást humanoid robotok helyváltoztatásának modellezésében hasznosító tanulmányt mutatunk be (Rokbani és társai, 2009) műve alapján.