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

计算机工程与科学

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

张瑾1，毕国通2，李丽丽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.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

摘要/Abstract

摘要：

蝙蝠算法是一种新型的群智能优化算法，在求解连续域优化问题上取得了较好的优化效果，但在离散优化领域的应用较少。研究了求解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

张瑾1，毕国通2，李丽丽1. 一种求解TSP问题的离散蝙蝠算法[J]. 计算机工程与科学.

ZHANG Jin1,BI Guotong2,LI Lili1. A discrete bat algorithm for the traveling salesman problem[J]. Computer Engineering & Science.

[1]	张瑾, 洪莉, 戴二壮. 求解带容量和时间窗约束车辆路径问题的改进蝙蝠算法[J]. 计算机工程与科学, 2021, 43(08): 1479-1487.
[2]	吴俊斌, 吴晟, 吴兴蛟. 一种用于求解TSP问题的随机最佳插入烟花算法[J]. 计算机工程与科学, 2020, 42(11): 2080-2087.
[3]	张于贤，丁修坤，薛殿春，王晓婷. 求解旅行商问题的改进蚁群算法研究[J]. 计算机工程与科学, 2017, 39(08): 1576-1580.
[4]	徐京雷，赵洪超，刘希玉. 旅行商问题的闭环DNA算法[J]. J4, 2014, 36(01): 111-114.
[5]	许智宏宋勃董建波. 用蚂蚁算法和模拟退火算法解大规模TSP问题的研究[J]. J4, 2008, 30(10): 43-44.
[6]	刘伯颖[1] 吴敬松[1] 镡铁春[2] 李世杰[1]. 离散粒子群优化算法求解旅行商问题[J]. J4, 2008, 30(10): 64-66.
[7]	宋玉阶吴怀宇. 求解线性约束二次优化问题的神经计算模型[J]. J4, 2000, 22(2): 73-76.
[8]	陈沐天. 货郎担问题的几何分块算法及ChinaTSP问题的最终解决[J]. J4, 1998, 20(1): 22-27.