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

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

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

免费全文下载 (已被下载 次)  
获取PDF全文
作者 戚远航,蔡延光,黄戈文,林卓胜,王福杰
机构 电子科技大学中山学院 计算机学院;电子科技大学 计算机科学与工程学院;广东工业大学 自动化学院;五邑大学 智能制造学部;东莞理工学院 电子工程与智能化学院
统计 摘要被查看 次,已被下载
摘要 传统烟花算法求解大规模离散问题存在收敛速度慢,求解精度不高等问题。针对旅行商问题的特点,提出一种带固定半径近邻搜索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/02-2021-06-031.html
收稿日期
修回日期
页码 -
中图分类号 TP301
文献标志码