Research On Neighborhood Topologies And Modifications Of Particle Swarm Optimization

Inspired by the emergent motion of a flock of birds searching for food, Kennedy and Eberhart introduced a new evolutionary computation technique, Particle Swarm Optimization (PSO), in 1995. As a population-based stochastic algorithm, PSO adopts simple velocity-position model, avoids complex genetic operators and takes advantage of cooperation and competition among individuals in the swarm to attain the solution. Due to the simple concept and easy implementation, PSO has gained much attention and wide applications in different fields.However, the research on PSO is still far from maturity. PSO also suffers from unsubstantial theoretical analysis, premature convergence, unsatisfactory solution precision and limitation of applications. In our work, several aspects of PSO such as neighborhood topologies, algorithm modification and application in discrete optimization problems are studied intensively. The main contributions and innovations of this dissertation are summarized as follows:①Delve into the graph properties of neighborhood topologies and their influences on PSO's performance. By introducing the graph properties (diameter, average path length, clustering coefficient and average degree),the typical static neighborhood topologies such as complete, ring and von Neumann structure are investigated and their graph properties are given. Also, the influences of these graph properties on PSO's performance as well as the correlations between them are analyzed. It is, for the first time, discussed about the neighbor distribution's effects on the performance of PSO and its connection with clustering coefficient. It is concluded that among topologies having same average degree, those with smaller clustering coefficient have more uniform neighbor distribution, smaller diameter and shorter average path length.②A new static neighborhood topology, the non-clique neighborhood topology, is designed. With a given average degree, the non-clique neighborhood topology possesses the lowest clustering coefficient and more uniform neighbor distribution. The performances of the PSO algorithms with different neighborhood topologies which have the same population size and average degree but different clustering coefficient are compared. The experimental results verify the effect of clustering coefficient and the superiority of the non-clique neighborhood topology. Additionally, a further experiment is made to analyze the relationship between average degree and population size in the non-clique neighborhood topology.③A new information-sharing mechanism, the local elitist information-sharing strategy, is proposed. Firstly, the existing information-sharing mechanisms on static neighborhood topologies are analyzed. Then, the influence of neighborhood correlation on the performance of PSO is discussed. The'rich nodes'and the'rich-club'phenomenon in the particle swarm are revealed. It is indicated that the'rich -club'phenomenon may lead PSO to be trapped in local optimum. Based on this idea, local impact factor and local elitist particle are defined, and the local elitist information-sharing strategy is proposed. The experimental results on the benchmark functions and measurement of population diversity show that the PSO with the local elitist information-sharing strategy has better stability and larger diversity but slower searching speed than the PSOs with other information-sharing mechanisms on the different static neighborhood topologies.④Two types of the PSOs with number-based self-adaptive neighborhood extension, the PSO with self-adaptive dynamic neighborhoods (PSOSADN) and the PSO with restricted dynamic neighborhood extension (PSODNE), are developed. The proposed PSOs begin the search with ring topology and then employ neighborhood extension to improve the performance of the original PSO according to particle's evolutionary state and neighborhood relation. In PSOSADN, an expanding probability, derived from the relation between particle and its neighbor best position, is introduced to adaptively adjust the expanding speed,and three expanding strategies are proposed on the basis of the quality of the non-clique neighborhood topology. Three different PSO algorithms, PSOSADN1, PSOSADN2 and PSOSAND3, are presented based on the three expanding strategies. Different from PSOSADN, PSODNE follows the idea of controlling the influence of'rich nodes'. In PSODNE, neighborhood extension factor is defined and novel neighborhood extension & restriction strategies are proposed to adjust the expanding movement and speed. The proposed PSOs are compared with other PSOs using different neighborhood schemes on a suite of benchmark functions. The experimental results show that PSOSADN1 has great superiority on convergence speed, PSOSADN2 has better balanced performance, and PSOSADN2 & PSODNE outperform other PSOs on global searching ability. Also, an experimental analysis is presented about the influences of different extension movements on PSO's performance. ⑤A hybrid particle swarm optimizer with dynamic subswarms (HPSODS) is proposed. On the basis of particle's fitness value, hierarchical clustering method is adopted to dynamically divide the swarm into several subswarms in HPSODS. And these subswarms are classified into four categories according to their performance. Four different functional evolutionary strategies are used in each category and different functional categories cooperate to achieve good optimization performance. Moreover, population entropy is introduced to control clustering frequency. Gaussian mutation and piecewise linear chaotic map are used and four evolutionary strategies are developed to realize searching for different areas and purposes. The experiments are conducted to analyze the effects of the subswarm number and the proposed strategies on the performance of PSO. And the range of the subswarm number is suggested. The experimental results on the classic unimodal and multimodal benchmark functions demonstrate the superiority of the proposed HPSODS over some famous PSOs in terms of global searching ability, solution precision, convergence speed and stability.⑥A new discrete PSO model (SDPSO) for set-based combinatorial optimization problems is constructed and a set-based method for knapsack problems based on this model is designed. In SDPSO, set concepts and operations are introduced into particle swarm optimization. A search space of variable set is defined, particle'velocity and location are re-stated, and new operation rules are designed on the search space. Four knapsack examples with different scales are employed to test the model. The experimental results demonstrate the superiority of the algorithm based on SDPSO over the traditional binary PSO in terms of searching ability and convergence speed, which validates the feasibility and effectiveness of the proposed model.