An improved genetic algorithm with decision function for solving travelling salesman problem
Dongming Guo, Hongmei Chen, Bin Wang · 2017
Travelling Salesman Problem (TSP) is one of famous discrete optimization problems and has been proven to be NP-complete in mathematics. An improved genetic algorithm with quick decision functions for solving TSP is proposed in this paper. By using decision functions to control mutational direction, the chromosomes become better step by step through two mutation operations which can substantially lessen the running time of algorithm. The improved algorithm with a longest distance strategy and a random strategy can prevent it from falling into local optimization. The experiment results show the 13 of random chosen 38 test instances are better than the given optimum solutions in TSPLIB and all relative errors of test instances are less than 0.7% which show the validity and efficiency of the proposed algorithm.