柯西变异和自适应权重优化的蝴蝶算法

高文欣，刘 升，肖子雅，于建芳

上海工程技术大学 管理学院，上海 201620

1 引言

群智能算法模拟自然界中动植物的行为，例如蚁群和蜂群，模仿它们的求偶行为、捕食行为、筑巢行为等。蚁群算法和粒子群算法是两种早期提出的算法，现如今又提出了许多新颖的算法比如象群游牧算法[1]、磷虾群算法[2]、蚁狮算法[3]、乌鸦搜索算法[4]、鸡群算法[5]等。群智能算法也用于一些问题的解决，例如，旅行商问题、无线传感器网络节点定位问题、支持向量机优化问题、投资组合优化问题等。

Sankalap Arora和Satvir Singh两位学者，通过观察蝴蝶觅食行为而受到启发，提出了一种新的群智能优化算法——蝴蝶优化算法（Butterfly Optimization Algorithm）[6]。该算法的主要思想是模拟蝴蝶的觅食和求偶行为实现对目标问题的求解。蝴蝶的行为可以描述为它们向食物源位置的合作运动。蝴蝶接收、感知和分析空气中的气味以确定食物源或配对伴侣的潜在方向。BOA算法模拟此行为在搜索空间中寻找最优解。与现有的一些元启发式算法相比，基本BOA操作简单、调整的参数少、鲁棒性好，并在工程实践的初步应用中取得了良好的效果。然而在求解较高维函数问题时，BOA具有与其他的群智能仿生算法类似的问题，即容易陷入局部最优值、收敛性差等缺陷。为了改进蝴蝶算法容易陷入局部最优和收敛性能差等问题，文献[7]提出了基于莱维飞行的蝴蝶优化算法，在全局位置更新和局部位置更新处引入莱维飞行策略，提高了算法的搜索能力；文献[8]提出了一种基于学习自动机机制的蝴蝶优化算法，引入学习自动机机制，加速了全局搜索的速度，达到真正的全局最优；文献[9]提出了一种基于感觉模态变化的蝴蝶优化算法，采用动态变化的感觉模态参数策略，改变了收敛精度，提高了收敛速度；文献[10]提出了一种混合人工蜂群算法的蝴蝶优化算法，克服了蝴蝶优化算法后期搜索能力不足，提高了算法的收敛速度。对于现存的BOA改进策略的研究，虽然在一定程度上改进了算法的寻优性能，但是一般的也只是针对蝴蝶优化中某一个更新策略进行改进或者是改变初始化种群的方式，并没有有效的改进全局寻优和局部寻优的盲目性。

基本的蝴蝶优化算法存在着依赖初始种群、收敛精度低和易陷入局部最优等问题，针对这些问题本文提出了一种多策略改进的蝴蝶优化算法。利用柯西分布函数对蝴蝶的全局位置更新进行变异，提升算法的全局搜索能力，在蝴蝶算法的局部位置更新处引入自适应惯性权重因子，改进了算法的局部开采能力，并且使用动态切换概率来平衡局部搜索和全局搜索的比重，提高了寻优性能。通过14个基准测试函数测试，结果表明改进算法具有更高的收敛精度和鲁棒性。

2 蝴蝶优化算法

在自然界之中，蝴蝶可以使用它们的各种感官如：嗅觉、视觉、味觉、触觉和听觉去寻找食物和求偶，这些感觉能够帮助它们迁徙、躲避狩猎者以及帮助它们找到合适的地方产卵。在所有的感觉中最重要的是嗅觉，嗅觉能够帮助蝴蝶寻找食物（花蜜），即使在很远的地方也不例外。为了能够找到食物，蝴蝶使用感觉受体用于嗅觉，这些受体分散在蝴蝶的身体部位，如触角、腿和手掌等。这些受体实际上是蝴蝶身体表面的神经细胞，被称为化学感受器。这些化学感受器引导蝴蝶找到最佳的交配伙伴，以便继续强大的遗传系统。雄性蝴蝶能够通过信息素来识别雌性，这是雌性蝴蝶发出的气味分泌物引起特异性反应。

蝴蝶会产生一些强度与其适应性相关的香味，即当蝴蝶从一个位置移动到另一个位置时，它的适应性会相应地变化，香味会在远处传播，其他蝴蝶个体能够感知它，这就是蝴蝶个体如何与其他蝴蝶共享个体信息，形成一个群体的社会知识网络。当一只蝴蝶能够闻到来自其他的蝴蝶分泌的香味的时候，它将会朝着香味最浓的方向移动，该阶段在算法中被称为全局搜索。在另一种情况下，当蝴蝶不能从周围感知香味时它将随机移动，这一阶段是局部搜索阶段。

针对上述行为，提出如下假设：

（1）所有的蝴蝶都应该散发一些香味，使蝴蝶能够相互吸引。

（2）每只蝴蝶都会随机移动或向发出最多香味的蝴蝶移动。

（3）蝴蝶的刺激强度受目标函数的影响或决定。

（4）全局搜索和局部搜索使用切换概率 p来控制，受到物理接近度以及风、雨、雷、电等各种其他自然因素，局部搜索和全局搜索中的切换概率p具有重要意义。

在BOA算法中，每一只蝴蝶有它自己独特的感觉和个体感知能力。这同时也是区分于其他元启发式算法的一个主要特征。蝴蝶个体产生的香味数学公式如下：

其中，f是香味的感知强度，即香味被其他蝴蝶感知的强度，c是感觉模态，I是刺激强度，a是依赖于模态的幂指数，它解释了不同程度的吸收。本文在[0，1]范围内取a，参数a是取决于模态的功率指数（在此为香味），这意味着它表征吸收的变化。

在每次迭代中，搜索空间中的所有蝴蝶移动到新位置，然后评价它们的适应值。该算法首先计算解空间中不同位置上所有蝴蝶的适应度值。然后这些蝴蝶将通过计算公式（1）在它们的位置产生香味。在全局搜索阶段，蝴蝶朝着最优的蝴蝶(g*)移动，它可以用公式（2）表示：

算法1基本蝴蝶算法

输入：目标函数 f(x)，蝴蝶群体的规模N，刺激浓度I，感觉模态c，幂指数a的初始值，全局更新和局部更新的转换概率p，最大迭代次数MaxIter

1.初始化种群

2.Whilet

3. fori=1∶N

4. 计算每只蝴蝶的香味浓度

5. end for

6. 找到最优蝴蝶个体g*

7. fori=1∶N

8. 随机产生[0，1]之间的随机数r

9. ifrand>p

10． 进行全局位置更新，按照公式（2）进行计算

11. else

12. 进行局部随机游走，按照公式（3）进行计算

13. end if

15. end for

16. 更新a的值

17.end while

输出：全局最优解

3 蝴蝶优化算法的改进

为了改进蝴蝶算法容易陷入局部最优和收敛精度低的问题，本文从三个方面对蝴蝶算法进行改进。首先通过引入柯西分布函数的方法对全局搜索的蝴蝶位置信息进行变异，提高蝴蝶的全局搜索能力；其次通过引入自适应权重因子来提高蝴蝶的局部搜索能力；最后采用动态切换概率p平衡算法局部搜索和全局搜索的比重，提升了算法的寻优性能。因此本文提出一种混合策略改进的蝴蝶优化算法（CWBOA）。

3.1 柯西变异

针对蝴蝶优化算法易陷入局部最优的特点，利用柯西变异来增加种群的多样性，提高算法的全局搜索能力，增加搜索空间。柯西分布函数在原点处的峰值较小但在两端的分布比较长，利用柯西变异能够在当前变异的蝴蝶个体附近生成更大的扰动从而使得柯西分布函数的范围比较广[11]，采用柯西变异两端分布更容易跳出局部最优值。本文融入柯西算子，充分利用柯西分布函数两端变异的效果来优化算全局最优个体，使得算法能够更好地达到全局最优。标准柯西分布函数公式如下：

柯西分布函数从峰值向两侧下降相对平缓，蝴蝶个体受局部的极值点约束力在进行柯西变异后下降，并且柯西分布函数的峰值相对较小，蝴蝶个体在变异后会使用相对较少的时间来搜索相邻区间，把更多的时间放在搜寻全局最优值上，使得改进的蝴蝶优化算法在寻找全局的最优值方面具备很好的调节能力。用柯西变异进行随机扰动有利于增加种群的多样性从而避免算法陷入局部最优，提高全局搜索最优值的能力。柯西分布的特征使其能够产生与原点相距较远的随机数，这意味着经过柯西变异后的蝴蝶个体具备了能够迅速逃离局部极值的能力。另外，柯西分布函数的峰值较低，该特点能够缩短变异后的蝴蝶个体在邻域周围搜索的时间。因此在求得当前最优解后，本文使用公式（5）所示的更新公式对当前全局最优解进行变异处理。

3.2 自适应权重

惯性权重因子是很重要的一个参数，当惯性权重比较大时，算法全局搜索能力较强，能够增加种群多样性，可以搜索较大的区域；当惯性权重比较小时，算法局部搜索能力较强，可以在最优解周围精细搜索，加快收敛速度。蝴蝶进行局部寻优时，是以公式（3）进行局部搜索的，其中当蝴蝶以公式（3）向局部最优解靠近时，这时只能靠近局部最优解，而不能进行更好的局部寻优[12]，针对这个问题受文献[13]、文献[14]的启发，提出了新的自适应权重方法，蝴蝶接近食物的时候，采用较小的自适应权重改变此时最优的蝴蝶的位置，使得蝴蝶局部寻优能力得到提高。自适应权重公式如式（6）所示：

式（6）中，t为当前迭代次数，itmax是最大迭代次数。

改进式（3）的公式如（7）所示：

通过融合自适应权重因子w，使蝴蝶个体具有更好的局部寻优能力，改进后的蝴蝶算法流程图如图1所示。

3.3 动态切换概率策略

在基本蝴蝶优化算法中，局部搜索和全局寻优过程用常量切换概率 p∈[0,1]来控制，一个合理的搜索过程在算法的前期应该进行较强烈的全局搜索，迅速定位搜索空间中全局最优解所在范围，在探索后期局部开采能力应增强，以提升算法的寻优精度。本文引入动态切换概率来平衡局部开采和全局开采的比重，来实现更好的寻优策略。动态切换概率p的公式如下：

3.4 算法描述

CWBOA的具体执行步骤如下：

图1 改进算法的流程图

步骤1初始化种群及各个参数设置。

步骤2计算每只蝴蝶的香味浓度，得到每个个体的适应度值，并且求出当前最优解。

步骤3若动态转换概率p>rand，则按照式（2）、（5）对全局位置进行更新。

步骤4若动态转换概率p

步骤5越界处理。

步骤6计算步骤4和步骤5的函数适应度值，若得到新的函数适应度值，则更新全局最优适应度值和全局最优解。

步骤7判断结束条件，如果满足，则退出程序，输出最优值及最优解，否则转步骤3。

3.5 改进算法（CWBOA）的时间复杂度分析

设蝴蝶群体的规模为N，迭代次数为MaxIter，维度为D，则根据CWBOA算法的描述和时间复杂度符号O的运算规则，随机初始化种群的时间复杂度为O(N⋅D)，以及找到当前最香的蝴蝶的时间的复杂度O(N⋅D)，利用柯西分布函数对于全局位置更新进行变异的时间复杂度为O(D)，引入惯性权重因子对局部位置更新的时间复杂度为O(MaxIter⋅D⋅N)，CWBOA算法的总的时间复杂度为O(D⋅N⋅MaxIter)，所以CWBOA的时间复杂度与BOA相同，并没有增加计算负担。

4 函数测试与结果分析

4.1 仿真实验环境

本仿真测试环境为：操作系统Windows 7，CPU为Intel®Core™ i5-4210U，主频1.7 GHz，内存为4 GB，仿真软件为Matlab2018b。

4.2 实验的初始参数设置

本文选取了基于柯西变异和动态自适应权重的蝴蝶优化算法（CWBOA）、基本蝴蝶算法（BOA）、鲸鱼算法（WOA）[15]，以及花授粉算法（FPA）[16]进行对比。为了实验的公平、客观性，本文将所有算法的初始种群规模统一设为30，迭代次数设置为500，四个算法的共有参数保持一致。CWBOA和BOA中的c感官形态设置为0.01，a幂指数在迭代过程从0.1迭代到0.3；基本的BOA和FPA中的切换概率均为p=0.8。

4.3 测试函数

为了验证改进后的BOA在收敛性和鲁棒性两方面的性能上更优，本文基于14个测试函数进行对比实验，标准测试函数的信息见表1。

4.4 实验结果与分析

为了验证本文中改进CWBOA算法具有更好的收敛性和稳定性，本文用14个基准测试函数进行了验证，为了避免由于偶然的因素带来的结果的偏差，每个算法在每个测试函数上面独立运行30次。表2将给CWBOA、BOA、BA、FPA四个算法在多个测试函数上通过独立运行30次后所得到的实验结果。

表2分别列出了CWBOA、BOA、WOA、FPA算法独立运行30次所得到的最优值、最差值、平均值和标准差。很容易看出对于所选测试函数，CWBOA的寻优性能最强，明显优于BOA、WOA、FPA。函数f1、f5、f6、f7、f8、f9、f12、f13、f14可以直接搜索到最优值0，寻优效果可以达到100%；对于函数f4，CWBOA的寻优平均值和基本花授粉算的寻优性能差不多，略优于基本BOA；对于函数f11，CWBOA的寻优精度平均值达到了8.881 8E−16的水平，比基本的蝴蝶优化算法提高了7个精度，算法整体的稳定性比较好；对于函数f13，CWBOA、BOA、WOA均最优值均为0，但是在稳定性上面，CWBOA的寻优性能要远远优于BOA和WOA，而FPA的寻优效果都是比较差的，可见改进后算法的性能具有明显的竞争优势。

为了直观展示CWBOA的寻优性能，本文选取了7个基准测试函数的收敛迭代曲线图。这里仅给出f1、f3、f7、f9、f11、f12、f14的函数图像。如图2所示。

由函数的收敛曲线可知，改进的CWBOA在收敛的速度上要优于BOA、WOA、FPA。f1是单峰函数，比较容易达到最优值，因此常常用来测试收敛能力，由函数的收敛曲线图可以直观地看出改进后的算法CWBOA的收敛精度较高，克服了基本的BOA寻优精度不高的问题。f7和f14是两个低维测试函数，由收敛曲线图可知在迭代过程中有多个拐点出现，证明改进后的算法容易跳出局部最优并且以较快的速度收敛到最优值，f11函数是一种很难找到全局最优值的爬山形态的多模态函数，对比基本BOA算法，改进后的蝴蝶优化算法提高了7个数量级的寻优精度。f12是一个复杂的多峰函数有许多广泛的局部最小值，并且它们是有规律地分布的，在（0，0）处取得最优值0，CWBOA在不到50代已经达到最优值而且寻优速度也远远快于BOA、WOA和FPA，由收敛曲线图可以知，CWBOA的收敛性要优于基本的BOA、WOA、FPA。

表1 测试函数的基本信息

表2 测试函数实验结果

另外，本文的改进算法与文献[7]中的BA、文献[8]中的LBOA、文献[9]中的IBOA分别进行比较，每个算法的初始化种群数均为30，其中BA和LABOA的最大迭代次数为1 000，CWBOA和IBOA的最大迭代次数为500，均参考原文献实验参数设置，本文设置最大迭代次数为500次的实验结果已经明显优于文献[7-9]中的对比算法的实验结果了。根据实验结果可知本文改进算法的寻优效果更佳。对比结果如表3所示。“—”表示原文献的实验中不涉及的测试函数。

图2 函数的收敛曲线

4.5 求解高维函数的实验分析

根据上述低维实验结果对比分析可知，本文的改进算法在低维测试函数上无论在最优值还是标准差上面均得到了较好的收敛效果。但是一般的改进策略在较为复杂的工程问题上面，特别是高维测试函数上极易失效，为了测试本文改进算法的有效性，进行了CWBOA的高维函数优化求解实验，因为在实际的问题中普遍存在的是大规模的、复杂的优化问题。为了更好地证明本文改进算法能够应用于求解大规模复杂问题，高维参数设置与4.2节相同。

表3 改进算法的实验结果对比

根据表4的实验结果，发现CWBOA求解高维函数上面的效果比较好，但是在解决100维、500维的f3函数的时候失效。f3是连续的，平滑的多峰函数，当自变量趋近于无穷大时，函数会形成大量局部极值区域，易陷入局部最优且不易跳出，在高维测试函数下求解难度较大，在测试函数维数大于100维时，就属于大规模函数优化问题。随着搜索空间维数的增加，问题的复杂度以及指数级数的增长，从而出现“维数灾难”问题[17]，根据无万能算法理论，没有任何一个算法适合解决所有问题，所以这个结果是可以接受的。函数f1、f5～f9、f12、f13均能达到最优值0，所以在求解高维测试函数时，本文的改进策略依然具有较强的稳定性，能够有效地处理复杂的高维问题。选取本文的测试函数f1、f4、f6、f10、f11测试结果与文献[18]中的对立学习策略的鲸鱼优化算法（IWOA）在500维的情况下的结果进行对比（实验结果如表5所示）。函数f1、f6这两个测试函数的结果始终能精确达到最优值0，寻优效果能达到100%，说明CWBOA在处理复杂的大规模问题上鲁棒性较强；对于函数f4和f11，CWBOA的寻优精度略优于IWOA，但是标准差始终稳定在0，表明其较强的寻优稳定性，对于函数f10，本文的改进算法要比IWOA的寻优精度提高近70个单位。综上，能够证明本文改进算法的可行性和有效性。

表5 CWBOA与IWOA对比结果

5 结束语

本文提出了一种混合策略的蝴蝶优化算法（CWBOA），在全局位置更新后的值引入柯西变异算子，增加了种群多样性，降低算法陷入局部最优的可能性；在BOA局部位置更新中引入自适应权重因子，提高了算法的局部搜索能力，并且采用动态切换概率p来权衡局部开采和全局搜索的比重，基于三种改进策略提升了算法的寻优能力和鲁棒性。接下来的研究方向主要是拓展改进算法的实际应用领域。

表4 CWBOA的高维函数求解结果