• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学

• 人工智能与数据挖掘 • 上一篇    下一篇

一种求解TSP问题的离散蝙蝠算法

张瑾1,毕国通2,李丽丽1   

  1. (1.河南大学计算机与信息工程学院,河南 开封 475004;2.河南大学商学院,河南 开封 475004)
  • 收稿日期:2017-06-27 修回日期:2017-09-14 出版日期:2018-11-25 发布日期:2018-11-25
  • 基金资助:

    国家自然科学基金(41401466)

A discrete bat algorithm for the traveling salesman problem

ZHANG Jin1,BI Guotong2,LI Lili1   

  1. (1.School of Computer and Information Engineering,Henan University,Kaifeng 475004;
    2.School of Business,Henan University,Kaifeng 475004,China)
  • Received:2017-06-27 Revised:2017-09-14 Online:2018-11-25 Published:2018-11-25

摘要:

蝙蝠算法是一种新型的群智能优化算法,在求解连续域优化问题上取得了较好的优化效果,但在离散优化领域的应用较少。研究了求解TSP问题的离散蝙蝠算法,设计了相关操作算子实现算法的离散化,并引入逆序操作使算法跳出局部最优。对TSPLIB标准库中若干经典实例进行测试并与粒子群和遗传算法进行对比分析,结果表明设计的离散蝙蝠算法无论在求解质量还是求解效率上都有明显优势,是一种高效的优化算法。
 

关键词: 离散优化, 离散蝙蝠算法, TSP问题

Abstract:

The bat algorithm is a new swarm intelligence optimization algorithm. It has good optimization results in solving continuous domain optimization problems. However, its applications in the fields of discrete optimization are comparatively rare. We propose a discrete bat algorithm for solving the traveling salesman problem (TSP), and design related operators to realize the discretization of the algorithm. Reverse operation is also introduced to make the algorithm jump out of local optimal solutions. Comparative analysis on some classical examples from the TSPLIB shows that compared with the particle swarm optimization algorithm and the genetic algorithm, the proposed discrete bat algorithm has better solution quality and efficiency, which is an efficient optimization algorithm.
 

Key words: discrete optimization, discrete bat algorithm, traveling salesman problem