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

Solving MTSP with Two-stage SA and GA Based on Spark

作　　者：孙鉴 刘品 李昊 陈攀 SUN Jian;LIU Pin;LI Hao;CHEN Pan(School of Computer Science and Engineering,North Minzu University,Yinchuan 750021,China;The Key Laboratory of Images and Graphics Intelligent Processing of State Ethnic Affairs Commission,North Minzu University,Yinchuan 750021,China)

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

出　　处：《郑州大学学报（工学版）》2024年第4期62-69,94,共9页Journal of Zhengzhou University（Engineering Science）

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

摘　　要：针对总路径长度最小的单站点多旅行商问题,提出了基于Spark的模拟退火和遗传算法结合的两阶段KSAGA算法。在第一阶段,通过k-means聚类将多旅行商问题拆分为多个单旅行商问题,并使用模拟退火算法对组内城市的遍历次序进行优化。在第二阶段,通过遗传算法对城市的分组进行优化,并基于染色体分组编码方式设计了交叉、变异算子以及混合局部优化算子,以提高算法的搜索空间和收敛速度。随着城市数量的增加,计算规模变大,利用遗传算法的特性实现算法的并行,以加快算法运行效率。最后,通过选取TSPLIB的部分数据集进行仿真实验,将KSAGA与ACO、GA、SPKSA、ALNS和NSGA-Ⅱ的求解质量以及GA和NSGA-Ⅱ的收敛速度进行对比。研究结果表明:KSAGA在解决单站点多旅行商问题时能够快速收敛,并且相较于其他算法,求解质量得到了很大提升。同时,随着城市数量和旅行商数量增加,KSAGA的优势更为明显。A two-stage KSAGA algorithm combining Spark-based simulated annealing and genetic algorithms was proposed for the single-depot multiple traveling salesman problem with minimum total path length.In the first stage,the multiple traveling salesman problem was split into multiple single traveling salesman problems by kmeans clustering,and the traversal order of cities in the group was optimized using the simulated annealing algorithm.In the second stage,the classification of cities was optimized by genetic algorithm,and the cross-variance operator as well as the hybrid local optimization operator were designed based on the chromosome grouping encoding method to improve the search space and convergence speed of the algorithm.As the number of cities increased and the computational scale became larger,the characteristics of genetic algorithm were used to realize the parallelism of the algorithm in order to speed up the algorithm operation efficiency.Finally,the solution quality of KSAGA was compared with that of ACO,GA,SPKSA,ALNS and NSGA-Ⅱand the convergence speed of GA and NSGA-Ⅱby selecting some datasets of TSPLIB for simulation experiments.The results showed that KSAGA could converge quickly in solving the single-depot multiple traveling salesman problem,and the solution quality was greatly improved compared with other algorithms.Meanwhile,the advantage of KSAGA was more obvious as the number of cities and the number of travelers increased.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]