An Improvement of the Compact Genetic Algorithm for Solving Clustering Traveling Salesman Problem

Compared with classical genetic algorithm for solving traveling salesman problem (TSP),compact genetic algorithm (CGA) exploited without significantly increasing memory requirements,but the computational cost of generation of feasible Tours increased.Facing the characteristic of city nodes distributing as cluster in clustering TSP,the roulette wheel is applied in generating individuals chromosomes of CGA to overcome the drawbacks of expensive computation.Based on the cluster analysis of city nodes in clustering TSP,the initialization operator and update protocol of the probability matrix corresponding to the characteristic of clustering TSP is proposed to improve the speed of convergence efficiently and capacity of global optimization.The results of experiments conducted on TSP instances in open datasets TSPLib shows the efficacy of the improved compact genetic algorithm.