《计算机应用研究》|Application Research of Computers

带固定半径近邻搜索3-opt的离散烟花算法求解旅行商问题

Discrete fireworks algorithm with fixed radius nearest-neighbor search 3-opt for travelling salesman problem

免费全文下载 (已被下载 次)  
获取PDF全文
作者 戚远航,蔡延光,黄戈文,林卓胜,王福杰
机构 1.电子科技大学中山学院 计算机学院,广东 中山 528402;2.电子科技大学 计算机科学与工程学院,成都 611731;3.广东工业大学 自动化学院,广州 510006;4.五邑大学 智能制造学部,广东 江门 529020;5.东莞理工学院 电子工程与智能化学院,广东 东莞 523808
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2021)06-007-1642-06
DOI 10.19734/j.issn.1001-3695.2020.09.0241
摘要 传统烟花算法求解大规模离散问题存在收敛速度慢、求解精度不高等问题。针对旅行商问题的特点,提出一种带固定半径近邻搜索3-opt的离散烟花算法。该算法基于基本烟花算法进行离散化改进,采用整数编码的路径表示方法来表示旅行商问题的解,对爆炸算子、高斯变异算子进行离散化操作策略设计。为了使算法具有较好的局部搜索能力,提出固定半径近邻搜索3-opt策略来提高算法精度和收敛速度,同时采用不检测标志策略提高算法效率。实验结果表明:该算法能有效地求解旅行商问题,其离散烟花算子在全局收敛能力、收敛精度、求解时间和稳定性等方面均优于传统烟花算子;基准测试算例的最优解平均误差率仅为0.002%,优于对比算法。
关键词 离散烟花算法; 旅行商问题; 固定半径近邻搜索; 3-opt
基金项目 国家自然科学基金资助项目(61074147,61901304)
广东省自然科学基金资助项目(S2011010005059,2019A1515010493,2016A030313018)
广东省教育部产学研结合项目(2012B091000171,2011B090400460)
广东省科技计划资助项目(2012B050600028,2014B010118004,2016A050502060)
广州市花都区科技计划资助项目(HD14ZD001)
广州市科技计划资助项目(201604016055)
广州市天河区科技计划资助项目(2018CX005)
广东省普通高校青年创新人才项目(2018KQNCX333,2018KQNCX252)
广东省普通高校重点领域专项资助项目(2019KZDZX1052,2020ZDZX3030)
本文URL http://www.arocmag.com/article/01-2021-06-007.html
英文标题 Discrete fireworks algorithm with fixed radius nearest-neighbor search 3-opt for travelling salesman problem
作者英文名 Qi Yuanhang, Cai Yanguang, Huang Gewen, Lin Zhuosheng, Wang Fujie
机构英文名 1.School of Computer Science,University of Electronic Science & Technology of China,Zhongshan Institute,Zhongshan Guangdong 528402,China;2.School of Computer Science & Engineering,University of Electronic Science & Technology of China,Chengdu 611731,China;3.School of Automation,Guangdong University of Technology,Guangzhou 510006,China;4.Faculty of Intelligent Manufacturing,Wuyi University,Jiangmen Guangdong 529020,China;5.School of Electrical Engineering & Intelligentization,Dongguan University of Technology,Dongguan Guangdong 523808,China
英文摘要 The traditional fireworks algorithm has slow convergence speed and low precision when solving large-scale discrete problems. Aiming at the characteristics of travelling salesman problem, this paper proposed a discrete fireworks algorithm with fixed radius nearest-neighbor search 3-opt. It discretized and improved the proposed algorithm based on the basic fireworks algorithm, where adopted the integer coding path representation method to represent the solution of the travelling salesman problem, as well as designed the explosion operator and the Gauss mutation operator of the algorithm for discretization solution. To enhance local search ability of the algorithm, the algorithm proposed implements 3-opt local search to strengthen search ability of the algorithm, and introduced the fixed radius of neighbor search and don't-look-bits strategy to improve the efficiency of the algorithm. The experiments indicate that the proposed algorithm solves travelling salesman problem effectively. The discrete fireworks operator proposed is superior to the traditional fireworks operator in global convergence ability, convergence accuracy, solution time and stability. The average costs of the solutions of the algorithms for all benchmark instances probed have an overall deviation in only 0.002% from those of the best known solutions, which is lower than those of all comparing algorithms.
英文关键词 discrete fireworks algorithm; traveling salesman problem(TSP); fixed radius nearest-neighbor search; 3-opt
参考文献 查看稿件参考文献
 
收稿日期 2020/9/18
修回日期 2020/11/5
页码 1642-1647
中图分类号 TP301
文献标志码 A