基于K均值的改进遗传算法求解TSP

摘要

提出一种基于K均值聚类方法的改进遗传算法,该算法通过聚类方法把大规模TSP转换为多个小型TSP,利用改进的遗传算法针对每一个类分别优化,求解得到多个闭合回路,再利用节约的思想将多段回路连接构成单一回路.其中遗传算法引入距离因子,结合TSP回路中边的长度进行交叉和变异,实验证明,基于K均值的改进遗传算法在求解结果方面提高30％以上.%The paper proposes an improved genetic algorithm(GA) for the traveling salesman problem on the basis of K- Means Clustering, which transforms a large TSP into several smaller ones using the cluster method and optimizes each class using the GA to get several circuits. Then saving method is used to connect the circuits into a single hyper circuit. Distance as a factor is introduced into the GA and the improved GA takes into consideration the length of the edges of the hyper circuit. A subsequent experiment shows that the K-means-based method can improve the final result by more than 30%.