布谷鸟算法课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,1,布谷鸟算法,Cuckoo Search,1布谷鸟算法Cuckoo Search,启发式算法,时间,名称,来源,1950-1955,模式搜索,1960-1965,随机搜索,1975,遗传算法,1990,文化基因算法,1990-1995,蚁群算法,模拟蚁群觅食过程,1995,粒子群算法,鸟类和鱼类群体运动行为,2000,和声算法,/,蜂群算法,即兴音乐创作,/,蜜蜂采蜜过程,2005,人工萤火虫优化算法,萤火虫通过通过荧光进行信息交流,2009,布谷鸟算法,布谷鸟孵育行为,启发式算法时间名称来源1950-1955模式搜索1960-1,背景起源,布谷鸟的孵育寄生行为,某些种属的布谷鸟将自己的卵偷偷产入宿主巢穴，由于布谷鸟后代的孵化时间比宿主的幼雏早，孵化的幼雏会本能地破坏同一巢穴中其他的卵,(,推出巢穴,),，并发出比宿主幼雏更响亮的叫声。很多宿主通过后代的叫声大小判断其健康程度,而健康后代获得的食物较多,进而拥有更高的存活率。在某些情况下,宿主也会发现巢穴中的陌生卵。这时,宿主将遗弃该巢穴,并选择其他地方重新筑巢。在与宿主不断的生存竞争中， 布谷鸟的卵和幼雏叫声均朝着模拟宿主的方向发展,以对抗宿主不断进化的分辨能力。,背景起源布谷鸟的孵育寄生行为 某些种属的布谷鸟将自己,背景起源,莱维飞行,在自然界中，动物寻找食物采用随机的方式。一般情况下，动物觅食路径实际上是一个随机游走，因为下一步的行动是取决于两个因素，一个是当前的位置,/,状态，另一个是过渡到下一个位置的概率。,莱维飞行行走的步长满足一个重尾,( heavy-tailed),的稳定分布,在这种形式的行走中,短距离的探索与偶尔较长距离的行走相间。在智能优化算法中采用莱维飞行,能扩大搜索范围、增加种群多样性,更容易跳出局部最优点。,背景起源莱维飞行 在自然界中，动物寻找食物采用随机的,CS,算法,国内外研究进展,分类,学者,观点,步长,Walton,等人,针对,Levy flights,随机游动中的,Levy,随机步长大小提出一种改进版本以加强局部搜索,Tuba,等人,针对偏好随机游动中的步长提出一种基于种群排序的改进版本,自适应,Valian,等人,提出了一种自适应步长和自适应发现概率的,CS,算法,Layeb,等人,引入量子比特、量子纠缠以及量子变异等量子计算概念,以提高,CS,算法种群的多样性,并成功地应用于求解装箱问题,与其他算法结合,Ghodrati,等人,借鉴,PSO,算法中全局最优和个体最优的概念,在,CS,算法,Levy flights,随机游动和偏好随机游动之间引入,PSO,组件,Wang,等人,将,PSO,与,CS,串行,在每次迭代过程中首先用,PSO,算法优化种群,并记录全局最优和个体最优,其次采用,CS,算法对种群个体最优继续寻优,CS算法国内外研究进展分类学者观点步长Walton 等人针,CS,算法,基本假设,1,每只布谷鸟一次产一个卵,并随机选择寄生巢来孵化它,;,2,在随机选择的一组寄生巢中,最好的寄生巢将会被保留到下一代,;,3,可利用的寄生巢数量是固定的,一个寄生巢的主人能发现一个外来鸟蛋的概率为,.(,即新的解决方案的概率为,),CS算法基本假设1 每只布谷鸟一次产一个卵, 并随机选择寄,CS,算法,基本流程,CS算法基本流程,CS,算法,基本流程,布谷鸟位置更新公式：,表示第,i,个鸟巢在第,g,代的鸟巢位置,表示点对点乘法,表示步长控制量，通常取,1,表示莱维随机搜索路径,(1),CS算法基本流程布谷鸟位置更新公式：表示第i个鸟巢在第g代,CS,算法,基本流程,(2),步长公式：,：常数,:,当前最优解,(3),服从莱维概率分布,CS算法基本流程(2)步长公式：常数:当前最优解(3)服,9,CS,算法,基本流程,为了便于计算，采用下列公式产生,Levy,随机数,u,v,服从标准正态分布，,=1.5,CS算法基本流程为了便于计算，采用下列公式产生Levy随机,CS,算法,基本流程,综合上述公式，布谷鸟位置更新公式如下：,（,4,）,按一定概率丢弃部分解后，采用偏好随机游走重新生成相同数量的新解,r,是缩放因子，是（,0,1,）区间内的均匀分布随机数,：表示,g,代的两个随机数,CS算法基本流程综合上述公式，布谷鸟位置更新公式如下：（4,11,改进的,CS,算法,自适应步长的,CS,算法,在标准的布谷鸟优化算法中，利用莱维飞行随机产生步长，不利于计算。当步长较小时，会降低搜索速度，但步长较大时，会降低搜索精度，因此提出了自适应步长的布谷鸟搜索算法，该算法根据不同阶段的搜索结果，自适应的调整步长的大小。引入公式,:,：第,i,个鸟巢的位置,：当前最优的鸟巢位置,：最优位置与剩余鸟巢位置的最大距离,：最大步长,：最小步长,改进的CS算法自适应步长的CS算法在标准的布谷鸟优化算法中,改进的,CS,算法,基于共轭梯度的,CS,算法,共扼梯度算法是沿着己知点附近的一组共扼方向搜索，能够充分的利用局部区域的信息，有较强的局部搜索能力，将其引入到,CS,算法中，进而提高,CS,算法的收敛速度与计算精度。,主要思想：,将更新后位置的梯度与共轭因子的乘积加到该位置的负梯度上，利用线性组合构造出新的共轭方向，沿着该方向进行搜索,改进的CS算法基于共轭梯度的CS算法共扼梯度算法是沿着己知,CS,算法,使用范围,多目标 多约束的优化问题，包括,N-P,问题,CS算法使用范围多目标 多约束的优化问题，包括N-P问题,CS,算法验证,Himmelblau,问题,约束条件：,CS算法验证Himmelblau问题约束条件：,CS,算法验证,Himmelblau,问题,CS算法验证Himmelblau问题,CS,算法,优势,1,一种群智能算法（与粒子群算法以及遗传算法类似），但同时引入了生物学进化论（类似于和声算法）；,2,由于莱维飞行的步长满足重尾的稳定分布，因此这种随机搜索更有效；,3,与遗传算法和粒子群算法相比，参数更少，本质上只有一个,P,。,CS算法优势1 一种群智能算法（与粒子群算法以及遗传算法类,