基于自适应层次谱聚类与遗传优化的TSP算法

• 作者: 杨彩虹 杨明
• 来源期刊: 云南师范大学学报（自然科学版）
• 学科: 工学
• 关键词: 层次谱聚类 最近邻 禁忌搜索 遗传算法 旅行商问题
• 年，卷（期）: 2020,（1）
• 所属期刊栏目: 计算机科学与应用
• 页码范围: 44-51
• 页数: 8页
• 分类号: TP18
• 字数: 4933字
• 语种: 中文
• DOI: 10.7699/j.ynnu.ns-2020-010

摘要

提出一种基于自适应层次谱聚类与遗传优化的算法求解大规模TSP,算法首先构建一种自适应相似矩阵,并应用到谱聚类算法中实现城市的初步聚类,当聚类城市规模超过设定阈值,用上述自适应谱聚类算法进行层次聚类,直到每类城市规模均小于阈值;其次,采用结合了最近邻与禁忌思想的改进遗传算法求解GTSP,得类间最短回路;最后,用改进遗传算法求解每类城市群的最优解,综合类间GTSP最短回路以及类内TSP最优解,即得大规模旅行商问题的最优解.实验结果表明,该算法能够取得相对较优解且求解效率显著提高.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨明	中北大学理学院	38	158	8.0	10.0
3	杨彩虹	中北大学理学院	2	5	1.0	2.0