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

摘要：

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

关键词：层次谱聚类、最近邻、禁忌搜索、遗传算法、旅行商问题

所属期刊栏目：40

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金资助项目61601412,61571404,61471325

在线出版日期：2020-05-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：44-51