改进的分布式并行遗传算法求解大规模TSP问题

摘要：

TSP问题的应用十分广泛,而传统的遗传算法在求解TSP问题时存在求解精度低和时间长等不足.针对该问题提出了一种改进的分布式并行遗传算法用来求解大规模TSP问题.改进遗传算法使父代染色体进行顺序交叉、就近变异和局部最优选择,将大规模TSP问题用k-均值聚类算法进行分组,使用分布式并行算法将子问题分配到不同的计算节点上用改进的遗传算法求解.求解得到的子问题用Delaunay三角剖分算法进行合并,从而得到整个问题的解.通过TSPlib数据库进行实验,结果显示提出的算法在求解时间和求解精度上均有所提高.

关键词：TSP问题、分布式并行遗传算法、贪心策略、k-均值聚类、Delaunay三角剖分

所属期刊栏目：45

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金51378076

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

页数：共9页

页码：135-143