优化算法笔记（十八）灰狼算法

（以下描述，均不是学术用语，仅供大家快乐的阅读）
　　灰狼算法（Grey Wolf Algorithm）是受灰狼群体捕猎行为启发而提出的算法。算法提出于2013年，仍是一个较新的算法。目前为止（2020）与之相关的论文也比较多，但多为算法的应用，应该仍有研究和改进的余地。
　　灰狼算法中，每只灰狼的位置代表了解空间中的一个可行解。群体中，占据最好位置的三只灰狼为狼王及其左右护法（卫）。在捕猎过程中这三只狼将带领着狼群蛇皮走位，抓捕猎物，直至找到猎物（最优解）。当然狼王不会一直是狼王，左右护法也是一样，每一轮走位后，会根据位置的优劣重新选出新的狼王和左右护法。狼群中的每一只灰狼会向着（也可能背向）这三只位置最优的灰狼移动一定的距离，来决定这一步自己将如何走位。简单来说，灰狼个体会向则群体中最优的三个个体移动。

很明显该算法的主角就是灰狼了。

　　灰狼群在D维空间内有N个个体，其位置为
，其适应度值为F(x) ，每只灰狼并没有其他特殊的属性，行为也较为简单。
　　原文描述了灰狼群的很多行为，如包围猎物（Encircling prey）、搜寻猎物(Search for prey )、攻击猎物（Attacking prey），但其核心行为只有一个，就是捕猎(Hunting)。其他的行为都是捕猎行为的组成部分，用来说明捕猎的流程以及参数对行为的影响。
　　在这里，为了方便描述，根据算法的计算流程将其捕猎行为分为两个步骤：
　　1.观察，即计算一只灰狼向着目标头狼（头狼及其左右）前进后的位置。
　　2.行动，根据观察所有的头狼计算出的下一步的位置并移动到那里。

设定目标灰狼为
，当前灰狼的为 ，则该灰狼向着目标灰狼移动后的位置 可以由一下公式计算得出：

　　其中A为取值范围-a到a的均匀随机数，a为常数，初始值为2，并随着算法迭代由2线性递减至0。C为取值0或2的随机数。
　　从公式可以看出，经过移动后，灰狼i将移动到目标灰狼p的周围，其方位由自身每一维度的大小及随机数C决定，而其距离目标灰狼p的距离将由随机数A决定。由A的定义可知随着迭代次数增加，观察后的灰狼位置将会离目标灰狼越来越近。

灰狼群体中位置最好的三只灰狼编号为1,2,3，那么当前的灰狼i通过观察灰狼1、灰狼2和灰狼3，根据公式（1）得出的三个位置为Ｘi1,Xi2,Xi3。那么灰狼i将要移动到的位置可以根据以下供述计算得出：

　　可以看出该灰狼的目标位置是通过观察三只头狼得到的三个目标位置的所围成的区域的质心。（质心超出边界时，取值为边界值）。

灰狼算法的论文描述很多，但是其公式和流程都非常简单，主要对其参数A和C的作用效果进行了详细描述。
　　C主要决定了新位置相对于目标灰狼的方位，而A则决定新位置向目标靠近还是远离目标灰狼。当|A|>=1时，为远离目标，表现出更强的全局搜索能力，|A|<1时靠近目标，表现出更强的局部搜索能力。

适应度函数。
实验一：

	值
问题维度(维度)	2
总群数量(种群数)	20
搜索次数(最大迭代次数)	100
A	Rand(-a,a),a=2->0
C	Rand{0,2}
取值范围	（-100，100）
实验次数	10

	值
最优值	2.6062775921213544E-22
最差值	5.17099440808296E-14
平均值	5.175029931249637E-15

看看这图像和结果，效果好极了。每当我这么认为时，总会出现意想不到的转折。
　　修改一下最优解位置试一试，。
实验二：。

	值
最优值	0.023179729319963736
最差值	0.42578156266405487
平均值	0.18248549905908668

其结果比上面的实验差了不少，但我觉得这才是一个优化算法应有的搜索图像。其结果看上去较差只是因为迭代次数较少，收敛不够迅速，这既是优点也是缺点，收敛慢但是搜索更细致。
　　仔细分析灰狼算法的流程，它并没有向原点靠近的趋势，那只能理解为算法群体总体上向着群体的中心移动。猜想：当初始化群体的中心恰好是正解时，算法的结果将会非常的好。
　　下面使用，并将灰狼的初始位置限定在（50,100）的范围内，看看实验图像是否和实验二的图像一致。

实验三. ,初始种群取值范围为（50,100）

	值
最优值	2.1606056479627276E-24
最差值	8.28885463444239E-18
平均值	1.5379045385036046E-18

这图像和结果跟实验一的不是一样的吗?这说明从实验二中得出的猜想是错误的。

　　从图像中可以看出，虽然初始化时，群体集中在右下角，但随着算法的迭代，群体将迅速扩散到整个解空间中，在逐渐的收敛到原点且收敛速度很快。故猜想：当最优解在原点附近时，灰狼算法将会得到非常好的结果。
　　下面将目标函数的解空间搬离原点，看看灰狼算法的效果
实验四.,初始种群取值范围为（50,100），解空间范围同样为（50，100）

	值
问题维度(维度)	2
总群数量(种群数)	20
搜索次数(最大迭代次数)	100
A	Rand(-a,a),a=2->0
C	Rand{0,2}
取值范围	（50，100）
实验次数	10

	值
最优值	0.002612674971178293
最差值	0.5531163122132745
平均值	0.17749064798407285

从图像和结果上看，都和实验二非常相似，当解在解空间的中心时但不在原点时，算法的结果将差一些。
　　为什么会这样呢？从算法的流程上看，灰狼算法的各个行为都是关于头狼对称的，当最优解在原点且头狼在附近时，公式（1）将变为如下：

　　通过公式（2）计算其中心在原点附近很大（其数学期望为原点）。
　　单独看灰狼个体的移动过程没有任何问题，但是总体上看则产生了微弱的向原点靠近的趋势，所以当解在原点时，算法的结果会异常的好。
　　个人认为这并没有什么问题，只是在做对比试验时应避免将待求函数的解放在原点即可。
　　迭代过程中，由于A的值由2线性递减至0，在算法的前半段A>1,个体将会进行全局搜索，而在后半段进行局部搜索，所以群体会在一开始时扩散到整个解空间，再慢慢聚拢到群体中心附近。
　　从图像中可以看出，灰狼算法是一个没有“贪心”的算法，所有的个体都在不停的移动，这样算法的全局搜索能力会更强，精度稍差。下面试着为3只头狼添加“贪心算法”：即这三只头狼在找到优于当前的位置时才进行移动。

实验五. ,三只头狼添加贪心算法。

	值
问题维度(维度)	2
总群数量(种群数)	20
搜索次数(最大迭代次数)	100
A	Rand(-a,a),a=2->0
C	Rand{0,2}
取值范围	（50，100）
实验次数	10

	值
最优值	0.02060156741278336
最差值	0.27945550433647137
平均值	0.10352694023379161

从图像可以看出中心的三个点移动的频率要比其他点的移动频率低。从结果上可以看出其结果相对稳定了不少，不过差距非常的小，几乎可以认为是运气好所导致。如果所有的个体都添加贪心算法呢？显然，算法的全局搜索能力将进一步减弱，并且更容易向群体中心收敛，这并不是一个好的操作。

实验六. ,
在实验五的基础上为狼群添加一个统一的步长，即每只狼每次向着目标狼移动的距离不能大于其步长，将其最大步长设为1，看看效果。

	值
问题维度(维度)	2
总群数量(种群数)	20
搜索次数(最大迭代次数)	100
A	Rand(-a,a),a=2->0
C	Rand{0,2}
StepMax(最大步长)	1
取值范围	（50，100）
实验次数	10

从图像可以看出，受到步长的约束每只狼的移动距离较小，在结束时还没有收敛，其搜索能力较强但收敛速度过慢且极易陷入局部最优。现在将最大步长设置为10（1/10解空间范围）使其搜索能力和收敛速度相对平衡，在看看效果。

	值
最优值	1.7013036590205155E-4
最差值	0.21432062721204184
平均值	0.09147526762644856

从图像可以看出，算法的收敛速度快了不少，但从结果可知，相较于实验五，算法的提升并不太大。
　　不过这个图像有一种似曾相识的感觉，与萤火虫算法（FireFly Algorithm）差不多，仔细对比这两个算法可以发现，灰狼算法相当于萤火虫算法的一个简化。实验六种对灰狼算法添加步长的修改，让其离萤火虫算法更近了一步。

实验七. ,
在实验六的基础上让最大步长随着迭代次数增加递减。

	值
问题维度(维度)	2
总群数量(种群数)	20
搜索次数(最大迭代次数)	100
A	Rand(-a,a),a=2->0
C	Rand{0,2}
StepMax(最大步长)	20->0
取值范围	（50，100）
实验次数	10

	值
最优值	5.15374332251629E-5
最差值	0.13904018569004928
平均值	0.04869044113468185

从实验七的图像可以看出，种群的收敛速度好像快了那么一点，结果也变好了不少。但是和改进后的萤火虫算法相比仍然有一定的差距。
　　灰狼算法在全局搜索和局部搜索上的平衡已经比较好了，尝试过对其进行改进，但是修改使搜索能力更强时，对于局部最优的函数求解效果很差，反之结果的精度较低，总体而言修改后的算法与原算法相差无几。

灰狼算法是根据灰狼群体的捕猎行动而提出的优化算法，其算法流程和步骤非常简单，数学模型也非常的优美。灰狼算法由于没有贪心算法，使得其有着较强的全局搜索能力同时参数A也控制了算法的局部搜索范围，算法的全局搜索能力和局部搜索能力比较平衡。
从算法的优化图像可以看出，灰狼算法和萤火虫算法非常的相似。可以认为，灰狼算法是对萤火虫算法的一种改进。萤火虫算法向着由于自己的个体飞行，而灰狼算法则的条件更为苛刻，向着群体前三强前进，萤火虫算法通过步长控制搜索范围，而灰狼算法则直接定义搜索范围参数A，并令A线性递减。
灰狼算法的结构简单，但也不容易改进，数次改进后只是改变了全局搜索能力和局部搜索能力的比例，综合能力并没有太大变化。
由于原点对于灰狼算法有着隐隐的吸引力，当测试函数目标值在原点时，其结果会异常的好。因此，灰狼算法的实际效果没有论文中的那么好，但也不差，算是一个中规中矩的优化算法。
参考文献
Mirjalili S , Mirjalili S M , Lewis A . Grey Wolf Optimizer[J]. Advances in Engineering Software, 2014, 69:46-61. 提取码：wpff

以下指标纯属个人yy,仅供参考

指标	星数
复杂度	★★☆☆☆☆☆☆☆☆
收敛速度	★★★★★☆☆☆☆☆
全局搜索	★★★★★☆☆☆☆☆
局部搜索	★★★★★☆☆☆☆
优化性能	★★★★★☆☆☆☆☆
跳出局部最优	★★★☆☆☆☆☆☆☆
改进点	★★☆☆☆☆☆☆☆☆

目录
上一篇 优化算法笔记（十七）万有引力算法
下一篇 优化算法笔记（十九）头脑风暴算法

优化算法matlab实现（十八）灰狼算法matlab实现