Particle Swarm Optimization - A Survey <s> Index Topologies <s> The effects of various population topologies on the particle swarm algorithm were systematically investigated. Random graphs were generated to specifications, and their performance on several criteria was compared. What makes a good population structure? We discovered that previous assumptions may not have been correct. <s> BIB001 </s> Particle Swarm Optimization - A Survey <s> Index Topologies <s> Neighbourhood topologies in particle swarm optimization (PSO) are typically random in terms of the spatial positions of connected neighbours. This study explores the use of spatially meaningful neighbours for PSO. An approach is designed which uses heuristics to leverage the natural neighbours computed with Delaunay triangulation. The approach is compared to standard PSO sociometries and fitness distance ratio approaches. Although intrinsic properties of Delaunay triangulation limit the practical application of this approach to low dimensions results show that it is a successful particle swarm optimizer. <s> BIB002
In the lbest-type PSO, neighborhood of particle c i is often a set of particles in the vicinity of c i in the particle indexing structure. In this case, the neighborhoods will have some overlaps. Therefore, the lbest information ( g i and g j ) of different particles (c i and c j ) will be mutually affected via the pbest p k of particle c k which is included in both neighborhoods (S i and S j ). In Fig. 2 (a) , an example of an indexing structure with circular topology is shown where S i includes other particles within arc distance k. Another method of lbest implementation is shown in Fig. 2 (b) . It is the wheel topology which uses a focus particle c 0 . The focus particle is special in that S 0 = S. The neighborhood of other particles always include the focus. In this configuration, the focus c 0 gradually moves towards the global best found so far by the swarm. By its movement towards the global best, the focus c 0 will always indicate the "global trend" of the search by way of its pbest p o . When compared with the gbest-type PSO, lbest-type swarm tends to be slow in convergence, but is less likely to be captured in a local minimum because remote neighbor-hoods (on the indexing structure) tend to search in a different candidate regions BIB001 . In effect, this is equivalent to the maintenance of the diversity which plays an important role in avoiding early convergence of evolutionary algorithms. In the experiments for several functions in Table 1 , Kennedy and Mendes tested various neighborhood types on a Class 1" PSO BIB001 . The types included gbest, lbests with k = 1 on a circular topology, k = 1 on a 3D-pyramid topology, a wheel in Fig. 2 (b) , von Neumann topology in Fig. 2 (c) , and a swarm divided into several isolated neighborhood subsets. The findings from the experiments were as follow. • von Neumann lbest generally achieved best in convergence speed and solution quality. • 3D-pyramid topology scored second best. • Isolated subsets and wheel topology gave moderate results. • Circular lbest was slowest to converge with worsethan-moderate solutions. • gbest had the worst performance, being quick to converge, mostly to one of the local minima. • Results were problem dependent. No all-around superior neighborhood topology was found. Other works on neighborhoods based on indexing topologies include Lane et al. BIB002 finding Delauney triangular grids effective in low dimensional search domains.