Genetic algorithms based on clustering for traveling salesman problems

摘要

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 proposed genetic algorithm based on k-means clustering (KGA) and genetic algorithm based on affinity propagation clustering (APGA). Experimental results demonstrate their effective and efficient performances. Comparing results with other clustering genetic algorithms show that KGA and APGA are competitive and efficient.