基于改进萤火虫算法求解旅行商问题
作者:
基金项目:

国家自然基金项目(61772416)


Solving Traveling Salesman Problem Based on Improved Firefly Algorithm
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [18]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    鉴于TSP问题是古老的组合优化难题,而萤火虫算法在求解函数优化问题中表现出优良的性能,因此,本文利用改进的萤火虫算法求解TSP问题.首先,在分析了旅行商问题的特点后,采用整数编码的方式来表示萤火虫的位置.然后,在标准萤火虫算法的位置更新过程中引入了对数递减的惯性权重来影响萤火虫的迭代过程,同时结合了遗传算法中的选择,交叉,变异以及进化逆转操作来提高每一次迭代中种群的多样性及种群的搜索能力,并将改进的算法解决TSP问题.最后,通过Matlab仿真实验表明改进的算法在求解TSP问题时具有更好收敛速度和优化效果.

    Abstract:

    Traveling Salesman Problem (TSP) is an oldest combinatorial optimization problem, and Firefly Algorithm (FA) shows excellent performance to complicated function optimization. Hence, in this study, we used improved FA to solve TSP. Firstly, after the characteristics of TSP are analyzed, and the method of integer encoding is adopted to set the position of fireflies. Then, the logarithmic adjustment factor is introduced in the standard FA. Meanwhile, we combine the crossover, mutation, and reverse operation in Genetic Algorithm (GA) to improve the population diversity and search ability of each iteration, and it is applied to solve TSP. Finally, the numerical experiments show that the proposed algorithm has faster convergence speed and optimization effect.

    参考文献
    1 Changdar C, Mahapatra GS, Pal RK. An efficient genetic algorithm for multi-objective solid travelling salesman problem under fuzziness. Swarm and Evolutionary Computation, 2014, 15:27-37.[DOI:10.1016/j.swevo.2013.11.001]
    2 Caballero R, Hernández-Díaz AG, Laguna M, et al. Cross entropy for multiobjective combinatorial optimization problems with linear relaxations. European Journal of Operational Research, 2015, 243(2):362-368.[DOI:10.1016/j.ejor.2014.07.046]
    3 雷秀娟. 群智能优化算法及其应用. 北京:科学出版社, 2012.
    4 Smith SL, Imeson F. GLNS:An effective large neighborhood search heuristic for the generalized traveling salesman problem. Computers & Operations Research, 2017, 87:1-19.
    5 Kinable J, Smeulders B, Delcour E, et al. Exact algorithms for the equitable traveling salesman problem. European Journal of Operational Research, 2017, 261(2):475-485[DOI:10.1016/j.ejor.2017.02.017]
    6 Yang XS. Nature-inspired metaheuristic algorithms. Frome:Luniver Press, 2008.
    7 Sayadi MK, Ramezanian R, Ghaffari-Nasab N. A discrete firefly meta-heuristic with local search for makespan minimization in permutation flow shop scheduling problems. International Journal of Industrial Engineering Computations, 2010, 1(1):1-10.[DOI:10.5267/j.ijiec]
    8 Jati GK, Suyanto. Evolutionary discrete firefly algorithm for travelling salesman problem. Bouchachia A. Adaptive and Intelligent Systems. Austria:Springer-Verlag, 2011:393-403.
    9 Jati GK, Manurung R, Suyanto. Discrete firefly algorithm for traveling salesman problem:A new movement scheme. In:Yang XS, Cui ZH, Xiao RB, eds. Swarm Intelligence and Bio-Inspired Computation. London:Elsevier, 2013:295-312.
    10 吴宏超, 刘检华, 唐承统, 等. 基于萤火虫算法的管路系统布局序列优化技术. 计算机集成制造系统, 2016, 22(8):1837-1848.
    11 戚远航, 蔡延光, 蔡颢, 等. 旅行商问题的混沌混合离散蝙蝠算法. 电子学报, 2016, 44(10):2543-2547.[DOI:10.3969/j.issn.0372-2112.2016.10.037]
    12 赵玉新, Yang XS, 刘利强. 新兴元启发式优化方法. 北京:科学出版社, 2013.
    13 陈兆芳, 张岐山. 基于粒子群算法的电梯系统选择性维修模型. 计算机系统应用, 2015, 24(8):229-233.[DOI:10.3969/j.issn.1003-3254.2015.08.041]
    14 Baykasoğlu A, Ozsoydan FB. Adaptive firefly algorithm with chaos for mechanical design optimization problems. Applied Soft Computing, 2015, 36:152-164.[DOI:10.1016/j.asoc.2015.06.056]
    15 戴文智, 杨新乐. 基于惯性权重对数递减的粒子群优化算法. 计算机工程与应用, 2015, 51(17):14-19, 52.[DOI:10.3778/j.issn.1002-8331.1412-0259]
    16 Wang JQ, Ersoy OK, He MY, et al. Multi-offspring genetic algorithm and its application to the traveling salesman problem. Applied Soft Computing, 2016, 43:415-423.[DOI:10.1016/j.asoc.2016.02.021]
    17 徐小平, 张东洁. 一种改进的猴群算法. 计算机系统应用, 2017, 26(6):193-197.[DOI:10.15888/j.cnki.csa.005822]
    18 Saenphon T, Phimoltares S, Lursinsap C. Combining new fast opposite gradient search with ant colony optimization for solving travelling salesman problem. Engineering Applications of Artificial Intelligence, 2014, 35:324-334.[DOI:10.1016/j.engappai.2014.06.026]
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

王艳,王秋萍,王晓峰.基于改进萤火虫算法求解旅行商问题.计算机系统应用,2018,27(8):219-225

复制
分享
文章指标
  • 点击次数:2167
  • 下载次数: 2754
  • HTML阅读次数: 1369
  • 引用次数: 0
历史
  • 收稿日期:2018-01-04
  • 最后修改日期:2018-01-23
  • 在线发布日期: 2018-08-04
文章二维码
您是第11326053位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号