An Empirical Study on Evolutionary Algorithms for Traveling Salesman Problem
Feng-Feng Wei, Wei–Neng Chen, Xiao-Min Hu, Jun Zhang · 2019
Evolutionary computation (EC) has been one of the most important methods to solve NP-hard optimization problems. When using EC algorithms to solve combinatorial optimization problems (COPs), the common dilemmas are how to make the candidate solutions satisfy the problems' constraints, which values of parameters are more proper for different problems and so on. In order to discover some general rules on solving COPs using EC algorithms, this paper takes the traveling salesman problem (TSP) as an example and performs a comprehensive empirical study on three popular EC algorithms. Genetic algorithm, ant colony optimization and particle swarm optimization are adopted in this study. Further, the configuration parameters of algorithms are fine-tuned and the effect of operators and parameters are also analyzed on TSP instances with different scales. We also discuss the effect of different initialization strategies and apply candidate set and local search strategies to these three algorithms to further accelerate the search speed when solving large-scale problems. Based on the analysis, we hope to give some guidance for designing efficient evolutionary algorithms to solve COPs.