1. Introduction
Particle Swarm Optimization (PSO) [1] is an algorithm to simulate the movement of flocks of birds.  Due to the simple concept, easy implementation and quick conver- gence, PSO has attracted much attention and is used to wide applications in different fields in recent years. In PSO algorithm, there are no special relationships between parti- cles. Each particle position is updated according to its per- sonal best position and the best particle position among the all particles, and their weights are determined at random in every generation.  Due to these features, the standard PSO greatly depends on its parameters and converge pre- maturely in case of solving complex problems which have local optima. On the other hand, the Self-Organizing Map (SOM) [2] is an unsupervised learning algorithm.  SOM consists of neurons located on 2-dimensional network.  The neurons self-organize statistical features of the input data according to the neighborhood relationship of the map structure. Various topological neighborhoods for PSO have been considered by researches [3]–[7]. Each particle shares its best position among neighboring particles on the network. However, the information of each particle is not updated depending on the neighborhood distance on the network. 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) [8][9].  All particles of NS-PSO are connected to adjacent particles by a neighborhood relation, which dic- tates the topology of the networks.  The connected parti- cles, namely neighboring particles on the network, share the information of their own past best position.  In every generation, we find a winner 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 the network. We applied NS- PSO to the various network topology as rectangular, hexag- onal, cylinder and toroidal.  From comparison results, we find that the circular-topology is effective for the simple unimodal functions and the hexagonal-topology is appro- priate for the complex multimodal functions. In this study, we apply NS-PSO to well-known net- work; "small-world network" suggested by Watts and Stro- gatz [10]. Simulation results and comparisons with the pre- vious PSOs show that the proposed NS-PSO with small- world topology can effectively enhance the searching effi- ciency.
2. Network-Structured Particle Swarm Optimizer 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 posi- tion among all particles.  Each particle has two informa- tions; position and velocity.  The position vector of each particle i and its velocity vector are represented by X i = ( X i1 , · · · , X id , · · , X iD ) and V i = ( V i1 , · · · , V id , · · · , V iD ), re- spectively, where ( d = 1,2, . . . ,D ), ( i = 1,2, . . . ,M ) and Xid E [Xmin, Xmax]. The algorithm of NS-PSO is based on both two struc- tures; the standard PSO and SOM. NS-PSO has following three key features. 1. All particles are connected to adjacent particles by a neighborhood relation, which dictates the topology of the network. 2. The particles share the local best position between the neighborhood particles directly connected. 3. In every generation, we find a winner particle with best function value among all particle as SOM learning. By these features, each particle of NS-PSO is updated de- pending on its own best position, the position of the winner and the neighborhood distance between it and the winner on the network.
2.1.  Small-World Model
In this study, we apply NS-PSO to the 1-dimensional (1-D) small-world topology shown in Fig. 1(b).  The 1-D small-world topology is defined on a lattice with M par- ticles and periodic boundary conditions.  The 1-D small- world topology is generated by following algorithm; (1) Connect each particle i to its k neighbor particles ac- cording 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 lat- tice, and when p = 1, it is a random graph.
2.2. Algorithm of NS-PSO with Small-World Topology
The algorithm of NS-PSO with the small-world topology is same as the conventional NS-PSO except its topology and a neighborhood function as Eq. (3). (NS-PSO1) (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 = ( P i1 , P i2 , . . , P iD ) with a copy of X i .  Evaluate the objec- tive function f ( X i ) for each particle i and find P g with the best function value among all the particles. Define g as the winner c . Find L i = ( l i1 , l i2 , . . . , l iD ) with the best function value among the directly connected particles, namely own neighbors.  Connect all the particles to adjacent particles according to the subsection 2.1. (NS-PSO2) Evaluate the fitness f(X i ) and find a winner particle c with the best fitness among the all particles at current time t ;
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(Xc) < f(P g ), update gbest  P g = Xc, where X c = ( x c 1 , x c 2 , · · · , x c D ) is the position of the winner c (NS-PSO3) Find each local best position (called lbest) L i among the particle i and its neighborhoods, which are di- rectly connected with i on the network, so far.  For each particle i , update lbest L i , if needed. (NS-PSO4) Update V i and X i of each particle i depending on its lbest , position of the winner X c and the distance on the network between i and the winner c , according to
where w is the inertia weight determining how much of the previous velocity of the particle is preserved. c 1 and c 2 are two positive acceleration coefficients, generally c 1 = c 2 , rand( · ) is an uniform random number sample from U (0, 1). h c j is the fixed neighborhood function defined by
where dis(c, i) is the shortest-path distance between parti- cles c and i on the network and is called neighborhood dis- tance . The fixed parameter σ corresponds to the width of the neighborhood function. Therefore, large σ strengthens particles' spreading force to the whole space, and small σ strengthens their convergent force toward the winner. (NS-PSO5) Let t = t + 1 and go back to (NS-PSO2).
3. Simulation
In order to evaluate the performance of NS-PSO with small-world topology, we use six benchmark optimization problems summarized in Table 1. f 1 , f 2 and f 3 are uni- modal functions, and f 4 , f 5 and f 6 are multimodal func- tions with numerous local minima. The optimum solution x* of Rosenbrock's function f 2 is [1,1,...,1], and x* of the other functions are all [0, 0, . . , 0]. The optimum value f ( x * ) of all the functions is 0. All the functions have D vari- ables. In this study, D is set to 30 and 50 to investigate the performances in various dimensions. The landscape maps of benchmark functions with two variables are shown in Fig. 2. We compare NS-PSO with small-world topology to the standard PSO, PSO with small-world topology and NS- PSO with rectangular-topology. Features of each algorithm are follows: PSO: This is the standard PSO with NO neighborhood re- lationship. Each particles is updated depending on its pbest and gbest. PSO with small-world topology:  Its particles are con- nected to other particles according to small-world network and share their lbest with directly connected particles. Each particles is updated depending on its lbest and gbest . The winner does NOT exist, and the neighborhood distance is NOT considered. NS-PSO with various topology:  Its particles are con- nected to other particles according to the topology of the network and share their lbest with directly connected parti- cles. Each particles is updated depending on its lbest , win- ner's position and the neighborhood distance. The population size M is set to 36 in PSO, and the net- work sizes are 36 in NS-PSO with small-world topology
and 6 × 6 in NS-PSO with rectangular-topology.  For all PSOs, the parameters are set as w = 0.7 and c 1 = c 2 = 1.6. The neighborhood radius σ of NS-PSO with small-world topology and with rectangular-topology are 1.6 and 1.5, re- spectively. To generate the small-world topology, the prob- ability p is chosen 0.04, and the neighborhood parameter k is set to 2. We carry out the simulations repeated 30 times for all the optimization functions with 3000 generations.
3.1.  Experimental Results
The performances with the minimum and mean function values over 30 independent runs on six functions are listed in Table 2. The best results of the mean values among all the algorithms are shown in bold. On both dimension, the standard PSO, PSO with small- world topology, NS-PSO with rectangular-topology and with small-world topology achieve the best values 0, 1, 2 and 9 times, respectively. It is interesting to note that PSO with small-world topology can not obtain better results than the standard PSO with no connection, and in fact, it dramat- ically degrades the performance on almost functions. How- ever, two kinds of NS-PSOs evidently surpass not only the standard PSO but also PSO with small-world topology, on almost functions for both dimensions. These results mean that it is not important to share lbest among neighbors, and updating with considering the neighborhood distance pro- duces the effective results. In the updating of NS-PSO, the neighborhood gaussian function is used, then, the particles move according to the neighborhood distance between the winner and them.  The roles of the NS-PSO particles are determined by the connection relationship, and they pro- duce the diversity of the particles. These effects avert the premature convergence, and the particles of NS-PSO can easily escape from the local optima. In contrast to PSO, NS-PSO with small-world topol- ogy obtain significantly-improved results over rectangular- topology.  In particular, NS-PSO with small-world topol- ogy tends to upgrade the performance on unimodal func- tions as f 1 , f 2 and f 3 . It is considered that NS-PSO with small-world topology has advantages of both the particle- diversity and the ease of exchanging of the particle infor- mation. From these results, we can say that NS-PSO, whose par-
ticles are updated depending on the neighborhood distance, is more effective than the standard PSO, which has no neighborhood relationship, and PSO with network topol- ogy which does not use the neighborhood distance.  Fur- thermore, although the results slightly depend on the prob- lems, NS-PSO with small-world topology is suitable for optimization, especially on unimodal functions.
4. Conclusions
In this study, we have proposed Network-Structured Par- ticle Swarm Optimizer (NS-PSO) with Small-World topol- ogy. All particles of NS-PSO are connected to adjacent par- ticles by a neighborhood relation of small-world network, and their information are updated depending on the neigh- borhood topology.  We have applied NS-PSO with small- world topology to optimization problems.  We have con- firmed that NS-PSO, whose particles are updated depend- ing on the neighborhood distance, is more effective than the standard PSO, which does not use the neighborhood dis- tance.  Furthermore, NS-PSO with small-world topology is suitable for optimization, especially on unimodal func- tions.