混沌烟花算法求解旅行商问题

计算机科学 ›› 2019, Vol. 46 ›› Issue (6A): 85-88.

混沌烟花算法求解旅行商问题

蔡延光¹, 陈厚仁¹, 戚远航²

广东工业大学自动化学院广州510006¹;
电子科技大学中山学院广东中山528402²

出版日期:2019-06-14 发布日期:2019-07-02
通讯作者: 蔡延光(1963-),男,博士,教授,博士生导师,主要研究方向为网络控制与优化、组合优化、智能优化、智能交通系统等,E-mail:caiyg99@163.com
作者简介:陈厚仁(1994-),男,硕士生,主要研究方向为物联网智能信息处理技术;戚远航(1993-),男,博士,主要研究方向为复杂系统控制与优化、智能优化、物流运输优化调度。
基金资助:
本文受国家自然科学基金(61074147),广东省自然科学基金(S2011010005059),广东省教育部产学研结合项目(2012B091000171,2011B090400460),广东省科技计划项目(2012B050600028,2014B010118004,2016A050502060),广州市花都区科技计划项目(HD14ZD001),广州市科技计划项目(201604016055),广州市天河区科技计划项目(2018CX005),广东省普通高校青年创新人才项目(2018KQNCX333)资助。

Chaotic Fireworks Algorithm for Solving Travelling Salesman Problem

CAI Yan-guang¹, CHEN Hou-ren¹, QI Yuan-hang²

School of Automation,Guangdong University of Technology,Guangzhou 510006,China¹;
Zhongshan Institute,University of Electronic Science and Technology of China,Zhongshan,Guangdong 528402,China²

Online:2019-06-14 Published:2019-07-02

摘要/Abstract

摘要： 旅行商问题(Travelling Salesman Problem,TSP)是一种经典的组合优化问题,属于典型的NP难问题,具有重要的研究价值。文中提出了一种混沌烟花算法来求解TSP。所提算法使用最大位置法定义离散域中的烟花算法,并加入混沌优化策略来增强算法的搜索能力。设计了4个参数实验来分析主要参数对CFWA的影响并确定了较优的参数设置。对比实验表明:相比于对比算法,混沌烟花算法求解旅行商问题时具有较好的收敛性和稳定性。

关键词: 参数分析, 混沌搜索, 旅行商问题, 烟花算法, 最大位置法

Abstract: Travelling salesman problem (TSP) is a classic combinatorial optimization problem,which is a typical NP hard problem and has important research value.This paper presented a chaotic fireworks algorithm to solve the TSP problem.The algorithm uses LOV to define the discrete domain and adds chaos optimization strategy to enhance search capability of the algorithm.In this paper,four parametric experiments were designed to analyze the influence of the main parameters on CFWA and determine the optimal parameter setting.The comparison experiment shows that the chaotic fireworks algorithm has better convergence and stability than the comparison algorithm.

Key words: Chaotic searching, Fireworks algorithm, Largest order value, Parameter analysis, Travelling salesman problem

中图分类号:

TP301

蔡延光, 陈厚仁, 戚远航. 混沌烟花算法求解旅行商问题[J]. 计算机科学, 2019, 46(6A): 85-88. https://doi.org/

CAI Yan-guang, CHEN Hou-ren, QI Yuan-hang. Chaotic Fireworks Algorithm for Solving Travelling Salesman Problem[J]. Computer Science, 2019, 46(6A): 85-88. https://doi.org/

参考文献

[1]孙惠文.遗传算法求解旅行商问题[J].西南交通大学学报,1996,31(5):550-554.
[2]高海昌,冯博琴,朱利.智能优化算法求解TSP问题[J].控制与决策,2006,21(3):241-247.
[3]周永权,黄正新,刘洪霞.求解TSP问题的离散型萤火虫群优化算法[J].电子学报,2012,40(6):1164-1170.
[4]张涛,王梦光.遗传算法和3-opt结合求解带有能力约束的VRP[J].东北大学学报(自然科学版),1999,20(3):254-256.
[5]LIN S,KERNIGHAN B W.An Effective Heuristic Algorithm for the Traveling-Salesman Problem[M].INFORMS,1973.
[6]孟繁桢,胡云昌,徐慧,等.旅行商问题的遗传算法[J].系统工程理论与实践,1997,17(9):15-21.
[7]程毕芸,鲁海燕,徐向平,等.求解旅行商问题的改进局部搜索混沌离散粒子群优化算法[J].计算机应用,2016,36(1):138-142.
[8]李擎,张超,陈鹏,等.一种基于粒子群参数优化的改进蚁群算法[J].控制与决策,2013(6):873-878.
[9]戚远航,蔡延光,蔡颢,等.旅行商问题的混沌混合离散蝙蝠算法[J].电子学报,2016,44(10):2543-2547.
[10]吴华锋,陈信强,毛奇凰,等.基于自然选择策略的蚁群算法求解TSP问题[J].通信学报,2013(4):165-170.
[11]冯春松,王军宇,周松盛,等.TSP问题的一种改进遗传算法[J].武汉理工大学学报,2006,28(4):116-118.
[12]高尚,韩斌,吴小俊,等.求解旅行商问题的混合粒子群优化算法[J].控制与决策,2004,19(11):1286-1289.
[13]谭营,郑少秋.烟花算法研究进展[J].智能系统学报,2014(5):515-528.
[14]朱启兵,王震宇,黄敏.带有引力搜索算子的烟花算法[J].控制与决策,2016,31(10):1853-1859.
[15]韩守飞,李席广,拱长青.基于模拟退火与高斯扰动的烟花优化算法[J].计算机科学,2017,44(5):257-262.
[16]张以文,吴金涛,赵姝,等.基于改进烟花算法的Web服务组合优化[J].计算机集成制造系统,2016,22(2):422-432.
[17]QIAN B,WANG L,HUANG D X,et al.An effective hybrid DE-based algorithm for flow shop scheduling with limited buf-fers[J].Computers & Operations Research,2008,35(9):2791-2806.
[18]ZHENG S,JANECEK A,LI J,et al.Dynamic search in fireworks algorithm[C]∥Evolutionary Computation.IEEE,2014:3222-3229.
[19]曹磊,叶春明,黄霞.应用混沌烟花算法求解置换流水车间问题[J].计算机应用与软件,2016,33(11):188-192.
[20]包晓晓,叶春明,黄霞.烟花算法求解JSP问题的研究[J].计算机工程与应用,2017,53(3):247-252.
[21]高尚.解旅行商问题的混沌蚁群算法[J].系统工程理论与实践,2005,25(9):100-104.
[22]江新姿,高尚,陈建忠.求解旅行商问题的模拟退火蚁群算法[J].计算机工程与设计,2008,29(6):1491-1493.
[23]WANG K P,HUANG L,ZHOU C G,et al.Particle swarm optimization for traveling salesman problem[C]∥International Conference on Machine Learning and Cybernetics.IEEE,2003:1583-1585.
[24]朱小平,赵曦.一种改进的离散粒子群优化算法在TSP问题中的应用[J].江西师范大学学报(自然版),2010,34(4):369-373.

相关文章 15

[1]	王永, 崔源. 基于四边形最优圈内最短路径的旅行商问题割边方法 Cutting Edge Method for Traveling Salesman Problem Based on the Shortest Paths in Optimal Cycles of Quadrilaterals 计算机科学, 2022, 49(6A): 199-205. https://doi.org/10.11896/jsjkx.210400065
[2]	杨德成, 李凤岐, 王祎, 王胜法, 殷慧殊. 智能3D打印路径规划算法 Intelligent 3D Printing Path Planning Algorithm 计算机科学, 2020, 47(8): 267-271. https://doi.org/10.11896/jsjkx.190700184
[3]	胡士娟, 鲁海燕, 向蕾, 沈莞蔷. 求解MMTSP的模糊聚类单亲遗传算法 Fuzzy C-means Clustering Based Partheno-genetic Algorithm for Solving MMTSP 计算机科学, 2020, 47(6): 219-224. https://doi.org/10.11896/jsjkx.190500137
[4]	廖义辉, 杨恩君, 刘安东, 俞立. 基于改进变邻域搜索的数控裁床路径优化 Path Optimization in CNC Cutting Machine Based on Modified Variable Neighborhood Search 计算机科学, 2020, 47(10): 233-239. https://doi.org/10.11896/jsjkx.190800035
[5]	陈建荣,陈建华. 求解TSP问题的离散捕鱼策略优化算法 Discrete Fishing Strategy Optimization Algorithm for TSP 计算机科学, 2017, 44(Z6): 139-140. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.032
[6]	韩守飞,李席广,拱长青. 基于模拟退火与高斯扰动的烟花优化算法 Fireworks Optimization Algorithm Based on Simulated Annealing and Gaussian Perturbations 计算机科学, 2017, 44(5): 257-262. https://doi.org/10.11896/j.issn.1002-137X.2017.05.046
[7]	高峰,郑波. 基于IPSO算法的TSP问题求解研究 Study on TSP Solving Based on IPSO 计算机科学, 2014, 41(Z11): 69-71.
[8]	王诏远,李天瑞,易修文. 基于MapReduce的蚁群优化算法实现方法 Approach for Development of Ant Colony Optimization Based on MapReduce 计算机科学, 2014, 41(7): 261-265. https://doi.org/10.11896/j.issn.1002-137X.2014.07.054
[9]	张新明,魏峰,牛丽平,王鲜芳. 混合排名映射概率和混沌搜索的ABC算法 Artificial Bee Colony Algorithm Based on Hybrid Rank Mapping Probability and Chaotic Search 计算机科学, 2014, 41(2): 102-106.
[10]	柯良军，尚可，冯祖仁. 不确定旅行商问题的鲁棒模型及其算法研究 Robust Model and Algorithms for the Uncertain Traveling Salesman Problem 计算机科学, 2012, 39(Z6): 238-241.
[11]	郝承伟,高慧敏. 求解TSP问题的一种改进的+进制MIMIC算法 Modified Decimal MIMIC Algorithm for TSP 计算机科学, 2012, 39(8): 233-236.
[12]	黄凯，周永权. 带交尾行为的混沌人工萤火虫优化算法 Chaotic Artificial Glowworm Swarm Optimization Algorithm with Mating Behavior 计算机科学, 2012, 39(3): 231-235.
[13]	王彦伟，黄正东，马露杰. 基于FFT的三维CAD模型形状描述 Shape Description of 3D CAD Models Using FFT 计算机科学, 2010, 37(7): 251-254259.
[14]	吴建辉,章兢,张小刚,刘朝华. 一种求解TSP问题的分层免疫算法 Novel Hierarchical Immune Algorithm for TSP Solution 计算机科学, 2010, 37(6): 256-260.
[15]	许昌,常会友,徐俊,衣杨. 一种新的融合分布估计的蚁群优化算法 Novel Ant Colony Optimization Algorithm with Estimation of Distribution 计算机科学, 2010, 37(2): 186-188.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed