Gene Fragment Inserting Algorithms For Traveling Salesman Problem

Traveling Salesman Problem is referred to as TSP. The problem is searching for the minimum path cost of a traveler start from the origin city and passing through all the other cities, then returning to the origin city. How to find the shortest path to visit every place for one time and then back to the starting point? The rule is simple, but the solving time increase rapidly when the number of cities increased. Over the years, the mathematicians in the world trying to find an efficient algorithm that can find the optimal or near-optimal solution quickly.In recent years, researchers have tried to using various methods to solve the TSP. However, due to the characteristics of TSP, the exact and efficient algorithm to solve the TSP is impossible, which replaced by a variety of approximate methods. Researchers who trying to using single methods to solve TSP are reducing, at the same time they combine various methods gradually occupying the mainstream.To solve this problem, this article studies advantages and disadvantages of different algorithms for solving TSP. We introduce a new operator:the gene fragment inserting. Drawing on the particle swarm optimization algorithm ideas and Guo Tao’s algorithm, the three algorithms are considered for solving the traveling salesman problem.Firstly, an algorithm is considered which combining the gene fragment inserting and particle swarm optimization. By some iterations, it can get the optimal or near-optimal solution for the TSP.Secondly, we study an evolutionary algorithm which based on the gene fragment inserting for the traveling salesman problem. It random pick a gene fragment from other individual, and it is inserted to the evoluting individual. By some iterations, it can get the optimal or near-optimal solution for the TSP. Experiments show that this algorithm is better than the former one.Finally, an algorithm is proposed which merging the Guo Tao’s Inver-over operator and the gene fragment inserting. When an individual is evoluting, we use Guo Tao’s Inver-over operator to inver-over the gene fragment in this individual. Then it randomly picks a gene fragment from other individual, and insert it to the evoluting individual. Experiments show that the last algorithm can get the best result. This algorithm can find the optimal or near-optimal solution quickly for the TSP.