Research On Dynamic Topology Of Particle Swarm Algorithms

Optimization problems are of vital importance in fields of computer science, artificial intelligence, operational research and other relative fields. Many problems encountered in engineering technology, scientific research and economic management can be treated as variations of challengeable nonlinear optimization problem, such as: configuration designing need to minimize total weight of materials used while satisfying the intensity request; resource allotting need to maximize total benefit utilizing limited resources; transportation scheming need to minimize total expense on circumstance of appointed material and load capability; manufacture scheme arranging need to maximize total benefit by controlling the costs of manpower, devices, and raw and processed materials according to the flow of techniques and demand of client. Optimization theory and its techniques will surely take more and more important part in the information era of 21 century.Numerical optimization methods were proposed these years due to the universality of optimization problems. Many hard optimization problem emerged which cannot be solved in acceptable time, with the increasing complexity of real tasks in the field of industry and scientific research. More effective and practicable algorithms are needed for the traditional programming methods cannot meet complex problems nowadays.As a newly developed swarm intelligence paradigm, particle swarm algorithm is a very promising optimization tool, with many advantages in high-dimensional problems or tasks that lack prior knowledge. Its basic idea is originated from Social Psychology and Artificial Life as a simulation of socio-cognitive processes. Because of its high convergence rate and excellent generalization, particle swarm algorithm has attracted much attention since it was first proposed in 1995.In this literature, most researchers have focused their efforts on how to promote the convergence rate and avoid the premature convergence problem. Introducing new mechanisms to ensure the diversity of swarm population or escape from local minima may be useful on relieving premature convergence of the algorithm. As to improving convergence rate, much work focus on tuning strategy parameters, or modifying the original framework with ideas inspired from other meta-heuristics. As most researchers of this field are with pure scientific computing or engineering applications background, they care more about the results than probe into the real cause, not to mention consider social psychology origins of the algorithm.In our research, we attach importance to both theoretical analysis and experimental demonstration. From the aspect of information spread efficiency, a dynamic topology of particle swarm algorithm is thoroughly investigated and a novel particle swarm algorithm based on small world network model is proposed. The major contributions of the dissertation are:(1) We summarize the developing background of swarm intelligence, and introduce three methodologies of swarm intelligence: Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO) and Artificial Fish-Swarm Algorithm (AFSA). The intrinsic and general character of swarm intelligence is analyzed through relevancy of reductionism, artificial life, self-organization system, and other topics.(2) We investigate the influence of parameters by large experiments and verify the parameter selecting of canonical PSO.(3) We analyze convergence of traditional PSO algorithm from the view of linear constant system, and elicit that the track of any particle will converge to the position held by the optimal particle. Then we theoretically analyze algorithm convergence from the view of random system, and present a sufficient condition for the system to be mean square stable. This enhances the effectiveness of conclusion under linear constant condition.(4) We propose two novel PSO algorithm based on edge-reassigning and edge-addition small-world network model, thus implement dynamic topology of PSO algorithm. New parameters introduced are thoroughly investigated by large amount of experiments on Benchmark problems.(5) The proposed algorithms are rigorously tested and compared on large amount of selected benchmark problems taken from the literature. These benchmark problems are designed to challenge optimization techniques with difficulty of high-dimensionality, multimodality, and deceptive gradient information. In this dissertation, we focus attention on comparing the performance of different algorithms on hard multimodal functions, and give the statistical results on measurements of convergence rate, success rate, function evaluations, and the quality of obtained solutions. The results of experiments demonstrate that the proposed small-world PSO algorithms with dynamic topology can improve performance of classical PSO algorithms apparently.