群体智能优化算法布谷鸟搜索Word文件下载.docx
- 文档编号:3022917
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:14
- 大小:140.27KB
群体智能优化算法布谷鸟搜索Word文件下载.docx
《群体智能优化算法布谷鸟搜索Word文件下载.docx》由会员分享,可在线阅读,更多相关《群体智能优化算法布谷鸟搜索Word文件下载.docx(14页珍藏版)》请在冰点文库上搜索。
如果一个随机变量只取不同的值,比如1,2,那么它就是离散的;
如果它可以在一个区间内取任意值,那它就是连续的。
这些通常用曲线下的面积或积分表示。
随机变量X在一组结果A上的概率,就是A上和曲线下之间的面积,这条曲线下的总面积必须是1,对于集合A中的任何元素都不应该有负值。
这样的曲线称为密度曲线。
随机游走
随机游走(记为SN)是一系列随机步的和,每一步都由一个随机变量Xi表达:
(1)
随机游走的长度可以是固定的,也可以是可变的(取决于步长)。
幂律
当一个量相对变化时会导致两一个量成比例的相对变化时,需要应用幂律(比例律),幂律分布的一般形式是:
(2)
其中X和Y是目标变量,α是律指数,k为常量。
赫维赛德函数(阶跃函数)
通常用H或θ表示,用于表达分段常数函数或广义函数。
作为分段函数时:
(3)
作为广义函数:
(4)
简化表示为:
(5)
Lé
vy(莱维)分布
vy分布是非负随机变量的稳定连续概率分布,可以用以下简单的方式表达:
(6)
其中µ
是最小步长,γ是尺度参数。
vy飞行
vy飞行是步长服从Lé
vy分布的随机游走,通过下式表达:
(7)
其中β是一个索引。
以下为布谷鸟搜索的伪代码和算法流程图。
Begin
目标函数f(I),I=(i1,i2,…,id)T
生成初始种群
forn个寄主巢穴:
Ij(j=1,2,…,n)
while(t<
MaxGeneration)||(停止准则)
根据Lé
vy飞行随机选择布谷鸟
计算适应度值Fj
在n中随机选择巢穴(假设为k)
if(Fj>
Fk)
使用新解替换k
end
抛弃一小部分(pα)更糟糕的巢穴并建立新巢
保留最优解(或优质解的巢穴)
对解进行排序并考虑最优解
endwhile
后处理结果和可视化
end
图1布谷鸟搜索算法流程图
布谷鸟搜索的优点
布谷鸟搜索(CS)有很多优势:
●布谷鸟搜索在搜索空间探索时,在局部搜索和多样性或随机性之间保持了有效的平衡;
●布谷鸟只包含两个控制参数:
种群大小n和概率pα,使得算法更简单更通用;
●如果种群大小固定,则仅通过来pα控制精英(将最优解带到下一代以构造新的解)、随机均衡和局部搜索;
●布谷鸟搜索具有高效的随机化,并有大步长的可能性;
●收敛率pα与无关,因此对于每一个新的问题,不需要调整参数;
●因其通用性可以应用于各种优化问题;
●在多峰函数上,它的求解优于PSO和GA。
布谷鸟搜索的数学证明
如前所述,布谷鸟搜索通过Lé
vy飞行进行全局搜索或探索,飞行中步长可变并且进行突然90°
的转弯,偶尔的大步长可以保证搜索不回陷入到局部最优。
该算法执行两种类型的搜索:
局部搜索和全局搜索。
局部搜素通过局部随机游走执行:
(8)
其中xj和xk为随机选择的解,H(µ
)为赫维赛德函数,pα是用于平衡局部和全局随机游走的切换参数,s为步长,ε为均匀分布的随机数。
全局搜索通过Lé
vy飞行执行:
(9)
其中α>
0为步长缩放因子,且
(10)
其中
。
vy分布的随机游走:
(11)
通过Lé
vy飞行生成的随机数由通过正太分布创建的随机方向选择组成,步长使用Mantegna算法生成:
(12)
和ν服从正太分布:
和
(13)
(14)
设r∈[0,1],与发现/切换概率pα相比得到全局分支:
(15)
因为CS算法是一个随机搜索算法,我们可以总结为以下主要步骤:
1.初始种群由n个随机位置的巢构成,X={x10,x20,...,xn0},然后评估它们的目标函数值,以找到当前的全局最佳gt0;
2.由下式更新解:
(16)
3.从均匀分布[0,1]中取随机数r。
如果r>
pα,则更新xi(t+1)。
然后评估新解,找到新的全局最佳gt∗;
4.如果满足停止要求,则gt∗是目前为止发现的最好的全局解。
否则,返回步骤2。
布谷鸟搜索的变种
离散布谷鸟搜索
离散布谷鸟旨在解决像旅行商(TSP)、调度这样的组合问题。
组合问题中组合的数量随着问题的规模呈指数增长,解决这样的问题需要大量的计算。
Ouaarab,Ahiod和Yang(2014)[4]针对TSP提出了布谷鸟搜索的离散版本,Ouyang等(2013)[5]提出了求解环形TSP的离散布谷鸟搜索。
改进的布谷鸟搜索
提出的改进将布谷鸟作为控制集中和分散的第一层,种群是第二个控制层。
增加了一种新型的更聪明的布谷鸟用于种群重组,这些新的布谷鸟能够改变它们的寄主巢穴以降低被遗弃的机会,这样就有了新的一小部分布谷鸟pc,其首先通过Levy飞行搜索寄主巢穴(新解),然后从当前解寻找更优的解。
以下为改进布谷鸟搜索的伪代码:
目标函数f(I),I=(i1,i2,…,id)T
生成初始种群
for(n)个巢穴:
while(t<
MaxGeneration)||(停止准则)
使用一小部分智能布谷鸟(pc)进行搜索
使用Levy飞行随机选择一只布谷鸟
计算其适应度Fj
从hn中随机选择一个巢穴,例如k
if(Fj>
使用新解替换k
endif
遗弃一小部分(Pa)糟糕的解,构建新的解
记录最优解
endwhile
结果后处理及可视化
作者在算法中使用了扰动,使用局部扰动使得算法足够灵活,可以适应其他优化问题。
二进制布谷鸟搜索
优化问题可以是连续的,其中解可以用一组实数表示,也可以是离散的,可以用一组整数表示。
然而,在二进制优化中,解是由一组位表示的。
二进制版本的布谷鸟搜索(BCS)可应用于路由、调度、特征选择等问题。
在使用Levy飞行的原始CS算法中,解表示为连续搜索空间中的实数集合,这些都需要转换成二进制值,以适应离散二进制版本的布谷鸟搜索。
BCS有两个主要方面(Pereira等,2014)[6]:
●二进制布谷鸟动态,包括
使用Levy飞行获得新解;
二进制解的表达(BSR)以寻找每只布谷鸟移动的可能性。
●目标函数和选择算子—其原理与遗传算法相同
设xi为[0,1]上具有连续值的解,xi’为二进制表达的解,使用sigmoid函数对值进行转换:
(17)
其中S(xi)代表xi’的变动机会。
为了确定二进制解xi’,S(xi)在解x的每一维i上与生成的随机数γ比较,如果变动机会大于γ,二进制值为1,否则为0:
(18)
混沌布谷鸟搜索(ChaoticCuckooSearch,CCS)
在CCS中将混沌理论融入到了布谷鸟搜索技术中,混沌理论研究高度敏感系统的行为,其中初始位置的微小变化会对系统的行为产生很大的影响,混沌具有非重复和遍历性的特点,便于快速搜索。
同时也引入了遗传算法中的精英概念,将最优布谷鸟代入下一代,以构建新的更优解。
Wang等(2016)[7]提出的CCS使用一个混沌可变步长α,可通过归一化的混沌地图(展示混沌行为)进行调整,归一化混沌地图后,其总是在[0,2]内变化。
精英可以防止最优布谷鸟随着解的更新变差。
以下是混沌布谷鸟搜索的伪代码:
Begin:
Step1:
初始化。
设置代计数器i=1,随机初始化种群P,随机设置pa和混沌地图的初始值c0,以及精英参数KEEP。
Step2:
Whilet<
MaxGeneration
根据适应度值对种群进行排序
KEEP←最优布谷鸟
使用混沌地图更新步长(α=ci+1)
随机选择一个布谷鸟(假如i),通过执行Levy飞行替换该解
计算其适应度值Fi
在n中随机选择一个巢穴(假如k)
if(Fi<
endif
使用新解替换一小部分(pa)糟糕解
使用KEEP个最优布谷鸟替换KEEP个最劣布谷鸟
对种群进行排序以确定当前最优
t=t+1
endwhile
并行布谷鸟搜索
并行化是受自然界启发基于种群算法的自然拓展,Tzy-Luen等(2016)[8]提出了并行布谷鸟搜索。
该算法将主种群分解成子种群,从而在搜索解空间时增加了多样性。
并行布谷鸟搜索的伪代码:
目标函数f(n),n=(n1,…,nd)T
生成n个巢穴的初始主种群np
将种群分解成子种群,每个子种群1…p在相同的搜索空间中并行执行布谷鸟搜索
while(i<
停止准则)
子种群1…p并行地
通过Levy飞行随机选择一只布谷鸟i
计算其适应度值Fi
从p中随机选择一个巢穴(假如s)
if(Fi>
Fs)
使用新解替换s
end
丢弃一小部分(pa)劣质巢穴,并建立新的巢穴
保留最优解
对解进行排序,找到最优解
每n代同步最优巢穴
高斯布谷鸟搜索
基础的布谷鸟搜索虽然可以有效地找到最优解,但是不能保证快速地收敛和精度,为了解决这个问题,Zheng和Zhou(2012)[9]对原始算法引入了一些改进:
(19)
其中σ0和µ
为常数,k为当前代数。
因此新解通过下式得到:
(20)
其中α是与问题规模相关的步长,大多数情况下取1,基于高斯分布的布谷鸟搜索的伪代码如下:
生成h个巢穴的初始种群ni
MaxGeneration或停止准则)
根据高斯分布随机选择一只布谷鸟
从h中随机选择一个巢穴(假如k)
参考文献
1.Nayyar,A.,D.-N.Le,andN.Nhu,AdvancesinSwarmIntelligenceforOptimizingProblemsinComputerScience.2018,NewYork:
ChapmanandHall/CRC.
2.Yang,X.andD.Suash.CuckooSearchviaLé
vyflights.in2009WorldCongressonNature&
BiologicallyInspiredComputing(NaBIC).2009.
3.Yang,X.-S.,CuckooSearchandFireflyAlgorithm:
TheoryandApplications.Vol.516.2014.
4.Ouaarab,A.,B.Ahiod,andX.-S.Yang,Discretecuckoosearchalgorithmforthetravellingsalesmanproblem.NeuralComputingandApplications,2014.24(7):
p.1659-1669.
5.Ouyang,X.,etal.,ANovelDiscreteCuckooSearchAlgorithmforSphericalTravelingSalesmanProblem.AppliedMathematics&
InformationSciences,2013.7
(2):
p.777-784.
6.Pereira,L.,etal.,ABinaryCuckooSearchandItsApplicationforFeatureSelection.2014.p.141-154.
7.Wang,G.-G.,etal.,Chaoticcuckoosearch.SoftComputing,2016.20(9):
p.3349-3362.
8.Tzy-Luen,N.,Y.T.Keat,andR.Abdullah.ParallelCuckooSearchalgorithmonOpenMPfortravelingsalesmanproblem.in20163rdInternationalConferenceonComputerandInformationSciences(ICCOINS).2016.
9.Zheng,H.andY.-Q.Zhou,AnovelCuckooSearchoptimizationalgorithmbaseongaussdistribution.JournalofComputationalInformationSystems,2012.8:
p.4193-4200.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 群体 智能 优化 算法 布谷鸟 搜索