辛梓芸，张达敏，陈忠云，张绘娟，闫 威

贵州大学 大数据与信息工程学院，贵阳550025

1 引言

近年来元启发式算法作为一种有效的演化计算技术，已受到众多学者的重视。元启发式算法是指受到现实环境的启发提出的一类算法，其核心思想是实现搜索过程中随机性行为和局部搜索的平衡。常用的元启发式算法包括布谷鸟搜索算法（Cuckoo Search，CS）、粒子群优化算法（Particle Swarm Optimization，PSO）、蚁群优化算法（Ant Colony Optimization，ACO）等以及较新的蝴蝶优化算法（Butterfly Optimization Algorithm，BOA）都简单易行、参数少、运行时间短等特点，因此在解决众多非线性和多模态的现实寻优问题中，元启发式算法呈现了优良的可操作性以及寻优能力[1-6]。

乌鸦搜索算法[7]（Crow Search Algorithm，CSA）是由Askarzaden 学者在2016 年提出的一种新兴的元启发式算法，该算法基于长期对乌鸦习性的研究，模拟了该群体之间相互追踪窃取食物的社会行为，这一特性使算法种群的多样性并不会随着迭代有较大的降低，也就增加了跳出局部最优的概率。目前该算法已经成功应用于众多工程优化和函数优化问题中。文献[8]提出了一种混沌乌鸦算法（Chaotic Crow Search Algorithm，CCSA），引入混沌理论调整CSA参数，从四种变体中找到最好的变体以提高全局收敛速度增强寻优能力，并将算法用于求解分数优化问题。文献[9]提出了一种自适应步长的乌鸦算法（Modified Crow Search Algorithm，MCSA），有效地开发了算法的搜索能力，将算法应用在非凸经济负荷调度。文献[10]提出了基于Levy 飞行策略的混沌乌鸦搜索算法（Levy Differential Evolution Crow Search Algorithm，LDECSA），提高算法跳出局部最优的概率，改变编码方式，将该算法用于求解{0-1}背包问题上。以上算法均主要针对全局搜索性能的提升进行改进，没有将平衡乌鸦算法的全局搜索性能与局部搜索性能作为研究的重点，算法收敛速度较慢的问题没有较好地解决。因此本文提出一种基于多段扰动的共享型乌鸦算法（Multi-segment Interference Sharing Crow Search Algorithm，MISCSA），通过引入向最优粒子学习的思想，以及在迭代的不同阶段加入扰动，使算法同时兼具收敛速度与精度的提升。

2 乌鸦搜索算法

乌鸦被认为是世界上最聪明的动物之一，它们会使用工具、复杂地交流。在不同的时节乌鸦会藏匿多余的食物，并在需要时取回。同时它们也互相跟随，窃取别的乌鸦所藏匿的食物以获得更好的食物来源。但是当一只乌鸦发现被跟随时，它会试图通过改变藏匿的地点来避免被盗。因此基于以上乌鸦的行为。乌鸦搜索算法有以下原则：

（1）乌鸦以群体形式生活。

（2）乌鸦能够记得藏匿食物的位置。

（3）乌鸦相互跟随盗窃食物。

（4）乌鸦对于跟随者有一定的感知能力，感知到被跟随就会改变藏匿地点。

其中，fl 表示乌鸦的飞行长度（一般设置为0.8～2）；APi,iter表示在iter 次迭代中第i 只乌鸦的感知概率（一般设置0.1～0.4）；ri，rj是[0，1]内服从均匀分布的随机数。mj,iter表示第j 只乌鸦藏匿食物的位置，其实质是第j 只乌鸦在iter 次迭代的最优位置。藏食位置的更新公式如下：

CSA的伪代码如下：

设置参数步长fl、感知概率AP、迭代次数iter 、种群大小N 、维度n；

初始化N 只乌鸦的位置和藏食位置；

While iter ＜itermax

For i=1∶N

随机选择一只乌鸦j

If r ≥AP

Else

End If End For

计算适应度值FIT(iter)

评估乌鸦的新位置

更新乌鸦的藏食位置

End while

迭代完毕后，m 中储存的最优位置即寻优问题中最优解的位置。

3 基于多段扰动的共享型乌鸦算法

3.1 加入共享机制的位置更新方式

在乌鸦算法中，乌鸦(i)以随机方式跟踪某一乌鸦(j)进行位置更新，这样的更新方式可以在迭代的前期保持种群较好的多样性，但是也会使算法的盲目性较大，收敛速度变缓，无法在较短时间收敛到最优值。

1995 年Kennedy 学者提出了粒子群算法（PSO）[11]，通过群体内个体之间的信息共享来对问题的解进行协同搜索，即粒子的飞行速度不仅参考自身历史最优位置，也会参考群体中最优粒子的位置进行动态调整，这使算法具有收敛速度快的特点。因此为了增强算法的领导能力，在乌鸦搜索算法的位置更新部分引入粒子群算法中向最优粒子学习的思想，使乌鸦种群共享出环境中最优的藏食位置，即在随机跟随某一个体的同时也参考种群中最优藏食位置来进行自身更新。乌鸦种群在最优藏食位置的领导下，算法大大地提高了收敛速度。新的位置更新公式如下：

3.2 加入扰动策略更新最优藏食位置

CSA是一种非贪婪型算法，即当前解如果不优于上一代则不会被保留。因此，乌鸦搜索算法到了迭代后期极易陷入局部最优。特别是在应用于较复杂的多峰函数中时，收敛过早且精度低下的缺点更为明显。其次，3.1节中改进后的位置更新公式也一定情况影响算法在多峰函数中最优解的精度。对此本文引入赵新超等提出的多段扰动策略[12]用于更新最优藏食位置mgbest,iter，即对全局最优藏食位置根据方差可调的正态随机分布进行扰动得到新的全局最优藏食位置mgbest′,iter，速度更新公式如下：

其中δ 表示正态随机分布的方差，δ 的更新方式如下：

其中，δ 表示正态扰动的半径参数且δ1＞δ2；α1,α2是半径变化的控制参数，且α1＜α2；t 是当前函数值计算次数，T 是最大函数计算次数。在迭代早期δ1取值较大，群体会向全局最优藏食位置较大的邻域内搜索；在迭代后期干扰半径δ2取值较小，则在全局最优藏食位置较小的邻域进行搜索，使得当前解几乎不再从较优区域跳出保证算法群体仅向全局最优解学习，从而保证算法具有较好的收敛性。

结合3.1、3.2 节对算法的改进，即在加强全局最优藏食位置的领导力的同时，依靠对全局最优藏食位置进行不同阶段大小不同的扰动可以极大增加算法跳出局部最优的概率，使算法达到了全局搜索与局部搜索的平衡，既提高了搜索精度也加快了收敛速度。

MISCSA算法的伪代码如下：

设置参数：步长fl、感知概率AP、迭代次数iter、最大迭代次数T、种群大小N、维度n；扰动参数α1、α2、δ1、δ2；

初始化N 只乌鸦的位置x(0)和藏食位置m(0)；

记录最优藏食位置mgbest,0；

计算初始适应度值FIT（0）

While iter ＜itermax

For i=1∶N

随机选择一只乌鸦j

If r ≥AP

xi,iter+1=xi,iter+ri×fl×(mj,iter-xi,iter)+sm

Else

xi,iter+1=任意位置

End if

End for

计算适应度值FIT(iter)

评估乌鸦的新位置

更新乌鸦的藏食位置

If α1T ＜iter ＜α2T

mgbest′,iter=N(mgbest,iter,δ1)

End

If iter ＞α2T

mgbest′,iter=N(mgbest,iter,δ2)

End

End while

4 仿真实验

为了验证MISCSA 算法在求解各类优化问题的有效性，本文选取8 个典型的基准测试函数[13]在不同维度下对CS[14]、CSA[7]、PSO[11]、BOA、MISCSA 的优化性能进行比较。

4.1 实验平台

该实验的操作系统为Windows 10，CPU 为Intel Core i5-7300U，主频2.6 GHz，内存8 GB，编程语言为Matlab R2014b。

4.2 实验设计

为了公平起见，将最大迭代次数设置为1 000，5 种算法针对每一个测试函数独立运行50 次，将测试函数的全局最小值的平均值、标准差、平均耗时作为衡量优化性能的指标。并采用Wilcoxon 秩和检验比较各算法的优越性。

表1中选取的测试函数中包含单峰、多峰等不同特征的测试函数。单峰函数为在定义上下限内只有一个严格上的极大值（或极小值），通常用来检测算法收敛速度。多峰函数为含有多个局部最优解或全局最优解的函数，经常用于检测算法探索能力和开发能力。

表1 基准函数

5种算法参数设置如表2所示。

表2 参数设置

4.3 实验结果分析

实验1 CS、CSA、PSO、BOA 和MISCSA 的函数优化结果比较

为了更好地研究MISCSA算法的优化性能，分别在10、30、50 的算法维度下进行50 次独立寻优，并记录这50次的平均值以及计算其标准差进行比较。结果如表3～表5所示。

表3 10维实验结果分析

通过分析表3～5 的数据可知，当求解维度为10 维，CS、CSA在求解单峰函数(f1～f5)时精度较高，特别CS算法在求解sphere 函数时高达1E-12，表现出了较好的寻优能力，稍优于CSA，但是随着变量维度的增加，这两个算法的搜索能力均有明显的下降，对于50 维的sphere 函数算法CS、CSA 求解的精度均为1E+00，降低了9 个数量级以上。对于f6～f8 这一类复杂的多峰函数，明显CS和CSA不论低维还是高维的求解的精度都不理想，即使在10维条件下，最高精度也没有超过1E+2，说明算法的全局开采能不足，存在不同程度的早熟收敛现象。

表4 30维实验结果分析

作为新型智能算法BOA，除了f5 和10 维的f6 其余函数在高维度和低维度问题均收敛到了10E-10 精度以上，明显相较于CSA和CS算法都表现出更强的寻优能。但是对比3个维度上BOA算法在求解某些函数，比如Rastigin、Griewank，可以发现收敛情况不稳定，均值的波动较大，说明函数维度的改变对该函数影响较大。

表5 50维实验结果分析

本文提出的MISCSA 算法不仅在简单的单峰函数的求解均值都相较于以上3种算法更高，大部分函数的精度远高出CS、CSA 算法10 个数量级以上，高出BOA算法7个数量级以上，而且在求解复杂的多峰函数时表现出了优秀的寻优能力，特别是具有大量按照正弦拐点排列的局部最优值的Rastigin 函数和Griewank 函数，MISCSA 算法分别在10、30 和50 维均搜索到了函数最优值。由此认为在位置更新中加入共享机制促使乌鸦群体快速向优良解区域移动，提高收敛速度。并且多段扰动策略的加入使MISCSA 在进化的过程中很大程度上保持种群多样性，避免陷入局部最优。其次，表3～5中的标准差也反映了算法在求解中的稳定性。算法CS、CSA 随着求解维度的增高，标准差值明显增加，说明两个算法在求解高维度问题时算法的稳定性较差。而MISCSA 算法相较于CS、CSA、BOA 都低，说明算法的稳定性更好。

在算法运行时间方面，明显PSO在不同的维度下以及不同测试函数的平均耗时都最少，CSA 第二，而MISCSA又要优于CS和BOA。MISCSA改进了原始算法位置更新公式，使个体加速向全局最优的位置靠近，因此也增加了算法的耗时。在不同迭代阶段加入扰动，也一定程度增加了耗时，但是在10 维下的平均耗时与CSA相比没有超过0.2 s，30维下没有超过0.5 s，而50维的搜索维度下也没有超过1 s，均是在可接受范围内。

实验2 CS、CSA、PSO、BOA 和MISCSA 的迭代曲线对比

为了更加直观地分析5 种算法在迭代过程中的寻优能力。记录下算法在30 维度下求解8 个函数的迭代曲线如图1～8 所示。迭代图的横纵坐标分别表示迭代次数和平均适应度值取对数（lg）。

图1 Sphere函数平均收敛曲线

图2 Schwefel2.22函数平均收敛曲线

图3 Schwefel2.2函数平均收敛曲线

图4 Schwefel2.21函数平均收敛曲线

图5 Quartic函数平均收敛曲线

图6 Rastigin函数平均收敛曲线

图7 Quartic函数平均收敛曲线

图8 Griewank函数平均收敛曲线

由图1～8可看出，原始CSA的曲线在寻优前期大概30 代左右相较CS 有较快速的下降，但是后期没能保持优势，收敛速度放缓，表现出算法后期的全局开采能力较弱的问题。BOA 作为全局性搜索算法与MISCSA 具有相似的收敛趋势，并且是除MISCSA外具有最好的收敛速度与精度。本文提出的MISCSA 在计算每一个函数的进化初期其个体质量就明显优于CS、CSA和BOA算法，随着迭代次数的增加，MISCSA 的曲线下降非常快，并且在迭代后期具有持续寻优的能力。图5～8 是多峰函数的平均收敛曲线，可以看出算法MISCSA具有良好的收敛速度与精度。对于Griewank 函数和Rastigin，PSCSA 在200 代以内搜索到函数的最优值0，并且在迭代过程中并没有出现明显的拐点。由此说明对于这一类的多峰函数，MISCSA 具有很强的搜索能力，可以快速跳出局部最优值束缚向全局最优点靠近。

实验3 统计检验

基于50次独立运行算法的平均值和标准差不会比较每次运行结果。Derrac 等在文献[15]中提出，对于改进进化算法性能的评估，仅基于平均值和标准偏差值来比较算法优劣不够严谨，应该进行统计检验。通过统计检验以证明所提出的改进算法比其他现有算法具有显著的改进优势。为了判断MISCSA 的每次结果是否在统计上显著地与其他算法的最佳结果不同，Wilcoxon统计检验在5%的显著性水平下进行。在表6中给出所有基准函数的MISCSA 和其他算法的Wilcoxon 秩和检验中计算的p-value。例如，如果最佳算法是MISCSA，则在MISCSA/CS、MISCSA/CSA 等之间进行成对比较。由于最佳算法无法与自身进行比较，因此，针对每个函数中的最佳算法标记为N/A，表示“不适用”。这意味着相应的算法可以在秩和检验中没有统计数据与自身进行比较。根据Derrac 等人的论文，那些p-value ＜0.05 的可以被认为是拒绝零假设的有力验证。

根据表6中的结果，因为BOA计算50维的f6 和10维的f8 也同时收敛到全局最小值0所以该统计检验不适用。其他的MISCSA的p-value 全部小于0.05，这表明该算法的优越性在统计上是显著的，即认为MISCSA算法比CS、CSA和BOA具有更高的收敛精度。

表6 Wilcoxon秩和检验的p 值

综上所示，基于多段干扰的共享型乌鸦算法对于大部分的基准函数具有良好的寻优结果，有效地解决了原始乌鸦算法收敛速度缓慢和在搜索后期易陷入局部最优问题，在没有增加太多运行时间以及编程步骤的情况下使乌鸦算法的收敛速度和搜索精度有较大的提升。

5 结束语

通过对原始乌鸦算法的原理和更新公式进行研究与分析，针对算法收敛速度缓慢以及后期的搜索精度低等问题，本文提出了MISCSA算法。MISCSA在位置更新公式中加入了共享机制，在单纯的随机性跟随行为中加入跟随全局最优位置的思想，达到了多样性与收敛性的共存；针对全局最优解在不同的迭代时期进行扰动，可以使算法扩大了种群的搜索范围，在迭代后期具有强大的跳出局部最优的能力。结合以上两点改进，使算法在全局搜索与局部搜索之间达到了平衡。文中的测试结果也表明了MISCSA 的寻优能力优于原始算法与其他算法。下一步工作中，将MISCSA算法应用于工程问题上，进一步地验证算法的有效性。