Solving Traveling Salesman Problem by a hybrid combination of PSO and Extremal Optimization

Particle Swarm Optimization (PSO) has received great attention in recent years as a successful global search algorithm, due to its simple implementation and inexpensive computation overhead. However, PSO still suffers from the problem of early convergence to locally optimal solutions. Extremal Optimization (EO) is a local search algorithm that has been able to solve NP hard optimization problems. The combination of PSO with EO benefits from the exploration ability of PSO and the exploitation ability of EO, and reduces the probability of early trapping in the local optima. In other words, due to the EO´s strong local search capability, the PSO focuses on its global search by a new mutation operator that prevents loss of variety among the particles. This is done when the particle´s parameters exceed the problem conditions. The resulting hybrid algorithm Mutated PSO-EO (MPSO-EO) is then applied to the Traveling Salesman Problem (TSP) as a NP hard multimodal optimization problem. The performance of the proposed approach is compared with several other metaheuristic methods on 3 well known TSP databases and 10 unimodal and multimodal benchmark functions.