布谷鸟算法.ppt

布谷鸟算法CuckooSearch启发式算法时间名称来源1950-1955模式搜索1960-1965随机搜索1975遗传算法1990文化基因算法1990-1995蚁群算法模拟蚁群觅食过程1995粒子群算法鸟类和鱼类群体运动行为2000和声算法/蜂群算法即兴音乐创作/蜜蜂采蜜过程2005人工萤火虫优化算法萤火虫通过通过荧光进行信息交流2009布谷鸟算法布谷鸟孵育行为背景起源—布谷鸟的孵育寄生行为某些种属的布谷鸟将自己的卵偷偷产入宿主巢穴,由于布谷鸟后代的孵化时间比宿主的幼雏早,孵化的幼雏会本能地破坏同一巢穴中其他的卵(推出巢穴),并发出比宿主幼雏更响亮的叫声。很多宿主通过后代的叫声大小判断其健康程度,而健康后代获得的食物较多,进而拥有更高的存活率。在某些情况下,宿主也会发现巢穴中的陌生卵。这时,宿主将遗弃该巢穴,并选择其他地方重新筑巢。在与宿主不断的生存竞争中,布谷鸟的卵和幼雏叫声均朝着模拟宿主的方向发展,以对抗宿主不断进化的分辨能力。背景起源—莱维飞行在自然界中,动物寻找食物采用随机的方式。一般情况下,动物觅食路径实际上是一个随机游走,因为下一步的行动是取决于两个因素,一个是当前的位置/状态,另一个是过渡到下一个位置的概率。莱维飞行行走的步长满足一个重尾(heavy-tailed)的稳定分布,在这种形式的行走中,短距离的探索与偶尔较长距离的行走相间。在智能优化算法中采用莱维飞行,能扩大搜索范围、增加种群多样性,更容易跳出局部最优点。CS算法—国内外研究进展分类学者观点步长Walton等人针对Levyflights随机游动中的Levy随机步长大小提出一种改进版本以加强局部搜索Tuba等人针对偏好随机游动中的步长提出一种基于种群排序的改进版本自适应Valian等人提出了一种自适应步长和自适应发现概率的CS算法Layeb等人引入量子比特、量子纠缠以及量子变异等量子计算概念,以提高CS算法种群的多样性,并成功地应用于求解装箱问题与其他算法结合Ghodrati等人借鉴PSO算法中全局最优和个体最优的概念,在CS算法Levyflights随机游动和偏好随机游动之间引入PSO组件Wang等人将PSO与CS串行,在每次迭代过程中首先用PSO算法优化种群,并记录全局最优和个体最优,其次采用CS算法对种群个体最优继续寻优CS算法—基本假设1每只布谷鸟一次产一个卵,并随机选择寄生巢来孵化它;2在随机选择的一组寄生巢中,最好的寄生巢将会被保留到下一代;3可利用的寄生巢数量是固定的,一个寄生巢的主人能发现一个外来鸟蛋的概率为.(即新的解决方案的概率为)CS算法—基本流程CS算法—基本流程布谷鸟位置更新公式:表示第i个鸟巢在第g代的鸟巢位置表示点对点乘法表示步长控制量,通常取1表示莱维随机搜索路径(1)CS算法—基本流程(2)步长公式::常数:当前最优解(3)服从莱维概率分布CS算法—基本流程为了便于计算,采用下列公式产生Levy随机数u,v服从标准正态分布,=