2008 IEEE Workshop on
Nonlinear Circuit Networks, Tokushima, Dec 5-6, 2008

Particle Swarm Optimization with Map Structure
Haruna Matsushita and Yoshifumi Nishio
Department of Electrical and Electronic Engineering,
Tokushima University
Email: {haruna, nishio}@ee.tokushima-u.ac.jp

Abstract— This study proposes a Particle Swarm Optimization
with Map Structure (PSOMS). All particles of PSOMS areconnected to adjacent particles by neighborhood relation, which
dictates the topology, of the 2-dimensional map. Each particle
is updated depending on the neighborhood distance between it
and a winner, whose function value is best among all particles.
Simulation results show the searching efficiency of PSOMS.

I. I NTRODUCTION
Particle Swarm Optimization (PSO) [1] is an evolutionary
algorithm to simulate the movement of flocks of birds. Dueto the simple concept, easy implementation, and quick convergence, PSO has attracted much attention and is used towide applications in different fields in recent years. However,PSO greatly depends on its parameters and converge prematurely in case of solving complex problems which have
local optima. Furthermore, in PSO algorithm, there are no
special relationships between particles. Each particle position
is updated according to its personal best position and the best
particle position among the all particles, and their weights are
determined at random in every generation. On the other side, in
the real world, various personal relationships exist, such as thehierarchical relationship, the trust relationships, the parentschild relationship and so on.
In this study, we propose a new Particle Swarm Optimization with Map Structure (PSOMS). All particles of PSOMS
are connected to adjacent particles by neighborhood relation,
which dictates the topology, of the 2-dimensional map. In
every generation, we find a winner particle, whose function
value is best among all particles, and each particle is updated
depending on the neighborhood distance between it and thewinner on the map. Simulation results and comparisons withthe standard PSO show that the proposed PSOMS can effectively enhance the searching efficiency.
II. PARTICLE S WARM O PTIMIZATION WITH M AP
S TRUCTURE (PSOMS)
In the algorithm of PSO, multiple solutions called “particles” coexist. The most important feature of PSOMS is that all
particles are organized on a rectangular 2-dimensional grid. In
other words, the particles are connected to adjacent particles
by neighborhood relation, which dictates the topology, of themap. The position vector of each particle i and its velocity
vector are represented by X i = (xi1 , · · · , xid , · · · , xiD )and V i = (vi1 , · · · , vid , · · · , viD ), respectively, where (d =1, 2, · · · , D), (i = 1, 2, · · · , M ) and xid ∈ [xmin , xmax ].

(PSOMS1) (Initialization) Let a generation step t = 0.
Randomly initialize the particle position X i and its velocity
V i for all particles i, and initialize P i = (pi1 , pi2 , · · · , piD )with a copy of X i . Evaluate the objective function f (X i ) forall particle i and find P g with the best function value among
the all particles. Define g as the winner c.
(PSOMS2) Evaluate the fitness f (X i ) and find the winnerparticle c with the best fitness among the all particles at currenttime.
c = arg min{f (X i (t))}.
(1)i

For each particle i, if f (X i ) < f (P i ), the personal best
position (called pbest) P i = X i .
Let P g represents the best position with the best fitness
among all particles so far (called gbest). If f (X c ) < f (P g ),update gbest P g = X c , where X c is the position of thewinner c.
(PSOMS3) Update V i and X i of each particle i depending
on its pbest, gbest and the distance on the map between i andthe winner c, according tovid (t + 1) = wvid (t) + c1 rand(·) (pid − xid (t))+ c2 hc,i (xcd − xid (t)) ,(2)

xid (t + 1) = xid (t) + vid (t + 1),
where w is the inertia weight determining how much of theprevious velocity of the particle is preserved. c1 and c2 are two
positive acceleration coefficients, generally c1 = c2 . rand(·)
is an uniform random numbers samples from U (0, 1). hc,i isthe fixed neighborhood function defined byµ¶kr i − r c k2
hc,i = exp −
,
(3)
2σ 2
where kr i − r c k is the distance between map nodes c and ion the map, the fixed parameter σ corresponds to the width of
the neighborhood function. Therefore, the large σ strengthens
particles’ spreading force to the whole space, and the small σstrengthens their convergent force toward the winner.
(PSOMS4) Let t = t + 1 and go back to (PSOMS2).
III. E XPERIMENTAL R ESULTS
In order to evaluate the performance of PSOMS, we use
two benchmark optimization problems. One is the Rosenbrockfunction f1 as Eq. (4) and the other is the Rastrigin function-3-

TABLE IC OMPARISON R ESULTS OF PSO AND PSOMS FOR f1 AND f2 .

f1
f2

MethodMean

Minimum

Maximum

PSO

178.5590

95.0156312.9265

PSOMS

102.9688

96.4675

138.9978PSO

444.3451

337.3337

584.0390

PSOMS

178.9360114.3723

236.46545

log(f(x))

f

10

PSO
PSOMS

10

0

0.5

0.55

0.6

0.65
w

0.7

0.75

0.8

1.9

2

10
10
10

5

PSO
PSOMS

4

PSO
PSOMS

10

3

0

1.5

1.6

1.7

1.8
c1,c2

10

2

(b)

0

Fig. 1.

Mean result log(f(x))

5log(f(x))

Mean result log(f(x))

(a)

10

10

500
1000
1500
Number of time steps t

2000

Fig. 3.
Results for Rosenbrock function f1 with different parameters.
(a) Using different w. c1 (= c2 ) is fixed as 1.6 for PSO and as 1.8 for
PSOMS. (b) Using different c1 (= c2 ). w is fixed as 0.7 for PSO and as 0.8
for PSOMS.

Mean Rosenbrock function value of every generation.

4

PSO
PSOMS
10

10

3

2

0

Fig. 2.

500
1000
1500
Number of time steps t

2000

Mean Rastrigin function value of every generation.

f2 as Eq. (5).
f1 (x) =

D−1
X³

´
¡
¢2
2
100 x2d − xd+1 + (1 − xd ) ,d=1x ∈ [−2.048, 2.047]
f2 (x) =DX¡¢
x2d − 10 cos (2πxd ) + 10 ,d=1

x ∈ [−5.12, 5.12]

(4)

D

(5)

D

For both two functions, we use D = 100 dimensions. The
optimum solutions x∗ of f1 and f2 are [1, 1, . . . , 1] and[0, 0, . . . , 0], respectively, and the optimum function valuesf (x∗ ) of both functions are 0.
The population size is set to 36 in PSO, and the network
size is 6 × 6 in the proposed PSOMS. We choose the bestparameters for each algorithm by the trial-and-error method
although PSOMS can obtain better results than PSO even if
PSOMS uses same parameters as PSO. For PSO, w = 0.7
and c1 = c2 = 1.6. For PSOMS, w = 0.8, c1 = c2 = 1.8 andσ = 1.0.

We carry out the simulations repeated 30 times for each
optimization function with 2000 time steps. The performanceof PSO and PSOMS with their corresponding minimum andmean function values are listed in Table I. Figures 1 and2 show the mean value of the best function value of every
generation over 30 runs for f1 and f2 function, respectively.
From these results, we can see that the results of PSOMS
have better accuracy. In PSO, the number of particles whichmove toward gbest or toward pbest is decided by random on
every generation and is not stable. On the other hand, theneighborhood gaussian function is used in PSOMS, therefore,
the particles move according to the neighborhood distance
between the winner and them. The winner’s neighborhood
particles move beyond the winner so that they spread to whole
space. The particles, which are connected at a little distancefrom the winner, move toward the winner. The other particles
fly toward their pbest. In other words, the roles of the PSOMS
particles are determined by the connection relationship.
Furthermore, in order to investigate the effect of the parameters; the inertia weight w and the acceleration coefficients c1
and c2 , on performance quality and their sensitivity, Figs. 3
and 4 show the mean function values with different parameters.
The fixed parameters are same as above simulations. The
proposed PSOMS is more effective and the parametricaldependence is not stronger than PSO. The performance of
PSO is sensitive to the parameters, however, the performanceof PSOMS is stable.
IV. C ONCLUSIONSThis study has proposed a Particle Swarm Optimization with
Map Structure (PSOMS). All particles of PSOMS are connected to adjacent particles by neighborhood relation, which
dictates the topology, of the 2-dimensional map. Each particle
is updated depending on the neighborhood distance between it-4-

log(f(x))

10
10
10

4

2

PSO
PSOMS

0

0.5

0.55

0.6

0.65
w

0.7

0.75

0.8

(a)

log(f(x))

10
10
10

4

2

PSO
PSOMS

0

1.5

1.6

1.7

1.8

1.9

2

c1,c2
(b)

Fig. 4. Results for Rastrigin function f2 with different parameters. (a) Using
different w. c1 = c2 is fixed as 1.6 for PSO and as 1.8 for PSOMS. (b) Using
different c1 (= c2 ). w is fixed as 0.7 for PSO and as 0.8 for PSOMS.

and a winner, whose function value is best among all particles.
In the simulation results, the searching efficiency of PSOMS
is better than PSO. Furthermore, we have confirmed that theparametrical dependence of PSOMS is not stronger than PSO.
R EFERENCES[1] J. Kennedy and R. C. Eberhart, “Particle swarm optimization,” in Proc.
IEEE. Int. Conf. Neural Netw., pp. 1942–1948, 1995.

-5-