Optimizacija rojevima čestica

(Particle swarm optimization, PSO)

Optimizacija rojevima čestica predstavlja metaheurističku metodu inspirisanu inteligencijom grupe. Udruživanjem jedinki u grupe, interakcijom i razmenom znanja jedinki formira se kolektivna inteligencija koja utiče na veoma brz napredak čitave grupe.

U PSO metodi svaka čestica predstavlja jedno rešenje koje pripada $d$-dimenzionom prostoru dopustivih rešenja. Poziciju čestice $i, i = 1, 2,...,n$ (u roju od $n$ čestica) odreduje $d$-dimenzioni vektor položaja $X_i = (x_{i1}, x_{i2},...,x_{id})$ i vektor brzine, odnosno pravca u kom bi se čestica kretala bez drugih uticaja $V_i = (v_{i1}, v_{i2},...,v_{id})$. Sve čestice istovremeno pokušavaju da poprave svoju poziciju koristeći svoje iskustvo, ali i iskustva ostalih čestica (celog roja ili podskupa - okoline čestice) iz prethodnih iteracija. Najbolja pozicija čestice $i$ čuva se u vektoru $p_i = (p_{i1}, p_{i2}, ...,p_{id})$, dok najbolju poziciju celog roja predstavlja vektor $p_g = (p_{g1}, p_{g2}, ..., p_{gd})$.

U procecsu inicijalizacije PSO metode, za svaku od $n$ čestica roja na slučajan način generišu se vektor pozicija i vektor brzina. U svakoj iteraciji, sve dok nije ispunjen kriterijum zaustavljanja, ažurira se vektor brzine i vrši se pomeranje čestice na novu poziciju. U novodobijenom roju čestica ažuriraju se najbolje pozicije čestica kao i najbolja čestica celog roja ukoliko je došlo do poboljšanja.

Ažuriranje vektora brzine čestice $i$ u iteraciji $j$ vrši se po sledećoj formuli:

$$ v_{ik}^j=wv_{ik}^{j-1}+c_1r_1(p_{ik}^j-x_{ik}^j)+c_2r_2(p_{gk}^j-x_{gk}^j),\ k=1,...,d $$

gde je $w$ parametar inercije kojim se kontroliše uticaj prethodne brzine čestice na trenutnu brzinu. Parametar $c_1$ kontroliše uticaj iskustva čestice (faktor kognitivnog učenja), dok se parametrom $c_2$ kontroliše uticaj okolinih čestica (faktor socijalnog učenja). Konstante $r_1, r_2$ su izabrane uniformnom raspodelom $[0,1]$. Promena pozicije čestice i u iteraciji j vrši se po formuli:

$$ x_{ik}^{j+1}=x_{ik}^{j}+v_{ik}^{j},\ k=1,...,d $$

Kako se ne bi izašlo izvan prostora dopustivih rešenja, vrednosti $v_{id}$ se ograničavaju na vrednosti iz unapred definisanog segmenta $[V_{min}, V_{max}]$. Odnos izmedu diverzifikacije i intenzifikacije procesa pretrage odreduje parametar $w.$ Veće vrednosti parametra $w$ pojačavaju stepen diverzifikacije, dok se uzimanjem manjih vrednosti intenzivira pretraga trenutnog područja.

Pseudokod:

Generisi inicijalnu populaciju cestica P
while Nije ispunjen kriterijum zaustvaljanja
			Izracunaj vrednost funkcije cilja za svaku cestici iz P	
			for cesticu x_i iz P
					azuriraj vektor brzine %ovde je ukljucena i kognitivna i socijalna komponenta
					azuriraj poziciju cestice x_i
					if f(x_i)<f(p_i_best) %p_i_best je najbolja pozicija cestice i 
							p_i_best=x_i
					end
					if f(x_i)<f(g_best) %g_best je najbolja pozicija celog roja
							g_best=x_i
					end
			end
end

Primena PSO metode na resavanje probelma UFLP

Opis problema

$C$ - skup korisnika ($n$ korisnika)

$F$ - skup uslužnih centara ($m$ centara)

$f_j$ - trošak izgradnje/održavanja centra $j\in F$

$c_{ij}$ - trošak pridruživanja korisnika $i$ centru $j$