计算机应用研究

作者：戚远航,蔡延光,黄戈文,林卓胜,王福杰,

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

关键词：离散烟花算法,旅行商问题,固定半径近邻搜索,3-opt,

基金：国家自然科学基金资助项目(61074147,61901304)；广东省自然科学基金资助项目(S2011010005059,2019A1515010493,2016A030313018)；广东省教育部产学研结合项目(2012B091000171,2011B090400460)；广东省科技计划资助项目(2012B050600028,2014B010118004,2016A050502060)；广州市花都区科技计划资助项目(HD14ZD001)；广州市科技计划资助项目(201604016055)；广州

传统烟花算法求解大规模离散问题存在收敛速度慢、求解精度不高等问题。针对旅行商问题的特点，提出一种带固定半径近邻搜索3-opt的离散烟花算法。该算法基于基本烟花算法进行离散化改进，采用整数编码的路径表示方法来表示旅行商问题的解，对爆炸算子、高斯变异算子进行离散化操作策略设计。为了使算法具有较好的局部搜索能力，提出固定半径近邻搜索3-opt策略来提高算法精度和收敛速度，同时采用不检测标志策略提高算法效率。实验结果表明：该算法能有效地求解旅行商问题，其离散烟花算子在全局收敛能力、收敛精度、求解时间和稳定性等方面均优于传统烟花算子；基准测试算例的最优解平均误差率仅为0.002%，优于对比算法。

来源：2021年第6期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2021年第6期