优化算法笔记（九）杜鹃搜索算法

作者: stronghorse | 来源:发表于2019-07-21 11:11 被阅读0次

优化算法笔记（九）杜鹃搜索算法
优化算法matlab实现（九）杜鹃搜索算法matlab实现
遗传算法简析
优化算法笔记（十一）群搜索算法
关于一些算法
算法-二分搜索算法
局部搜索算法简介
数据结构与算法--BFS&DFS
Local Search
A*算法和最佳优先搜索算法（Best-First-Searc

1. 杜鹃搜索算法简介

（以下描述，均不是学术用语，仅供大家快乐的阅读）
　　杜鹃搜索算法（Cuckoo search，CS）是一种模仿杜鹃鸟寻窝产卵活动的群集智能优化算法。杜鹃搜索算法的流程简单，有较强的跳出局部最优能力，但由于算法中列维飞行实现较复杂且算法提出时间不长，还有很多基础研究正在进行。
　　杜鹃搜索算法中，每个杜鹃的寄生巢的位置代表待求问题的一个可行解。每个杜鹃每次只会在一个寄生巢中生产一枚卵。在所有的寄生巢中，最优秀的寄生巢才会被留到下一代，继续在该寄生巢中产卵。每个寄生巢的主人都有一定的几率察觉自己的巢中有外来单从而放弃该鸟巢。寄生巢被放弃后，杜鹃将会重新随机选择一个鸟巢作为新的寄生巢。

2. 算法流程

杜鹃搜索算法的主角当然就是杜鹃了。

　　杜鹃不自己养育后代，而是将自己的卵放置在其他鸟的鸟巢中，将自己的后代寄养其中。每一个寄生鸟窝是一个候选解。为了生存繁衍，杜鹃有两种产卵的策略：
　　1. 列维飞行，杜鹃将在通过列维飞行所找到的与之前的寄生巢对比，选择较优的寄生巢作为下一代的寄生巢
　　2. 随机选择，每个寄生巢的主人都有一定的几率发现自己的巢被寄生。发现后，杜鹃将随机选择一个新的鸟巢作为自己的寄生巢。
　　可以说杜鹃搜索的算法流程也是极其的简单，但是其实现起来并没有看上去的那么容易，困难点在于如何实现列维飞行。什么是列维飞行以及其特点将在下一节介绍。
　　在D维解空间内每个鸟巢的位置为:

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

第t+1代时，杜鹃将根据第t代的寄生巢的位置，结合列维飞行求得新的寄生巢的位置，飞行公式如下：
$x_{i,d}^{t+1}=x_{i,d}^{t}+\alpha\times Levy(\lambda)$
其中 $x_{i,d}^{t}$ 表示第i个杜鹃在第t代时选择的寄生巢的位置的第d维， $\alpha$ 为列维飞行的步长。 levy表示服从当前迭代次数的t的随机分布，在杜鹃搜索算法中其真正的含义其实是向当前的全局最优解以levy飞行的方式靠近（这是作者原代码中的实现，与论文不相符(╰_╯)#）。
　　实际的飞行公式如下：
$x_{i,d}^{t+1}=x_{i,d}^{t}+r\times\alpha\times Levy(\lambda)\times (x_{best,d}^{t}-x_{i,d}^{t})$
　　其中ｒ为[0,1]内的均匀随机数。

　　杜鹃搜索算法的流程是不是相当的简单明了，其中的关键步骤就是列维（levy）飞行了，很许多小伙伴都是在学习杜鹃搜索算法时才知道列维飞行这个概念，当然我自己也是。
　　下面我们将来详细的探究一下什么是列维飞行，这对以后我们改进其他优化算法提供了一个思路。

3.levy飞行

Levy 过程直观上讲,可以看做连续时间的随机游动 .它的特征是有平稳独立的增量, 重要的 Levy 过程有 Brown 运动, Poisson 过程, Cauchy 过程等。（没看过随机过程的小伙伴应该看不懂吧）。
　　来个levy飞行的链接，也是杜鹃搜索算法的：levy飞行。
　　Levy飞行简单来说就是一种随机飞行的过程，飞行有很大的概率在当前位置周围运动，也会有极小的概率飞到很远的地方去。就好比我们不经常打扫房间，平时也就清理一下垃圾桶，但是也会偶尔抽风花点时间将房间从里到外仔细的打扫一遍，这也是一个列维过程，可以称之为列维打扫房间。
　　看一下列维飞行的公式，找了好久，还是从自己论文抄一个吧。
$Levy(\lambda)$ 表示服从当前迭代次数的t的随机分布，其概率分布为式如下：
$Levy(\lambda)\sim u=t^{-\lambda},1<\lambda<3　　(1)$

本文中采用Mantegna 于1992 年提出的模拟levy 飞行来进行搜索，其计算公式如式（2）：
$s=\frac{u}{|v|^{\frac{1}{\beta}}}　　(2)$
　　其中s即为 $Levy(\lambda)$ 所求得的路径，参数与式（1）中的关系为，通常取值在[0,2]范围内，杜鹃搜索算法中取。为服从正态分布的随机数，如下式 (3)：
$u\sim N(0,\sigma_u^2),\sigma_u^2=\{\frac{\Gamma(1+\beta)sin(\beta\pi/2)}{\Gamma((1+\beta)/2)2^{(\beta-1)/2}\beta}\}^\frac{1}{\beta}　　(3)$
$v\sim N(0,\sigma_v^2),\sigma_v^2=1$
　　式（3）中 $\Gamma(x)$ 的定义如下式 (4)：
$\Gamma(x)=\int_{0}^{+\infty} t^{x-1}e^{-t}\,dt$
　　从式（2）中我们可以看出列维飞行的长度其实是两个正态分布随机数之商。
$\beta=1.5$
$\Gamma(1+1.5)=1.329340388179137$
$\sigma_u=1.849902656990532$
我们先看看 $\Gamma$ 函数的图像：

由

1<\lambda<3

可知，列维飞行中gamma函数的取值范围为[1,2]。
然后我们再来看一下标准正态分布的分布图：

　　可以看出方差越大的正态分布曲线越平缓。而levy飞行长度可以看成是两个正态分布相关随机数的商，其中分母为标准正态分布相关，而分子为服从标准差为1.85，均值为0的正态分布的随机数。
我们看一下此时列维飞行的分布图，

　　总共进行飞行了100次，可以看出有近1/2的次数分布在0左右，而最大值取到了16仅出现了1次，最小取到了-41，也只出现了一次。比较符合我们心中的levy飞行的特点，大多数集中于绝对值较小的数，极少量为绝对值较大的数。我们再来看看

\beta

取其他值时分布图：

　　我们可以看出，不同的

\beta

值对应的levy飞行长度分布基本相似，大多数分布于较小数，较少出现于极大数，由于算法可以根据问题各维度的取值范围来设定levy飞行的最大最小值。如取值为（-100,100）的问题，若

\beta=0.5

，那么其最大取到273030，最小取到-711，这些极少出现的较大值在整个算法过程中几乎没有意义，它们会使进行levy飞行的杜鹃飞出了搜索空间的边界，然后被遣返，这浪费了杜鹃的一次搜索。而取

\beta=1.5

是，最大最小值均在搜索范围内，越界的可能较小（当飞到边界附近后再向边界外飞行仍会越界）。
　　现在问题来了,既然levy飞行在杜鹃搜索算法中只是提供了一个小概率的大波动,那么能不能使用其他的概率分布呢?
　　先看看

s=\frac{u}{v}

,其中，u、v均为符合正态分布的随机数，那么S的概率分布如何呢，

　　怎么样，是不是感觉和levy飞行的分布很像，只不过最大值更大，最小值更小，其实levy飞行本来就是两个符合正态分布的随机数相除，所以直接用感觉也不会有太大的影响。
　　u均为符合正态分布的随机数，v为（-1,1）的均匀分布随机数时，那么S的概率分布如下

　　其分布与levy也比较相似，但是分布更为均匀。

4.实验

实验又开始了

实验1.标准杜鹃搜索算法

参数	值
问题维度(维度)	2
杜鹃数量(种群数)	20
搜索次数(最大迭代次数)	50
最大步长	1
飞行方式	Levy
宿主发现概率	0.3
取值范围	（-100，100）
实验次数	10

杜鹃搜索

	值
最优值	5.6989487065157614E-8
最差值	2.1765283245215035E-5
平均值	7.18140639739042E-6

可以看出杜鹃搜索的位置跳跃性较大，符合我们对levy飞行的期待。真的是这样吗，我们先看看其他算法的位置移动路线图。

粒子群算法

遗传算法

差分进化算法

人工蜂群算法
　　对比可以发现，杜鹃搜索的路线图会出现部分较远的飞行距离，且路线图也相对曲折，但是飞行的长度明显少于其他算法。
　　粒子群算法的路线图，由于不会要求下一个位置优于上一个位置，所以飞行的路线图非常的密集，也说明了其较强的全局搜索能力。
　　遗传算法的进化曲线在初始阶段比较密集，到了后来基因多样性降低后只能靠变异取产生新的基因时才会出现进化曲线。
　　差分进化算法的进化曲线非常有意思，多数为横线或者竖线，这也和其算法描述一致，至少保留一位交叉基因到下一代。
　　人工蜂群算法的飞行曲线与遗传算法相似，不过其飞行目标更加集中，遗传算法的进化曲线比较散乱，这也图像了它们的区别，进化-不向最优解靠近，群智能-向最优解靠近。
实验2.使用正态分布相除为飞行距离的杜鹃搜索算法

参数	值
问题维度(维度)	2
杜鹃数量(种群数)	20
搜索次数(最大迭代次数)	50
最大步长	1
飞行方式	正态分布随机数相除
宿主发现概率	0.3
取值范围	（-100，100）
实验次数	10

正态分布随机数相除

　　上面的飞行路线图与使用levy飞行时的路线图好像没什么差别，都是有较少飞到了较远的位置，然后飞行轨迹越来越少。我们再来看看结果。

	值
最优值	1.0910862398043029E-6
最差值	2.1833086940861702E-4
平均值	4.1908193647164885E-5

对比使用levy飞行的杜鹃搜索算法结果，使用正态分布相除的杜鹃搜索算法的结果更差，不过差距不大。对比它们的飞行公式可知，当作为分母的正态分布随机数的绝对值<1时，使用levy飞行方式会使得飞行长度更小，而作为分布的标准正态分布随机数的绝对值小于1的概率约为68%，这说明使用levy飞行的杜鹃搜索算法的飞行精度会更高，但是使用正态分布相除的杜鹃搜索算法的搜索能力会更强那么一点。
实验3.去除levy飞行杜鹃搜索算法
　　前面看了使用不同飞行方式的杜鹃搜索算法，我们再来看看去除levy飞行的杜鹃搜索算法，此时，杜鹃们只会向着最优位置飞行，是不是像一个弱化的人工蜂群算法？

参数	值
问题维度(维度)	2
杜鹃数量(种群数)	20
搜索次数(最大迭代次数)	50
最大步长	1
飞行方式	飞向最优位置
宿主发现概率	0.3
取值范围	（-100，100）
实验次数	10

无·levy飞行

　　从图像可以看出，没有了levy飞行的杜鹃们，它们的收敛速度变快了，同时，它们的飞行路线明显少于标准杜鹃搜索算法，这表明没有levy的杜鹃们的搜索能力弱于标准杜鹃搜索算法，我们看一看结果。

	值
最优值	1.2450419211891007E-19
最差值	0.0606152612083874
平均值	0.008891217058396326

结果与我预料的一致，算法的搜索能力较弱，但是收敛速度和收敛性较好，当有杜鹃“出生在罗马”时，其他个体迅速靠近可能得出进度超高的结果，而其他情况则是只能找到大致的结果，精确度较低。

5.总结

杜鹃搜索算法的探究到此也告一段落，杜鹃搜索算法的流程相对比较简单，但是杜鹃们的搜索行为则比较复杂，我们较为详细的看了levy飞行的实现以及其分布的特点，可以看出levy飞行实际上实现了一个类似与买彩票的过程，不得奖或的小奖的概率较大，但是得大奖的概率非常低，的大奖一次既可以改变（人生）轨迹。同时，由于levy飞行的实现方式过于复杂，也给出了一个结果较为相似但过程更加简单的方式-正态分布随机数相除，出了精度有点差异外，分布情况大致相同。
　　杜鹃搜索算法的流程如此简单，仅凭levy飞行就能得出如此结果，那么我们是不是可以详细研究一下《随机过程》，说不定下一个算法就使用了brown过程或是poisson过程，又发明了一个什么燕子算法、大雁算法甚么的。
以下指标纯属个人yy,仅供参考

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

目录
 上一篇优化算法笔记（八）人工蜂群算法
 下一篇优化算法笔记（十）萤火虫算法

优化算法matlab实现（九）杜鹃搜索算法matlab实现

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