基于莱维飞行的鸟群优化算法

刘晓龙，宁 芊，赵成萍， 涂 榫

(四川大学 电子信息学院，成都 610065)

基于莱维飞行的鸟群优化算法

刘晓龙，宁 芊，赵成萍， 涂 榫

(四川大学 电子信息学院，成都 610065)

针对鸟群优化算法(BSA)在求解高维多极值优化问题时容易陷入局部最优解和出现早熟收敛的情况，在原始鸟群算法的基础上，在模拟鸟群飞行行为的过程中引入莱维飞行，提出了一种基于莱维飞行的改进算法——莱维-鸟群算法(LBSA);这种算法替换了原算法中随机的飞行位置跳变，而采用莱维飞行更新鸟群飞行后的位置，大幅提高了鸟群的位置变化活力，提高了算法的有效性;仿真结果表明，在求解高维多极值优化问题时，该算法性能优于原始鸟群算法。

鸟群算法；莱维飞行；高维；多极值

0 引言

最优化问题是当今社会各领域应用十分广泛的一类问题，如空间最优化、时间最优化、分类最优化等。有些最优化问题非常复杂，难以在可接受的时间内获取有效解，如非凸的或不可微的问题。为了解决这些复杂问题，近年来人们模仿自然进化和生物系统，提出了大量群体智能优化算法[1]，如遗传算法(GA)[2]、微分进化算法(DE)[3]、粒子群算法(PSO)[4]、人工鱼群算法(AFSA)[5]、布谷鸟搜索算法(CS)[6]、蝙蝠算法(BA)[7]、鸡群算法(CSO)[8]等。这些算法为求解大量存在于计算科学、工程科学、管理科学等领域的全局最优化问题提供了有效的途径。

鸟群算法(bird swarm algorithm，BSA)是由Xian-Bing Meng等[9]于2015年提出的一种基于鸟群智慧和鸟群行为的群体智能优化算法。通过文中的测试表明，鸟群算法在解决多领域的最优化问题时的性能明显优于粒子群算法和微分进化算法，但也发现在解决部分高维多极值问题时仍存在容易陷入局部最优解和早熟收敛的问题。对此，根据作者Xian-Bing Meng等提出的几种算法改进意见对原始鸟群算法进行改进，通过动态调整鸟群飞行频率FQ以提高收敛性能，以及在鸟群的飞行行为中引入莱维飞行以改善种群寻优的灵活性，大幅提升算法跳出局部最优解的能力。这种改进的鸟群算法，称之为莱维-鸟群算法(levy bird swarm algorithm，LBSA)。

1 鸟群算法

鸟群算法是对鸟群群体行为和群体互动的简化，它模仿的是鸟群的觅食行为、警戒行为和飞行行为，并用这种群体智慧解决最优化问题。鸟群算法可以被如下规则简化描述：

1)鸟群中的每只鸟可以在警戒行为和觅食行为之间切换，鸟类是否觅食或是保持警戒是一个随机决策模型。

2)觅食的时候，每只鸟可以迅速记录和更新个体和群体之前最好的觅食经验，这个经验也将用于觅食，群体信息将即刻共享于整个鸟群。

3)保持警戒的时候，每只鸟都将试图向群体中心靠近。这种行为会被群体竞争诱发的冲突所影响。而具有较高食物储量的鸟类更倾向于躲起来向群体中心靠近。

4)鸟类可以周期性地向其他位置移动。当移动到另一个位置时，鸟类一般要在生产者和乞讨者之间做出选择。具有最高食物储量的鸟将成为生产者，而具有最低食物储量的鸟将成为乞讨者。其他食物储量在最高和最低之间的鸟将随机选择成为生产者或者是乞讨者。

5)生产者积极寻觅食物，乞讨者随机跟随一个生产者寻找食物。

假设有N只鸟在D维空间中飞行觅食，第i只鸟在t时刻的位置描述为：

规则1可以被表述为一个随机的决策。每一只鸟的决策依赖于一个[0，1]之间的均匀随机数，同时设定一个[0，1]之间的常量P，当随机数小于P时，该鸟将进行觅食，否则，继续保持警戒。

基于规则2，鸟群的觅食行为遵从每只鸟自身的经验以及种群经验，觅食行为的位置更新公式为：

(1)

式中，j∈[1,…,D]，rand(0,1)表示在[0，1]范围内独立均匀分布的随机数。C和S是两个正数，分别称为感知系数和社会加速系数。Pi,j表示第i只鸟早先的最佳位置，gj表示群体共享的早先最佳位置。

基于规则3，鸟群保持警戒的时候将尝试向种群的中心移动，并伴随着与同类的竞争，因而不能直接向种群中心移动，警戒行为的位置更新公式为：

(2)

(3)

(4)

式中，k(k≠i)是一个[1，N]之间的随机正整数。a1和a2是两个[0，2]之间的常量，pFiti表示第i只鸟的最佳适应度值，sumFit表示整个种群的最佳适应度值之和。ε是为了避免零因子错误而使用的由计算机产生的最小正常量。meanj表示整个种群平均位置的第j个元素。A1描述的是一只鸟向鸟群中心移动过程中由环境引发的间接作用，而A2描述的则是由某个具体冲突而引发的直接作用。

基于规则4和规则5，鸟类会因逃避捕食等原因变动飞行中的位置，每当其飞行到一个新的位置，将在生产者和乞讨者之间做出选择，自行觅食或者跟随生产者获取食物，飞行行为中生产者和乞讨者的位置更新公式分别为：

(5)

(6)

式中，randn(0,1)表示均值为0，标准差为1的高斯随机分布，FL∈[0,2]代表乞讨者跟随生产者寻找食物。鸟群的飞行移动间隔为FQ，FQ是一个正整数。

2 莱维飞行

莱维分布是法国数学家莱维(Lévy)于20世纪30年代提出的一种概率分布，而莱维飞行是服从莱维分布的随机搜索路径，这是一种短距离搜索与偶尔长距离搜索相间的随机行走模式[10]。经过大量的研究，莱维飞行符合蜜蜂、信天翁等多种自然界生物的行为轨迹[11]，并可以解释许多自然界的随机现象，如布朗运动等。

近年来，莱维飞行被大量引入优化领域，如Yan Xinshe等利用莱维飞行改进布谷鸟算法[12]，Wang Qingxi等利用莱维飞行改进粒子群算法[13]。莱维飞行的引入，增强了种群的多样性，扩大了搜索的范围，更容易跳出局部最优点[14]，有效增强了算法的寻优能力。

莱维飞行的实质是一种随机步长，其位置更新公式为：

⊕Levy(λ)

(7)

式中，i∈[1,…,N]，代表步长控制量，Levy(λ)为随机搜索路径，⊕为点对点乘法。并满足莱维分布：

Levy～u=t-λ,1<λ≤3

(8)

由于莱维飞行十分复杂，目前大多使用Mantegna算法模拟，数学表达式表示如下。

步长s计算公式：

(9)

其中:μ,υ满足正态分布：

(10)

(11)

(12)

各式中的β通常取常量1.5。

为了证明莱维飞行的优越性，在Matlab中分别对莱维飞行和随机行走进行了模拟仿真，步长均为200步，结果如图1所示。

图1 莱维飞行和随机行走对比图

从图1可以看出，莱维飞行具有更大的搜索范围和更强的搜索能力，而随机行走则搜索范围相对集中。因而，将莱维飞行引入鸟群算法的飞行规则中，将使鸟群算法具有更强的跳跃能力，特别是提高算法跳出局部最优点的能力，从而有效提高算法的全局寻优能力。

3 基于莱维飞行的鸟群优化算法

3.1 算法改进

莱维-鸟群优化算法在原有的鸟群算法基础上做出了3个方面的改进：

3.1.1 在鸟群的飞行行为中引入莱维飞行进行位置更新，公式5由以下公式替换：

⊕Levy(β)

(13)

Levy(β)由式(9)计算得出。由于式(12)中含有Γ积分运算，因而莱维飞行的引入将大大增加整个算法的运算开销。为节约开销，β常常取定值1.5，则σμ运算的结果也为常量0.696 6。式(13)可以简化为：

(14)

s(μ,υ)由式(9)计算得出，其中:

μ～N(0,0.69662)

(15)

υ～N(0,1)

(16)

3.1.2 鸟群的飞行频率FQ动态改变

图2 LBSA算法基本流程图

参数FQ是决定算法能否有效跳出局部最优点，获得全局最优的关键参数。FQ取固定值时，算法在计算开销和准确性两者之间难以取得好的平衡。FQ过小，则计算开销直线上升，FQ太大，则准确性难以得到保障，算法容易陷入局部最优。因此，改进的鸟群算法使FQ成为一个动态改变的量，FQ的取值范围为[3,15]，初始化的时候选取默认值5。在迭代的过程中，每完成H次飞行位置跳跃，即进行H次莱维飞行运算，就对整个周期内全局最优值改变情况进行判断：如果完全没有发生变化，说明算法长期处于某一极值点中无法跳出，则增加飞行频率，FQ默认自减1。若变化h～H(h

3.1.3 生产者和乞讨者的分类更加随机化。

在鸟群算法的原始设计中，生产者和乞讨者的划分是更加细致和随机的。具有最高食物储量的鸟将成为生产者，具有最低食物储量的鸟将成为乞讨者。在两者之间的鸟类也并非完全随机选择成为生产者和乞讨者，而是拥有食物越多的鸟将有更大的概率成为生产者，反之则有更大的概率成为乞讨者。因此，改进的鸟群算法在划分生产者和乞讨者时，将产生一组随机数Pi(Pi为范围在[0,1]之间的随机数，i∈ [1, …,N])。当鸟i的适应度值pFiti小于Pi时，鸟i成为生产者，否则成为乞讨者。这种改进，增加了算法的灵活性。

3.2 算法步骤

LBSA的基本流程见图2。

3.3 计算量与耗时

LBSA算法因引入了莱维飞行，计算复杂度呈几何倍率增长。从50次对比仿真实验中可以得出平均运行时间，每100次莱维飞行的计算耗时约为2.181秒，而100次随机行走的计算耗时仅为0.002秒。当选用sphere为测试函数，迭代次数1 000次，维数为20维，飞行频率FQ为常量10，即固定飞行100次时，LBSA平均耗时36.892秒，BSA平均耗时0.682秒。这种计算量的大幅增加，主要是因为式(2)～(6)中的两次Γ积分运算，为减小计算复杂度，将参数β取定值1.5，则计算复杂度直接下降至接近原始算法水平。依旧采用上述测试标准，50次仿真实验的平均耗时0.832秒。因为莱维飞行的引入大大增加了算法的活力和性能，因而这种程度的计算开销增加是可以接受的。

4 验证与比较

表1所列的8个基本测试函数涵盖了单极值、多极值、高维和低维等各种情况，其中的大多数最优化问题用传统经典算法是无法解决的。通过对这8个基本测试函数的仿真实验，以及和粒子群算法(PSO)、微分进化算法(DE)、原始鸟群算法(BSA)的对比测试，验证改进的莱维-鸟群算法(LBSA)的有效性、高效性和稳定性。

为使测试结果更加公平，所有的测试均采用Intel i5-5200U 2.2G双核处理器，4G内存，Win10操作系统，Matlab R2014a仿真环境。各种算法的种群规模为、维数、最大迭代次数等关键参数都设置相同，并分别独立运行100次。

相关参数见表2；测试结果见表3。

表1 测试函数

表2 算法参数设置

从表3的所有8个测试结果来看，BSA和LBSA算法在整体性能上是明显超越了PSO和DE算法的，特别是F3、F4、F6及F8四个测试函数的结果显示，在同样的条件下，PSO和DE算法在多极值函数的最优化求解方面存在较大的困难，容易陷入局部最优。

表3 四类算法在D=20(F1-F4)、D=2(F6-F7)及D=1(F8)时求解结果比较

在BSA和LBSA的横向比较中，可以看出，两种算法的性能整体是比较接近的。在F1、F3、F5～F8的最优值结论都是一致的，其中在标准差方面的差异主要是因为第3种算法改进导致的随机性区别。而在F2和F4函数的求解中，LBSA体现出了其改进的优势。可以看出，在这两个问题上BSA算法是陷入了局部极值点的，F2问题可以通过增加迭代次数来解决这个问题，但F4问题则无法通过增加迭代数的方法来解决，这说明通过引入莱维飞行增加算法的跳跃灵活性、提高算法性能是有效的。

同时，从实验的函数收敛曲线也可以发现，BSA和LBSA的收敛性能比PSO和DE算法有优势，而LBSA因对FQ系数进行了自适应改进，因而也比BSA收敛速度更快。

5 结论

对于鸟群算法在求解高维多极值优化问题时容易陷入局部最优解和出现早熟收敛的情况，对鸟群算法进行了性能改进。在算法的飞行公式中引入了莱维飞行，并对飞行频率进行了自适应改进，调整了飞行行为中两类鸟群的分类模型。这些改进的优点是增加了算法的跳跃活力，在高迭代次数的情况下，通过FQ的自适应调整能有效调节整体运算量，增加算法的收敛性能。缺点是一定程度上增加了计算量，且因加入了更加随机的分类机制，使算法的稳定性有轻微的下降。通过8个基本测试函数的仿真测试表明，莱维-鸟群算法在增加了可控的时间开销情况下，比原始的鸟群算法更易于跳出局部最优值，算法的收敛性能有明显的提高，同时保持了良好的稳定性。所以文中综合前人研究，试验改进的算法具有可行性和先进性。

[1] Beheshti Z, Shamsudding S M H. (2013).A review of population- based meta- heuristic algorithms[J]. Int. J. Adv. Soft Comput. Appl.，5(1):1-35.

[2] Kuo H C, Lin C H. (2013).A directed Genetic Algorithm for global optimization[J]. Applied Mathematics and Computation, 2013:7348-7364.

[3] Das S, Suganthan P N. Differential evolution: A survey of the state-of-the-art[J]. IEEE Transactions on Evolutionary Computation,2011.

[4] Rezaee J A R, Jasni J. Parameter selection in particle swarm optimization : A survey[J]. Journal of Experimental & Theoretical Artificial Intelligence, 2013,25:527-542.

[5] Gao X Z, Wu Y, Zenger K, et al. A knowledge-based artificial fish-swarm algorithm[A].13th IEEE International Conference on Computational Science and Engineering[C]. Hong Kong: IEEE Computer Society,2010:327-332.

[6] Yang X S, Deb S.Cuckoo search: Recent advances and applications[J]. Neural Computing &Applications,2014,24: 169-174.

[7] Yang X S. A new metaheuristic bat-inspired algorithm[A]. Nature Inspired Cooperative Strategies for Optimization (NICSO 2010)[C]. Studies in Computational Intelligence, 2010,284: 65-74.

[8] Meng X B, Liu Y, Gao X Z, et al. A new bio- inspired algorithm: chicken swarm optimization[A].5th International Conference on Swarm Intelligence[C]. Hefei: Springer International Publishing, 2014:86-94.

[9] Meng X B, Gao X Z, Lu L H,et al. A new bio-inspired optimization algorithm: bird swarm algorithm[J]. Journal of Experimental & Theoretical Artificial Intelligence, 2015.

[10] 杨 娇，叶春明，应用新型萤火虫算法求解Job-shop调度问题[J]. 计算机工程与应用，2013，49(11):213-215.

[11] 刘长平，叶春明，一种新颖的仿生群智能优化算法：萤火虫算法[J]. 计算机应用与研究，2011，28(9):3295-3297.

[12] Yang X S, Deb S. Engineering optimization by cuckoo search[J]. International Journal of Mathematical Modeling and Numerical Optimization,2010 (4):330-343.

[13] 王庆喜，郭晓波， 基于莱维飞行的粒子群算法[J]. 计算机应用与研究，2016，33(9).

[14] Yang X S. Nature-inspired metaheuristic algorithm[M]. 2nd ed. Frome: Luniver Press, 2010:16-29.

Bird Swarm Algorithm Based on Levy Flight

Liu Xiaolong, Ning Qian, Zhao Chengping, Tu Sun

(College of Electronics and Information Engineering, Sichuan University, Chengdu 610065,China)

Considering the fact that the original Bird Swarm Algorithm(BSA) in optimizing high-dimensional multi-extreme value easily gets locally optimal solution and premature convergence, an improved algorithm, Levy-Bird Swarm Algorithm(LBSA) is proposed, which is based on Levy flight, a simulation of the birds flying. LBSA replaces the random location changes in the original algorithm by using Levy flight to update the flight locations, which substantially increases the vitality of the location changes, and makes the algorithm more effective. The results of simulation show that the LBSA outperforms the original BSA in optimizing high-dimensional multi-extreme value.

bird swarm algorithm; Levy flight; high-dimensional; multiple extreme value

2016-07-06；

2016-08-09。

973计划科研项目(2013CB328903-2)。

刘晓龙(1983-)，男，四川成都人，硕士研究生，主要从事卫星通信方向的研究。

1671-4598(2016)12-0194-04

10.16526/j.cnki.11-4762/tp.2016.12.055

TP301.6

A