摘要
模拟退火算法是求解无约束优化问题的有效方法,但求解旅行商问题时存在精度较差、容易陷入局部最优且收敛速度慢等缺点。为了改进上述问题,提出了一种基于Spark平台的并行模拟退火算法。修改模拟退火算法的降温函数,构造旅行商问题的解空间,采用大邻域搜索技术和2-opt算子增强局部搜索能力,引入OX交叉思想增强全局搜索能力,提出交叉协同试验并行策略与Spark平台并行实现。选取若干TSPLIB数据集进行仿真实验,对求解质量和运行时间两个方面进行测试,与其他Spark框架的并行算法进行对比实验。仿真结果表明,该算法求解精度有较大的提高,求解速度上对比其他算法提升3~10倍,能够有效求解旅行商问题。
Simulated annealing algorithm is an effective method for solving unconstrained optimization problems,but it has the disadvantages of poor accuracy,easy to fall into local optimum and slow convergence when solving travel quotient problems.In order to improve the above problems,aparallel simulated annealing algorithm based on Spark platform is proposed.The cooling function of the simulated annealing algorithm is modified to construct the solution space of the travel quotient problem,the local search capability is enhanced by using the large neighborhood search technique and the 2-opt operator,the global search capability is enhanced by introducing the OX crossover idea,and the crossover cooperative experiment parallel strategy is proposed to be implemented in parallel with the Spark platform.A number of TSPLIB datasets are selected for simulation experiments to test both solution quality and running time,and to compare the experiments with other parallel algorithms of Spark framework.The simulation results show that the solution accuracy of this method is greatly improved,and the solution speed is 3~10times higher than other algorithms,which can effectively solve the traveling salesman problem.
作者
孙鉴
刘凇佐
武晓晓
巫思敏
Sun Jian;Liu Songzuo;Wu Xiaoxiao;Wu Simin(College of Computer Science and Engineering,North Minzu University,Yinchuan 750021,China)
出处
《电子测量技术》
北大核心
2022年第4期53-58,共6页
Electronic Measurement Technology
基金
国家自然科学基金(62062002)
北方民族大学中央高校基本科研业务费专项(FWNX09)
北方民族大学校级一般项目(2021XYZJK01)资助。
关键词
并行模拟退火算法
大规模邻域算法
降温策略
旅行商问题
SPARK
parallel simulated annealing algorithm
large neighborhood search algorithm
cooling strategy
traveling salesman problem
Spark
