A MODIFIED HYBRID PARTICLE SWARM OPTIMIZATION ALGORITHM FOR SOLVING THE TRAVELING SALESMEN PROBLEM

摘要

The traveling salesman problem (TSP) is a well-known NP-hard combinatorial optimization problem. The problem is easy to state, but hard to solve. Many r eal-world problems can be formulated as instances o f the TSP, for example, computer wiring, vehicle routing, crystallography, robot control, drilling of printe d circuit boards and chronological sequencing. In thi s paper, we present a modified hybrid Particle Swar m Optimization (MHPSO) algorithm in which we combine some principles of Particle Swarm Optimization (PSO), the Crossover operation of the Genetic Algor ithm and 2-opt improvement heuristic. The main feature of our approach is that it allows avoiding a major problem of metaheuristics: the parameters s etting. In the aim to prove the performance and convergence of the proposed algorithm, we have used it to solv e some TSP instances taken from TSPLIB library. Moreover, we have compared our results with those obtained by other algorithms based PSO.