ABSTRACT

Grey wolf optimization algorithm is a new swarm intelligence algorithm with simulation of grey wolf predation behavior. Based on the encircling, hunting and attacking of grey wolves prey behavior in nature, a niche grey wolf optimization (NGWO) algorithm is proposed. In this algorithm, calculating the fitness of individual using basic GWO, to poor fitness with penalty function through compares fitness of individual with niche radius as limit, thus improve the global search ability. From the above, according to algorithmic flows analyze the time complexity of NGWO. Moreover, tested the NGWO by 5 benchmark functions and compared with two intelligent algorithms, grey wolf optimization and particle swarm optimization. Simulation results indicate that the algorithm has significant improvement in aspects of convergence speed and accuracy.

Keywords:Grey Wolf Optimization Algorithm, Niche, Penalty Function, Functions Optimization

改进灰狼优化算法的研究与分析

白媛，陈京荣，展之婵

兰州交通大学数理学院，甘肃 兰州

收稿日期：2017年6月4日；录用日期：2017年6月20日；发布日期：2017年6月23日

摘 要

灰狼优化算法是一种模拟灰狼捕食行为的群智能优化算法。基于灰狼捕食行为的包围、追捕、攻击三个阶段提出了一种小生境灰狼优化算法(Niche Grey Wolf Optimization, GWO)。该算法利用基本GWO计算各灰狼的适应度值，以小生境半径作为限制，比较灰狼个体的适应度值，通过对适应度值较差的灰狼个体施以罚函数，来提高全局搜索能力。分析了NGWO算法的时间复杂度，利用NGWO对5个基准函数进行了测试，并与基本灰狼算法和粒子群算法的结果进行了比较，表明NGWO算法无论是在收敛速度还是求解精度上均有明显改善。

关键词 :灰狼优化算法，小生境，罚函数，函数优化

Copyright © 2017 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

大自然中物种会因为不同的任务而表现出不同的社会行为，在过去的几十年中，因模仿动物的某种行为方式而产生了多种仿生智能算法。最早的仿生算法是由Holland教授在1975年提出的遗传算法 [1] (Genetic Algorithms, GA)，其模拟自然界生物自然选择和遗传原理，通过个体间的选择、交叉、变异等操作实现优化问题的求解。1992年Dorigo提出的蚁群算法 [2] (Ant Colony Optimization, ACO)其灵感源于蚂蚁在寻找食物过程中发现路径的行为。粒子群算法 [3] [4] (Particle Swarm Optimization, PSO)是Kennedy于1995年模拟鸟群飞行觅食过程中位置和速度改变提出的一种智能优化算法。2002年李晓磊等人提出了根据鱼群觅食、聚群和追尾行为的人工鱼群算法 [5] (Artificial Fish-Swarm Algorithm, AFSA)。近几年，随着计算机技术的不断发展一系列的仿生算法被提出，并在组合优化、自动控制、医疗等社会科学方面取得了良好的理论成果。

灰狼优化算法 [6] (Grey Wolf Optimizer, GWO)是一种模拟灰狼捕食行为的群体智能算法，该算法最先由澳大利亚学者Mirjalili于2014年提出，根据灰狼的社会等级将包围、追捕、攻击等捕食任务分配给不同等级的灰狼群来完成捕食行为，从而实现全局优化的过程。GWO算法具有操作简单、调节参数少、编程易实现等特点。在函数优化方面，与其他群智能优化算法相比有明显的优越性。但同时也存在着易陷入局部最优、求解精度不高、收敛速度慢等缺点。魏政磊等 [7] 采用计算分配值的方法提出了一种自适应搜索的灰狼求解算法从而加快算法的收敛速度；罗佳等 [8] 将混沌序列方法引入初始化种群个体，给出了一种寻优性和鲁棒性更好的改进GWO算法。龙文等 [9] 引入了佳点集理来初始化狼群，并用非固定多段映射罚函数法处理约束条件，利用改进GWO算法求解约束优化问题，并验证了其有效性。

灰狼算法在函数优化方面与PSO、ACA、GA相比，有着结构简单、易操作等优点，但在寻优的过程中，由于种群多样性差，从而影响收敛速度且易陷入一种局部最优的状态。根据算法存在的缺点，本文提出了一种小生境灰狼优化算法(Niche Grey Wolf Optimization, NGWO)。该算法利用基本GWO算法计算各灰狼的适应度值，当灰狼间的距离小于小生境半径时，比较灰狼个体的适应度值，通过对适应度值较差的灰狼个体施以罚函数，来提高全局搜索能力。通过对5个基准函数的测试，将结果与基本GWO算法和PSO算法进行比较，表明了该算法的优越性。

2. 灰狼优化(GWO)算法

2.1. GWO算法原理

灰狼属于食物链顶端的食肉动物，常以群居的方式生存，且灰狼的数量一般控制在5~12只。在捕猎过程中灰狼群有着严格的社会等级制度，它们分工明确、协同合作进行捕食。在GWO算法中，领导能力最强的灰狼被记为α，主要负责捕猎(寻优)过程中的决策部分及管理狼群。剩下的灰狼个体按社会等级被依次记为β, δ和ω。

α狼是整个灰狼群在捕猎过程中的领导者，是最有智慧和能力最强的个体(即其适应度最佳、离最优值最接近的狼)；β狼和δ狼是适应度次佳的两个个体，捕猎中它们会协助α狼对灰狼群的进行管理及捕猎过程中的决策问题，同时也是α狼的候选者；剩余的狼群被定义为ω，其主要职责是平衡灰狼种群的内务关系及协助α, β, δ对猎物进行攻击。在整个捕猎过程中，首先由α狼带领狼群搜索、跟踪、接近猎物，当距离猎物的范围足够小时，β, δ狼在α的指挥下对猎物进行围攻，并召唤周围的ω狼对猎物进行攻击，当猎物移动时，狼群形成包围猎物的圈也随之移动，直至捕获猎物。

2.2. GWO算法描述

GWO算法可以将整个捕猎的过程分为包围、追捕、攻击三个阶段 [6] ，最终捕获猎物(获得全局最优解)。具体算法描述如下：

1) 包围

狼群在确定猎物的位置后，首先要对猎物进行包围，在此过程中猎物与灰狼之间的距离可表示为

(1)

(2)

其中为灰狼和猎物之间的距离，t为迭代次数，为第t次迭代后猎物的位置(即最优解的位置)，为第t次迭代后灰狼的位置(即潜在解的位置)，A和C为系数因子，其计算公式为：

(3)

(4)

其中a随着迭代次数的增加从2到0呈线性递减，r₁、r₂为[0, 1]间的随机数。

2) 追捕

对猎物进行包围后，β, δ狼在α狼的带领下对猎物进行追捕，在追捕过程中狼群个体的位置会随猎物的逃跑改变，而后可以根据α, β, δ的更新后的位置来重新确定猎物(最优解)的位置。此阶段狼群位置更新机制如图1所示，更新方程如下：

(5)

(6)

(7)

其中分别表示α, β, δ狼与ω狼(其他个体)之间的距离。

3) 攻击

图1. GWO算法中灰狼位置更新图

攻击是捕猎过程的最后阶段，狼群对猎物进行攻击并捕获猎物，即得到最优解。该过程的实现主要通过式(3)中a值的递减来实现，当a的值从2线性递减0时，其对应的A的值也在区间变化。另外，当时，即A的取值范围在时，则表明狼群的下一个位置会更加接近猎物的位置；当时，狼群就会朝着远离猎物的方向分散开去，导致GWO算法失去最优解位置，从而陷入一个局部最优的过程。

灰狼优化算法

Step 1初始化等参数以及灰狼群体，每个灰狼的位置；

Step 2计算每个灰狼个体的适应度值，将适应度值排列前三的灰狼个体的位置分别记为，并将适应度值最好的记为最优解；

Step 3按照(5)式计算剩余个体ω与的距离，并根据(6~7)式更新灰狼α, β, δ和猎物的位置；

Step 4按照 (3~4)式更新参数的值；

Step 5若算法到达到最大迭代次数t，那么算法结束并输出最优解；否则，返回Step 2。

3. 小生境灰狼优化(NGWO)算法

小生境是一种“物以类聚，人以群分”的自然现象，即物种总偏好于和那些与自己有共同习性的生物生活在一起，并与同类进行交配而生育后代。这样的交配方式对于物种的进化有着积极的作用。小生境原理是在每一代进化前，根据个体间的距离将种群划分成多个小生境种群，让不同小群体进行交配产生新的后代。在群智能优化算法中同样可釆用小生境原理，物种的生活习性相似度一般用适应度值或距离进行分辨。将小生境原理引入到灰狼优化算法中，采用个体间的距离对灰狼群生活习性的相似度进行分辨，通过对适应度值较差的灰狼个体施以罚函数，来实现寻优过程。

3.1. NGWO算法

个体间的欧式距离能反映出个体间的疏散程度，对于D维空间灰狼i的位置为，灰狼j的位置为，那么灰狼i与灰狼j之间的欧式距离为 [10] [11]

(8)

给出指定参数(为小生境半径)，如果，则该个体加入到小生境群体。

小生境灰狼优化算法

Step 1初始化等参数以及灰狼群体，每个灰狼的位置；

Step 2计算每个灰狼个体的适应度值f_i，将适应度值排列前三的灰狼个体的位置分别记为，并将适应度值最好的记为最优解；

Step 3按照(5)式计算剩余个体ω与的距离，并根据(6~7)式更新灰狼α, β, δ和猎物的位置；

Step 4小生境原理：根据式(8)计算灰狼个体间的距离，当时，比较灰狼i与灰狼j的适应度值的大小，并对其中适应度值较小的灰狼施以罚函数。即若，则(函数的惩罚力度由所求函数解值的大小决定)；

Step 5按照(3~4)式更新参数a, A, C的值；

Step 6若算法到达到最大迭代次数t，那么算法结束并输出最优解；否则，返回Step 2。

3.2. NGWO算法分析

根据算法的执行步骤，下面讨论NGWO算法时间复杂性，这里只计算每一步的运算次数。在Step 1中，对D维搜索空间下的N个灰狼进行初始化赋值需要ND次运算；在Step 2中，计算N个灰狼个体的适应度值f_i需要N次运算，而适应度函数的复杂度一般是，选出适应度值前三的个体至多需要次运算，记录最优解其运算次数加1；在Step 3中，按照(1.5)式计算剩余个体与的距离需要次运算，而距离函数的复杂度是。根据(6~7)式更新α, β, δ灰狼和猎物的位置需次运算；在Step 4的小生境原理中，计算灰狼i与灰狼j间的距离需要D次运算，比较它们适应度值大小运算次数加1，对适应度值较小的灰狼施以罚函数运算次数加1。而对于整个灰狼群而言，计

算灰狼个体间的距离至多需要次运算；在Step5和Step6中更新等参数的值及判断算法

是否满足终止条件，其复杂度均为常数时间。由于算法最多执行t次(t是用户设定的最大迭代次数或者是为了达到某计算精度所需的迭代次数)。因此，通过近似和简化运算，NGWO算法的时间复杂度约为

。

4. 仿真与分析

4.1. 基准函数

为了验证NGWO算法的寻优能力，本文利用5个基准函数测试了算法执行效果，并与标准GWO算法和PSO算法进行了比较，说明了NGWO算法的有效性。5个基准函数的表达式及变量范围如表1所示，其中为单峰函数，只有一个全局最优解；为多峰函数，即函数有很多极值点(对于函数而言有局部最优解)。另外，5个基准函数的理论最优解均为0。

4.2. 实验结果与分析

利用NGWO算法对上述5个基准测试函数进行数值实验，其参数设置如下：种群规模N = 30，最大迭代次数t = 500，每个函数的维数D = 30，小生境半径。(根据测试的多峰函数各峰值的差所决定)在PSO算法中，种群规模N = 30，最大迭代次数t = 500，，惯性权重，。每个基准函数在上述参数的设置下运行30次，记录其最优值、平均值、标准差，并与GWO、PSO的运行结果进行比较。

对于只有一个全局最优的单峰函数而言，测试结果可表明算法的寻优能力，而对于有多个极值点的多峰函数而言，测试结果可表明算法跳出局部最优值的能力。从表2可以看出，对于Sphere函数、Schwefel函数、Rastrigin函数、Griewank函数NGWO算法均能较好的找到全局最优解，且均得到了较优的平均值、标准差(标准差能反应解的离散程度，即算法求解的稳定性)，尤其是对Griewank函数算法能找到理论最优值0，而对Sphere函数其寻优精度达到了10⁻³⁰；由于Step函数属于阶跃函数它由很多平滑的高地和陡脊组成，且不连续，所以在寻求最优值上有一定的难度，对于此函数PSO算法却能获得较好的全局最优解。图2~6给出了5个基准函数在三种算法下的进化收敛曲线，可以清楚的看出除Step函数外其余4个函数均能较快的收敛到全局最优解。对于改进的灰狼优化算法我们从计算结果及实验曲线图均能看出算法在处理函数优化问题时表现出优越的稳定性及鲁棒性，具有更好的优化性能。

表1. 基准函数

表2. 三种算法对5个函数的实验结果比较

图2. Sphere 函数收敛曲线

图3. Schwefel函数收敛曲线

图4. Step函数收敛曲线

图5. Rastrigin函数收敛曲线

图6. Griewank函数收敛曲线

5. 结束语

灰狼优化算法自提出以来备受学者关注。但基本灰狼优化算法存在收敛速度慢、易陷入局部最优等缺点。为了克服上述缺点，本文将小生境技术引入灰狼优化算法中，利用基本GWO计算各灰狼的适应度值，并对灰狼个体的位置进行更新。灰狼群的生活习性相似度采取两者间的距离进行分辨，通过比较灰狼的适应度值并对适应度值较差的灰狼个体施以罚函数，来减少盲目搜索的几率，从而实现寻优的过程。本文根据NGWO算法流程，分析了算法的时间复杂度；通过对5个基准函数的测试，并与GWO、PSO的结果进行了比较，表明改进后的算法对基准函数的求解精度有所提高，且具有较好的全局收敛性。

文章引用

白 媛,陈京荣,展之婵. 改进灰狼优化算法的研究与分析
Analysis and Research of Improved Grey Wolf Optimization Algorithm[J]. 计算机科学与应用, 2017, 07(06): 562-571. http://dx.doi.org/10.12677/CSA.2017.76067

参考文献 (References)