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

• 作 者: 崔文 吴耀华
• 机 构: 山东大学现代物流研究中心
• 出 处: 物流技术
• 发表日期: 2011年9期
• 关键词: K均值 聚类方法 TSP 遗传算法 K-Means clustering TSP genetic algorithm

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