基于Spark的双阶段SA及GA求解MTSP

作     者：孙鉴 刘品 李昊 陈攀 SUN Jian;LIU Pin;LI Hao;CHEN Pan

作者机构：北方民族大学计算机科学与工程学院宁夏银川750021 北方民族大学图像图形智能处理国家民委重点实验室宁夏银川750021 

基　　金：国家自然科学基金资助项目(62062002) 宁夏自然科学基金资助项目(2022AAC03289,2022AAC03245,2022AAC03261) 

出 版 物：《郑州大学学报（工学版）》 (Journal of Zhengzhou University（Engineering Science）)

年 卷 期：2024年第45卷第4期

页      码：62-69,94页

摘      要：针对总路径长度最小的单站点多旅行商问题,提出了基于Spark的模拟退火和遗传算法结合的两阶段KSAGA算法。在第一阶段,通过k-means聚类将多旅行商问题拆分为多个单旅行商问题,并使用模拟退火算法对组内城市的遍历次序进行优化。在第二阶段,通过遗传算法对城市的分组进行优化,并基于染色体分组编码方式设计了交叉、变异算子以及混合局部优化算子,以提高算法的搜索空间和收敛速度。随着城市数量的增加,计算规模变大,利用遗传算法的特性实现算法的并行,以加快算法运行效率。最后,通过选取TSPLIB的部分数据集进行仿真实验,将KSAGA与ACO、GA、SPKSA、ALNS和NSGA-Ⅱ的求解质量以及GA和NSGA-Ⅱ的收敛速度进行对比。研究结果表明:KSAGA在解决单站点多旅行商问题时能够快速收敛,并且相较于其他算法,求解质量得到了很大提升。同时,随着城市数量和旅行商数量增加,KSAGA的优势更为明显。

主 题 词：多旅行商问题 并行 遗传算法 分组编码 局部优化算子 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.13705/j.issn.1671-6833.2024.01.019

馆 藏 号：203128197...