查看文章

Based on k-means clustering, we designed and implemented an improved genetic algorithm(IGA) to find the best solution for the traveling salesman problem. IGA includes three characteristics of classical genetic algorithm(CGA). The first characteristic is the use of k-means clustering method on all cities to reduce the complexity of the problem by dividing the cities into several groups. The second characteristic is the adoption of genetic algorithm in each group for optimizing the sub-path. The third characteristic is the use of evolution operation on the inter-group for integral optimization. We performed many experiments to test the ability of IGA. Our experimental results show that IGA is more effective than CGA, especially for large-scale traveling salesman problems.