InTech uses cookies to offer you the best online experience. By continuing to use our site, you agree to our Privacy Policy.

Computer and Information Science » Numerical Analysis and Scientific Computing » "Evolutionary Computation", book edited by Wellington Pinheiro dos Santos, ISBN 978-953-307-008-7, Published: October 1, 2009 under CC BY-NC-SA 3.0 license. © The Author(s).

Chapter 28

Multi-Ring Particle Swarm Optimization

By Carmelo J. A. Bastos-Filho, Danilo F. Carvalho, Marcel P. Caraciolo, Pericles B. C. Miranda and Elliackin M. N. Figueiredo
DOI: 10.5772/9597

Article top

Overview

Commonly used particle topologies: (a) Star topology used in gbest, (b) Ring topology used in lbest, (c) Von Neumann topology and (d) Four clusters topology.
Figure 1. Commonly used particle topologies: (a) Star topology used in gbest, (b) Ring topology used in lbest, (c) Von Neumann topology and (d) Four clusters topology.
Multi-Ring Topology.
Figure 2. Multi-Ring Topology.
Ring layers structure.
Figure 3. Ring layers structure.
Rotation skill example.
Figure 4. Rotation skill example.
Multi-Ring topology of 2 ring layers with 3 particles.
Figure 5. Multi-Ring topology of 2 ring layers with 3 particles.
Multi-Ring particle swarm optimization algorithm.
Figure 6. Multi-Ring particle swarm optimization algorithm.
Particle swarm position and velocity updating algorithm.
Figure 7. Particle swarm position and velocity updating algorithm.
Particle information updating algorithm.
Figure 8. Particle information updating algorithm.
Rotation simulation process.
Figure 9. Rotation simulation process.
Multi-Ring rotation process.
Figure 10. Multi-Ring rotation process.
Grade criteria at Multi-Ring PSO.
Figure 11. Grade criteria at Multi-Ring PSO.

Multi-Ring Particle Swarm Optimization

Carmelo J. A. Bastos-Filho1, Danilo F. Carvalho1, Marcel P. Caraciolo1, B. C. Miranda Péricles1 and M. N. Figueiredo Elliackin1

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, easy-to-use 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; Santana-Quintero 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 & Bastos-Filho, 2008; Carvalho & Bastos-Filho, 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 sub-swarms cooperatively. CPSO inserts another parameter called split factor which can be interpreted as the number of sub-swarms that compose the entire swarm.

By using the ring structure as an inspiration, a novel PSO topology called Multi-ring PSO (MRPSO) based on coupling different rings was recently proposed (Bastos-Filho 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 Multi-ring topology and its features are described. Section 4 is devoted to the Dispersed based Multi-ring approach. The simulation setup used by the experiments and the chosen benchmark functions are presented in Section 6. In section 7 the analysis of Multi-ring and Multi-ring Dispersed are shown. The results of a comparison with some well-known 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, i. e., the position of one particle represents exactly the values of the attributes of a solution. Besides, particles move inside the search space reaching new positions. After some iterations, particles tend to a global optimum based on two basic components: the cognitive component and the social component. The first one considers the best position already found by the particle itself (pbest). The second one use the best position attained by all the particles of the swarm (gbest) in order to guide the swarm to a common spot in the search space. Based on these two information components, each particle updates its own velocity. The velocity is a vector that directs the particle to the next position.

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 w (see equation 1). This factor balances the exploration-exploitation trade-off by controlling the contribution of the previous velocity in the evaluation of the current velocity of each particle. For each iteration of the PSO algorithm the velocity vi(t) contribution is decreased. Thus, the exploitation level of the swarm is increased.

vi(t+1)=ωvi(t)+c1r1(pi(t)xi(t))+c2r2(pg(t)xi(t))
(1)

where w is the inertia factor, xi(t) is the current position of particle i in time step t, c 1 and c 2 are positive acceleration constants, and r1 and r2 are two random numbers generated by a uniform distribution in the interval [0,1].

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

media/image4.jpg

Figure 1.

Commonly used particle topologies: (a) Star topology used in gbest, (b) Ring topology used in lbest, (c) Von Neumann topology and (d) Four clusters topology.

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 well-known 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).

Star and ring topologies are shown in Figure 1(a) and Figure 1(b), respectively. Star topology is composed by a fully-connected structure (gbest) that allows each particle of the swarm to share information globally. In a global neighbourhood, information is instantaneously disseminated to all particles, quickly attracting the entire swarm to the same swarm region. To avoid local minima, ring topology (Figure 1(b)) make use of local neighbourhoods (lbest), i. e., particles just communicate with its immediate neighbours. Therefore, the swarm needs a great number of iterations to converge, but higher quality solutions can be found.

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 Von Neumann topology.

Based on clusters of particles, the four clusters topology is shown in Figure 1(d). Each cluster communicates with the others by connections previous defined between the particles (Mendes et al., 2003; Engelbrecht, 2005). The number of connections originated from a cluster is equal to the number of neighbour clusters.

3. Multi-ring topology

3.1. Multi-ring concepts

Multi-Ring is a novel PSO topology that uses the ring structure as an inspiration. By using local communication, each particle of the swarm has its own neighbourhood. Many papers have shown that it improves the explorarion capacity of the entire swarm but decreases the convergence time of the algorithm (Engelbrecht, 2005; Carvalho & Bastos-Filho, 2008; Carvalho & Bastos-Filho, 2009). A topology based on coupling different rings with dynamic commutation of the neighbourhood is proposed, which aims to obtain better solutions as the benefit of the local communication. At the same time, we expect to reduce the number of iterations to reach a convergence as the benefit of the dynamic neighbourhood mechanism.

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

media/image5.jpg

Figure 2.

Multi-Ring Topology.

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 multi-ring 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 rl (k) , each particle rl (k)(i) is directly connected with the particles rl (k-1)(i) and rl (k+1)(i) of the next and previous ring layers. During the algorithm execution, one particle rl (k)(i) will exchange information with a neighbourhood composed by { rl (k)(i-1), rl (k)(i+1), rl (k-1)(i) , rl (k+1)(i) }.

media/image6.jpg

Figure 3.

Ring layers structure.

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 rl (1) is limited by the set { rl (1)(i-1), rl (1)(i+1), rl (2)(i) }. The same restriction must be considered for the ring rl (n), which the neighbourhood is composed by the set { rl (n)(i-1), rl (n)(i+1), rl (n-1)(i) }.

One particle which belongs to a ring layer rl (k) exchange information with other layers rl (k-1) and rl (k+1) in order to make use of the social information achieved by the other layers. If one particle just exchanges information with the same neighbourhood through the entire execution of the algorithm, the neighbourhood would be static. In this case, the topology is just a simple local approach. To avoid this static possibility, one important process was added to the proposed topology, called rotation skill.

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 Multi-Ring approach, the particles of different rings exchange information between themselves using local communication. The particle that belongs to a ring rl (k) exchanges information with other rings rl (k-1) and rl (k+1) aiming to transmit its previous experience.

Each ring layer of the Multi-Ring has the ability to self-rotate. It means that if the ring layer rl (k) does not improve its own best position, defined as ringbest, it will be rotated. In the rotation process, each particle in the ring layer has its index changed to i = (i+d) mod (nl), where d is the rotation distance and nl is the number of particles in a layer. Thus, the new neighbourhood will be composed by { rl (k)(i-1), rl (k)(i+1), rl (k-1)(i+d) , rl (k+1)(i+d) }. One can note that the main difference is the communication replacement between the neighbour ring layers.

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.

media/image7.jpg

Figure 4.

Rotation skill example.

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 rl (k) . If the best solution found remains with the same value during t r iterations, so this ring layer will be rotated after t r iteration.

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. Multi-ring 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 Multi-Ring topology containing an example with two ring layers (rl (1) and rl (2) ) of three particles.

media/image8.jpg

Figure 5.

Multi-Ring topology of 2 ring layers with 3 particles.

In the basic PSO algorithm, one of the steps is the definition of the initial pbest and gbest, which represent the best position found by the particle and swarm, respectively. The manner how the value of pbest is updated or chosen is not influenced by the use of Multi-Ring topology, since it is related to the individual experience of the particle. Therefore, all the particles of the swarm define the pbest in the same way.

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 gbest, in the Multi-Ring approach, the definition of this new position called ringbest, considers only the particles within the respective ring layer. Therefore, each ring layer will have its own ringbest. After that, the ringbests of each ring layer are compared with each other, and the best one will be selected as the best solution. The pseudo-code of the algorithm is presented in Figure 6.

media/image9.jpg

Figure 6.

Multi-Ring particle swarm optimization algorithm.

After the pbest evaluation, the algorithm performs the selection of the best particle of the respective ring layer. This process is repeated for all the ring layers that compose the Multi-Ring topology (see Line 10 in Figure 6). Line 12 of Figure 6 shows that the selection of the best ringbest for the topology occurs at the end of each algorithm iteration.

The updateVelocityAndPosition() and updateInformation() processes are the core of any PSO algorithm. These two processes are described in the pseudo-codes of Algorithms 2 and 3 that are shown in Figures 7 and 8, respectively.

media/image10.jpg

Figure 7.

Particle swarm position and velocity updating algorithm.

media/image11.jpg

Figure 8.

Particle information updating algorithm.

The other process involved in Algorithm 1 execution is rotate() (see Line 4), which belongs only to the multi-ring topology approach proposed here. One can note that this step is done before the fitness evaluation. Figure 9 can be used to represent this process. Consider that the rotation trigger criterion used is the number of successive iterations that the best solution found (ringbest) by the ring layer has not improved and d is the number of positions that the ring will be rotated. Using t r to represent the trigger mechanism and X i to represent the particle i of the ring layer X, the ring layer X will be rotated if the value of its best position has not improved after t r iterations. Otherwise, if the respective number of iterations is below t r, the algorithm does not rotate the ring layer X and the number of iterations is incremented. This process is done for all ring layers of the Multi-ring topology.

When the trigger criterion is satisfied, the ring layer is rotated by d particles and the number of iterations that the ringbest did not improved is reset. It implies in a new neighbourhood for each particle of the rotated ring and, as a result, it improves the social information exchange. One can note that there is a trigger criteria t r(k) for each ring layer rl (k). The figure 10 illustrates the rotation algorithm process described above.

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

media/image12.jpg

Figure 9.

Rotation simulation process.

media/image13.jpg

Figure 10.

Multi-Ring rotation process.

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 global or local approaches, they neglect the differences between the particles in the search process. These settings lose some information that can be useful to find the global optima or escape from local optima.

To minimize this problem, Cai et al. (Cai et al., 2008) proposed a new index to indicate performance differences, named Grade i (t). The definition of the index is provided as follows:

Gradei(t)=fworst(t)f[xi(t)]fworst(t)fbest(t)
(2)

where f worst (t) and f best (t) are the worst and the best fitness values of the swarm at time step t, respectively.

Occasionally, the swarm can converge onto one point, that means f worst (t) = f best (t). In this case, the value Grade i (t) of an arbitrary particle i is set to 1. Grade i (t) represents the performance of particle i at time t, according to its fitness value of the current position. The better particle is, the larger Grade i (t) is, and vice-versa.

In most cases, if the fitness value of particle i is better than the fitness of particle u, the probability of i’s neighbourhood falls into a global optima is higher than the particle u. Thus, the particle i should give more attentions to exploit its neighbourhood. On the contrary, it may tend to explore other regions with a larger probability. Therefore, the best solution should perform a complete search around its historical best position and the worst solution should perform a global search around the best solution found so far.

Then, the dispersed social coefficient of particle i at time t is set as follows:

c2,i(t)=clow+(cupclow)Gradei(t)
(3)

where c up and c down are two predefined numbers, and c 2,i (t) represents the social coefficient of particle j at time t. One can note that better particles will present higher values for c 2 .

4.2. Multi-ring dispersed particle swarm optimization

Based on the new manner to determine the acceleration coefficients, the dispersed PSO approach was included into the Multi-Ring Topology. By applying the Grade i (t) to determine the communication rules inside each ring, we expect that it will improve the performance of the search made by the Multi-Ring PSO algorithm.

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 Grade i (t) is above a threshold (good solutions), we reduce the neighbourhood of the particle. In this case, the neighbourhood of the particle i is defined as { rl (k)(i-1), rl (k)(i+1), rl (k-1)(i) , rl (k+1)(i) }. Otherwise, the particle should expand its communication range to achieve more information, which it would get information from all particles in the same ring in order to increase its experience. One can note that rings which the ringbest are below the threshold will perform searches using a more connected structure in order to achieve better regions in the search space. In spite of this, one should note that the communication between the ring layer remains local.

media/image16.jpg

Figure 11.

Grade criteria at Multi-Ring PSO.

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 (f 1 ) or multimodal (f 2 , f 3 , f 4 , f 5 , f 6 and f 7 ) containing many local minima and a high level of complexity. For the simulations, each function was tested with 30 dimensions.

Each simulation was performed using PSO with inertia factor. The reduction of w is linear and starts at 0.9 decreasing to 0.4 along the iterations. The number of rings was varied based on a swarm with 30 particles. Thus, the number of ring layers is defined as nl = 30 / n. The rotation distance is equal to a half of the ring layer size (d = nl / 2) and the trigger criterion was t r = 15.

We used c 1 and c 2 equal to 2.05. In the MRDPSO, we used c low = 1.5 and c up = 2.5.

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.

FunctionEquationSearch spaceInit.Opt.
Rosenbrock ( f 1 ) f1=i=1n1[100(xi+1xi2)2+(1xi)2] (-30, 30) D (15, 30) D 1.0 D
Ackley ( f 2 ) f4=20exp(0.21ni=1nxi2)exp(1ni=1ncos(2πxi))+20+e (-32, 32) D (16, 32) D 0.0 D
Griewank ( f 3 ) f3=1+i=1nxi24000i=1ncos(xii) (-600, 600) D (300, 600) D 0.0 D
Penalized P8 ( f 4 ) f7=πn{10sin2(πyi)+i=1n1(yi1)2{1+10sin2(πyi+1)}+(yn1)2}+i=1nμ(xi,10,100,4) yi=1+14(xi+1) μ(xiakm)={k(xia)mxia0axiak(xia)mxia} (-50, 50) D (25, 50) D -1.0 D
Penalized P16 ( f 5 ) f8=0.1{sin2(3πxi)+i=1n1(xi1)2{1+sin2(3πxi+1)}+(xn1)2×{1+sin2(2πxn)}}+i=1nμ(xi,5,100,4) (-50, 50) D (25, 50) D 1.0 D
Rastrigin ( f 6 ) f2=10n+i=1n[xi210cos(2πxi)] (-5.12, 5.12) D (2.56, 5.12) D 0.0 D
Schwefel 2.6 ( f 7 ) f6=i=1nxisin(xi) (-500, 500) D (-500, -250) D 420.96 D

Table 1.

Benchmark functions used in the experiments.

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 Multi-ring 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 f 6 , the structure composed by 3 ring layers behaved better. The 5-ring MRPSO achieved a better performance for functions f 1 , f 2 and f 3 , and the 10-ring behaves better for f 4 , f 5 , and f 7 .

One can note that the best choice for function f 6 was 3-ring layers followed by the 5-rings configuration. Thus, in general, the 5-rings configuration achieved the most satisfactory fitness values. This is due to the fact that maintaining a balance between the degree of

FunctionMRPSO
3 ring layers5 ring layers10 ring layers
MeanSDMeanSDMeanSD
( f 1 )17.489.3915.057.8729.4829.33
( f 2 )3.19E-93.40E-92.28E-93.53E-92.56E-103.41E-10
( f 3 )0.00970.010.005090.00630.00620.00902
( f 4 )2.56E-323.1E-322.72E-324.26E-321.62E-322.23E-32
( f 5 )2.722.823.564.940.561.03
( f 6 )16.35.1917.367.4119.575.85
( f 7 )3305.57577.242963.11498.92686.44456.16

Table 2.

Number of ring layers variation of MRPSO.

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 5-rings configuration achieved the best overall performance.

FunctionMRDPSO
3 ring layers5 ring layers10 ring layers
MeanSDMeanSDMeanSD
( f 1 )12.9919.059.8414.428.445.97
( f 2 )6.83E-151.44 E-157.31E-159.01E-167.54E-151.61E-15
( f 3 )0.70E-40.010.80E-40.80E-40.010.01
( f 4 )4.08E-325.40E-324.55E-325.36E-328.37E-337.96E-33
( f 5 )0.280.420.290.410.370.78
( f 6 )14.7254.00813.9293.10220.397.54
( f 7 )4063.20543.163969.54563.793975.34356.32

Table 3.

Number of ring layers variation of MRDPSO.

For functions f 2 , f 3 and f 5 the 3-rings configuration achieved the best fitness values. The configuration with 10 ring layers achieved better performance in functions f 1 and f 4 . Again, we can consider that a configuration with 5-rings is enough to reach satisfactory fitness values in complex and different search spaces.

The dispersed coefficient improves the convergence speed, thus is clearly expected that MRDPSO will converge fast than MRPSO. Therefore, the 5-rings 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 Multi-ring approaches are the ones that achieved the best performance or similar performance to the best performance.

fMRPSOGlobalLocalVon NeumannFour Clusters
MeanSDMeanSDMeanSDMeanSDMeanSD
( f 1 )15.057.8717.7126.368618.21512.99539.5429.3688.1544.51
( f 2 )2.28E-93.53E-91.26E-143.04E-159.61E-88.70E-81.81E-101.86E-100.160.51
( f 3 )0.005090.00630.010.020.00316.4E-30.0080.010.040.03
( f 4 )1.62E-322.23E-325.02E-325.52E-326.22E-337.82E-339.94E-331.27E-329.42E-325.05E-32
( f 5 )0.561.034.468.311.331.471.001.6452.6739.25
( f 6 )16.35.1915.355.9321.945.3319.584.8919.587.37
( f 7 )2686.44456.162164.17368.742964.79389.312898.37347.013633.34519.53

Table 4.

Comparison between MRPSO and other topologies.

fMRDPSOGlobal DispersedLocal DispersedVon Neumann DispersedFour Clusters Dispersed
MeanSDMeanSDMeanSDMeanSDMeanSD
( f 1 )8.445.9732.809933.707415.318018.008810.832113.891383.826454.0686
( f 2 )6.83E-151.44 E-151.13E-143.60E-159.73E-135.43E-137.54E-159.01E-160.29470.6127
( f 3 )0.70E-40.010.01340.01374.09E-112.24E-100.01030.0140.05290.0498
( f 4 )8.37E-337.96E-334.86E-324.81E-325.23E-337.53E-332.72E-324.14369.10E-325.09E-32
( f 5 )0.280.420.70801.51700.13750.220.160.40163.5040.47
( f 6 )13.9293.10213.993.6620.964.621.166.8436.926.86
( f 7 )3969.54563.792320.08355.313610.0 9461.82533889.64503.863750.91334.53

Table 5.

Comparison between MRDPSO and other topologies.

For function f 1 and f 5 MRPSO reaches the best fitness values (F = 15.05 and F = 0.56). For all the other functions used, it reaches values close to the best performance achieved by some well known topologies. A good example is the performance for functions f 6 and f 7 , in which the only topology that achieved fitness values better than the ones achieved by MRPSO was the global topology. Hence, considering that MRPSO is a local communication topology, the results presented by Table 4 are strongly satisfactory.

Table 5 shows the results of the MRDPSO and topologies enabled with the dispersion grade strategy. For function f 1 , f 2, and f 6 the MRDPSO achieves the best fitness values (F=8.44, F=6.83E-15 and F=13.929). For the functions f 3 and f 5 , it reaches a good value for the mean fitness with low standard deviation, close to the best performance achieved by well known topologies. For the function f 7, MRDPSO achieves a value for the mean fitness in the same order of magnitude of Dispersed PSO with local, Von Neumann and Four Clusters topologies. Therefore, considering all results shown at the Table 5, the MRDPSO achieves good solutions for both unimodal and multimodal problems.

7. Conclusions

This paper has proposed a novel topology for Particle Swarm Optimization based on a multi layer structure based on local communication (lbest). The Multi-ring PSO (MRPSO) and also its combination with the Dispersed PSO approach (MRDPSO) are thoroughly described. The first one introduces a new feature called rotation skill that minimizes the stagnation probability of the PSO algorithm. In the second one, some changes in the communication rules inside the rings were made by using the dispersion grade attribute of Dispersed PSO approach.

The Multi-ring approaches achieved better performance or close to well-known 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 - M. A. Abido, 2001 Optimal design of power system stabilizers using particle swarm optimization. IEEE Trans. Energy Conversion, 17 3 (September 2002) 7 406-413), 0885-8969
2 - D. K. Agrafiotis, W. Cedeno, 2002 Feature selection for structure-activity correlation using binary particle swarms. J. Medicinal Chem., 45 5 (February 2002) 9 1098-1107)
3 - T. Bäck, 1996 Evolutionary Algorithms in Theory and Practice, Springer-Verlag, 0-19509-971-0 Germany
4 - C. J. A. Bastos-Filho, M. P. Caraciolo, P. B. C. Miranda, D. F. Carvalho, 2008 Multi Ring Particle Swarm Optimization. In: SBRN’2008 (the 10th Brazilian Symposium on Neural Networks), 111 116 , 2008, Salvador/BA. Proceedings of SBRN’2008 (the 10th Brazilian Symposium on Neural Networks), 2008
5 - H. G. Beyer, 2001 The Theory of Evolution Strategies, Springer-Verlag New York, Inc., 3-54067-297-4 York, NY, USA
6 - H. G. Beyer, 2002 Evolution strategies: A comprehensive introduction. Nat. Comput., 1 1 (March 2002) 49 3-52), 1567-7818
7 - D. Bratton, J. Kennedy, 2007 Defining a standard for particle swarm optimization, Proceedings of Swarm Intelligence Symposium SIS 2007, 120 127 , 1-42440-708-7 HI, April 2007, IEEE Service
8 - X. Cai, Z. Cui, J. Zeng, Y. Tan, 2008 Dispersed particle swarm optimization. Information Processing Letters, 105 6 (February 2008) 4 231-235), 0020-0190
9 - D. F. Carvalho, C. J. A. Bastos-Filho, 2008 Clan particle swarm optimization, Proceedings of IEEE Congress on Evolutionary Computation CEC 2008 (IEEE World Congress on Computational Intelligence), 3044 3051 , 978-1-42441-822-0 Hong Kong, June 2008
10 - D. F. Carvalho, C. J. A. Bastos-Filho, 2009 Clan particle swarm optimization. International Journal of Intelligent Computing and Cybernetics, 2 2 (June 2009) 31 197- 227), 0175-6378X
11 - M. Clerc, J. Kennedy, 2002 The particle swarm- explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation, 6 1 (February 2002) 5 58-73), 0108-9778X
12 - Coello. C. A. Coello, M. S. Lechuga, 2002 MOPSO: A proposal for multiple objective particle swarm optimization, Proceedings of 2002 IEEE Congr. Evolutionary Computation CEC 2002, 1051 1056 , 0-78037-282-4 HI, May 2002, IEEE Computer Society, Washington, DC, USA
13 - R. C. Eberhart, Y. Shi, 2001 Tracking and optimizing dynamic systems with particle swarms, Proceedings of 2001 IEEE Congr. Evolutionary Computation CEC 2001, 94 100 , 0-78036-657-3 South Korea, May 2001
14 - A. P. Engelbrecht, 2005 Fundamentals of Computational Swarm Intelligence, John Wiley & Sons, 0-47009-191-6
15 - D. Fogel, 1996 Evolutionary Computation: Toward a New Philosophy of Machine Intelligence, Wiley-IEEE Press, 978-0-47166-951-7
16 - B. Jiao, Z. Lian, X. Gu, 2008 A dynamic inertia weight particle swarm optimization algorithm. Chaos, Solitons and Fractals, 37 3 (August 2008) 7 698-705), 0960-0779
17 - J. Kennedy, R. C. Eberhart, 1995 Particle swarm optimization, Proceedings of the IEEE Int. Conf. on Neural Networks, 1942 1948 , 0-78032-768-3 WA, Australia, December 1995, IEEE Service Center, Piscataway, NJ
18 - J. Kennedy, 1999 Small worlds and mega-minds: effects of neighborhood topology on particle swarm performance, Proceedings of 1999 Congress on Evolutionary Computation CEC 99, 1938 0-78035-536-9 DC, USA, July 1999, IEEE Service
19 - J. Kennedy, R. Mendes, 2002 Population structure and particle swarm performance, Proceedings of the 2002 Congress on Evolutionary Computation CEC 2002, 1671 1676 , 0-78037-282-4 HI, USA, May 2002, IEEE Press
20 - J. Kennedy, 2005 Why does it need velocity?, Proceedings of the Swarm Intelligence Symposium SIS 2005, 38 44 , 0-78038-916-6 California, June 2005
21 - R. Mendes, J. Kennedy, J. Neves, 2003 Watch thy neighbor or how the swarmcan learn from its environment, Proceedings Swarm Intelligence Symposium SIS 2003, 88 94 , 0-78037-914-4 Indiana, USA, April 2003, IEEE Service
22 - K. E. Parsopoulos, M. N. Vrahatis, 2001 Particle swarm optimizer in noisy and continuously changing environments, Proceedings of Artificial Intelligence and Soft Computing, 289 294 , Cancun, Mexico, 2001, IASTED/ACTA Press
23 - K. E. Parsopoulos, E. C. Laskari, M. N. Vrahatis, 2002 Recent approaches to global optimization problems through particle swarm optimization. Natural Computing, 1 2-3 , (June 2002) 235 306 ), 1572-9796
24 - E. S. Peer, F. van den Bergh, A. P. Engelbrecht, 2003 Using neighbourhoods with the guaranteed convergence PSO, Proceedings of 2003 IEEE Swarm Intelligence Symposium SIS’03, 235 242 , 0-78037-914-4 Indiana, USA, April 2003, IEEE Service
25 - M. A. Potter, K. A. De Jong, 1994 A cooperative coevolutionary approach to function optimization, In: The Third Parallel Problem Solving From Nature, 8 249-257), Springer Berlin / Heidelberg, 978-3-54058-484-1 Berlin, Germany
26 - K. Praveen, D. Sanjoy, M. W. Stephen, 2007 Multi-objective hybrid PSO using µ-fuzzy dominance, Proceedings of 9th annual conference on Genetic and evolutionary computation GECCO’07, 853 860 , 978-1-59593-697-4 London, England, July 2007, ACM, New York, NY, USA
27 - L. V. Santana-Quintero, Coello. C. A. Coello, A. G. Hernandez-Diaz, J. M. O. Velazquez, 2008 Surrogate-based Multi-Objective Particle Swarm Optimization, Proceedings of Swarm Intelligence Symposium SIS 2008, 1 8 , 978-1-42442-704-8 St. Louis, Missouri, September 2008, IEEE
28 - H. P. Schwefel, 1981 Numerical Optimization of Computer Models, John Wiley & Sons, Inc, 0-47109-988-0 York, NY, USA
29 - Y. Shi, R. C. Eberhart, 1998 A modified particle swarm optimizer, Proceedings of the IEEE International Conference on Evolutionary Computation, 69 73 , 0-78034-869-9 AK, USA, May 1998, IEEE Press, Piscataway, NJ
30 - Y. Shi, R. A. Krohling, 2002 Co-evolutionary particle swarm optimization to solve min-max problems, Proceedings of 2002 IEEE Conf. Evolutionary Computation CEC 2002, 1682 1687 , 0-78037-282-4 HI, May 2002, IEEE Computer Society, Washington, DC, USA
31 - P. N. Suganthan, 1999 Particle swarm optimiser with neighbourhood operator, Proceedings of the 1999 Congress on Evolutionary Computation CEC 99, 1962 0-78035-536-9 DC, USA, June 1999
32 - A. M. Sutton, D. Whitley, M. Lunacek, A. Howe, 2006 PSO and multi-funnel landscapes: how cooperation might limit exploration, Proceedings of 8th Annual Conference on Genetic and Evolutionary Computation GECCO’08, 75 82 , 1-59593-186-4 Washington, USA, July 2008, ACM, New York, NY, USA
33 - F. van den Bergh, A. P. Engelbrecht, 2001 Training product unit networks using cooperative particle swarm optimisers, Proceedings of International Joint Conference on Neural Networks IJCNN’01, 126 131 , 0-78037-044-9 DC, USA, July 2001
34 - F. van den Bergh, A. P. Engelbrecht, 2004 A Cooperative approach to particle swarm optimization. IEEE Transactions on Evolutionary Computation, 8 3 (June 2004) 14 225-239), 0108-9778 X