基于模拟退火的自适应离散型布谷鸟算法求解旅行商问题

doi:10.3969/j.issn.0372-2112.2018.08.008

电子学报 ›› 2018, Vol. 46 ›› Issue (8): 1849-1857.DOI: 10.3969/j.issn.0372-2112.2018.08.008

基于模拟退火的自适应离散型布谷鸟算法求解旅行商问题

张子成¹, 韩伟¹, 毛波^1,2,3

1. 南京财经大学信息工程学院, 江苏南京 210046;
2. 现代粮食流通与全协同创新中心, 江苏南京 210046;
3. 江苏省粮食大数据挖掘与应用重点实验室, 江苏南京 210046

收稿日期:2017-07-06 修回日期:2018-03-13 出版日期:2018-08-25
- 通讯作者:
- 韩伟
- 作者简介:
- 张子成 男,硕士研究生,研究方向为人工智能、数据挖掘等.E-mail:269627853@qq.com;毛波男,副教授,硕士生导师,研究方向为三维模型综合简化、在线可视化、数据挖掘以及物联网应用.E-mail:99454961@qq.com
- 基金资助:
- 国家科技支撑计划农资物流防伪和溯源关键技术与装备研发 (No.2015BAD18B02）

Adaptive Discrete Cuckoo Algorithm Based on Simulated Annealing for Solving TSP

ZHANG Zi-cheng¹, HAN Wei¹, MAO Bo^1,2,3

1. School of Inormation Engineering, Nanjing University of Finance and Economics, Nanjing, Jiangsu 210046, China;
2. Modern Grain Circulation and Full Cooperation Innovation Center, Nanjing, Jiangsu 210046, China;
3. Key Laboratory of Large Data Mining and Spplication of Grain,, Nanjing, Jiangsu 210046, China

Received:2017-07-06 Revised:2018-03-13 Online:2018-08-25 Published:2018-08-25
- Corresponding author:
- HAN Wei
- Supported by:
- Subject of National Key Technology Research and Development Program Research and Development of Key technologies and Equipment for Agricultural Goods Logistics Anti-Counterfeiting and Traceability (No.2015BAD18B02)

摘要/Abstract

摘要： 提出了一种基于模拟退火的自适应离散型布谷鸟算法求解旅行商问题.该算法在布谷鸟搜索算法原理的基础上，构造了旅行商问题的路径求解策略.由于算法的局限性，随着算法的调整和迭代次数的增加，容易破坏已形成的路径，从而使得算法通用性不强.针对这一局限性，本文提出了一种自适应局部调整算子和全局随机扰动策略.采用简单的2-opt算子作为局部优化算子加快算法收敛速度，引入模拟退火机制防止算法陷入局部最优.采用标准TSPLIB多组数据进行测试，并与有代表性的优化算法进行结果比较.实验结果证明了该算法在精度和稳定性方面的优势.

关键词: 布谷鸟算法, 旅行商问题, 2-opt 算子, 局部调整, 全局随机扰动

Abstract: An adaptive discrete cuckoo algorithm based on simulated annealing is proposed to solve the traveling salesman problem.The proposed algorithm constructs the path solving strategy of traveling salesman problem based on the principle of cuckoo search algorithm.Due to the limitation of algorithm,with the increasing of the number of iterations,it is inclined to destroy the formed paths,which makes algorithm can not be commonly used in variant applications.To overcome this shortcoming,this paper adopt an new strategy which adjust operator locally and disturb parameters randomly.A simple 2-opt operator is used as the local optimization operator to accelerate the convergence rate of the algorithm.The simulated annealing mechanism is introduced to prevent the local optimum in early iterations.The algorithm is tested by the standard TSPLIB multi-group data,comparing with several representative traveling salesman problem algorithm,the experimental results show the advantages of the algorithm in terms of accuracy and stability.

Key words: cuckoo search algorithm, traveling salesman problem, 2-opt optimization, partial adjustment, global random disturbance

中图分类号:

TN92

张子成, 韩伟, 毛波. 基于模拟退火的自适应离散型布谷鸟算法求解旅行商问题[J]. 电子学报, 2018, 46(8): 1849-1857.

ZHANG Zi-cheng, HAN Wei, MAO Bo . Adaptive Discrete Cuckoo Algorithm Based on Simulated Annealing for Solving TSP[J]. Acta Electronica Sinica, 2018, 46(8): 1849-1857.

参考文献

[1] Applegate DL,Bixby RE,Chvátal V,Cook WJ.The Traveling Salesman Problem:A Computational Study (Princeton in Applied Mathematics)[M].New Jersey:Princeton University Press,2007.
[2] Rego C,Gamboa D,Glover F,Osterman C.Traveling salesman problem heuristics:Leading methods,implementations and latest advances[J].European Journal of Operational Research,2011,211(3):427-441.
[3] Junger M,Reinelt G,Rinaldi G.Handbooks in OR&MS:Chapter4 the Traveling Sales Man Problem[M].Amsterdam:Elsevier Science,1995.
[4] Lawler EL,Wood D E.Branch-and-bound methods:A sur-vey[J].Operations Research,1966,14(4):699-719.
[5] Bellman RE,Dreyfus SE.Applied Dynamic Programming.Princeton[M].New Jersey:Princeton University Press,1962.
[6] Holland JH.Adaptation in Natural and Artificial Systems[M].Ann Arbour:The University of Michigan Press 1975.
[7] Kirkpatrick S,Gelatt Jr CD,Vecchi M P.Optimization by Simulated Annealing[J].Science,1983,220(4598):671-680.
[8] Dorigo M,Gambardella L M.A study of some properties of Ant-Q[A].Lecture Notes in Computer Science[C].1996(1141):656-665.
[9] Yang XS,Deb S.Cuckoo search via le'vy flights[A].Nature & biologically inspired computing,NaBIC World congress on[C].IEEE,2009.210-214.
[10] Krishnand KN,Ghose D. Detection of multiple source location using aglowworm metaphor with applications to collective robotics[A].Proc of IEEE Swarm Intelligence Symposium Piscataway[C].IEEE Press,2005.84-91.
[11] Kenney J,Eberhart R.Particle swarm optimization[A].Proceedings of IEEE Conference on Neural Networks[C].Perth,Australia,1995.
[12] Mostafa Mahi,Ömer Kaan Baykan,Halife Kodaz.A new hybrid method based on particle swarm optimization,ant colony optimization and 3-Opt algorithms for traveling salesman problem[J].Applied Soft Computing,2015,30:484-490.
[13] Bullnheimer B,Hartl R F,Strauss C.A new rank based version of ant system:A computational study[J].Central European J for Operations Research and Economics,1999,7(1):25-38.
[14] Yong Wang.The hybrid genetic algorithm with two local optimization strategiesfor traveling salesman problem[J].Computers & Industrial Engineering,2014,70:124-133.
[15] Saban Gulcu,Mostafa Mahi,Omer Kaan Baykan,Halife Kodaz.A parallel cooperative hybrid method based on ant colony optimization and 3-Opt algorithm for solving traveling salesman problem[J].Soft Comput,2016,1:1-17.
[16] Yassine Saji,Mohammed Essaid Riffi.A novel discrete bat algorithm for solving the travelling salesman problem[J].Neural Comput&Applic,2016,27:1853-1866.
[17] Maribel Guerrero,Oscar Castillo,Mario García Valdez.Cuckoo search via lévy flights and a comparison with genetic algorithms[J].Fuzzy Logic Augmentation of Nature-Inspired Optimization Metaheuristics,2015,91-103.
[18] Maribel Guerrero,Oscar Castillo,Mario García Valdez.Fuzzy dynamic parameters adaptation in the Cuckoo Search Algorithm using Fuzzy logic[J].CEC,2015,441-448.
[19] Claudia I González,Patricia Melin,Juan R Castro,Oscar Castillo,Olivia Mendoza.Optimization of interval type-2 fuzzy systems for image edge detection.Appl[J].Soft Comput,2016,47:631-643.
[20] Pavlyukevich I.L' evy flights,non-local search and simulated annealing[J].Computational Physics,2007,226,1830-1844.
[21] Pavlyukevich I.Cooling down L'evy flights[J].J Phys A:Math Theor,2007,40,12299-12313.
[22] Chiang CW,Lee WP,Heh J S.A 2-Opt based differential evolution for global optimization[J].Applied Soft Computing Computing,2010,10(4):1200-1207.
[23] Aziz Ouaarab·Belal"d Ahiod·Xin-She Yan.Discrete cuckoo search algorithm for the travelling salesman problem[J].Neural Comput & Applic 2014,24:1659-1669.
[24] Aziz Ouaarab·Belal"d Ahiod·Xin-She Yang.Random-key cuckoo search for the travelling salesman problem[J].Soft Comput 2015,19:1099-1106.
[25] Jose B.Escario,Juan F.Jimenez,Jose M.Giron-sierra.ant colony extended:experiments on the travelling salesman problem[J].Expert System with Applications,2015,42:390-410.

基于模拟退火的自适应离散型布谷鸟算法求解旅行商问题

Adaptive Discrete Cuckoo Algorithm Based on Simulated Annealing for Solving TSP

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

[1]	傅文渊. 均衡单进化布谷鸟算法[J]. 电子学报, 2019, 47(2): 282-288.
[2]	戚远航, 蔡延光, 蔡颢, 汤雅连, 吕文祥. 旅行商问题的混沌混合离散蝙蝠算法[J]. 电子学报, 2016, 44(10): 2543-2547.
[3]	马卫, 孙正兴. 采用搜索趋化策略的布谷鸟全局优化算法[J]. 电子学报, 2015, 43(12): 2429-2439.
[4]	何小娟;曾建潮;王丽芳. 一种基于信息传递的分布估计算法[J]. 电子学报, 2011, 39(4): 967-970.
[5]	王雪松;潘杰;程玉虎. 基于知识迁移的Ant-Q算法[J]. 电子学报, 2011, 39(10): 2359-2365.
[6]	邓方安;雍龙泉;周涛;刘丽华. 基于"矩阵乘法"的网络最短路径算法[J]. 电子学报, 2009, 37(7): 1594-1598.
[7]	吴春明;陈治;姜明. 蚁群算法中系统初始化及系统参数的研究[J]. 电子学报, 2006, 34(8): 1530-1533.