Research On The Improvements And Applications Of Particle Swarm Optimization

Particle Swarm Optimization (PSO) is a global optimization algorithm and it has attracted the attentions of more and more researchers because it is easy to implement and it has a good performance on many problems. At present, the research on Particle Swarm Optimization is focused on three aspects, namely, the theoretical analysis of PSO, the improvement of PSO and the application of PSO.This thesis analyzes the evolution process of the PSO algorithm, points out that the randomness is indispensable for the standard PSO and gives the methods to eliminate the random factors in the PSO. Since the standard PSO has premature problems, some improvements are made to the PSO to solve the premature problems. The application of PSO in the flow shop scheduling problem (FSSP) is also discussed. The main works in this thesis can be described as follows:(1) In the standard PSO algorithm, the randomness guarantees the good performance of the algorithm, but it presents great challenges for the theoretical analysis of the algorithm. Consequently, some researchers gave simplified deterministic models for the PSO algorithm, but it is questionable whether the conclusions derived from the deterministic models can be applied to standard PSO algorithm. In the thesis, experiment results demonstrate that directly eliminate the randomness in the PSO algorithm will result in the fail of the algorithm to get an acceptable result. Then the importance of the randomness is discussed and an equivalent method to use the randomness is given based on the analysis, the proposed method has similar performance with the standard PSO, which demonstrate the correctness of the analysis. To eliminate the randomness, a heuristic strategy to select dimensions that need to be updated in every iteration is given, and the experiment results proved the effectiveness of the strategy and it demonstrate that it is possible to eliminate the randomness in the PSO algorithm.(2) In the PSO algorithm, the diversity of the swarm will lose rapidly through the evolution process, and the premature convergence problem arises, which leads the algorithm to be trapped in local optima. Based on the analysis of the evolution process, two improved algorithms are proposed. In the first method, particle similarity based mutation is introduced to the PSO algorithm, which can increase the diversity of the swarm and discover potential better solutions which cannot be get through the normal evolution process. Experiment results show that this method can greatly improve the performance of the algorithm on the complex multimodal functions, In the second method, noting that PSO has great global-search ability, while EO has strong local-search capability, a novel hybrid PSO-EO algorithm which combines the merits of PSO and EO is presented. Experiment results indicate that the PSO-EO algorithm can get better results on almost all of the test functions. (3) Flow-shop scheduling problem (FSSP) is a strongly NP-hard combinatorial optimization problem, and it is a branch of production scheduling problem. To apply the PSO algorithm in the FSSP, the methods to represent the solutions of the FSSP need to be designed, so two representations are given, and the experiment results shows that the real-coded algorithm is a little better than the integer-coded algorithm. Also, some improved methods proposed in the thesis are also used to solve the FSSP, and they can get better solutions than the standard PSO algorithms.