《布谷鸟算法.ppt》由会员分享,可在线阅读,更多相关《布谷鸟算法.ppt(17页珍藏版)》请在金锄头文库上搜索。
1、1 布谷鸟算法 CuckooSearch 启发式算法 背景起源 布谷鸟的孵育寄生行为 某些种属的布谷鸟将自己的卵偷偷产入宿主巢穴 由于布谷鸟后代的孵化时间比宿主的幼雏早 孵化的幼雏会本能地破坏同一巢穴中其他的卵 推出巢穴 并发出比宿主幼雏更响亮的叫声 很多宿主通过后代的叫声大小判断其健康程度 而健康后代获得的食物较多 进而拥有更高的存活率 在某些情况下 宿主也会发现巢穴中的陌生卵 这时 宿主将遗弃该巢穴 并选择其他地方重新筑巢 在与宿主不断的生存竞争中 布谷鸟的卵和幼雏叫声均朝着模拟宿主的方向发展 以对抗宿主不断进化的分辨能力 背景起源 莱维飞行 在自然界中 动物寻找食物采用随机的方式 一般情
2、况下 动物觅食路径实际上是一个随机游走 因为下一步的行动是取决于两个因素 一个是当前的位置 状态 另一个是过渡到下一个位置的概率 莱维飞行行走的步长满足一个重尾 heavy tailed 的稳定分布 在这种形式的行走中 短距离的探索与偶尔较长距离的行走相间 在智能优化算法中采用莱维飞行 能扩大搜索范围 增加种群多样性 更容易跳出局部最优点 CS算法 国内外研究进展 CS算法 基本假设 1每只布谷鸟一次产一个卵 并随机选择寄生巢来孵化它 2在随机选择的一组寄生巢中 最好的寄生巢将会被保留到下一代 3可利用的寄生巢数量是固定的 一个寄生巢的主人能发现一个外来鸟蛋的概率为 即新的解决方案的概率为 C
3、S算法 基本流程 CS算法 基本流程 布谷鸟位置更新公式 1 CS算法 基本流程 2 步长公式 CS算法 基本流程 为了便于计算 采用下列公式产生Levy随机数 u v服从标准正态分布 1 5 CS算法 基本流程 按一定概率丢弃部分解后 采用偏好随机游走重新生成相同数量的新解 r是缩放因子 是 0 1 区间内的均匀分布随机数 表示g代的两个随机数 改进的CS算法 自适应步长的CS算法 在标准的布谷鸟优化算法中 利用莱维飞行随机产生步长 不利于计算 当步长较小时 会降低搜索速度 但步长较大时 会降低搜索精度 因此提出了自适应步长的布谷鸟搜索算法 该算法根据不同阶段的搜索结果 自适应的调整步长的大
4、小 引入公式 第i个鸟巢的位置 当前最优的鸟巢位置 最优位置与剩余鸟巢位置的最大距离 改进的CS算法 基于共轭梯度的CS算法 共扼梯度算法是沿着己知点附近的一组共扼方向搜索 能够充分的利用局部区域的信息 有较强的局部搜索能力 将其引入到CS算法中 进而提高CS算法的收敛速度与计算精度 主要思想 将更新后位置的梯度与共轭因子的乘积加到该位置的负梯度上 利用线性组合构造出新的共轭方向 沿着该方向进行搜索 CS算法 使用范围 多目标多约束的优化问题 包括N P问题 CS算法验证 Himmelblau问题 约束条件 CS算法验证 Himmelblau问题 CS算法 优势 1一种群智能算法 与粒子群算法以及遗传算法类似 但同时引入了生物学进化论 类似于和声算法 2由于莱维飞行的步长满足重尾的稳定分布 因此这种随机搜索更有效 3与遗传算法和粒子群算法相比 参数更少 本质上只有一个P