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

提出一种基于K均值聚类方法的改进遗传算法,该算法通过聚类方法把大规模TSP转换为多个小型TSP,利用改进的遗传算法针对每一个类分别优化,求解得到多个闭合回路,再利用节约的思想将多段回路连接构成单一回路。其中遗传算法引入距离因子,结合TSP回路中边的长度进行交叉和变异,实验证明,基于K均值的改进遗传算法在求解结果方面提高30%以上。

Improved Genetic Algorithm for TSP Based on K-Means Clustering

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 t...