基于Spark的并行模拟退火算法求解TSP

来源：电子测量技术杂志2022年第4期北京时间：

作者：孙鉴，刘凇佐，武晓晓，巫思敏

单位：北方民族大学计算机科学与工程学院 宁夏 银川 750021

摘要：模拟退火算法是求解无约束优化问题的有效方法，但求解旅行商问题时存在精度较差、容易陷入局部最优且收敛速度慢等缺点。为了改进上述问题，本文提出了一种基于Spark平台的并行模拟退火算法。修改模拟退火算法的降温函数，构造旅行商问题的解空间，采用大邻域搜索技术和2-opt算子增强局部搜索能力，引入OX交叉思想增强全局搜索能力，提出交叉协同试验并行策略与Spark平台并行实现。选取若干TSPLIB数据集进行仿真实验，对求解质量和运行时间两个方面进行测试，与其它Spark框架的并行算法进行对比实验。仿真结果表明，该算法求解精度有较大的提高，求解速度上对比其他算法提升3-10倍，能够有效求解旅行商问题。

关键词：并行模拟退火算法;大规模邻域算法;降温策略;旅行商问题;Spark

基金资助：国家自然科学基金项目（62062002）；北方民族大学中央高校基本科研业务费专项资金 （FWNX09）；北方民族大学校级一般项目（2021XYZJK01）