Hybrid Particle Swarm Optimization Based On Parasitic Behavior And Its Application In TSP

Traveling salesman problem is a well-known NP-hard problem,but also a typical combinatorial optimization problem. With the increasing in the number of cities, TSP has been more complex and difficult, which could not be solved by general algorithms,therefore, we urgently need a high efficiency and intelligent optimization approach. Particle swarm optimization is an intelligent algorithm that simulates the activity patterns and trajectories in birds foraging,which starts searching from generating a set of randomly candidate solutions and completes optimization objectives through the interaction between the particles iteration.To solve the traveling salesman problem better,we study the basic theory and related application of particle swarm optimization,then propose a hybrid particle swarm optimization based on parasitic behavior in this paper.The algorithm model consists of the host and the parasite populations,which simulates the parasitic behavior by regular exchange of particles to comply co-evolution and global optimization.Different evolutionary strategies are used in two sub-populations for reinforcing each other to improve the algorithm performance.In the host sub-population,to improve the iteration effect,the particles could choose to learn the velocity of the optimum particle in the parasite sub-population according to the evolutionary situation;in parasitic group,the genetic algorithm is used to improve the search ability and keep the population diversity,which leading into the crossover operator based on shortest neighbor and mutation operator based on fitness variance.We have proved that the stochastic process corresponding to HPSOPB algorithm is an absorbed state Markov process and the algorithm has global convergence.Finally, apply HPSOPB algorithm to solve TSP,and compare it with other algorithms by three experiments,which shows that the presented algorithm achieved a better optimal path and required less iterations converged to the final solution.