Benchmark functions used in the experiments.
1. Introduction
Many real world problems are quite expensive to be solved by using exhaustive computation. Because of this, many metaheuristics have been proposed recently to deal with optimization and search problems. Although many approaches have been proposed based on local search, the current research in Evolutionary Computation (EC) is mainly focused on algorithms that are based on populations and inspired in nature (Schwefel, 1981; Bäck, 1996; Fogel, 1996; Beyer, 2001; Beyer, 2002).
In this context, Swarm intelligence techniques, mainly Particle Swarm Optimization (PSO), have been widely applied to solve many different types of optimization problems. PSO was proposed by Kennedy and Eberhart (Kennedy & Eberhart, 1995) and the main idea is to explore the intelligence originated by the social knowledge disseminated by the agents during the search process. Due to its great performance in difficult optimization tasks and its simplicity, PSO became a popular, easytouse and extendable technique (Abido, 2001; Eberhart & Shi, 2001; Parsopoulos & Vrahatis, 2001; Agrafiotis & Cedeno, 2002; Coello Coello & Lechuga, 2002; Parsopoulos et al., 2002; Shi & Krohling, 2002; Praveen et al., 2007; SantanaQuintero ET AL., 2008).
By applying PSO to problems where the feasible solutions are too much difficult to find, more sophisticated approaches are required, mainly for hyper dimensional spaces. Many variations on the basic PSO form have been explored, most of them proposing different velocity update equations (Shi & Eberhart, 1998; Clerc & Kennedy, 2002 ; Kennedy, 2005; Jiao, et al., 2008). Other approaches attempt to change the structure of the swarm (Kennedy & Mendes, 2002; Suganthan, 1999) and its communication schema (Engelbrecht, 2005; Sutton et al., 2006).
To disseminate information within the swarm is the key of any swarm intelligence based algorithm. PSO, like others swarm algorithms, makes use of its own information exchange methods to distribute the best positions found during the algorithm execution (Engelbrecht, 2005). The way used by the swarm to distribute this information lies in the social structure formed by the particles. Variations in this structure can improve the algorithm performance.
By using local communication, each particle of the swarm has its own neighborhood. Many papers (Engelbrecht, 2005; Carvalho & BastosFilho, 2008; Carvalho & BastosFilho, 2009) have shown that it improves the exploration capacity of the entire swarm but decreases the convergence speed of the algorithm. It means that the algorithm obtains better solutions, but it needs more iterations to reach the convergence.
Other important and already known PSO algorithm variation is the Cooperative Particle Optimizer (CPSO) (van den Bergh & Engelbrecht, 2001; van den Bergh & Engelbrecht, 2004) which is based on the cooperative GA proposed by Potter and De Jong (Potter & De Jong, 1994). This approach proposes a performance improvement of the PSO algorithm by splitting the solution vector into different components that will be optimized by different subswarms cooperatively. CPSO inserts another parameter called
By using the ring structure as an inspiration, a novel PSO topology called Multiring PSO (MRPSO) based on coupling different rings was recently proposed (BastosFilho et al. 2008). This novel approach makes use of a diversity mechanism provided by ring rotations in order to improve the exploration of the search space. The structure of the proposed topology is formed by ring layers connected by axis that cross the layers trough the particles. Each single particle, which belongs to a specific layer, is automatically connected to other particles in neighbour ring layers. These connections establish the communication between neighbour particles which is a peculiar neighbourhood scenario based on local communication. The ring layers increase the capacity to avoid stagnation states making use of a process and an attribute called rotation skill and trigger criterion, respectively, also described in the chapter. Furthermore, we included a novel concept proposed by Cai et al. (Cai et al. 2008) that assigns a grade to the particles based on their fitness. This information is used to switch the neighbourhood inside the rings.
The rest of this paper is organized as follows. Section 2 shows a brief review about PSO. It also describes some well known topologies. In Section 3 the proposed Multiring topology and its features are described. Section 4 is devoted to the Dispersed based Multiring approach. The simulation setup used by the experiments and the chosen benchmark functions are presented in Section 6. In section 7 the analysis of Multiring and Multiring Dispersed are shown. The results of a comparison with some wellknown topologies are presented too.
2. Background
2.1. Particle Swarm Optimization  PSO
The basic form of the PSO algorithm is composed by a group particles, where each particle represents a possible solution to the problem. Each particle maps the attributes of a solution,
As the original PSO is based on the global knowledge of the swarm, it has a low capacity for local search. Thus, other approaches were proposed in order to avoid this disadvantage. Shi and Eberhart (Shi & Eberhart, 1998) proposed a velocity update equation that uses an inertia factor
where
Recently, Jiao et al. (Jiao et al., 2008) proposed a dynamic inertia weight for the particle swarm optimization algorithm. They showed that it can improve the quality of the solutions obtained by the algorithm.
Another popular approach for the PSO velocity update equation involves a constriction factor which implies a velocity value reduction at each time step (Clerc & Kennedy, 2002). Under some peculiar conditions, it can guarantee both convergence and a high degree of exploration.
Both inertia and constriction approaches balance exploration and exploitation abilities and improve the convergence speed and the quality of the solutions found by the algorithm (Bratton & Kennedy, 2007).
2.2. Topologies
The communication between particles inside a swarm is one of the most important mechanisms of PSO. This mechanism distributes information already achieved by the
swarm through all particles, updating the swarm status. Global and local communication structures are the two main structures used for particles’ communication. Considering that particles share information acquired through a structured swarm, this model of communication can be seen as a topology. Some of the wellknown topologies are depicted in Figure 1.
Each topology shown in Figure 1 has its own way to spread information through the swarm (Kennedy, 1999; Kennedy & Mendes, 2002).
In Figure 1(c), a grid of particles forming a peculiar social structure is shown. This structure is very useful for many optimization problems (Kennedy & Mendes, 2002; Peer et al., 2003) and is known as
Based on clusters of particles, the
3. Multiring topology
3.1. Multiring concepts
MultiRing is a novel PSO topology that uses the
The proposed topology is formed by particles arranged in multiple rings layers, where each particle of the ring can communicate with some particles of neighbour rings. In order to
couple different ring layers, the number of particles in each ring must be the same. Therefore, each single particle, which belongs to a specific layer, is automatically connected to other particles from neighbour ring layers, as shown in Figure 2. The structure in Figure 2 illustrates an example of the multiring topology with 3 rings (A, B and C) of 3 particles.
3.2 Communication between different rings
The particles from different ring layers communicate with each other by using a peculiar neighbourhood scenario. The Figure 3 can be used to illustrate this scenario. Considering a ring layer
One special observation must be considered for the first and last ring layers of the topology. The communication between the particles located at those two rings is partially limited, since both do not have a complete ring neighbourhood, it means that they only have a unique ring layer directly connected to them. Therefore, the information exchange for one particle belonging to a ring
One particle which belongs to a ring layer
3.3. Ring layer rotation skill
One of the biggest problems of PSO is the stagnation. In nonlinear multimodal problems, which have many local minima regions, the swarm can be stagnated in one those regions of the search space during the algorithm execution. In those regions, the particles can spend many time steps without varying the value of the best position found by their neighbourhoods. It can cause a stagnation state in the entire swarm. Hence, the proposed strategy to avoid stagnation is to add the ability of rotation to each ring layer. By adding the rotation skill, the position of the particles in the ring can be altered. Hence, the neighbourhood is changed. It can move the swarm from one region to another, increasing the exploration of the space search by considering different local minima regions.
In the MultiRing approach, the particles of different rings exchange information between themselves using local communication. The particle that belongs to a ring
Each ring layer of the MultiRing has the ability to selfrotate. It means that if the ring layer
Figure 4 shows an example of the rotation process. Initially, the particle E communicates with {D,F,B,H}. After the rotation, the neighbourhood of the particle E is changed to {D,F,A,G}. This process improves the social information exchange. Besides, it also improve the convergence capacity of the swarm. One can note that all the particles of the same ring layer change its neighbourhood.
The main mechanism of the rotation process is the trigger criterion that will be used to invoke the rotation skill. It is based on the idle status of the best solution found in a specific ring layer, i.e. the number of iterations that the best solution found by a specific ring does not change. To clarify the process described above, consider a ring layer
Therefore, the use of the exploration capacity provided by the local communication combined with rotation mechanisms helps to avoid the stagnation of the solution found by the swarm during the execution of the PSO algorithm.
3.4. Multiring PSO algorithm
Inspired by the entity described in the previous section, the PSO algorithm with this novel topology has some new specific steps that must be considered in the execution process of the algorithm. Figure 5 illustrates the MultiRing topology containing an example with two ring layers (
In the basic PSO algorithm, one of the steps is the definition of the initial
For each iteration, each ring layer performs a search and marks the particle that reached the best position of the entire ring layer. Different from
After the
The updateVelocityAndPosition() and updateInformation() processes are the core of any PSO algorithm. These two processes are described in the pseudocodes of Algorithms 2 and 3 that are shown in Figures 7 and 8, respectively.
The other process involved in Algorithm 1 execution is rotate() (see Line 4), which belongs only to the multiring topology approach proposed here. One can note that this step is done before the
When the trigger criterion is satisfied, the ring layer is rotated by
4. Dispersed particle swarm optimization
4.1. Dispersed PSO concepts
In particle swarm optimization (PSO) literature, the published social coefficients settings aims to increase the search around the swarm memory. However, few approaches
take into account the useful information inside the particle’s memories. Thus, to improve the convergence speed, a new approach considering the social coefficient was proposed (Cai et al, 2008) by introducing an explicit selection pressure, in which each particle decides its search direction toward the personal memory or swarm memory.
The fitness value of the current position of each particle represents its adaptive capability, and it can be selected to distinguish between search modes. In this approach, the better the fitness of the current position is, more adaptation this particle can get to enhance its survival ratio.
Since the literature consider the extreme situations such as
To minimize this problem, Cai et al. (Cai et al., 2008) proposed a new index to indicate performance differences, named
where
Occasionally, the swarm can converge onto one point, that means
In most cases, if the fitness value of particle
Then, the dispersed social coefficient of particle
where
4.2. Multiring dispersed particle swarm optimization
Based on the new manner to determine the acceleration coefficients, the dispersed PSO approach was included into the MultiRing Topology. By applying the
The grade criterion, which is calculated by evaluating a fitness comparison, will make the best solutions perform searches around its vicinities and the worst solutions look for the history of a larger part of the swarm, in order to increase its experience.
Figure 11 illustrates the grade strategy in action. If the
5. Simulation setup
In Table 1, seven commonly used benchmark functions are presented. Their names, definitions, search space, initialization range, and optimum compose the columns of Table 1.
All the functions described are used as minimization problems classified as unimodal (
Each simulation was performed using PSO with inertia factor. The reduction of
We used
The number of iterations used in a single simulation was 10,000. After 30 executions, the mean and standard deviation were stored. The initial positions of the entire swarm are defined randomly inside the initialization range of the benchmark function used. Comparisons with other topologies were also provided for convergence performance validation in both inertia and dispersed approaches.
Function  Equation  Search space  Init.  Opt. 
Rosenbrock ( f _{1} ) 

(30, 30) ^{D}  (15, 30) ^{D}  1.0 ^{D} 
Ackley ( f _{2} ) 

(32, 32) ^{D}  (16, 32) ^{D}  0.0 ^{D} 
Griewank ( f _{3} ) 

(600, 600) ^{D}  (300, 600) ^{D}  0.0 ^{D} 
Penalized P8 ( f _{4} ) 

(50, 50) ^{D}  (25, 50) ^{D}  1.0 ^{D} 
Penalized P16 ( f _{5} ) 

(50, 50) ^{D}  (25, 50) ^{D}  1.0 ^{D} 
Rastrigin ( f _{6} ) 

(5.12, 5.12) ^{D}  (2.56, 5.12) ^{D}  0.0 ^{D} 
Schwefel 2.6 ( f _{7} ) 

(500, 500) ^{D}  (500, 250) ^{D}  420.96 ^{D} 
6. Results
This section shows the results of the experiments involving the benchmark functions described previously. In the first section (Section 6.1) of the simulation results, we vary the number of ring layers. The second one (Section 6.2) presents a comparison between each Multiring approach and the topologies already mentioned in Section 2 of this paper.
6.1. Ring layer variation
Table 2 shows the results of MRPSO varying the number of ring layers in simulations involving each benchmark function. For function
One can note that the best choice for function
Function  MRPSO  
3 ring layers  5 ring layers  10 ring layers  
Mean  SD  Mean  SD  Mean  SD  
( f 1 )  17.48  9.39  15.05  7.87  29.48  29.33 
( f 2 )  3.19E9  3.40E9  2.28E9  3.53E9  2.56E10  3.41E10 
( f 3 )  0.0097  0.01  0.00509  0.0063  0.0062  0.00902 
( f 4 )  2.56E32  3.1E32  2.72E32  4.26E32  1.62E32  2.23E32 
( f 5 )  2.72  2.82  3.56  4.94  0.56  1.03 
( f 6 )  16.3  5.19  17.36  7.41  19.57  5.85 
( f 7 )  3305.57  577.24  2963.11  498.9  2686.44  456.16 
communication inside a ring and through different rings, the MRPSO can reach regions with better solutions.
For the dispersed approach for the proposed topology (MRDPSO) (see Table 3) the 5rings configuration achieved the best overall performance.
Function  MRDPSO  
3 ring layers  5 ring layers  10 ring layers  
Mean  SD  Mean  SD  Mean  SD  
( f 1 )  12.99  19.05  9.84  14.42  8.44  5.97 
( f 2 )  6.83E15  1.44 E15  7.31E15  9.01E16  7.54E15  1.61E15 
( f 3 )  0.70E4  0.01  0.80E4  0.80E4  0.01  0.01 
( f 4 )  4.08E32  5.40E32  4.55E32  5.36E32  8.37E33  7.96E33 
( f 5 )  0.28  0.42  0.29  0.41  0.37  0.78 
( f 6 )  14.725  4.008  13.929  3.102  20.39  7.54 
( f 7 )  4063.20  543.16  3969.54  563.79  3975.34  356.32 
For functions
The dispersed coefficient improves the convergence speed, thus is clearly expected that MRDPSO will converge fast than MRPSO. Therefore, the 5rings configuration can be considered the best configuration choice in both MRPSO and MRDPSO.
Varying the number of rings, both MRPSO and MRDPSO can fit to different kind of problems. Hence, the number of rings can be varied according to the problem to be solved.
6.2. Topologies comparison
The results between the comparison of MRPSO and MRDPSO and other topologies are shown in Table 4 and Table 5, respectively. For all the functions, the fitness values presented by the Multiring approaches are the ones that achieved the best performance or similar performance to the best performance.
f  MRPSO  Global  Local  Von Neumann  Four Clusters  
Mean  SD  Mean  SD  Mean  SD  Mean  SD  Mean  SD  
( f 1 )  15.05  7.87  17.712  6.3686  18.215  12.995  39.54  29.36  88.15  44.51 
( f 2 )  2.28E9  3.53E9  1.26E14  3.04E15  9.61E8  8.70E8  1.81E10  1.86E10  0.16  0.51 
( f 3 )  0.00509  0.0063  0.01  0.02  0.0031  6.4E3  0.008  0.01  0.04  0.03 
( f 4 )  1.62E32  2.23E32  5.02E32  5.52E32  6.22E33  7.82E33  9.94E33  1.27E32  9.42E32  5.05E32 
( f 5 )  0.56  1.03  4.46  8.31  1.33  1.47  1.00  1.64  52.67  39.25 
( f 6 )  16.3  5.19  15.35  5.93  21.94  5.33  19.58  4.89  19.58  7.37 
( f 7 )  2686.44  456.16  2164.17  368.74  2964.79  389.31  2898.37  347.01  3633.34  519.53 
f  MRDPSO  Global Dispersed  Local Dispersed  Von Neumann Dispersed  Four Clusters Dispersed  
Mean  SD  Mean  SD  Mean  SD  Mean  SD  Mean  SD  
( f 1 )  8.44  5.97  32.8099  33.7074  15.3180  18.0088  10.8321  13.8913  83.8264  54.0686 
( f 2 )  6.83E15  1.44 E15  1.13E14  3.60E15  9.73E13  5.43E13  7.54E15  9.01E16  0.2947  0.6127 
( f 3 )  0.70E4  0.01  0.0134  0.0137  4.09E11  2.24E10  0.0103  0.014  0.0529  0.0498 
( f 4 )  8.37E33  7.96E33  4.86E32  4.81E32  5.23E33  7.53E33  2.72E32  4.1436  9.10E32  5.09E32 
( f 5 )  0.28  0.42  0.7080  1.5170  0.1375  0.22  0.16  0.401  63.50  40.47 
( f 6 )  13.929  3.102  13.99  3.66  20.96  4.6  21.16  6.84  36.92  6.86 
( f 7 )  3969.54  563.79  2320.08  355.31  3610.0 9  461.8253  3889.64  503.86  3750.91  334.53 
For function
Table 5 shows the results of the MRDPSO and topologies enabled with the dispersion grade strategy. For function
7. Conclusions
This paper has proposed a novel topology for Particle Swarm Optimization based on a multi layer structure based on local communication (
The Multiring approaches achieved better performance or close to wellknown topologies used for comparison. This fact exalts how satisfactory the results involving MRPSO and MRDPSO were. By varying the number of rings, the size of each ring and how the rotation skill work, the proposed approach could be used to reach good quality solutions for both unimodal and multimodal problems. Besides, it helps to avoid the swarm of being trapped at local minima regions, making it moves to new regions of space search in order to help the PSO algorithm to converge to the best solution.
Due to its peculiar features, the proposed PSO topology is an interesting approach able to be applied in different kind of optimization problems.
References
 1.
Abido M. A. 2001 Optimal design of power system stabilizers using particle swarm optimization.  2.
Agrafiotis D. K. Cedeno W. 2002 Feature selection for structureactivity correlation using binary particle swarms.  3.
Bäck T. 1996  4.
BastosFilho C. J. A. Caraciolo M. P. Miranda P. B. C. Carvalho D. F. 2008 Multi Ring Particle Swarm Optimization. In:  5.
Beyer H. G. 2001  6.
Beyer H. G. 2002 Evolution strategies: A comprehensive introduction.  7.
Bratton D. Kennedy J. 2007 Deﬁning a standard for particle swarm optimization,  8.
Cai X. Cui Z. Zeng J. Tan Y. 2008 Dispersed particle swarm optimization.  9.
Carvalho D. F. BastosFilho C. J. A. 2008 Clan particle swarm optimization,  10.
Carvalho D. F. BastosFilho C. J. A. 2009 Clan particle swarm optimization.  11.
Clerc M. Kennedy J. 2002 The particle swarm explosion, stability, and convergence in a multidimensional complex space.  12.
Coello Coello. C. A. Lechuga M. S. 2002 MOPSO: A proposal for multiple objective particle swarm optimization,  13.
Eberhart R. C. Shi Y. 2001 Tracking and optimizing dynamic systems with particle swarms,  14.
Engelbrecht A. P. 2005  15.
Fogel D. 1996  16.
Jiao B. Lian Z. Gu X. 2008 A dynamic inertia weight particle swarm optimization algorithm.  17.
Kennedy J. Eberhart R. C. 1995 Particle swarm optimization,  18.
Kennedy J. 1999 Small worlds and megaminds: effects of neighborhood topology on particle swarm performance,  19.
Kennedy J. Mendes R. 2002 Population structure and particle swarm performance,  20.
Kennedy J. 2005 Why does it need velocity?,  21.
Mendes R. Kennedy J. Neves J. 2003 Watch thy neighbor or how the swarmcan learn from its environment,  22.
Parsopoulos K. E. Vrahatis M. N. 2001 Particle swarm optimizer in noisy and continuously changing environments,  23.
Parsopoulos K. E. Laskari E. C. Vrahatis M. N. 2002 Recent approaches to global optimization problems through particle swarm optimization.  24.
Peer E. S. van den Bergh F. Engelbrecht A. P. 2003 Using neighbourhoods with the guaranteed convergence PSO,  25.
Potter M. A. De Jong K. A. 1994 A cooperative coevolutionary approach to function optimization, In:  26.
Praveen K. Sanjoy D. Stephen M. W. 2007 Multiobjective hybrid PSO using µfuzzy dominance,  27.
SantanaQuintero L. V. Coello Coello. C. A. HernandezDiaz A. G. Velazquez J. M. O. 2008 Surrogatebased MultiObjective Particle Swarm Optimization,  28.
Schwefel H. P. 1981 Numerical Optimization of Computer Models, John Wiley & Sons, Inc,0471099880 York, NY, USA  29.
Shi Y. Eberhart R. C. 1998 A modified particle swarm optimizer,  30.
Shi Y. Krohling R. A. 2002 Coevolutionary particle swarm optimization to solve minmax problems,  31.
Suganthan P. N. 1999 Particle swarm optimiser with neighbourhood operator,  32.
Sutton A. M. Whitley D. Lunacek M. Howe A. 2006 PSO and multifunnel landscapes: how cooperation might limit exploration,  33.
van den Bergh F. Engelbrecht A. P. 2001 Training product unit networks using cooperative particle swarm optimisers,  34.
van den Bergh F. Engelbrecht A. P. 2004 A Cooperative approach to particle swarm optimization.