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

A discrete bat algorithm for the traveling salesman problem

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

The bat algorithm is a new swarm intelligence optimization algorithm. It has good optimi zation 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 patticle swarm optimization algorithm and the genetic algorithm, the proposed discrete bat algorithm has better solution quality and efficiency, which is an efficient optimization algorithm.