王思琦 高 尚 张 宁

（江苏科技大学计算机学院 镇江 212000）

1 引言

旅行商问题（Travelling Salesman Problem，TSP）是一种复杂的NP难题，近几十年来，许多专家学者进行了大量的研究，为解决这一问题提出了许多群智能算法。这些算法简单易操作，具有分布式计算机制、强鲁棒性、良好扩展性以及广泛的适应性等特点，为求解该类问题提供了新思路。典型的智能算法有模仿蚂蚁集体觅食行为的蚁群算法（ACO），模拟鸟类捕食行为的粒子群算法（PSO），借鉴达尔文生物进化过程的遗传算法（GA）等，它们不仅仅能够解决路径规划问题，并被应用在多种领域。但其都有各自的局限性，例如GA需要对问题进行编码解码，对初始种群有一定的依赖性［1］；ACO初始信息素匮乏，收敛速度慢，易陷入局部最优［2］；PSO优化速度和精度较低，计算效果与算子复杂度成正比［3］。

离散烟花算法（discrete fireworks algorithm，DFWA）是北京大学谭营教授继2010年开创性论文“Fireworks algorithm for optimization”［4］后提出的一种解决离散问题的群智能算法。针对烟花算法易陷入局部最优、火花之间缺少交流机制、选择策略随机性较大［5］等局限性，许多研究学者已经提出了相关改进策略。如：Zheng与Li［6等研究了烟花算法爆炸幅度的自适应策略，提出了动态搜索烟花算法和自适应烟花算法；Yu［7］等研究了烟花算法与差分演化算法的结合；Zhang［8］等提出生物地理学优化-烟花混合算法；Zhu［9］等提出引力搜索算子加强了火花之间的信息交流；徐焕芬等［10］提出双种群烟花算法促使种群间的信息交换以提高精度等。应用领域主要包括多目标调度问题［11］、方向性特征距离度量、油料作物的施肥问题、图像识别［12］、云计算［13］等。

随着烟花算法的不断改进，其在连续优化问题中已经表现出了出色的寻优能力，但离散烟花算法在路径优化问题方面的研究还很缺乏。为此，以解决TSP问题为目的，针对离散烟花算法中的选择策略，将每一代个体中最优解（适应度最小）保留，并且利用选择参数动态调整种群的被选概率，将精英火花与动态选择火花作为子代进行迭代搜索，以增强算法全局搜索能力，加快收敛速度，保证种群多样性及算法精度。

2 离散烟花算法

与传统烟花算法相比，离散烟花算法结构与其相似，由于其解不会超过定义域范围，从而省略了映射这一步［14］，包括爆炸算子、变异算子和选择策略。算法流程如图1所示。

图1 离散烟花算法流程图

2.1 爆炸操作

考虑到离散的路径规划问题其解为一个不重复序列，因此爆炸操作被定义为单个个体中两条边或三条边的交叉互换，从而产生新解，相当于2-opt操作和3-opt操作。把初始化的解带入适应度函数中计算适应度值，并根据适应度大小来产生火花。每个烟花爆炸的火花个数的计算公式如下：

其中，Si为第i个烟花爆炸所产生的火花个数；Ymax是当前适应度最差即适应度值最大的个体的适应度；f(xi)为第i个个体的适应度值；m为最大火花数目；ε为避免分母为零的极小常数。

2.2 均匀变异操作

考虑到爆炸算子是对边进行操作，均匀变异则定义为对点操作，目的是将个体中的一个点插入到两个相邻点中，以得出一个更优个体。例如，原个体为，要使ak插入到边(ai，ai+1)中，先将子序列(ai+1，…，ak)反转，再将子序列(ak-1，…，ai+1)反转，使得原序列变化为(… ，ai，ak，ai+1，…，ak-1，ak+1，…) ，从而得出新个体。如图2所示，经过变异后的新回路的路径长度要明显优于原回路。

图2 均匀变异操作

2.3 选择策略

选择策略则是由精英选择和轮盘赌策略相结合，保留最优解的同时加强局部搜索。每个个体被选中的概率可表示为

其中Lmin是最小适应度值，即最短路径的长度；ε为防止除零情况的一个极小参数。

轮盘赌策略的出发点是适应度值越好，其被选中的概率越大，但其随机性大并忽略了可能在下一代中爆炸变异出更好子代的差解，因此提出对选择操作进行改进。

3 改进离散烟花算法

3.1 适应度函数

在TSP问题中，其解为一个无重复的序列，用向量x=(x1，x2，…，xn)表示，xi为路径中第i个配送点，每个配送点必须且只能经过一次。因此待求问题L(x)可表示为

其中d(xi，xj)为第i个配送点和第j个配送点之间的距离。显然，算法的优化目标是min(L(x))，并且满足：

3.2 基于精英选择和动态调整的选择策略

易陷入局部最优是离散烟花算法的不足之处，利用确定性选择和随机选择相结合，通过选择过程中加入动态参数［15］来使其跳出局部收敛，能够加强离散烟花算法的全局搜索，保证种群多样性，更有利于提高算法寻优能力。

传统离散烟花算法中的精英选择是将初始烟花和火花同时纳入备选，其中最优解保留到下一次迭代中。改进后的精英选择，将备选种群内的父代烟花剔除，只在子代火花种群中进行选择。由于均匀变异操作只接受更优的解，因此一定程度上增大了选择到优质种群的概率，其伪代码如下。

考虑到被选概率依赖于适应度值的大小，而传统离散烟花算法中选择的子代个数为一个定值，并且式（2）中2次幂的形式使得优秀的个体更易被选中这样不利于较差解被选入下一代进行爆炸变异操作，从而不利于算法进行全局搜索。受文献［16］启发，提出尝试加入动态参数η和λ来调整选择数量以及被选概率。

其中η为选择子代数量，t为当前迭代次数，s为火花数目，C1和C2分别为增大因子和缩小因子。当本次平均适应度优于前一次平均适应度时减小选择数目，反之增加选择数目。

其中：

t为当前迭代次数。经实验证明随着迭代次数的增加，参数λ越来越小，对个体被选概率的干预增加，降低随机性从而使算法跳出局部最优。

该策略通过C1和C2来调整子代的选择数目，迭代前期适当增加子代数目，扩大搜索范围，而参数λ使得适应度较小的个体更容易被选择，在迭代的中后期最优解已经趋于稳定，则不需要过多的子代进行重复操作，而适当增加适应度较大的个体被选概率可以防止算法搜索过程中出现早熟。

改进后的选择策略为

4 仿真实验结果与分析

为验证本文算法的优越性，利用Matlab R2016a软件模拟34个地点进行实验，将路径距离之和作为适应度函数，并和遗传算法、传统离散烟花算法进行对比。实验参数设定为34个配送地坐标如表1，遗传算法种群大小为100，最大遗传代数500，交叉概率0.9，变异概率0.05；离散烟花算法烟花数量为5，最大火花数目为50，最大迭代次数为500次；本文算法烟花数量为5，最大火花数目为50，最大迭代次数为500次，增大缩小因子为±0.2。将三种算法各运行30次。

表1 34个点坐标

图3为改进算法运行的最优路径结果。其最优路径为5→17→18→20→19→12→24→21→16→7→27→6→1→3→28→30→8→2→29→9→32→31→14→23→15→33→13→26→22→11→25→4→10→34→5的回路，最优距离为15.6745。表2可见三种算法所寻找到的最优解差别不大，但遗传算法所需要的平均迭代次数较多，与改进离散烟花算法相差甚远，收敛速度较慢；传统离散烟花算法平均最优解略高，收敛代数比改进后的算法多出40代左右，两种算法所得方差较大，稳定性都略低于本文算法。

图3 改进算法所得最优路径

表2 算法对比实验结果

将改进离散烟花算法与遗传算法的优化过程对比，由图4可见改进离散烟花算法在前期收敛速度相当快，能够在前50代迅速下沉，寻优精度方面也明显优于遗传算法，说明精英选择和动态参数的结合使得离散烟花算法的全局搜索能力增强的同时收敛速度加快，在解决TSP问题上的性能有较大提升。

图4 改进算法和遗传算法的优化过程

进一步验证所提改进离散烟花算法的性能，在Matlab R2016a软件上将该算法应用到TSP标准数据集中进行测试，并与GA、PSO和ACO各运行20次进行对比，选取的TSP标准数据集为Fri26、Bays29、Att48、Eil51。

由表3可知改进离散烟花算法在以上数据集中的性能均优于其他三个算法，更接近已知最优解，从数据集大小来看本文算法在小数据集上体现的性能更为优异，预测随着数据集的增大其稳定性可能将会受到影响，因此选取数据集Eil101为下一个实验对象，将本文算法与遗传算法进行对比实验，结果如下。

表3 算法实验结果对比

由表4可知对于较大规模数据集，遗传算法的寻优性能更为优异，改进离散烟花算法的最优解虽与遗传算法仍有差距，但在算法稳定性上有明显进步。图5为改进离散烟花算法和遗传算法的一次寻优过程对比，改进算法在迭代初期优于遗传算法，收敛速度较快，优化比较稳定，但在600代以后寻优效率降低，曲线趋于平滑，从而导致最后寻优精度略低于遗传算法。

表4 算法在数据集Eil101的实验对比

图5 两种算法在数据集Eil101上的对比

5 结语

本文提出了一种改进的离散烟花算法，根据原算法易陷入局部最优而导致的早熟问题将选择策略改进为基于精英选择和动态参数相结合的策略，极大提升了算法的全局搜索性能，增加种群多样性的同时保证算法的收敛速度。通过与GA、PSO、ACO和传统离散烟花算法对TSP数据集的测试证明改进算法对小规模数据具有优良性能，大规模数据集以及不对称TSP问题将是后续的研究方向。