电子学报 ›› 2016, Vol. 44 ›› Issue (10): 2543-2547.DOI: 10.3969/j.issn.0372-2112.2016.10.037

• 科研通信 • 上一篇    下一篇

旅行商问题的混沌混合离散蝙蝠算法

戚远航1, 蔡延光1, 蔡颢2, 汤雅连1, 吕文祥1   

  1. 1. 广东工业大学自动化学院, 广东广州 510006;
    2. 奥尔堡大学健康科学与技术系, 丹麦奥尔堡 9220
  • 收稿日期:2015-03-24 修回日期:2015-06-04 出版日期:2016-10-25 发布日期:2016-10-25
  • 作者简介:戚远航,男,1993年6月出生,广东湛江人.现为广东工业大学硕博连读生,从事供应链物流及智能算法的研究.E-mail:qiyuanhang77@163.com;蔡延光,男,1963年2月出生,湖北咸宁人.1988年和1996年分别在重庆大学和浙江大学获理学硕士和工学博士学位.现为广东工业大学教授,博士生导师,从事复杂网络系统建模、控制与优化、物流控制与优化、智能交通系统、组合优化、智能优化、物联网信息处理与优化控制等方面的研究.
  • 基金资助:

    国家自然科学基金(No.61074147);广东省自然科学基金(No.S2011010005059);广东省教育部产学研结合项目(No.2012B091000171,No.2011B090400460);广东省科技计划项目(No.2012B050600028,No.2014B010118004);广州市花都区科技计划项目(No.HD14ZD001)

Chaotic Hybrid Discrete Bat Algorithm for Traveling Salesman Problem

QI Yuan-hang1, CAI Yan-guang1, CAI Hao2, TANG Ya-lian1, LÜ Wen-xiang1   

  1. 1. School of Automation, Guangdong University of Technology, Guangzhou, Guangdong 510006, China;
    2. Department of Health Science & Technology, Aalborg University, Aalborg 9220, Denmark
  • Received:2015-03-24 Revised:2015-06-04 Online:2016-10-25 Published:2016-10-25

摘要:

针对现有离散蝙蝠算法在求解旅行商问题时存在的收敛速度较慢、收敛率不高等问题,提出了混沌混合离散蝙蝠算法.该算法采用混沌初始化策略提高算法的寻优能力,引入2-Opt技术增强算法的局部搜索能力、加快算法的收敛速度.大量的仿真实验表明:所提出的算法在求解小规模TSP时能快速收敛到已知最优解;在求解大规模TSP时能在较短的时间内收敛到偏差0.4%以内的最优解.

关键词: 旅行商问题, 混沌初始化, 蝙蝠算法, 2-Opt

Abstract:

In view of some problems,like slow convergence speed and low constringency rate,arising during the process of applying discrete bat algorithms to solve travelling salesman problem,a chaotic hybrid discrete bat algorithm is proposed.The proposed algorithm adopts chaotic initialization strategy to improve the capability of optimization,and the 2-Opt to enhance the capability of local search and to speed up the convergence speed.A large amount of simulations show that the algorithm can achieve their solutions rapidly for some small scale traveling salesman problems,and obtain their solutions in a relatively short time with the error less than 0.4% for large ones.

Key words: traveling salesman problem, chaotic initialization, bat algorithm, 2-Opt

中图分类号: