计算机应用研究2021，Vol.38Issue(6) ：1642-1647.DOI:10.19734/j.issn.1001-3695.2020.09.0241

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

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

戚远航 蔡延光 黄戈文 林卓胜 王福杰
计算机应用研究2021，Vol.38Issue(6) ：1642-1647.DOI:10.19734/j.issn.1001-3695.2020.09.0241
✕
  • 国家科技期刊平台
  • NETL
  • NSTL
  • 维普
  • 万方数据

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

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

戚远航 1蔡延光 2黄戈文 2林卓胜 3王福杰4
扫码查看

作者信息

  • 1. 电子科技大学中山学院 计算机学院,广东 中山 528402;电子科技大学 计算机科学与工程学院,成都611731
  • 2. 广东工业大学 自动化学院,广州510006
  • 3. 五邑大学 智能制造学部,广东 江门529020
  • 4. 东莞理工学院 电子工程与智能化学院,广东 东莞523808
  • 折叠

摘要

传统烟花算法求解大规模离散问题存在收敛速度慢、求解精度不高等问题.针对旅行商问题的特点,提出一种带固定半径近邻搜索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)

出版年

2021
计算机应用研究
四川省电子计算机应用研究中心

计算机应用研究

CSTPCDCSCD北大核心
影响因子：0.93
ISSN：1001-3695
被引量4
参考文献量16
段落导航相关论文