模糊变异算子的改进鸽群优化算法

夏小刚，罗建婷，王 欣

(西安科技大学 理学院，陕西 西安 710054)

0 引言

鸽群优化算法(pigeon-inspired optimization, PIO)是文献[1]在2014年提出的一种模拟鸽子归巢行为的新型群体智能优化算法。当前鸽群优化算法研究主要集中在优化算法改进、理论研究和工程应用3个方面。优化算法改进即通过对算法中2个相互独立的迭代部分进行研究进而实现算法改进[2-4]； 理论研究即进一步完善算法的理论基础[5-7]； 而工程应用即将算法应用于解决工程实际问题中[8-11]，目前主要用于解决机器人、无人机路径规划问题等。鸽群优化算法虽然收敛速度快，但鸽群信息之间交互不足，且易于早熟收敛、陷入局部最优[12]。为此，文献[13]采用巩固参数简化传统鸽群优化算法的结构，实现了两个算子的平滑过渡，又将自组织映射与改进的鸽群优化算法相结合，更好地控制决策空间并找到解的当前分布。文献[14]将延迟因子引入位置更新公式，提高了鸽群优化算法的收敛速度。文献[15]将鸽群优化算法引入到粒子波算法中，从而提高了粒子波算法的精度和稳定性。文献[16-17]将鸽群优化算法与其他算法相融合，相互补充和促进，形成的混合优化算法可更好地解决无人机路径规划问题。

虽然近年来在鸽群优化算法改进方面取得了一定的研究成果，但优化算法仍存在位置更新公式全局搜索能力弱、多样性欠佳等不足。本文受差分进化算法(differential evolution, DE)的启发，在地图和指南针算子与地标算子的位置更新公式中引入模糊交叉变异算子，提出了一种改进的鸽群优化(improved pigeon-inspired optimization，IPIO)算法。借助仿真实验和对旅行商问题(traveling salesman problem,TSP)[18-19]的测试，验证了改进的鸽群优化算法有利于增加种群多样性，避免算法过早陷入局部最优，能够有效提高种群的收敛速度，增强算法的全局搜索能力。

1 改进的鸽群优化算法

1.1 鸽群优化算法的基本理论

PIO主要由两个算子构成：地图和指南针算子，地标算子。在地图和指南针算子中，由式(1)和式(2)确定第i只鸽子在第t次迭代中的位置Xi和速度Vi：

Xi(t)=Xi(t-1)+Vi(t)；

(1)

Vi(t)=Vi(t-1)·e-Rt+rand·(Xg-Xi(t-1))，

(2)

其中：R为地图和指南针因子；rand∈[0,1]；Xg为第t次迭代中的最好位置；Vi(t)为第t次鸽子的当前速度；Xi(t)为第i只鸽子在第t次迭代中的当前位置。

在地标算子中，每一代鸽子的数量都会减少1/2，用Np来记录每一代鸽子的数量。排序接近目的地的鸽子根据式(4)计算剩余鸽子的中心位置，以此作为地标来更新自己的位置。

(3)

(4)

其中：Np(t)为第t代鸽群的数量；Xc(t)是第t代鸽子飞近目的地时作为参考方向的中心位置(期望目的地)；Fitness(Xi(t))是适应度值，对每只鸽子的适应度值[16]进行评估并排序，找到最优路径。式(5)对鸽群位置进行越界处理，更新鸽群位置。

Xi(t)=Xi(t-1)+rand·(Xc(t)-Xi(t-1))。

(5)

1.2 模糊交叉变异的实现

针对种群中的每一个体Xi=(xi,1,xi,2,…,xi,n)，由模糊变异式(6)进行变异操作：

Wi=γ·xr1+(1-γ)·F·(xr2-xr3)，

(6)

其中：xr1为当前种群中适应度值最好的个体；xr2和xr3为群体中随机选取的个体；F∈[0,2]为比例因子，比例因子F保证了种群的多样性和搜索能力，大多数函数F的最优值为0.5～1.0；γ∈[0,1]为模糊参数，模糊参数γ表示变异算子的开发和贪婪程度，用于扩大局部和全局搜索能力[20]。

依据式(6)得到的变异种群Qi=(qi,1,qi,2,…,qi,n)，由式(7)进行交叉操作，得到新的种群Mi=(mr,1,mr,2,…,mr,n)。对排序接近目的地的鸽子进行越界处理，若Mi支配Xi,则用Mi代替Xi；若Xi支配Mi，则直接丢弃Mi。若互不支配，则将Mi加入Xi。交叉公式为：

(7)

其中：CR为交叉概率，取值(0,1)，即randβ∈(0,1)；β是在{1,2，…，n}中随机选取的数。

1.3 位置更新公式的修正

模糊交叉变异算子有利于种群之间的信息交换，保证种群多样性，扩展种群的全局搜索范围，据此在更新公式中引入模糊交叉变异算子，并提高算法的全局开发能力和局部搜索能力。通过随机选择解空间中的个体来调节鸽子的位置，从而增强群体的多样性和全局探索能力。

改进的鸽群优化算法的地图和指南针算子的位置更新公式为：

Xi(t)=Xi(t-1)+Vi(t)+Wi，

(8)

地标算子的位置更新公式为：

Xi(t)=Xi(t-1)+rand·(Xc(t-1)-Xi(t-1))+Wi，

(9)

其中：Wi为模糊交叉变异算子。由式(8)和式(9)可以看出：与式(1)和式(5)相比，式(8)和式(9)增加了模糊交叉变异算子，从而达到对传统鸽群优化算法位置更新公式的修正。

1.4 改进鸽群优化算法流程图

本文提出的改进算法流程图如图1所示。根据式(2)和式(5)可以看出，传统鸽群优化算法的位置更新公式只考虑了鸽子的当前位置和鸽群最优位置，由鸽群最优位置进行搜索，忽略了算法的搜索能力。受差分进化算法的启发，在传统鸽群优化算法中的位置更新公式中引入模糊交叉变异算子，位置更新公式的修正如式(8)和式(9)所示，引导种群变异，增加种群的多样性，提高算法的全局搜索能力。

图1 改进算法流程图

2 实验结果分析

2.1 测试函数及参数设置

表1给出DE、粒子群算法(particle swarm optimization，PSO)、PIO、IPIO这4种算法在19个标准测试函数中分别进行20次实验的结果，分别记录4种算法的最优适应度值(Optimal)、平均适应度值(Mean)和方差(Variane)。其中，最优适应度值反映解的质量；平均适应度值反映算法的收敛速度；方差反映算法的稳定性和鲁棒性。将表1中最优适应度值和平均适应度值达到理论最优值的数据均标注为粗体，最优个数表示达到最优适应度值及平均最优适应度值的个数。19个标准测试函数即Schwefel’s problem 2.22(f1)、Sphere(f2)、Schwefel 2.21(f3)、Rosenbrock(f4)、Step(f5)、Quartic(f6)、Goldstein-Price(f7)、Hartmann 6-Dimensional(f8)、Shekel(f9)、Generalized Schwefel’s(f10)、Rastrigin(f11)、Ackley(f12)、Griewank(f13)、Levy(f14)、Levy n.13(f15)、De Gong Function n.5(f16)、Kowalik(f17)、Camel(f18)、Branin(f19)。其中，f1～f9是单峰函数，f10～f19是多峰函数。实验中4种算法参数设置如下：种群规模50，最大迭代次数为1 000，比例因子设为0.5[21]，模糊参数设为0.5。实验在MATLAB2018b软件中进行编程运行。

2.2 实验结果分析

从表1可以看出： IPIO在f2、f7、f8、f10、f11、f13和f19均能收敛到理论最优值。对于其他测试函数，IPIO虽然没有收敛到理论最优值，但其获取的适应度值与理论最优值十分接近。对于函数f7、f18和f19，4种算法都能取得相同的理论最优值。对于函数f5，传统PIO取得了理论最优值。此外，DE有3个测试函数取得理论最优值，PSO有4个测试函数取得理论最优值。DE与PSO相比，寻优能力差不多，虽然DE和PSO求解最优适应度方面效果较差，但2个算法的稳定性较好。IPIO获取的寻优个数为18个，寻优率达到了94.7%，相较于传统PIO寻优个数提高了9个，寻优率提升了47.3%，取得了较好的最优适应度值、平均适应度值和方差，寻优能力均优于其他3种对比算法。

表1 4种算法在标准测试函数中适应度值比较

选出具有代表性的3个测试函数f8、f9、f10，4种算法在测试函数上的收敛曲线如图2所示。

(a) f8的收敛曲线 (b) f9的收敛曲线 (c) f10的收敛曲线

图2a表明：在求解函数f8时，4条曲线均为先快速下降，在50次至200次迭代后趋于稳定，PIO虽然在200次迭代后跳出局部最优，但求解精度不如其他3种对比算法。DE和PSO在前期收敛速度较快，但后期均陷入局部最优。IPIO收敛速度不仅快，而且比其他3种算法的求解精度高。图2b表明：在求解函数f9时，其他3种函数都过早地陷入局部最优，IPIO在早期收敛速度较慢，但分别在200次和700次迭代后跳出局部最优，因此可以得出IPIO的求解精度相比其他3种算法有了显著提高。图2c表明：在求解函数f10时，PSO过早地陷入局部收敛，DE和PIO前期下降速度几乎相同，PIO和IPIO都在700次迭代后跳出局部最优，但IPIO得到一个更好的适应度值。IPIO显然比其他3种算法求解精度高，且有效地避免算法陷入早熟收敛，可得到较好的结果。

3 改进鸽群优化算法求解旅行商问题

本文算法参数仿真均以TSPLIB数据集中的dantzig42问题作为测试数据，dantzig42问题是TSPLIB数据集中的一个数据文件，城市规模为42，已知最优解为699，运行10次。IPIO与其他3种对比算法的仿真实验结果如表2所示。

由表2可以看出：无论是平均最优值还是相对误差，改进算法均优于其他3种对比算法。在10次仿真结果中，IPIO有3次仿真实验达到理论最优解，平均最优值为700.3，且大多数数据都集中在最优解范围内，相对误差为0.19%。这表明对于dantzig42问题，IPIO的求解精度优于其他3种对比算法。除了单纯的数据，可以通过路径仿真图来模拟4种算法在实际中的最优路径效果。图3给出了4种算法对dantzig42问题的路径优化结果图，根据路径图的线路复杂程度可以看出IPIO较其他3种对比算法效果更好。

表2 4种算法仿真实验结果对比

(a) DE优化结果图 (b) PSO优化结果图

4 结论

(1)IPIO在平均适应度值方面优于DE、PSO和PIO。IPIO在寻找最优适应度值方面优于DE、PSO和PIO。

(2)IPIO能够跳出局部最优，避免早熟收敛，增强算法的全局搜索能力。

(3)IPIO能有效提高TSP的最优解。