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

• 学术论文 • 上一篇    下一篇

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

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

  1. 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-cheng1, HAN Wei1, MAO Bo1,2,3   

  1. 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)

摘要: 提出了一种基于模拟退火的自适应离散型布谷鸟算法求解旅行商问题.该算法在布谷鸟搜索算法原理的基础上,构造了旅行商问题的路径求解策略.由于算法的局限性,随着算法的调整和迭代次数的增加,容易破坏已形成的路径,从而使得算法通用性不强.针对这一局限性,本文提出了一种自适应局部调整算子和全局随机扰动策略.采用简单的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

中图分类号: