Research On Genetic Algorithms For A Class Of Large-scale TSP

Genetic algorithms are random search algorithms which have been developed based on the natural selection and evolutionary mechanism. They have some advantages such as implicit parallelism, global search ablity, robustness, simple operation and so on. The search methodology of the genetic algorithms is not deterministic, instead, it is in probability, can search the space automationcally and adjust search directions adaptively. Genetic algorithms have a wide range of applications in the area of combinatorial optimization and are often used to solve problems which are difficult to solve by the traditional optimization methods. Traveling salesman problem(TSP) is a typical NP-hard problem in the field of combinatorial optimization. The solution method of traveling salesman problem with genetic algorithms not only provides a plateform for some other problems, but also has been widely used in many fields such as machine learing, signal processing, automatic control, artificial life and so on. In this paper, for a special class of large-scale TSP, a new genetic algorithm is proposed and the main works are as follows:1. First, for a special large-scale TSP problem , a method to find the best clustering number of all cities is proposed, with clustering procedure, the large- scale TSP problem is divided into several small-scale TSP, then the criterion have been given.2. Second, for the obtained small-scale TSP, a new crossover operator based on graph theory is designed, then a new genetic algorithm is proposed using this operator and the best solution of the small-scale TSP can be obtained. Furthermore, the global convergence of the algorithm is proved.3. At last, the solutions of all small-scale TSP problems are merged into the solution of the large-scale problem by a proposed linking scheme. Simulations are made and the results demonstrate the effectiveness of the proposed algorithm.