查看文章

Genetic Algorithm (GA) is an effective method for solving Traveling Salesman Problems (TSPs), nevertheless, the Classical Genetic Algorithm (CGA) performs poor effect for large-scale traveling salesman problems. For conquering the problem, this paper presents two improved genetic algorithms based on clustering to find the best results of TSPs. The main process is clustering, intra-group evolution operation and inter-group connection. Clustering includes two methods to divide the large scale TSP into several sub-problems. One is k-means, and the other is affinity propagation (AP). Each sub-problem corresponds to a group. Then we use GA to find the shortest path length for each sub-problem. At last, we design an effective connection method to combine all those groups into one which is the result of the problem. we trial run a set of experiments on benchmark instances for testing the performance of the …