Improved Memetic Algorithm and Its Application on Traveling Salesman Problem

Abstract

The traveling salesman problem is a classic NP-hard combinatorial optimization problem which is important in operations research and theoretical computer science. It is not feasible to use the conventional particle swarm optimization and simulated annealing algorithm to find the optimal solution in such a large search space. In order to improve the efficiency of the memetic algorithm, an improved particle swarm optimization as the global search and an improved simulated annealing algorithm as the local search have been proposed in this paper. Finally, the simulation experiment results have shown that the improved memetic algorithm has fast convergence speed in solving TSP problem and could find the optimal solution efficiently.