Research On Solving Traveling Salesman Problem Based On Modified Genetic Algorithms

Traveling salesman problem (TSP) is to find the shortest closed cycle that visits every vertex exactly once, namely is to find a Hamiltonian cycle whose total cost is minimized. TSP is a combinational optimization problem which has wide application background and important theory value, and it belongs to classical NP problem. Therefore, it is very important to find the effective method to solve the TSP.With the research and analysis on genetic algorithms and methods for solving the TSP, a modified genetic algorithm is proposed to solve the TSP, also verify the performance of the modified genetic algorithms by some benchmark problem.Firstly, the scale of the problem is a very important factor for solving the TSP, time complexity of Algorithms grows exponentially with the scale. So the divide-conquer is an available method for solving the TSP. In order to lower the scale of the problem and shorten the running time of algorithm, we propose a problem-dividing method based on minimum spanning tree to solve the TSP.Secondly, crossover is the key operator in the genetic algorithms, and it is impetus for evolution. Based on the research of EAX algorithms, we analysis and compare the results, and find out the cycle combination algorithm is a bottleneck of EAX algorithms. In order to shorten the running time, we discuss a multi-stage cycle combination algorithm to solve the bottleneck. Meanwhile, we employ a modified e-set selection strategy in EAX, and use mixed local search algorithm to improve the result of EAX.Finally, we use some benchmark problem in TSPLIB to verify the performance of the modified genetic algorithms. From the results, we can conclude that the modified Genetic Algorithms can solve the TSP, and improve the efficiency of algorithms on solving the TSP.