1. Uvod

Optimizacija rojem čestica (Particle Swarm Optimisation, PSO) je stohastični algoritam koji se bazira na populaciji rješenja. Pripada skupini algoritama inteligencije roja (Swarm inteligence) koji se temelje na sociološko-psihološkim principima i pružaju uvid u sociološka ponašanja te pomoću njih pridonose inženjerskim aplikacijama. Osmislili su ga dvojica znanstvenika: James Kennedy i R. C. Eberhart ne tako davne 1995. godine. Motivaciju su pronašli u društvenom ponašanju raznih tipova organizama poput jata ptica ili ribljih plova. Tehnike programiranja su otada uvelike unaprijeđene, a originalan algoritam je gotovo i neprepoznatljiv u odnosu na današnje verzije.

1.1. Prirodno uporište

Promatramo jato ptica koje će svoj položaj mijenjati vođeno instinktom za hranjenjem. Sve ptice u jatu traže hranu na nekom prostoru. Vrlo je vjerojatno da će jato slijediti onu pticu koja je osjetila ili pronašla dobar izvor hrane. No, svaka ptica pojedinačno u sebi ima instinkt kojim želi za sebe pronaći još bolje hranilište, a kako bi to i postigla ona se nakratko odvaja od jata. Samim pronalaskom boljeg hranilišta, pomogla je jatu u cjelini jer će se ostale ptice preseliti na bolje hranilište. [2]

1.2. Socijalno uporište

Socijalni utjecaji i društveno učenje pomažu osobi da lakše spozna samu sebe tj. da uspostavi kognitivnu stabilnost. Ljudi rješavaju probleme razgovarajući jedan s drugim i prilikom interakcije s drugim ljudima njihova vjerovanja, pogledi na probleme i ponašanje se mijenjaju (u sociokognitivnom prostoru te se promjene prikazuju kretanjem individualaca). Nadalje, neki znanstvenici predlažu da znanje biva optimizirano socijalnom interakcijom i da razmišljanje nije samo privatno nego i interpersonalno.

PSO kao optimizacijsko oruđe pruža procedure za pretragu bazirane na populaciji u kojoj individualci (čestice) mijenjaju svoju poziciju (stanja) u vremenu. U skladu s tim, u PSO sustavu koji je inicijaliziran populacijom nasumičnih rješenja - česticama, čestice lete po multidimenzionalnom prostoru za pretraživanje. Za vrijeme leta, svaka čestica podešava svoju poziciju na bazi vlastitog iskustva i na temelju iskustva svojih najbližih susjeda te sa tim znanjima iskorištava najbolju poziciju na koju je naišla ona sama ili njen susjed. Detaljnije, svaka čestica unutar sustava pamti koordinate unutar prostora problema koje predstavljaju najbolje dosad postignuto rješenje te čestice. Nazovimo tu vrijednost vlastito najprikladnije rješenje (personal_best). Ako se u roju odrede međusobni susjedi svake čestice, čestica mora pamtiti i najbolje rješenje do kojeg je došla bilo koja susjedna čestica naše promatrane čestice (local_best). Ukoliko su sve čestice međusobni topološki susjedi, najbolje rješenje takvog roja je globalni optimum (global_optimum). Takvi načini pretraživanja imaju svoje prednosti, ali i mane. Tako će traženje lokalnog optimuma bolje istražiti prostor rješenje, no konvergencija će biti sporija.

PSO sustav iskorištava metode lokalnog i globalnog pretraživanja.

PSO dijeli mnogo sličnosti sa tehnikama evolucijskog računanja poput genetičkih algoritama (GA). Pomoću PSO-a optimum se traži obnavljanjem generacija. Za razliku od GA, u PSO algoritmu ne postoje evolucijski operatori kao što su krosoveri ili mutacije. [3]

2. Opis algoritma

2.1. Matematička formulacija

Roj čestica je u prirodi stohastičan; on iskorištava vektor brzine kako bi ažurirao trenutnu poziciju svake čestice u roju. Vektor brzine se ažurira na temelju pamćenja svake čestice, što koncepcijski odgovara autobiografskoj memoriji, kao i na temelju znanja koje je stekao roj kao cjelina. Pozicija čestice u jatu je ažurirana na temelju socijalnog ponašanja roja koji se prilagođava svom okruženju stalnim traženjem boljih pozicija tokom vremena.

Numerički, pozicija x čestice i u iteraciji k+1 je ažurirana na sljedeći način:

(2.1)

pri čemu je pripadajući ažurirani vektor brzine, a je vrijednost vremenske step funkcije. Vektor brzine svake čestice se računa kao:

(2.2)

Pri čemu je vektor brzine u iteraciji k, i su najbolja ikad pozicija čestice i globalna najbolja pozicija čitavog roja sve do trenutne iteracije k, dok r predstavlja nasumični broj iz intervala [0, 1]. Preostali članovi su konfiguracijski parametri koji igraju važnu ulogu u konvergencijskom ponašanju PSO-a. Član c₁(kognitivni, samospoznajni parametar) predstavlja stupanj povjerenja u najbolje rješenje do kojeg je došla pojedina čestica dok član c₂ (socijalni, društveni parametar) predstavlja stupanj povjerenja u globalno najbolje rješenje (najbolje pronađeno rješenje od jata kao cjeline). Uglavnom se uzima 1.8≤c₁ = c₂≤ 2.2. Posljednji član ω je inercijska varijabla koja je iskorištena za kontroliranje istraživačkih sposobnosti roja tako da skalira vrijednost trenutne brzine te na taj način utječe na iznos ažuriranog vektora brzine. Većim vrijednostima inercijske varijable vršimo globalno pretraživanje zbog toga što se ažurirani vektor brzine brže povećava dok zadavanjem manje vrijednosti inercijske varijable vrijednost ažuriranog vektora brzine postaje manja pa se tako novi položaj čestice ograničava na manje područje prostora istraživanja tj. omogućujemo lokalno pretraživanje.

Slika 2.1 Promjena položaja

Na slici se vidi pozicija čestice i ažuriranje vektora brzine na prethodno opisan način u dvodimenzionalnom prostoru. Isto tako je vidljivo da će ažurirani položaj čestice ovisiti ne samo o najboljim pozicijama roja i čestice samo, već i o veličini konfiguracijskih parametara. [4]

2.2. Kanonski algoritam

Predloženi algoritam upotrebljava globalno i lokalno najprikladnije rješenje, no ne i susjedno najprikladnije rješenje. Susjedna prikladna rješenja dopuštaju paralelizam u istraživanju prostora i smanjuju mogućnost upadanja u lokalni minimum, no smanjuju brzinu konvergencije.

Samostalno čestica ne može postići ništa, za uspjeh je potrebna suradnja s ostalim česticama roja.

Neka je funkcija prikladnosti koja uzima rješenje čestice iz višedimenzionalnog prostora i prepisuje ju u jednodimenzionalni prostor. Neka postoji n čestica i neka je svakoj dodijeljena pozicija i brzina . Neka je trenutno najprikladnije lokalno rješenje svake čestice, a neka predstavlja najprikladnije globalno rješenje.

Kao i ostali numeričko bazirani optimizacijski pristupi, PSO je po svojoj prirodi iterativan, a njegov osnovni algoritam je konstruiran na sljedeći način:

• Inicijaliziraj x_i i v_i za sve i.
• i
• Dok nije došlo do konvergencije
• Za svaku česticu 1≤i≤n
• Stvori nasumične vektore r₁, r₂
• Ažuriraj poziciju čestice: x_i←x_i+v_i
• Ažuriraj brzinu čestice:
• Ažuriraj najprikladnije lokalno rješenje: ako je
• Ažuriraj najprikladnije globalno rješenje: ako je
• je najbolje rješenje s prikladnošću

Promotrimo sljedeće parametre navedenog algoritma:

• ω je inercijalna konstanta čije su vrijednosti najčešće manje od 1.
• c₁ je kognitivni parametar koji predstavlja vrijednost samospoznaje čestice, odnosno najboljeg lokalnog rješenja, dok je c₂ društveni parametar koji predstavlja važnost društva, odnosno globalno najprikladnijeg rješenja. Ova dva koeficijenta se nazivaju još i koeficijenti povjerenja.
• r₁ i r₂ su dva nasumična vektora čije komponente poprimaju vrijednosti iz intervala [0, 1]. [3]

2.3. Pseudokod

Slika 2.2 Pseudokod PSO algoritma [3]

3. Primjene

Vrlo popularno područje primjene PSOa je dizajn antena – kontrola i dizajn faznih polja, dizajniranje i modeliranje širokopojasnih antena, ispravljanje grešaka u polju, dizajniranje ugradbenih antena…

Sljedeće važno područje primjene nalazimo u biomedicini gdje se PSO upotrebljava u svrhu detekcije Parkinsonove bolesti na temelju drhtavice, optimizacije biomehaničkog ljudskog pokreta, klasifikacije raka i predviđanja ostatka života, dizajniranje lijekova…

U području komunikacijskih mreži, PSO se koristi u dizajniranju bluetooth mreža, za usmjeravanje, za izgradnju radarskih mreža, rezervaciju pojasa…

U području kombinatoričkih problema, PSO služi za rješavanje problema trgovačkog putnika, optimizaciju puta, za rješavanje problema naprtnjače i N-kraljica…

Dizajn je jedno popularno područje koje je u IEEE zastupljeno s 5% bibliografije, a ono uključuje: dizajniranje motora, antena, filtera, dizajn kuhala, konceptualni dizajn…

Dizajniranje i restrukturiranje električnih mreža zauzima 7% bibliografije, a u ovo područje primjene spadaju širenje i rekonfiguracija mreža, distribuirano stvaranje te regulacija napona…

U kombinaciji s neuralnim mrežama, PSO se koristi za inverziju neuralnih mreža, kontrolu neuralnih mreža za nelinearne procese, za kontrolu mobilnih neuralnih mreža i za izgradnju neuralnih kontrolora.

PSO se koristi i u funkciji predviđanja kvalitete i klasificiranja vode, u predviđanju ponašanja kaotičnih sustava, u ekološkim modelima, u meteorološkim predviđanjima, za predviđanje migracije slonova te gradskog prometa.

Uz navedena, PSO se upotrebljava i u sljedećim područjima: enegteski sustavi, robotika, raspoređivanje, sigurnost i vojska, mreže senzora, procesiranje signala, modeliranje, metalurgija, zabava, financije, grafika i vizualizacija, motori te elektrotehnika.

S obzirom da PSO algoritam ima više svojih inačica te da se iz njega izrodilo već nekoliko novih podvrsta (npr. RPSO), u nastavku ću opisati jednu, u literaturi ne tako često spominjanu verziju – plemena. [11]

4. Zaključak

Od kada se PSO razvio prije otprilike 13 godina, autori vjerojatno nisu ni mogli zamisliti koliki će utjecaj taj algoritam imati na današnji računarski svijet. Idejno maštovit i kreativan, gotovo multidisciplinaran, no istovremeno, u svojoj suštini, prirodan te, najbitnije, programski lagan za implementaciju, PSO oduševljava svojim mogućnostima implementacije u najrazličitijim područjima ljudskog djelovanja, od biologije i medicine, preko elektronike, elektromagnetizma, kombinatoričkih problema, analize sustava do robotike. Ono što je posebno zanimljivo je trend rasta primjena ovog algoritma. U posljednjih nekoliko godina primjene ovog algoritma narasle su eksponencijalno i ne čini se da trend trenutno pada.

Zbog svoje jednostavnosti i jednostavne mogućnosti prilagodbe, PSO je lako testirati te ostvariti novu verziju koja više odgovara specifičnom optimizacijskom problemu.

5. Literatura

[1] Maurice Clerk, TRIBES a Parameter Free Particle Swarm Optimizer, 2.10.2003., TRIBES a Parameter Free Particle Swarm Optimizer, http://clerc.maurice.free.fr/pso/Tribes/Tribes_doc.zip, 28.10.2008.
[2] Particle swarm optimization - Wikipedia, the free encyclopedia, 16.10.2008., Particle swarm optimization - Wikipedia, the free encyclopedia, http://en.wikipedia.org/wiki/Particle_Swarm_Optimization, 28.10.2008.
[3] Goran radanović, Pregled heurističkih algoritama, Pregled heurističkih algoritama, http://www.zemris.fer.hr/~golub/ga/studenti/seminari/2007_radanovic/index.html, 16.10.2008.
[4] C. K. Mohan, E. Ozcan, Particle Swarm Optimization, Particle Swarm Optimization Homepage, http://www.cis.syr.edu/~mohan/pso/, 17.10.2008.
[5] Xiaohui Hu, Particle Swarm Optimization, 1.1.2005., Particle Swarm Optimization, http://www.swarmintelligence.org/index.php, 17.10.2008.
[6] Maurice Clerk, pso, 31.10.2008., pso, http://clerc.maurice.free.fr/pso/, 3.11.2008.
[7] Kennedy, J.; C. Eberhart, R.; Shi, Y. Swarm intelligence.
[8] E. Perez, R.; Behdinan, K. Particle Swarm Optimization in Structural Design
[9] Ekstremi funkcije više varijabli, Ekstremi funkcije više varijabli, http://www.grad.hr/nastava/matematika/mat2/node8.html, 13.12.2008.
[10] Minima and Maxima - Wikipedia, the free encyclopedia, Minima and Maxima, http://en.wikipedia.org/wiki/Maxima_and_minima, 10.12.2008.
[11] Technical reports, Technical reports, http://cswww.essex.ac.uk/technical-reports/2007/tr-csm469.pdf, 2.12.2008.
[12] Main, 30.4.2005., PSO Toolbox, http://psotoolbox.sourceforge.net/, 2.12.2008.