Algoritmi zasnovani na evolucijskom računanju

RPSO
       Naslovnica                                              autor: Zvonimir Fras                                                                        pdf  | doc  | Program


Optimizacija rojem čestica (odbijanjem)




1. Uvod

Inspiracija za optimizaciju rojem čestica dolazi od činjenice da je učenje društvena aktivnost. Ljudi uče jedni od drugih ne samo činjenice već i načine kako rukovati tim činjenicama.

Ne samo da ljudi uče jedni od drugih, već kako se znanja i vještine šire od čovjeka do čovjeka, tako cijela populacija konvergira optimalnim rješenjima. Pračovjek je u davno doba uzeo oštar kamen i probo kožu neke životinje kako bi došao do mesa koje je želio pojesti. Drugi su ga vidjeli kako to radi i preuzeli to od njega, tražeći druge oštre predmete kako bi napravili isto. Danas imamo kirurške noževe velike oštrine i preciznosti.

Jedinke uče od drugih u svojoj blizini. Ljudi komuniciraju s drugim ljudima, sakupljajući informacije i zauzvrat daju informacije koje su njima poznate. Na taj način širenje znanja postaje grupni proces. Društvo je samo-organizirajući sustav koji posjeduje neka svojstva koja se ne mogu predvidjeti iz svojstva jedinki koje čine to društvo.

Obrazovanje optimira spoznaju. Iako se svaka interakcija odvija lokalno, informacije i inovacije se obrazovanjem prenose do udaljenih jedinki. Primjerice ja Vama kažem neku novost, Vi to kažete nekom svom prijatelju kojeg ja ne poznajem i ne mogu mu to reći, on to kaže nekom svom prijatelju... Informacija se širi. Nadalje, kombinacije u različitim metodama dovode do još naprednijih metoda. Ovaj globalni efekt je nevidljiv članovima društva koji od njega imaju koristi.

U metodama optimizacije rojem čestica koristit će se upravo činjenica da skup jedinki ima svojstvo da optimizira različite probleme, pri čemu jedinke koje sačinjavaju taj skup ne moraju znati ništa o problemu kojeg optimiziraju, nego rade svoje jednostavne operacije.

2. Opis algoritma

2.1 PSO

Optimizacija rojem čestica je stohastička optimizacijska metoda modelirana prema socijalnom ponašanju promatranih životinja i kukaca, primjerice jata ptica, stada životinja, roj mušica itd. Od početka privlači pažnju istraživača kao robusna i efikasna tehnika za rješavanje složenih optimizacijskih problema.

U PSO (engl. Particle Swarm Optimization – Optimizacija rojem čestica) svaka čestica roja predstavlja potencijalno rješenje i kreće se kroz prostor problema u potrazi za optimalnim ili dovoljno dobrim rješenjem. Čestice razašilju svoj trenutni položaj susjednim česticama. Pozicija svake čestice mijenja se sukladno brzini gibanja čestice, svojoj najboljoj poziciji i najboljoj poziciji njoj susjednih čestica. Kako model napreduje, roj se sve više usredotočuje na područje koje sadrži visokokvalitetna rješenja.

Izvorni algoritam sastoji se od dvije jednadžbe prema kojima se u svakom koraku osvježuju brzina i pozicija:

(2.1)
(2.2)

gdje je:

vi – brzina ite čestice
xi – pozicija ite čestice
ω – inercijska konstanta, dobre vrijednosti su obično malo manje od 1
pi – najbolji osobni rezultat (engl. personal best)
pg – najbolji rezultat susjeda
r1, r2 - dvije odvojene funkcije od kojih svaka vraća vektor slučajnih vrijednosti u intervalu [0,1]
c1, c2 - koeficijenti ubrzanja, govore koliko je dobro čestica usmjerena prema dobrim pozicijama. Dobre vrijednosti su obično oko 1.

Jednadžba (2.1) pokazuje da brzina čestice ovisi o tri dijela: inerciji, osobnom dijelu i društvenom dijelu. Inerciju predstavlja brzina iz prethodnog koraka kojom se kretala čestica do tog trenutka. Osobni dio , predstavlja težnju čestice da se vrati na najbolje mjesto na kojem je bila dok društveni dio , predstavlja težnju čestice da ode na najbolje mjesto koje je našao čitav roj.

Na osnovu te dvije jednadžbe i dosad rečenog možemo napisati osnovni algoritam za optimizaciju rojem čestica.

Slika 1 Osnovni algoritam optimizacije rojem čestica (PSO)

2.2 RPSO

Optimizacija rojem čestica odbijanjem, RPSO (engl. Repulsive Particle Swarm Optimization), je varijanta klasičnog PSO. Posebno je efikasna u traženju globalnih optimuma izrazito složenih prostora pretraživanja iako može biti sporija kod određenih vrsta optimizacijskih problema[2].

Kod tradicionalnog RPSO, formule su nešto drugačije nego kod PSO:

(2.3)
(2.4)

vi – brzina ite čestice
xi – pozicija ite čestice
ω – inercijska konstanta, [0.01,0.7] pi – najbolji osobni rezultat (engl. personal best)
ph – najbolji rezultat slučajno izabrane čestice iz roja
r1, r2, r3 – slučajni brojevi u intervalu [0,1]
z – slučajni vektor brzine
α, β, γ – konstante

Povremeno, ukoliko proces zapne u nekom lokalnom optimumu, može biti potrebno kaotično uznemirenje pozicije i brzine nekih čestica.

Algoritam tradicionalnog RPSO se od tradicionalnog PSO razlikuje samo u korištenim formulama za osvježavanje brzine i položaja.

Slika 2 Osnovni algoritam optimizacije rojem čestica odbijanjem (RPSO)

Vidimo da se od osnovnog PSO algoritma razlikuje samo u koracima u kojima se izračunava brzina i pozicija čestica.

3. Primjene algoritama

Široka primjena PSO algoritama počinje od klasičnih problema izrade rasporeda, problema trgovačkog putnika, treniranja živčanih mreža (engl. neural networks) i raspodjele zadataka, pa sve do specijaliziranih problema kontrole snage reaktora i kontrole napona, u medicini, te čak za komponiranje glazbe. Zadnjih godina PSO je postao posebno popularan za optimizaciju problema s više ciljeva, te optimizaciju problema čije se rješenje dinamički mijenja.

Jedna od prvih primjena PSO bila je razvoj struktura živčanih mreža. Zbog svojeg svojstva da brzo konvergira, korištenje PSO kao zamjenu za tradicionalne algoritme značajno je smanjilo vrijeme učenja.

Živčana mreža uzima vektor nezavisnih varijabli i daje procijenjeni vektor zavisnih izlaznih varijabli. Mreža je strukturirana kao skup težina, obično organiziran u slojeve i optimizacijski problem je naći vrijednosti za te težine tako da mreža daje preslike s najmanjom greškom. Mreža je zadužena za razumijevanje i stoga se ponaša kao individua te kao takva donosi odluke o podražaju na osnovu vlastitog iskustva. S druge strane, razumijevanje kod roja čestica je na razini cijelog roja. Svaka čestica leti kroz mrežu i komunicirajući s ostalima optimiziraju mrežu koju svaka čestica za sebe ne razumije, ali ovdje je razumijevanje osobina roja, kojeg je svaka čestica jedan mali dio. [5]

U raznim Java appletima koji su dostupni na internetu možemo s korisničke strane ispitati PSO raznim predefiniranim funkcijama koje se često koriste kao ispitne funkcije za optimizacijske probleme (kugla, Rosenbrock, Rastrigrin, Griewank, DeJong, Ackley i druge) te promatrati ponašanje roja kroz korake algoritma. [4]

Razvijen je i PSO toolbox [3], alat otvorenog koda, pomoću kojeg je moguće optimizirati korisnički definirane funkcije i sustave. Trenutno je u beti i sastoji se od Matlab (.m) funkcija, te ne podržava optimizaciju FIS-a (engl. Fuzzy Inference System). U izradi je Java port toolboxa te podrška za optimizaciju FIS-a.

4. Zaključak

U ovom tekstu upoznali smo neke probleme optimizacije, što je to optimizacija matematički gledano, te neka od rješenja iz područja inteligencije roja za optimizacijske probleme. Tako smo saznali što je to PSO, kako tradicionalni algoritam PSO izgleda i jednu njegovu varijantu RPSO, napravili usporedbu PSO i RPSO i donijeli zaključke o njihovim performansama.

Dani su primjeri korištenja, kako s istraživačke, tako i s praktične strane. Istraživačka primjerna je u optimizaciji složenih funkcija pri čemu se pokušavaju postići što bolje performanse, dok je praktična primjerna u treniranju živčanih mreža, te optimizaciji FIS-a.

Ispitivanje je pokazalo da RPSO općenito daje bolje rezultate nego PSO pri optimizaciji realnih funkcija. S druge strane, uspoređujući RPSO s ostalim metodama optimizacije iz područja umjetne inteligencije (GA, SA) dolazi se do zaključka da nema "srebrnog metka", algoritma koji je pogodan za rješavanja svih problema nego da je probleme potrebno kategorizirati i za odgovarajuću kategoriju koristiti odgovarajući algoritam.

5. Literatura

[1] Swarm Intelligence, Introduction and Applications – Christian Blum, Daniel Merkle
[2] Repulsive Particle Swarm Method on Some Difficult Test Problems of Global Optimization - Mishra, SK (2006)
[3] http://psotoolbox.sourceforge.net/
[4] http://www.engr.iupui.edu/~shi/PSO/AppletGUI.html
[5] Swarm Intelligence – James Kennedy

FER - PROJEKT 2008/2009