Two Kinds Of Intelligent Algorithms For Traveling Salesman Problem

Traveling Salesman Problem (TSP) is a typical combinatorial optimization problem, but also a classic NP problem. It has a wide range of applications in engineering. There are many methods for solving TSP, such as classic algorithms, approximation algorithms and intelligent algorithms. In particular, the intelligent algorithm is considered to be one of the most effective algorithms for solving TSP. In this paper, two kinds of intelligent algorithms are designed under the framework of genetic algorithm, as follows:By making use of the better quality of genes derived from the nearest-neighbor algorithm and the non-cross property of the optimal path, the nearest-neighbor algorithm and crossover operation are added into the genetic algorithm. Then, a nearest-neighbor cross-annealing genetic algorithm is proposed.We present a bilevel parallel immune genetic algorithm, in which we designed the corresponding evolution operation for each layer of the bilevel model. Furthermore, the immune operation is added into the algorithm so that good genes can help making a better evolution for chromosomes and finding the desired solution as soon as possible. Numerical experiments show that these two methods perform well.In the end of this paper, we indicate the future research directions of the genetic algorithm for solving TSP.