2010 International Workshop on Nonlinear Circuits,Communication and Signal Processing
NCSP'10, Waikiki, Hawaii, March 3-5, 2010

Investigation of Network-Structured Particle Swarm Optimization
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
Our previous study has proposed the Network-Structured Particle Swarm Optimizer considering neighborhood relationships (NS-PSO). This study investigates the association between the network structure and the optimization performance by varying the degree of the small-world of NS-PSO.
1. Introduction
Particle Swarm Optimization (PSO) [1] is an algorithm tosimulate the movement of flocks of birds. 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 theirweights are determined at random in every generation.
On the other hand, the Self-Organizing Map (SOM) [2] isan unsupervised learning and is a simplified model of the selforganizing process of the brain. The map consists of neurons
located on a hexagonal or rectangular grid. The neurons selforganize statistical features of the input data according to theneighborhood relationship of the map structure.
In our past study, we have applied the concept of SOM
to PSO and have proposed Network-Structured Particle
Swarm Optimizer considering neighborhood relationships(NS-PSO) [3]. All particles of NS-PSO are connected to adjacent particles by a neighborhood relation, which dictates
the topology of the networks. The particles directly connected on the network share the information of their own past
best position. In every generation, we find a winning particle, whose function value is the best among all particles, as
SOM algorithm, and each particle is updated depending on
the neighborhood distance between it and the winner on thenetwork. NS-PSO can greatly improve the optimization performance from the standard PSO. Furthermore, we applied
NS-PSO to the various network topology [4],[5] and foundthat the circular-topology and the hexagonal-topology are appropriate for the simple unimodal functions and the complex
multimodal functions, respectively. However, the relevance
between the behaviors of NS-PSO with various topology andits parameters was not completely clear.

In this study, we investigate the association between thenetwork structure and the optimization performance by varying the degree of the small-world of NS-PSO with smallworld topology [6]. From results, we confirm that the smallworld network is suitable to the unimodal function, and therandom graph is suitable to the multimodal functions which
including a lot of local optima.
2. Network-Structured PSO with Small-World Topology
Considering Neighborhood Relationships (NS-PSO)
In the algorithm of the standard PSO, multiple solutions
called “particles” coexist. At each time step, the particle flies
toward its own past best position and the best position among
all particles. Each particle has two informations; position andvelocity. 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 ].
The standard PSO has no neighborhood relationship. On
the other hand, in the algorithm of NS-PSO, the particles areconnected to other particles according to the topology of thenetwork and share their local best position with neighbors.
2.1. Small-World Network (WS Model)
In this study, we investigate the behavior of the NS-PSO
with small-world topology proposed by Watts and Strogatz(called WS model). The small-world topology is defined ona lattice with M particles and periodic boundary conditions.
(1) Connect each particle i to its k neighbor particles according to the topology of 1-dimensional lattice.
(2) Rewire each particle i to another particle chosen at random with probability p.
When p = 0, the network topology is 1-dimensional lattice, and when p = 1, it is a random graph.
2.2. Algorithm of NS-PSO with Small-World Topology
This section explains the algorithm of NS-PSO with thesmall-world topology.

- 77 -

Table 1: Four Benchmark Functions.
Function nameBenchmark FunctionDX
f1 (x) =dx4d ,4th De Jong’s function;

f2 (x) =Rosenbrock’s function;

f3 (x) =Rastrigin’s function;
Stretched V sine wave function;

f4 (x) =d=1
D−1X³d=1DX

Initialization Spacex ∈ [−1.28, 1.28]D´¢2¡
2
100 x2d − xd+1 + (1 − xd ) ,¡ 2¢
xd − 10 cos (2πxd ) + 10 ,d=1D−1X¡¢(x2d + x2d+1 )0.25 1 + sin2 (50(x2d + x2d+1 )0.1 ) ,x ∈ [−2.048, 2.048]Dx ∈ [−5.12, 5.12]Dx ∈ [−10, 10]D

d=1(Step1) (Initialization) Let a generation step t = 0. Randomly initialize the particle position X i , initialize its velocity V i for each particle i to zero, and initialize P i =(pi1 , pi2 , · · · , piD ) with a copy of X i . Evaluate the fitness
f (X i ) for each particle i and find P g with the best fitness
among all the particles. Define a particle g as the winner c.
Connect all the particles according to the subsection 2.1. Find
Li = (li1 , li2 , · · · , liD ) with the best fitness among the directly connected particles, namely own neighbors.
(Step2) Evaluate the fitness f (X i ) and find a winning particle c with the best fitness among the all particles at current
generation t;
c = arg min{f (X i (t))}.
iRand(·) = (rand1 , rand2 , · · · , randD ) is an uniform random number vector from U (0, 1). hc,i is the fixed neighborhood function defined byµ¶dis(c, i)
hc,i = exp −,(3)σ2where dis(c, i) is the shortest-path distance between the winner c and the particle i on the network and is called neighborhood distance. The fixed parameter σ corresponds tothe width of the neighborhood function. Therefore, large σ
strengthens particles’ spreading force to the whole space, andsmall σ strengthens their convergent force toward the winner.
(1) (Step5) Let t = t + 1 and go back to (Step2).

For each particle i, if f (X i ) < f (P i ), update the personal
best position (called pbest) by 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 by P g = X c , where X c is the position of thewinner c.
(Step3) Find each local best position (called lbest) Li among
the particle i and its neighborhoods which are directly connected with i on the network. For each particle i, update lbest
Li , if needed.
(Step4) Update V i and X i of each particle i depending on
its lbest, the winner’s position X c and the distance on thenetwork between i and the winner c, according to3. Numerical ExperimentsIn order to evaluate the performance of NS-PSO with thesmall-world topology and to investigate its behavior, we use
four benchmark optimization problems summarized in Table 1. f1 is an unimodal function, and f2 , f3 and f4 are multimodal functions with numerous local optima. The optimum
solution x∗ of Rosenbrock’s function f2 is [1, 1, . . . , 1], andx∗ of the other functions are all [0, 0, . . . , 0]. The optimum
values f (x∗ ) of all the functions are 0. All the functions have
D = 50 variables.
The population size M is set to 36 in PSO, and the network
size is 36 in NS-PSO. For all PSOs, the parameters are set as
w = 0.7 and c1 = c2 = 1.6. The neighborhood radius σ of
NS-PSO is 2 for f4 and 1.5 for other functions. To generate
V i (t + 1) = wV i (t) + c1 Rand(·) (Li − X i (t))
the small-world topology, the neighborhood parameter k is+ c2 hc,i (X c − X i (t)) ,(2) set to 2. We carry out the simulations repeated 100 times for
all the optimum functions with 3000 generations.
X i (t + 1) = X i (t) + V i (t + 1),
We consider the behavior according to the network topolwhere w is the inertia weight determining how much of the ogy in terms of the clustering coefficient C [6] and the averprevious velocity of the particle is preserved. c1 and c2 are age shortest-path length L. Figure 2 shows the network avtwo positive acceleration coefficients, generally c1 = c2 , and erage clustering coefficient C and the average shortest-path- 78 -84000

642000

280

860

640

4200
−10−2210001−1(a)0−1005−2(b)10500220−500−510 −10(c)(d)

Figure 1: Landscape of the four benchmark functions with two variables. (a) 4th De Jong’s function. (b) Rosenbrock’sfunction. (c) Rastrigin’s function. (d) Stretched V sine wave function.

C( p)0.60.40.2

L( p)05432 −310−2−11010010Probability p

Figure 2: Network average clustering coefficient C and theaverage shortest-path length L of WS network with varying
the probability p. M = 36. k = 2.

length L of WS network with the population size 36 which isused in this simulation. From this figure, we can confirm thatthe network has the small-world property which satisfies thesmall L(p) and the large C(p) when p ∈ [0.03, 0.1].
3.1. Comparison results of PSO and NS-PSO

than other networks. On the other hand, at all the multimodal
functions as f2 , f3 and f4 , the results of the network withsome irregularities as p > 0 are better than the regular network as p = 0. Furthermore, when the network is the randomgraph as p = 1, the performances are the best.
Let us consider the association between the probability andits performance in detail. Simulation results of NS-PSO withsmall-world topology by varying the probability p are shownin Fig. 3. It should be noted that the characteristic is different between for the unimodal function as f1 and the multimodal functions. For the unimodal function as Fig. 3(a),the regular network can obtain the acceptable results, and theperformance achieves the best result when the network is thesmall-world. However, as the network becomes the randomgraph with large p, the optimization result grows worse than
the regular network. In contrast, for the unimodal function
as Figs. 3(b)–(c), the results of the regular network are theworst, and the performance grows better as the network becomes the random graph. These results are because that thediversity of the particles is different between the regular network and the random graph. On the regular network and thenetwork with small p, the shortest path length L and the number of particles in local neighbor Nl are almost same for eachparticle. From these effects, it is easy to transmit the information of lbest to the whole particles, therefore, the networkwith small p is effective for the unimodal function which issimple. However, the premature communication produces thepremature convergence, then, the regular network easily goes
into local optima in the multimodal functions. On the other
hand, NS-PSO with small-world topology. whose p is large,
contains various kinds of particles which has different shortest path length and different size of local neighbors. Because
these effects produce the diversity of the particles and avert
the premature convergence, the particles of NS-PSO with therandom-network can easily escape from the local optima.

Experimental results of the standard PSO with no connections and NS-PSO with small-world topology by using various the probability p are summarized in Table 2. p = 0 and
p = 1 mean that the networks are the regular network and therandom graph, respectively. We skip comparison with the results of PSO with small-world topology because our previous
study [5] has shown that its results are worse than the standardPSO. From this table, we can confirm that the standard PSO
has never obtained the better results than any NS-PSOs on all
the benchmarks. In addition, NS-PSOs significantly improve
the optimization efficiency for all the functions.
Next, let us note the probability p and its performance. At 4. Conclusions
the unimodal function as f1 , NS-PSO with the regular netIn this study, we have investigated the association between
work (as p = 0) obtains better results than the random graphnetwork (as p = 1), and NS-PSO with the small-world net- the network structure and the optimization performance bywork as p = 0.03 and p = 0.1 can obtain effective results varying the degree of the small-world of Network-Structured- 79 -Table 2: Comparison results of PSO and NS-PSO with small-world topology on 4 test functions.
NS-PSO with small-world topology
fPSO
p=0p = 0.03 p = 0.1
p=1
Mean
1.58e-35 4.41e-58 1.87e-59 5.48e-61 9.45e-57
f1
Minimum 9.86e-42 2.66e-65 6.06e-69 3.38e-71 4.60e-67
Mean
55.24
38.11
37.23
37.22
35.67
f2
Minimum
36.74
28.05
25.38
23.31
23.81
Mean
148.31
82.87
74.91
67.51
66.77f3
Minimum
94.52
48.75
35.82
39.80
33.83
Mean
65.62
30.62
29.78
21.40
16.13
f4
Minimum
39.36
12.64
7.26
4.94
4.37
−5039
Best Mean Result f (Pg)Best Mean Result f (Pg)

10−55

10−60

10−65

10−3

10−2−11010383736
35 −310010−2(a)010(b)
35
Best Mean Result f (Pg)Best Mean Result f (Pg)

10Pribability p

8580757065
60 −310−110Pribability p−2−1101030
25201510 −310010−2−11010Pribability p

Pribability p(c)(d)

010Figure 3: Results by varying the probability p. (a) 4th De Jong’s function f1 . (b) Rosenbrock’s function f2 . (c) Rastrigin’sfunction f3 . (d) Stretched V sine wave function f4 .

Particle Swarm Optimization. The simulation results haveshown that NS-PSO can greatly improve the optimization
performance from the original PSO. we have found that thesmall-world network is suitable to the unimodal function,and the random graph is suitable to the multimodal functions
which including a lot of local optima. From these results,
we can say that NS-PSO with small-world topology can obtain effective results flexibly by rewiring the network structure for various optimization problems without changing thealgorithm structure.

1995.
[2] T. Kohonen, Self-organizing Maps, Berlin, Springer, 1995.
[3] H. Matsushita and Y. Nishio, “Network-Structured Particle
Swarm Optimizer Considering Neighborhood Relationships,”
in Proc. of IEEE. Int. Joint Conf. on Neural Netw., pp. 2038–2044, 2009.
[4] H. Matsushita and Y. Nishio, “Network-Structured Particle
Swarm Optimizer with Various Topology and its Behaviors,”in Lecture Notes in Computer Science, vol. 5629, pp. 163–171,
2009.
[5] H. Matsushita and Y. Nishio, “Network-Structured Particle
Swarm Optimizer with Small-World Topology,” in Proc. of Int.
Symposium on Nonlinear Theory and its Applications, pp. 372375, 2009.

References[1] J. Kennedy and R. C. Eberhart, “Particle swarm optimization,”in Proc. of IEEE. Int. Conf. on Neural Netw., pp. 1942–1948,[6] D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘smallworld’ networks,” Nature 393, pp.440–442, 1998.

- 80 -