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

作者: stronghorse | 来源:发表于2019-08-04 12:04 被阅读0次

优化算法笔记（十一）群搜索算法
优化算法matlab实现（十一）群搜索算法matlab实现
优化算法笔记（二十一）麻雀搜索算法
遗传算法简析
优化算法笔记（九）杜鹃搜索算法
关于一些算法
算法-二分搜索算法
局部搜索算法简介
数据结构与算法--BFS&DFS
Local Search

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

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

优化算法笔记（十一）群搜索算法
1. 群搜索算法简介（以下描述，均不是学术用语，仅供大家快乐的阅读）群搜索算法（Group Search O...
优化算法matlab实现（十一）群搜索算法matlab实现
注意：此代码实现的是求目标函数最大值，求最小值可将适应度函数乘以-1（框架代码已实现）。注意：此代码实现的是求目标...
优化算法笔记（二十一）麻雀搜索算法
(手机阅读会有公式不显示！） 1. 麻雀搜索算法简介（以下描述，均不是学术用语，仅供大家快乐的阅读）麻雀搜索算法...
遗传算法简析
遗传算法（genetic algorithm (GA)）是用于解决最优化的搜索算法，是进化算法的一种。遗传算法基于...
优化算法笔记（九）杜鹃搜索算法
1. 杜鹃搜索算法简介（以下描述，均不是学术用语，仅供大家快乐的阅读）杜鹃搜索算法（Cuckoo search，...
关于一些算法
我们平常说的算法按照使用方向加密算法，排序算法，搜索算法，优化算法，音视频处理算法，图片处理算法 1.加密解密算法...
算法-二分搜索算法
算法：二分搜索算法（折半查找算法）时间复杂度：二分搜索算法概述二分搜索算法伪代码二分搜索算法实现二分搜索算...
局部搜索算法简介
局部搜索算法目录： 1、数学定义 2、过程描述 3、算法简介 4、总结 1、数学定义局部搜索是解决最优化问题的...
数据结构与算法--BFS&DFS
“搜索”算法深度优先搜索算法和广度优先搜索算法都是基于“图”这种数据结构。图上的搜索算法就是，在图中找出从一个...
Local Search
1 Local Search 局部搜索算法介绍局部搜索是解决最优化问题的一种启发式算法。因为对于很多复杂的问...