摘要
本文通过蒙特卡洛、最近邻、2-opt、3-opt、最远插入、Christofides等算法改进了算法性能和精确度,同时引入了俄罗斯轮盘赌等相关数据操作手段,综合了多种算法的优缺点,基于效率和准确度提出了新的改进方案.在对数十组数据进行评测后,对结果进行了可视化处理,达到了预期的收敛速度和度量标准.与传统的模拟退火及遗传算法等启发式算法相比,该算法采用了更加合理的初始解选取方法,采用了适合大多数数据的淘汰准则及计算标准,精度损失控制在2%~5%.通过各种算法的精度对比和数理逻辑推算,表明在该改进方法下误差降低了近10%.
Through Monte Carlo,nearest neighbor,2-opt,3-opt,farthest insertion,christofides and other algorithms,the performance and accuracy of the algorithm are improved.At the same time,the Russian roulette and other related data operation methods are introduced.Based on the balance of efficiency and accuracy,a new improvement scheme is proposed.Through the evaluation of dozens of groups of data,the results are visualized,and the expected convergence speed and measurement standard are achieved.Compared with the traditional heuristic algorithms such as simulated annealing and genetic algorithm,it adopts a more reasonable method to select the initial solution,adopts the elimination criteria and calculation standards suitable for most of the data,and the accuracy loss of the algorithm is controlled within 2% ~ 5%.Through the comparison of the accuracy of various algorithms and the calculation of mathematical logic,it is shown that the error is reduced by nearly 10% under the improved method.Good results can be obtained by calculating TSPLIB.
作者
包家华
刘澳霖
邓宇豪
BAO Jiahua;LIU Aolin;DENG Yuhao(College of Computer Science and Engineering,Northeastern University,Shenyang Liaoning 110169,China)
出处
《信息与电脑》
2020年第23期36-39,共4页
Information & Computer
基金
东北大学大学生创新训练计划自筹项目(项目编号:201229)
“中央高校基本科研业务专项资金资助”(项目编号:N182410001)。
关键词
TSP问题
优化策略
收敛速度
多算法改进
遗传算法
TSP problem
optimization strategy
convergence rate
multi algorithm improvement
genetic algorithm
