Discrete Parallel QUasi-Affine TRansformation Evolution Algorithm for Traveling Salesman Problem

Abstract

The traveling salesman problem (TSP) is a classic combinatorial optimization problem belonging to the NP-hard problem. This paper extends the QUATRE algorithm to this field. The quasi-affine transformation evolution (QUATRE) algorithm provides six evolution schemes and simplifies the setting of control parameters. Because the QUATRE algorithm is easy to fall into local optimal and the convergence performance of the QUATRE algorithm is insufficient for the application, many excellent heuristic algorithms are continuously proposed. This article modified the QUATRE algorithm using reverse learning and mutation strategy. In order to expand the application of the QUATRE algorithm to the TSP problem, a discretization method is adopted to improve the QUATRE. It proposes the discrete parallel quasi-affine transformation evolution (DPQUATRE) algorithm. DPQUATRE beats the comparison algorithm on all 14 test sets of the Traveling Salesman problem library (TSPLIB). TSPLIB is utilized to assess the property of the DPQUATRE algorithm to show the effectiveness of the method. In addition, the error rate metrics PDBest and PDAverage are also used to evaluate the performance of the algorithms. The error rate provides a more visual demonstration of the gap between the distance calculated by the algorithm and the shortest distance.