2009 International Workshop on Nonlinear Circuits and Signal Processing
NCSP'09, Waikiki, Hawaii, March 1-3, 2009

Particle Swarm Optimizer Arranged in Two-Dimensional Array
Haruna Matsushita† and Yoshifumi Nishio††Tokushima University
2-1 Minami-Josanjima, Tokushima, Japan.
Phone:+81-88-656-7470, Fax:+81-88-656-7471
Email: {haruna, nishio}@ee.tokushima-u.ac.jp

Abstract
This study proposes a Particle Swarm Optimization with Map
Structure (PSOMS). All particles of PSOMS are connected toadjacent particles by neighborhood relation, which dictates
the topology, of the 2-dimensional map. Each particle is updated depending on the neighborhood distance between it anda winner, whose function value is best among all particles.
Simulation results show the searching efficiency of PSOMS.
1. Introduction
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 otherside, in the real world, various personal relationships exist,
such as the hierarchical relationship, the trust relationships,
the parents-child relationship and so on.
Various topological neighborhoods have been consideredby researches [2]–[6]. They have applied ring neighborhood,the von Neumann neighborhood, or some other topologicalneighborhoods. However, the parameters are increased byusing fourth term for considering the neighboring best position when updating the velocity. Moreover, their methods
are complex algorithms although the one of advantages of thestandard PSO is the simple concept.
In this study, we propose a new Particle Swarm Optimization with Map Structure (PSOMS) which is the simple algorithm as the standard PSO. All particles of PSOMS are arranged in 2-dimensional grid and are connected to adjacentparticles by neighborhood relation which dictates the topology of the grid. In every generation, we find a winner par-ticle, whose function value is best among all particles, andeach particle is updated depending on the neighborhood distance between it and the winner on the map.
In Section 3, the algorithm of the proposed PSOMS is explained in detail. We apply PSOMS to two test functions,which are unimodal and multimodal function. Simulation results and comparisons with the standard PSO are shown in
Section 4, and we confirm that the proposed PSOMS caneffectively enhance the searching efficiency. Furthermore,in Section 5, we investigate the effect of the parameters on
performance quality and their sensitivity. We confirm thatPSOMS is more effective and its parametrical dependence is
not stronger than the standard PSO.

2. Standard Particle Swarm Optimization (PSO)
Particle Swarm Optimization (PSO) is an evolutionary algorithm to simulate the movement of flocks of birds. In thealgorithm of PSO, multiple solutions called “particles” coexist. At each time step, the particle flies towards its own
past best position and the best position among all particles.
Each particle has two informations; position and velocity.
The position vector of each particle i and its velocity vector are represented by Xi = (xi1 , · · · , xid , · · · , xiD ) and V i =(vi1 , · · · , vid , · · · , viD ), respectively, where (d = 1, 2, · · · , D),(i = 1, 2, · · · , M) and xid ∈ [xmin , xmax ].
(PSO1) (Initialization) Let a generation step t = 0. Randomly
initialize the particle position Xi and its velocity V i for eachparticle i, and initialize Pi = (pi1 , pi2 , · · · , piD ) with a copyof Xi . Evaluate the objective function f (Xi ) for each particle i and find Pg with the best function value among the allparticles.
(PSO2) Evaluate the fitness f (Xi ). For each particle i, if
f (Xi ) < f (Pi ), the personal best position (called pbest)
Pi = Xi . Let Pg represents the best position with the best
fitness among all particles so far (called gbest). Update Pg , ifneeded.
(PSO3) Update V i and Xi of each particle i depending on its- 141 -

pbest and gbest according to

12

x 10

vid (t + 1) = wvid (t) + c1 rand(·) (pid − xid (t))
+ c2 Rand(·) pg − xid (t) ,

80
60

10

40
5

(1)

20
0
500

xid (t + 1) = xid (t) + vid (t + 1),

0
5
0

0
−500

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(·) and Rand(·) are two uniform random numbers samples
from U(0, 1).
(PSO4) Let t = t + 1 and go back to (PSO2).

5

500

0
−500

0
−5

(a)

−5

(b)

Figure 1: Two test functions with two variables. First andsecond variables are on the x-axis and y-axis, respectively,and z-axis shows its function value. (a) Rastrigin function f1
which is unimodal function. (b) Rastrigin function f2 which
is multimodal function.

3. Particle Swarm Optimization with Map Structure(PSOMS)In the algorithm of PSO, multiple solutions called “particles” coexist. The most important feature of PSOMS isthat all particles are organized on a rectangular 2-dimensional
grid. In other words, the particles are connected to adjacentparticles by neighborhood relation, which dictates the topology, of the map. The position vector of each particle i and its
velocity vector are represented by Xi = (xi1 , · · · , xid , · · · , xiD )and V i = (vi1 , · · · , vid , · · · , viD ), respectively, where (d =1, 2, · · · , D), (i = 1, 2, · · · , M) and xid ∈ [xmin , xmax ].

where kri − rc k is the distance between map nodes c and i on
the map, the fixed parameter σ corresponds to the width of theneighborhood 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).

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

In order to evaluate the performance of PSOMS, we use
two benchmark optimization problems. One is the Rosenbrock function f1 as Eq. (5), which is unimodal function
shown in Fig. 1(a), and the other is the Rastrigin function
f2 as Eq. (6) which is multimodal function shown in Fig. 1(b)with numerous local minima.

4. Simulation Experimentationi

f1 (x) =

D−1 
X



2
100 xd2 − xd+1 + (1 − xd )2 ,d=1

x ∈ [−2.048, 2.047](5)DFor each particle i, if f (Xi ) < f (Pi ), the personal best poD X
sition (called pbest) Pi = Xi .
2
(2πx
)
f
(x)
=
x
−
10
cos
+
10
,
2
d
d
Let Pg represents the best position with the best fitness(6)
d=1
among all particles so far (called gbest). If f (Xc ) < f (Pg ),Dx ∈ [−5.12, 5.12]
update gbest Pg = Xc , where Xc is the position of the winnerc.
For both two functions, we use D = 100 variables. The(PSOMS3) Update V i and Xi of each particle i depending on optimum solutions x∗ of f and f are [1, 1, . . . , 1] and12
its pbest, the position of the winner c and the distance on the [0, 0, . . . , 0], respectively, and the optimum function values
map between i and the winner c, according tof (x∗ ) of both functions are 0.
The population size is set to 36 in PSO, and the networkvid (t + 1) = wvid (t) + c1 rand(·) (pid − xid (t))
size
is 6 × 6 in the proposed PSOMS. We choose the best+ c2 hc,i (xcd − xid (t)) ,(3) parameters for each algorithm by the trial-and-error method
although PSOMS can obtain better results than PSO even if
xid (t + 1) = xid (t) + vid (t + 1),
PSOMS uses same parameters as PSO. For PSO, w = 0.7 andwhere hc,i is the fixed neighborhood function defined by
c1 = c2 = 1.6. For PSOMS, w = 0.8, c1 = c2 = 1.8 and!
σ = 1.0. We carry out the simulations repeated 30 times forkri − rc k2,(4) each optimization function with 2000 time steps.
hc,i = exp −2σ2- 142 -

12

Table 1: Comparison Results of PSO and PSOMS for f1 and
f2 .

f1
f2

MethodMean

Minimum

Maximum

PSO

210.655

81.773313.365

PSOMS

108.52994.227147.550

PSO

442.639334.330

577.101

PSOMS

190.151135.687

252.401

Function Value log(f(x))

f

10

PSO (Gbest)
PSO (Mean fitness)
PSOMS (Gbest)
PSOMS(Mean fitness)

10

10

8

10

6

10

4

10

2

10

4.1. Experiment Results

500
1000
1500
Number of Generation t

2000

(a)
10
Function Value log(f(x))

The performance of PSO and PSOMS with their corresponding minimum and mean function values are listed inTable 1. We can see that the results of PSOMS have better
accuracy. In PSO, the number of particles which move toward gbest or toward pbest is decided by random on every
generation and is not stable. On the other hand, the neighborhood 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 distance fromthe 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.
Figures 2 shows the mean gbest value and the mean function value of all the particles of every generation over 30 runs
for two functions. In other words, the mean gbest value of every generation shows the swarm convergence, and the mean
fitness value of all the particles shows the particle-diversityof the swarm. From these figures, the convergence rate of
PSOMS is almost same or slower than the standard PSO, and
it is clear that PSOMS has the more diversity of the particles
than the standard PSO. We can appear this behavior prominently in Rastrigin function f2 which is the multimodal function. This is because that the roles of the PSOMS particles
are determined by the connection relationship, therefore they
produce the diversity of the particles. These effects avert thepremature convergence, and the particles of PSOMS can easily escape from the local optima.

0

10

10

10

10

6

PSO (Gbest)
PSO (Mean fitness)
PSOMS (Gbest)
PSOMS(Mean fitness)

5

4

3

2

0

500
1000
1500
Number of Generation t

2000

(b)

Figure 2: Mean gbest value of every generation, and mean
fitness value of all particles of every generation over 30 runs.
(a) Rosenbrock function f1 . (b) Rastrigin function f2 .

ters are varied. If we decrease or increase the parameter byjust 0.1, the performance of the standard PSO becomes drastically worse as especially. In other words, the performanceof PSO is sensitive to the parameters, however, the performance of PSOMS is stable. From these results, the proposed
PSOMS is more effective and the parametrical dependence is
not stronger than PSO.

5. Parameter Dependence
6. Conclusions
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.
We can see that PSOMS achieve better performances than
the standard PSO for both test functions even if the parame-

This study has proposed a Particle Swarm Optimization
with Map Structure (PSOMS) which is the simple method
as the standard PSO. All particles of PSOMS are connectedto 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- 143 -

5log(f(x))

10log(f(x))

10

PSO
PSOMS

10

0

0.5

0.55

0.6

0.65
w

0.7

0.75

10
10

0.8

4

2

PSO
PSOMS

0

0.5

0.55

(a)

10

10
log(f(x))

log(f(x))
0

1.5

1.6

0.65
w

0.7

0.75

0.8

(a)

5

PSO
PSOMS

10

0.6

1.7

1.8

1.9

10
10

2

c1,c2

4

2

PSO
PSOMS

0

1.5

1.6

1.7

1.8

1.9

2

c1,c2

(b)

(b)

Figure 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.

Figure 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.

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.

borhood Strategies and Preliminary Results” in Proc. ofIEEE Swarm Intelligence Symposium, 2008.

References[1] J. Kennedy and R. C. Eberhart, “Particle swarm optimization,” in Proc. IEEE. Int. Conf. Neural Netw., pp. 1942–
1948, 1995.
[2] J. Kennedy, “Small worlds and mega-minds: effects ofneighborhood topology on particle swarm performance,”in Proc. of Cong. on Evolut. Comput., pp. 1931–1938,
1999.
[3] J. Kennedy and R. Mendes, “Population structure andparticle swarm performance,” in Proc. of Cong. on Evolut. Comput., pp. 1671–1676, 2002.
[4] R. Mendes, J. Kennedy and J. Neves, “The Fully Informed Particle Swarm: Simpler, Maybe Better,” in IEEE
Trans. Evolut. Comput., vol. 8, no.3, pp. 204–210, June
2004.
[5] J. Lane, A. Engelbrecht and J. Gain, “Particle Swarm
Optimization with Spatially Meaningful Neighbours” inProc. of IEEE Swarm Intelligence Symposium, 2008.
[6] S. B. Akat and V. Gazi, “Particle Swarm Optimization
with Dynamic Neighborhood Topology: Three Neigh-- 144 -