优化算法笔记（十一）群搜索算法

2019-08-04 本文已影响0人 stronghorse

1. 群搜索算法简介

（以下描述，均不是学术用语，仅供大家快乐的阅读）
　　群搜索算法（Group Search Optimizer）是一种基于发现者，跟随者，游荡者模型而产生的算法。算法模型较为复杂，提出时间也不长，对于其的深度研究相对较少，但也有一定的应用研究。
　　在群搜索算法中，每个个体的位置表示解空间内的一个可行解。根据位置的优劣可以将种群分为发现者，跟随者，游荡者。其中当前的最优个体为发现者，它将在它自身周围搜寻，其他个体按照一定的比例分为跟随者和游荡者，跟随者将在跟随发现者的同时进行搜索，而游荡者则自行随机行动。每个个体的头部方向角度将决定该个体下一步的搜索方向，个体会在该搜索方向上前进一定的步长来该方位的区域进行搜索，但是只有发现者可以进行转向来改变搜索方位，跟随者只能更随发现者，而游荡者只能依照当前方向，无法转向。

2. 算法流程

群搜索算法是我的入门算法。不知为什么我每次看到群搜索算法，脑海中就会响起《动物世界》的音乐并出现鬣（lie）狗的画面，想起它们在草原上游荡的画面，那这次的主角就是它了吧，虽然不知道是否合适。

　　看了群搜索算法的简介，我们可以发现，这不是人工蜂群算法吗，当采蜜蜂数量为1时，人工蜂群算法不就成了群搜索算法了吗？确实，它们的种群分类相似，但是它们的搜索行为和搜索策略大相径庭。其实优化算法中有很多感觉都是兄弟姐妹关系，感觉主体流程几乎一样，只不过有某些改进点或者新增了某种属性就成了一个新的算法，既然人家都承认，我们也只好跟着认了。

　　群搜索算法中的个体有三个属性：位置，角度和方向。（其实也可以说是两个属性，方向可以由角度计算出来。
　　在D维解空间内每个鬣狗的位置为

$X=(x_1,x_2,...,x_D)$

每只鬣狗的头部角度为

$\varphi=(\varphi _1,\varphi _2,...\varphi _D)$

可以看出头部的角度的维度比位置的维度少1。
　　其前进方向为 $D(\varphi) =（d_1,d_2,...,d_D)$ ，维度与位置维度一致，比头部角度多1维，前进方向将由头部角度计算得出，计算公式如下

$d_{i1}=\prod_{q=1}^{D-1}cos(\varphi_{iq})$

$d_{ij}=sin(\varphi_{i(j-1)})\prod_{q=j}^{D-1}cos(\varphi_{iq}),(j=2,...,n-2)$

$d_{iD}=sin(\varphi_{i(D-1)})$
　　举个栗子，在3维解空间内， $X=(x_1,x_2,x_3)$ , $\varphi=(\varphi _1,\varphi _2,\varphi _3)$ , $D(\varphi)=（d_1,d_2,d_3)$

$d_{i1}=cos(\varphi_{i1})cos(\varphi_{i2})$

$d_{i2}=sin(\varphi_{i1)})cos(\varphi_{i2})$

$d_{i3}=sin(\varphi_{i1})$
　　可以看出 $||d||=\sqrt {d_{i1}^2+d_{i2}^2+d_{i3}^2}=1$ 即保证前进方向是模为1的单位向量。

2.1发现者行为

发现者是当前群体中位置最优的个体，所以它没有目标去跟随，只能根据当前线索取继续发现新目标。发现者会根据当前头部角度搜索三个方向，前方，左边和右边。

　　如图，前方为该鬣狗当前的头部方向，而左方和右方则为它向左和向右随机转向r度后的方向，即，具体的计算公式如下：

向前方搜索的位置：

$X =X_p +r_1l_{max}D_p(\varphi)$
　　向左方搜索的位置：
$X =X_p +r_1l_{max}D_p(\varphi+r_2\theta_{max}/2)$
　　向右方搜索的位置：
$X =X_p +r_1l_{max}D_p(\varphi-r_2\theta_{max}/2)$
　　其中 $X_p$ 为发现者当前的位置， $r_1$ 为符合标准正态分布的随机数（均值0，方差1）， $r_2$ 为（0,1）内的均匀随机数, $l_{max}$ 为最大的搜索步长, $\theta_{max}$ 为最大转向角度。（这里和原文不一样，我的左右和他是反的，不过没影响）
　　如果这三个新位置比之前的位置好，则移动到这三个位置中最好的位置，否则不移动，只转变头部方向，转向公式如下：
$\varphi^{k+1} = \varphi^k+r_2\theta_{max}/2$
　　如果经过a代都没有找到更好的位置则将头转会a代之前的角度即：
$\varphi^{k+a} = \varphi^k$

2.2跟随者行为

群体中的大部分都是跟随者，它们会向着发现者的位置靠近。
$X_i^{k+1} =X_i^{k} +r_3(X_p^k-X_i^k)$

2.3游荡者行为

游荡者不跟随任何个体，它们会在当前角度上随机搜索。
$X_i^{k+1} =X_i^{k} +ar_1l_{max}D(\varphi^{k+1})$

2.4 流程

由于算法中参数较多，作者也给出了部分标准参数

参数	值
跟随者者比例	80%
游荡者比例	20%
$l_{max}$	解空间上下界的欧式距离
$\theta _{max}$	$\pi/a^2$
a	$round(\sqrt{D+1})$
$\varphi ^0$	$(\pi/4,\pi/4,...,\pi/4)$

３. 实验

适应度函数还是 $f(x_1,x_2)=(x_1-a)^2+(x_2-b)^2$

实验一：标准群搜索算法

参数	值
问题维度(维度)	2
搜索次数(最大迭代次数)	50
跟随者比例	80%
游荡者比例	20%
$l_{max}$	解空间上下界的欧式距离
$\theta _{max}$	$\pi/a^2$
a	$round(\sqrt{D+1})$
$\varphi ^0$	$(\pi/4,\pi/4,...,\pi/4)$
取值范围	（-100，100）
实验次数	10

看看实验图像

　　这应该是到目前为止的实验中最令人满意的实验图像了，几乎所有的粒子随机出现在解空间内然后不断的向着最优个体移动，群体既没有分散的飞舞，也没有随着迭代次数增加过于集中于某一个区域。看看实验结果。

	值
最优值	1.2251107571974537E-7
最差值	0.013024894028570514
平均值	0.0013084455258887948

结果还行，虽然没有想象中的那么好，但也算是在较少的迭代次数下得出的不错的结果，如果增加迭代次数，结果应该会更好。同时结合图像我们可以看出，由于群体没有集中于某一个区域，使算法有了不错的跳出局部最优的能力，同时也削弱了其局部搜索的能力，局部搜索仅由“发现者”提供。但就算法整体而言，“发现者”提供的局部搜索几乎没有起到什么作用。
实验二：标准群搜索算法，移除发现者行为
　　去掉了发现者在左中右的搜索行为，发现者只需要站着不动就好了。

　　图像与标准群搜索算法相比，我看不出什么差别。看看结果

	值
最优值	1.854714209417366E-7
最差值	0.002949841226367196
平均值	3.533115910203305E-4

怎么感觉移除了“发现者”的搜索行为后，其结果反而更好了？只能说运气更好吧，一次最差值就可能拖累整个实验的均值。从结果可以看出，移除“发现者”行为对群搜索算法在这类较为简单的问题上的性能影响不大，也许在更加复杂的问题中，这一算子能够发挥决定性的作用。
实验三：修改种群比例

参数	值
问题维度(维度)	2
总群数量(种群数)	20
搜索次数(最大迭代次数)	50
跟随者比例	80%，60%，40%，20%
游荡者比例	20%，40%，60%，80%
$l_{max}$	解空间上下界的欧式距离
$\theta _{max}$	$\pi/a^2$
a	$round(\sqrt{D+1})$
$\varphi ^0$	$(\pi/4,\pi/4,...,\pi/4)$
取值范围	（-100，100）
实验次数	10

跟随者比例60%

	值
最优值	3.069507400059027E-5
最差值	0.02114359466660109
平均值	0.005540228815855548

跟随者比例40%

	值
最优值	6.59279233735544E-4
最差值	9.738505469931752
平均值	1.4289853174442497

跟随者比例20%

	值
最优值	0.08231541229310135
最差值	82.13212839416113
平均值	16.697520989453512

从图像上可以看出，随着跟随者比例的下降，群体的运动越来越无序，仅有较少的个体向着最有个体靠近。
　　从结果中可以看出，跟随者的比例越大，其结果的精度越高，而且也越稳定。
　　从这个实验中我们可以看出，跟随者提供了全局搜索能力，游荡者提供了跳出局部最优能力。发现者呢，应该是提供了局部搜索能力。前面说了群搜索的局部搜索能力较弱，那为什么不多设置一些发现者，来增强其局部搜索能力呢？
实验四.将10%的最优个体作为发现者

参数	值
问题维度(维度)	2
总群数量(种群数)	20
搜索次数(最大迭代次数)	50
发现者比例	10%
跟随者比例	72%
游荡者比例	18%
$l_{max}$	解空间上下界的欧式距离
$\theta _{max}$	$\pi/a^2$
a	$round(\sqrt{D+1})$
$\varphi ^0$	$(\pi/4,\pi/4,...,\pi/4)$
取值范围	（-100，100）
实验次数	10

	值
最优值	1.380210268180854E-7
最差值	0.0016625529372137474
平均值	2.5507510902798446E-4

图像和结果与标准几乎没有太大的差别，我总感觉发现者其实并没有什么太大的作用。群搜索算法的如果去掉了发现者的行为，其实是一个比较简单的算法，而发现者的搜索行为使算法的流程、理解以及实现都复杂了少，却对算法的性能影响甚微，即使移除也无大碍。

４. 总结

群搜索算法的探究也到此为止，群搜索算法的流程比较复杂，作为我的入门算法，我当年也头疼了几天，现在看来，不能说它“也不过如此”，至少流程上清晰了不上，由于是当年的入门算法，我的侧重点也放在了应用上，对于改进并没与太多的研究，此处也只是分析了某些参数的作用以及对结果的影响。
　　相对标准群搜索算法，后面的实验主要在研究发现者，跟随者，游荡者的作用。其中可以明确的得出，游荡者起到了跳出局部最优的作用，跟随者的作用是局部搜索和少量的局部搜索，而发现者的作用是引导跟随者。目前看来，发现者的行为对算法影响不大，如果后续有什么新的发现再来更新。
　　以下指标纯属个人yy,仅供参考

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

参考文献
S. He†, Q. H. Wu†, J. R. Saunders‡. Group Search Optimizer - An Optimization Algorithm Inspired by Animal Searching Behavior[J]. IEEE Transactions on Evolutionary Computation, 2009, 13(5):973-990.提取码：p9da

目录
 上一篇优化算法笔记（十）萤火虫算法
 下一篇优化算法笔记（十二）烟花算法