Research On Discrete Particle Swarm And Its Application In Optimization Problems

The Particle Swarm Optimization(PSO)is an efficient and parallel optimization algorithm, proposed by Eberhart and Kennedy in 1995. Because of its intelligence, simple and easily achieve, so its appearance cause to the attention of many scientists. Now the PSO has become a hot pot in only a few years. There are many improved PSO which is applied in many field, such as function optimization, the training of neural networks, pattern classification, fuzzy systems control. However, the mostly problems which are solved by PSO are not discrete ones. In effect, a remarkably wide variety of problems can be represented by discrete optimization models, such as the Traveling Salesman Problem, Job-shop. So, it is the research content of this paper to extend the basic PSO to solve the discrete optimization models.This paper has mainly finished four research jobs based on existent research results:(1) Taking TSP as an example, redefined the speed and position of the DPSO for solving the discrete problems, and discussed the search performance of the DPSO.(2) The strategy of self-escape which derives from the phenomena that some organisms can escape dynamically from the original cradle when they find the survival density is too high to live is introduced into DPSO, and can boost up the diversity of group.(3) To improve the convergent speed of the algorithm, SEC which is used to solve TSP is introduced into DPSO.(4) To improve the convergent speed of the algorithm further, the method of selecting candidate edges is modified. This paper did many simulative experiments, verified the feasibility and correctness of the above job, and obtained some corresponding results:(1) The self-escape hybrid discrete particle swarm optimization algorithm (SEHDPSO) which is based on the strategy self-escape method and local search method is proposed. The SEHDPSO can improve the premature convergence and search speed of the DPSO. SEHDPSO and ACS+2-OPT is applied in TSP individually. Experimental on 26 TSP cases simulations indicate that the superiority of SEHDPSO over ACS+2-OPT, especially the U724, not only the accuracy of the results, but also the computing time, the SEHDPSO is better than ACS+2-OPT. The average error, the least error and the CPU time of The SEHDPSO is 35 percent, 29 percent, 26.6 percent of the ACS+2-OPT.(2) The 5-relative nearest neighbor method which can produce candidate list more efficiently than 5-nearest neighbor method is proposed. The candidate list which is produced by the previous one is only four-five of the one which is produced by the latter.(3) The reinforced self-escape discrete particle swarm optimization(RSEHDPSO)which is based on the improved method of self-escape and producing candidate list is proposed. RSEHDPSO is applied in TSP, and the experiment results show that the RSEHDPSO have a better performance. The average error, the least error and the CPU time of The RSEHDPSO is 33.3 percent, 25 percent, 24.8 percent of the ACS+2-OPT.At last, the RSEHDPSO is applied in fixed shelf order-picking optimization problem, and compared with the hybrid genetic algorithm. Simulation results show that all the indicators of the RSEHDPSO are better than the hybrid genetic algorithm.