平成20年度電気関係学会四国支部連合大会

374

17-5Particle Swarm Optimization
Containing Multiple Swarms
Masaki SUGIMOTO(Tokushima University)

Taku HARAGUCHI(Tokushima University)

1. Introduction
The particle swarm optimization (PSO) is a popularoptimization technique for the solution of object function and is an evolutionary algorithm to simulate themovement of ﬂocks birds. Due to the simple concept,
such as easy implementation and quick convergence,
PSO has gained much attentions and wide applications
in diﬀerent ﬁelds. However, if a particle is trapped intoa local optimum, the bust-out is diﬃcult.
This study proposes Multiple PSO (MPSO). The
feature of MPSO is that the swarm of MPSO is not one
but multiple. The swarms share an information of thebest value in each group. Except the swarm including
the best particle in whole swarms, all the particles arerepositioned to escape the local optimum. We investigate behaviors of MPSO and conﬁrm its eﬃciency.

2. Multiple PSO (MPSO) Algorithm
The most important feature of MPSO is that MPSO
has K swarms, i.e. multiple particle groups; Swarmk(k = 1, 2, . . . , K). Each swarm contains N/K particles whose position X ki = (xki1 , xki2 , . . . , xkiD ) (i =1, 2, . . . , N/K) are located randomly. The velocity vector V ki ∈ [V min , V max ] for each particle ki belonging
to Swarmk is assigned randomly.
[MPSO1](Initialization) Let t = 0 and tR = 0, i.e.,
t is the simulation step and tR is the time step forthe reposition. The quality of a particle position depends on a cost function F (X ki ). We ﬁnd the personal
best pbestki , which is the best cost of the particle i in
Swarmk , and the global best gbestk , which is the bestvalue of pbestki in Swarmk . The whole global best
gbestw , which is the best value in whole particles inall swarms, is also found;gbestk = min(pbestki ), gbestw = min(gbestk ). (1)ik

The swarm including the particle with gbestw is called
the best swarm. P ki = (pki1 , pki2 , . . . , pkiD ), P kg =(pkg1 , pkg2 , . . . , pkgD ) and P w = (pw1 , pw2 , . . . , pwD )represent the position of particle ki with pbestki , theposition of the particle with gbestk , and the positionof the particle with gbestw , respectively.
[MPSO2] Compare the current cost F (X ki (t)) ofeach particle with its best cost so far: if F (X ki (t)) <pbestki then pbestki = F (X ki (t)) and P ki = X ki (t).
Similarly, gbestk and gbestw are evaluated according
to Eq. (1). Therefore, P kg and P w are also evaluated.
[MPSO3](Update) The velocity vector V ki for eachparticle and each particle position X ki are updated;

Haruna MATSUSHITA Yoshifumi NISHIO(Tokushima University)(Tokushima University)where d = 1, 2, . . . , D, r1 , r2 and r3 are random variables distributed uniformly in [0, 1], w is an inertia
weight, and c1 , c2 , and c3 are positive acceleration coeﬃcients.
[MPSO4] If tR = T /K, we perform [MPSO5], if not,we perform [MPSO6]. Thus, we perform [MPSO5] every time when T /K simulation steps are performed.
T is the maximum number of the simulation.
[MPSO5](Reposition) We reposition the particle
positions X ki of all the Swarmsk except the best
swarm at random and reassign their velocities V ki atrandom. We reset tR = 0.
[MPSO6] Let t = t + 1 and tR = tR + 1. Go back to[MPSO2], and repeat until t = T .

3. Numerical Experiments
In order to conﬁrm the performance of MPSO algorithm, we apply MPSO to the Rastrigin Function;∑DF (X ki ) = DA + d=1 (x2kid − A cos(2πxkid )) (3)where −5.12 ≤ X i ≤ 5.12, D = 30, and A = 5. We set
parameters as follows; w = 0.5, c1 = 2.0, c2 = 1.7, c3 =0.3, T = 2000. MPSO has K = 4 swarms, and eachswarm contains 10 particles, i.e. N = 40.
We carry out the simulation 100 times and the results of MPSO, the standard PSO and PSO*, whichis the standard PSO with the reposition process, areshown in Table 1. We can see that the result of MPSO
is the best value in three algorithms. In MPSO, all theparticles share the information of the best value in eachswarm, and the particles except the best swarm arerepositioned. As the result, if the particle is trapped
into local optimum, the particle easily escapes fromthe local optimum. Therefore, we can conﬁrm thatMPSO algorithm is the most eﬀective.

Table 1: Result of Optimization
AVGMIN
MAX

PSO
35.94
11.87
87.80

PSO*
22.51
10.75
45.52

MPSO
13.83
6.92
27.26

4. Conclusions
In this study, we have proposed the new PSO algorithm, Multiple PSO (MPSO). We have investigatedits behaviors with the simulation and have conﬁrmed
the eﬃciency.

Referencevkid (t + 1){ = wvkid (t) + c1 r}1 {pkid (t) − xkid (t)}+ c2 r2 pkgd (t) − xkid (t) + c3 r3 {pwd (t) − xkid (t)} , [1] J. Kennedy and R. Eberhart, “Particle swarm optimization”, Proc. of IEEE Int. Conf. Neural Networks, vol. 4,xkid (t + 1) = xkid (t) + vkid (t + 1),(2) pp. 1942–1948, 1995.