求解TSP的变邻域蝙蝠算法

朱德鑫，蔡延光

（广东工业大学自动化学院，广东广州，510006）

0 引言

旅行商问题(Traveling Salesman Problem，TSP)是一个经典的NP-hard组合优化问题。该问题具有重要的工程应用价值，在车间调度、物流运输等领域都有其应用。

蝙蝠算法(BA)是一种受启发于蝙蝠觅食行为的算法，最早由Yang Xin-she于2010年提出。自然界中蝙蝠利用自身独特的生物结构，通过超声波探测的信息定位周围环境和猎物，以进行规划飞行路线和捕食猎物。蝙蝠算法就是模仿此类行为而创造的一种新型群体智能优化算法。目前在车间调度、工程优化等领域中均得到应用。

本文提出一种变邻域蝙蝠算法(VNBA)，在传统蝙蝠算法上混合三种变邻域策略改善算法局部特性，同时加入惯性权重平衡算法前期的全局搜索和后期的局部搜索，改善传统算法易陷入局部最优的困境。

1 旅行商问题的数学模型

旅行商问题可以描述为：一名销售员需要去往N个城市进行销售，已知各个城市的具体位置以及城市与城市间的具体距离，现需要规划一条路线，使得该路线能够经过每一个城市，且每个城市仅被经过一次，并最终回到出发点，同时总行程最短。假设遍历所有城市后形成的路线为：，则最短路径的求解为：

其中，式（1）表示最小化路程，式（2）表示两个城市间的距离。

2 变邻域蝙蝠算法设计

2.1 蝙蝠速度和位置更新

蝙蝠算法的速度、位置更新公式如式(3)(4)(5)所示。其中β∈[0, 1]是从均匀分布中抽取的随机量。fmin和fmax代表种群脉冲频率上下限，fi代表第i只蝙蝠个体的脉冲频率，x*则代表当前代数下全局最优的蝙蝠所处位置，表示t+1时刻下蝙蝠个体的位置和速度。

2.2 蝙蝠响度和发射频更新

当蝙蝠最优解更新时，调整蝙蝠个体响度A和发射频r：

2.3 变邻域策略

虽然在求解较为复杂的组合优化问题上，蝙蝠算法具有较好的全局搜索能力，但在求解后期时，蝙蝠算法容易出现收敛精度较低和陷入局部极值的问题，为此加入三个邻域策略，以提高算法的搜索性能。

（1）2-opt策略

（2）exchange策略

（3）insert策略

在变邻域蝙蝠算法的迭代过程中，为使局部搜索性能更优，搜索空间更为多样性，将同时使用以上三种策略，在对当前某个蝙蝠个体的解Xi使用某一邻域搜索后产生新解Xnew，若新解比原解更优则替换掉原解且在当前邻域中继续搜索，否则保留原解进入下一个邻域搜索，达到设定的迭代次数后，停止邻域搜索并保留邻域搜索最优解。

2.4 惯性权重

由蝙蝠算法速度更新公式可知，当蝙蝠算法的速度更新时，会将当前蝙蝠与全局蝙蝠对比更新以此达到加快收敛速度的目的，但这也容易让蝙蝠算法陷入局部最优，为了平衡好算法的全局和局部的搜索能能力，使得蝙蝠算法能够在算法搜索的前期能有更好的全局寻优能力，在算法搜索的后期能有更好的局部寻优能力，此处在蝙蝠速度更新中加入惯性权重ω，加入惯性权重后的公式如式(8)：

其中ω的设置为了契合旅行商问题，将其离散化，具体权重ω如式(9)：

其中，t为算法当前迭代次数，T为全局最大迭代次数。由式子可知，在算法前期，惯性权重较小，增强全局搜索能力，后期惯性权重大，使得与上一代蝙蝠的关联性增大，提升局部搜索能力。

2.5 算法步骤

在蝙蝠算法中加入三种变邻域优化策略和惯性权重后，VNBA算法步骤如下：

Step1：初始化变邻域蝙蝠算法种群。

Step2：通过计算个体适应值找出蝙蝠种群中的最优蝙蝠蝙蝠，并记录对应个体的位置及其适应度值。

Step3：根据公式(1)(9)(3)更新每一只蝙蝠的脉冲频率fi、速度vi和位置xi，求解当前每只蝙蝠对应的适应度值，并与上一代的适应度值做比较，保留更优的个体。

Step4：随机生成一个随机数R1，若R1大于ri，则将全局搜索的最优蝙蝠个体进行三种变邻域搜索，否则保留原来的最优蝙蝠个体。

Step5：再随机生成一个随机数R2，若该数R2小于当前蝙蝠个体的响度Ai且新个体的适应度优于原个体的适应度时，则接受Step4中的个体解。同时更新个体i的响度A以及其脉冲发射率ri，否则不对其响度以及脉冲发射率进行更新。

Step6：计算全部个体对应的适应度值并作对比排序，寻找到当代全局最优解。

Step7：重复步骤Step3到Step6，直到迭代次数超过最大迭代次数时停止迭代，并且输出全局最优解。

3 实验仿真及分析

实验选取5组TSP标准算例作为实验算例，并与遗传算法(GA)和蚁群算法(ACO)作对比。VNBA算法参数为：种群大小N=100，脉冲频率fmin=0，fmax=1、脉冲响度A=0.9、脉冲发射率ri=0.9、常数α=0.9，γ=0.9、惯性权重ωmin=0.2，ωmax=1；GA算法参数为：种群大小N=100，变异概率Pm=0.05、交叉概率Pc=0.95、代沟GGAP=0.9；ACO算法参数参数为：种群大小N=100，信息素因子α=1，启发函数因子β=5，信息素挥发因子ρ=0.1，信息素释放总量Q=1。每组算例测试20次。

由表1可知，VNBA算法Oliver30和Att48能找出最优解，其优化后的路径如图1、2所示。在求解50个点以上的TSP算例时，VNBA也能寻找到较优的解，且误差都在5%以内。同时VNBA的在各个算例的最优解都要优于GA、ACO算法的解，证明VNBA在求解TSP问题时的全局寻优性能更优。同时VNBA在各个算例中的平均解也更优，且平均解和最优解的差距较小，证明了VNBA算法也有较好的求解稳定性。

表1 各算法性能对比分析

图1 VNBA优化后的Oliver30路径图

图2 VNBA优化后的Att48路径图