肖海军，王芬艳，卢常景，曹 颖

(中国地质大学 数学与物理学院，武汉430074)

群智能优化算法是近年来兴起的一种概率搜索式算法,相比于线性规划[1]、动态规划[2]和混合规划[3]等传统优化算法，它具有以下4种特征：(1)相互作用的个体分布在群体中；(2)所有个体都能感知当前信息；(3)模型易于扩展；(4)具有自组织性,其基本理论是模拟生物群体之间的相互交流与合作，根据简单有限的个体行为与智能，通过群体作用形成不可估量的整体效应,由于具有良好的直观性和实用性，研究者们相继提出了蚁群优化算法(Ant Colony Optimization，ACO)[4]、混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)[5]、蝙蝠算法(Bat Algorithm，BA)[6]等优化算法，现在这些算法已经广泛地应用于工程中解决实际问题.

2016年，Meng等人受到鸟类群智能的启发，提出了一种全新的群智能优化算法——鸟群算法(Bird Swarm Algorithm，BSA)[7],鸟群算法是在基于鸟类社会行为和社交互动的基础上，模拟其三种社会行为：觅食行为、警戒行为与飞行行为而来.相比于粒子群算法和差分进化算法等传统优化算法，鸟群算法不仅遗传了寻优速度快、变异性强等优点，更具有自身独特的特点,由于鸟群算法存在四条灵活的搜索路线，并且可以自由调整，其在寻优的过程中能更好地平衡高效性与准确性,由于该算法提出的时间较短，研究的文献较少，目前主要的研究方向可分为两个方面：算法的改进和应用.在算法改进方面，2016年，刘晓龙等人[8]在鸟群算法中引入了一种辅助搜索策略，即莱维飞行，在鸟群飞行位置更新时采用这一方式，从而有效地提升了算法性能.在算法应用方面，2016年，崔东波等人[9]提出了一种改进的鸟群算法，并成功应用于梯级水库群模型优化中.目前，由于关于鸟群算法的研究非常有限，还存在较大的研究和改进空间.如何有效地提高鸟群算法的优化性能，使得其在搜索和开发过程中保持更好的平衡将会是以后研究的重点.

在对鸟群算法进行研究的过程中，发现鸟群算法在优化一些高维多峰问题时会陷入到局部极值中，且鸟群算法的仿生过程也仍有一些不合理之处.本文提出了一种有效的多峰优化鸟群算法(Multi-peak Optimized Bird Swarm Algorithm，MOBSA)，其主要是将莱维飞行引入到鸟群空间位置初始化和位置更新中，并通过调整鸟类身份的分类策略来对标准鸟群算法进行改进.多峰优化鸟群算法既能使得鸟群算法的仿生过程变得更加科学，还能得到比鸟群算法更好的优化结果.通过基于18个基准优化问题的仿真实验和比较证明了多峰优化鸟群算法相比于粒子群优化算法(Particle Swarm Optimization，PSO)和差分进化算法具有更好的准确性与稳定性.

1 鸟群算法

1.1 鸟群算法的数学模型

由于群居生活会产生生存优势，每个个体都能从中受益，因此很多鸟类都是群体的，以达到良好的觅食效率和最优的生存环境.通过最简单的社会互动，群体行为可以发展为复杂的相互作用，鸟群算法就是在基于这些群体社会行为的基础发展而来.

觅食行为：每只鸟在寻找食物时都会依靠自身经验和群体经验.因此，假设(2)可以描述为

(1)

其中j∈{1,2,…，D},rand(0,1)是产生一个(0,1)间均匀分数的随机数,U和V是两个人为定义的正数,pi,j表示当前第i只鸟在j维的最优位置，gj表示当前鸟群在j维的最优位置.

警戒行为：对于假设(3)，群体位置更新方法可以描述为

(2)

(3)

(4)

其中k∈{1,2,…，N}且k≠i,α1∈(0,2),α2∈(0,2).Fiti是当前时刻第i只鸟最优适应度值，AllFit是当前时刻所有鸟个体最优适应度值的总值,ε是计算机程序中的最小常数，用于避免出现零除法错误,meanj是群体处于j维的平均位置.

飞行行为：根据假设(4)，可以从鸟群中区分出生产者和乞讨者，其位置更新方法可以描述为

(5)

(6)

其中k∈{1,2,…，N}且k≠i,randn(0,1)表示随机生成一个服从(0,1)分布的高斯分布值,S(S∈(0,2))是乞讨者跟随生产者寻找食物的一个常数,此外，假设鸟群以Q为时间频率迁徙地点且Q为正整数[7].

1.2 鸟群算法的基本步骤

根据以上描述的数学模型和计算方法，鸟群算法的基本步骤可以归纳如下：

步骤2 由适应度函数分别计算得出每只鸟所处位置的适应度值，得到当前个体最优位置和群体最优位置.

步骤3 判断Q除t是否能整除,若整除，则进行步骤4；若有余数，则进行步骤5.

步骤4 将鸟群所有个体区分为乞讨者和生产者,对生产者采用公式(5)进行位置更新，对乞讨者采用公式(6)进行位置更新,结束后转至步骤6.

步骤5 判别每只鸟在觅食还是警戒,对每只鸟，随机生成一个服从(0,1) 均匀分布的数值，如果觅食概率P大于该数值，那么判别该鸟处于觅食状态，采用公式(1)进行位置更新；不然判别该鸟处于警戒状态，采用公式(2)进行位置更新,结束后转至步骤6.

步骤6 根据适应度函数计算所有鸟个体的适应度值，然后更新当前个体最优位置和群体最优位置.

步骤7 判断t是否小于M,若是，则令t=t+1，转至步骤3；若否，则迭代结束，转至步骤8.

步骤8 输出群体最优位置和对应的最佳适应度值[7].

1.3 鸟群算法存在的问题

根据鸟群算法基本优化原理及其实际优化问题中的性能表现，可以发现其仍然存在着一些不足，可以总结为：

(1)鸟群算法在处理多极值优化问题时容易出现早熟情况和陷入局部最优.标准鸟群算法性能测试实验显示，相对于粒子群算法和差分进化算法，鸟群算法在处理单峰问题时具有明显优势，但在处理一些多峰优化问题时同样会陷入局部极值，优化结果甚至可能会更差.

(2)鸟群算法仿生过程与实际存在着一些差异，没有完美的体现生物群智能.标准鸟群算法将鸟群个体区分为生产者和乞讨者，食物储量最高者为生产者，食物储量最低者为乞讨者，而食物储量介于这两者之间的鸟则随机选择身份.综合分析可知，如果规定食物储量更高的鸟更可能是生产者，而食物储量低的鸟更可能是乞讨者的话将更加科学.

(3)参数配置的合理性对优化结果影响非常大.比如飞行频率这一参数的变化，将会完全改变鸟群算法的迭代寻优路径，从而影响到最终结果.Meng等人也指出鸟群算法中的参数设置需要进行统一分析，如果单独进行参数研究可能会没有效果.

2 一种有效的多峰优化算法

2.1 莱维飞行

莱维飞行是一类非高斯随机过程，其随机行走过程服从莱维分布[10].有研究显示，信天翁、布谷鸟等鸟类生活习性都适用于莱维飞行.因此，近年来许多优化算法中都引入了莱维飞行，如2010年Yang等人利用莱维飞行优化了布谷鸟搜索算法[11].2014年Hakl等人在粒子群优化算法中融合了莱维飞行[12].2016年Sharma等人提出了一种基于莱维飞行的人工蜂群优化算法[13].在引入莱维飞行后，这些优化算法性能都得到了有效提升.

莱维飞行是按随机步长进行的一种游走，其具有一定概率分布特性,随机步长可以表示为

L(s)～|s|-1-β,0<β≤2,

(7)

其中β为指数变量，s为随机步长.

由于实现莱维飞行过于复杂，本文采用了Yang提出的Mantegna算法[14]来模拟产生随机步长.在Mantegna算法中，随机步长s的计算可通过

(8)

其中β一般取1.5，u和β都服从于正态分布

(9)

(10)

当|s|≥|s0|，s0为设定的最小步长，这种分布将符合莱维分布,Γ(·)为伽玛函数，其计算可通过

(11)

为了验证莱维飞行与随机行走的性能，本文进行了一个简单的MATLAB仿真对比实验，在两种游走都设置为200步的情况下，最终结果如图1所示.

图1 两种游走的位置分布Fig.1 Distribution of two kinds of walks

由图1可知，随机游走产生的位置相对来说比较集中，而利用莱维飞行可以产生更广的位置分布范围.因此，在优化算法中引入莱维飞行，会增强算法的区域搜索能力和跳出局部极值的能力，从而提升算法优化性能.

2.2 多峰优化鸟群算法(MOBSA)

根据标准鸟群算法存在的问题，本文提出的多峰优化鸟群算法主要在以下3个方面对鸟群算法进行改进：

(1)将莱维飞行引入到鸟群空间位置初始化中，以增强算法初期位置分布的多样性,位置初始化公式可以表示为

(12)

(2)当鸟群群体最优位置迭代6次还未进化时，则对鸟群飞行行为采用莱维飞行更新位置，以增强算法跳出局部极值的能力,那么公式(5)将变为

(13)

(3)调整鸟类身份的分类策略.标准鸟群算法将鸟群个体区分为生产者和乞讨者，食物储量最高者为生产者，食物储量最低者为乞讨者，而食物储量介于这两者之间的鸟个体则随机选择身份.本文认为，如果将食物储量高者设定为具有更大概率成为生产者，而食物储量低者更可能成为乞讨者更为科学.因此，本文根据鸟类食物储量高低的不同，设定了一组介于[0,1]之间大小不同的Pi,如果对第i只鸟，[0,1]间随机生成的数值大于Pi，则该鸟定义为生产者，否则为乞讨者.这种更加科学化的设置，增强了算法仿生智能，使算法更为灵活.

2.3 算法流程图

根据多峰优化鸟群算法(MOBSA)的具体流程绘制出图2.

图2多峰优化鸟群算法(MOBSA)流程图Fig.2 Multi-peak Optimized Bird Swarm Algorithm(MOBSA) flow chart

3 仿真实验

3.1 测试函数

如表1所示，表中列出了所选取的函数表达式，取值范围及最优解.在6个测试函数中，F1、F2、F3为单峰函数，主要用于测试算法优化精度，F4、F5、F6为多峰函数，主要用于评估算法跳出局部极值的能力.本文将在测试函数维度D为30的情况下进行实验.

表1 测试函数

3.2 实验环境与参数设置

所有实验均在统一的环境中进行，实验环境为：Intel i5奔腾双核处理器，2.5GHz，2G运行内存，Win7操作系统，MATLAB R2014a.此外，3种算法的关键参数，如最大迭代次数、种群规模等都保持一致，相关参数设置可见表2.

3.3 实验结果与对比

对于选定的6个测试函数，每种算法都分别进行了10次实验，实验结果包括均值、最优值、最差值和标准差，3种算法在维度为30的最终优化结果见表3.

表2 算法参数设置Tab.2 Algorithm parameter settings

表3 维度为30时优化结果对比Tab.3 Comparison of optimization results when the dimension is 30

结论1：MOBSA与BSA在优化单峰函数时性能明显优于PSO算法，且MOBSA相对于BSA能有效地提高寻优精度.事实上，由表3可知，对于F1和F2这2个单峰函数，PSO算法在30维上都陷入到了局部最优，而MOBSA与BSA在30维上的平均优化结果最终都接近于0.值得注意地是，MOBSA的平均优化结果要好于BSA几个数量级,对于F3这个单峰函数，虽然在维度为30的PSO算法偶尔能优化到0，但是其大多数时候还是会陷入到局部最优.相比之下，MOBSA与BSA在优化F3函数时结果能一直稳定在0.

结论2：当优化多峰函数时，MOBSA能有效跳出部分局部极值，从而提升鸟群算法优化性能.事实上，以F4和F5这2个多峰函数为例，由于极值众多且分布复杂，大多数优化算法都会陷入到局部极值中，MOBSA、BSA与PSO算法也都未能幸免.在30维上，PSO算法的平均优化结果偏离最优解都非常大，MOBSA与BSA的平均优化结果虽然也有一定偏离，但相比之下已经足够优异.当然，相对于BSA的平均优化结果，MOBSA的平均优化结果也会有一定程度的提升.但是，从标准差来看，MOBSA优化效果的稳定性会不如BSA.F6作为一个简单的多峰函数，MOBSA与BSA优化时在维度为30时都能稳定地寻找到最优解0，而PSO算法却仍然陷入到了局部极值.

综上可知，不管在优化单峰函数还是多峰函数时，多峰优化鸟群算法都能实现优化性能的提升,这主要源于多峰优化鸟群算法增强了算法初期位置分布的多样性，从而扩大了寻优空间，此外莱维飞行模式在位置更新上的引入也加强了算法跳出局部极值的能力.不过跳跃能力的增强也带来了一定的局限性，它造成算法的稳定性下降，这种缺陷在复杂多峰函数上会更明显.

4 结语

本文主要介绍了一种有效的多峰优化鸟群算法(MOBSA)，并进行了MATLAB仿真对比实验来说明改进鸟群算法的优越性.首先具体介绍了标准鸟群算法，包括算法数学模型、算法基本原理及算法存在的缺陷.随后，针对鸟群算法存在的缺陷，提出了改进方法，那就是将莱维飞行引入到算法中，用于初始位置的生成和飞行位置的更新，同时对算法仿真过程进行了一些调整.为了测试MOBSA的性能，以标准BSA和PSO作为对比算法，选取了3个单峰函数和3个优化函数，并设置维度为30进行实验.实验结果表明，MOBSA与 BSA在所有函数上的性能都会优于PSO算法.相对于BSA，MOBSA在单峰函数上能有效提高优化精度，在多峰函数上也能跳出部分极值，得到比BSA更好的优化结果.因此，MOBSA实现了鸟群算法性能的提升，是一种有效地智能优化算法.虽然本文提出的多峰优化鸟群算法达到了鸟群算法优化性能的提升，但是鸟群算法的改进方法不仅限于此.未来关于鸟群算法的改进可以集中于杂交其他元启发式算法或优化算法.另外，引入多群思想也是可以考虑的一个方向.