飞行路径分别按照 Kennedy 和 Eberha 公式及刘建华公式进行二进制代码变换， 引入二 进 制编码 控 制 系 数 对 变 换 得 到 的二进制编码进行混合更新， 保留布谷鸟蛋被淘汰的机制等方法将新型高效的布谷鸟搜索( CS) 算法 改 进 为 二 进 制 布 谷鸟搜索( BCS) 算法。将 BCS 算法用于求解背包问题， 结果 好 于 遗 传 算法和 几 种 混 合 遗 传 算法; 将 BCS 算法 用于 求 解旅行商问题， 结果好于遗传算法、 蚁群算法和 微 粒 群 算法， 但 略 差 于 改 进 的 惯 性 权 重 自 适 应 调整 微 粒 群 优化算法。 二进制布谷鸟搜索算法是求解 NP 完全问题的新型高效算法。 关键词： 二进制; 布谷鸟搜索算法; NP 完全问题; 背包问题; 旅行商问题 中图分类号： TP18 ; TP301． 6 文献标志码： A
。与其他方法相比， 使用遗传算法（ Genetic Algorithm，
GA） ［4 － 6］ 、蚁 群 优 化 （ Ant Colony Optimization， ACO ） 算
［7 － 8 ］
、 PSO） 算法［9］ 微粒群优化（ Particle Swarm Optimization，
等这些演化算法求解 NP 完全问题时其计算速度快， 求出的 能够满足人们生产生活的需要 。 但是这些演化 解相对合理， 算法在求解 NP 完全问题时是有随机性的， 并不能保证每次
Binary cuckoo search algorithm
FENG Dengke， RUAN Qi ， DU Limin
( College of Chemistry and Chemical Engineering， Fuzhou University， Fuzhou Fujian 350108 ，China)
Journal of Computer Applications 计算机应用，2013，33( 6) : 1566 － 1570 文章编号： 1001 － 9081 （ 2013 ） 06 － 01566 － 05
ISSN 1001-9081 CODEN JYIIDU
2013-06-01 http: / / www． joca． cn doi： 10． 3724 / SP． J． 1087． 2013． 01566
1
原始 CS 算法
CS 算法是基于布谷鸟的繁殖行为和 Lévy 飞行机制而演
收稿日期： 2013-01-19 ； 修回日期： 2013-02-13 。 基金项目： 福建省教育厅科技基金资助项目（ JB08001 ） 。 作者简介： 冯登科（ 1987 － ） ， 男， 河南郑州人， 硕士研究生， 主要研究方向： 化工过程模拟与优化、 演化算法； 阮奇（ 1956 － ） ， 男， 福建古田 人， 教授， 主要研究方向： 化工过程模拟与优化 、 演化算法； 杜利敏（ 1988 － ） ， 男， 福建漳平人， 主要研究方向： 化工传质与分离模拟与优化、 演化 算法。
*
Abstract: In order to find a new algorithm to solve the NPcomplete problem， the new efficient Cuckoo Search ( CS) algorithm was improved into a Binary Cuckoo Search ( BCS) algorithm by some means． These means include: binary coding strings were used to express the position of bird s nest， the path of Lévy flights that cuckoos searched for new bird s nest was transformed into binary coding respectively according to Kennedy and Eberha s formula and Liu Jianghua's formula， and then a binary coding control factor was introduced to the hybrid update of the transformed binary coding， and the elimination mechanism of cuckoo eggs was reserved． The BCS algorithm performs better than genetic algorithm and some mixed genetic algorithms in solving the knapsack problem， and also better than genetic algorithm， ant colony optimization and particle swarm optimization in solving the traveling salesman problem， but slightly worse than the improved particle swarm optimization through adjusting the inertia weights adaptively． In solving the NPcomplete problem， BCS algorithm is a new efficient algorithm． Key words: binary; Cuckoo Search ( CS) algorithm; NPcomplete problem; knapsack problem; Traveling Salesman Problem ( TSP)
［3 ］
和莱维（ Lévy ） 飞行特性之后 于 2009 年 创 立 了 布 谷 鸟 搜 索 （ Cuckoo Search， CS） 算法， 并用大量的函数对其性能进行了 测试， 结果表明该算法在许多方面的性能已经超过了微粒群 算法和遗传算法： CS 算法具有全局搜索能力强 、 选用参数少、 搜索路径优、 多目标问题求解能力强等优点
二进制布谷鸟搜索算法
冯登科，阮 奇 ，杜 利 敏
*
( 福州大学 化学化工学院， 福州 350108) ( * 通信作者电子邮箱 hys@ fzu． edu． cn)
摘
要： 为了寻找求解 NP 完全问题的新算法， 采用二进 制编码 串 表 示 鸟巢 的 位 置， 对 布 谷鸟寻找 新 鸟巢 的 Lévy
0
来
引言
20 世 纪 70 年 代， NP 完 全 问 题 被 许 多 研 究 者 提 出
［1 － 2 ］
都能用很快的计算速度求出相同的满意解， 因此寻找计算速 求解稳定的新型演化算法具有重要的科学价值 。 度快、 英国剑桥大学的 Yang 等
［10 ］
在研究了布谷鸟的繁殖行为
。通常 NP 完全问题被认为是人们在有限的时间和空
NP 完 间内难以找到其最优解的问题， 随着问题规模的扩大， 全问题的求解难度大大增加 。 然而， 在交通调度、 物流配送、 互联网规划、 工业控制和生物化学计算等众多领域都不可避 免地出现了大量的 NP 完全问题， 快速高效地寻求这些问题 的最优解对人们的生产生活具有重要的现实意义 。到目前为 止， 研究者们已经研究出了很多用于求解 NP 问题的方法， 如 穷举法、 近似算法、 随机算法、 动态规划法、 贪婪算法、 演化算 法等 法
［10 － 13 ］
。 然而， 原
始的 CS 算法只能用于求解连续型的优化问题， 不能用于求 NP 。 解离散型的优化问题如 完全问题 本文将原始的 CS 算 BCS） 算 法改进成为二进制布谷鸟搜索（ Binary Cuckoo Search， 法， 并应用 0 /1 背包问题 （ Knapsack Problem ） 和旅行商问题 （ Traveling Salesman Problem， TSP） 这两类 NP 完全问题对二进 制布谷鸟搜索算法的性能进行了测试 。
（ β －1 ） / 2
（ 5）
短和方向都是高度随机改变的， 很容易从一个区域跃入另外 一个区域， 使得 CS 算法的全局多样性即全局寻优能力特别 CS 算法借鉴了布谷鸟的繁殖行为， 定义布谷 强。另一方面， ［10 ］ 鸟蛋被宿主鸟发现的概率 pa = 0 ． 25 ， 不适应环境的较差 的布谷鸟蛋被淘汰， 适应环境的优秀的布谷鸟蛋被孵化， 保证 新生的布谷鸟群体都是由优秀个体组成， 使得 CS 算法具有 较强的收敛性。 在实际的优化问题中， 鸟巢的位置 x ij 代表所有变量的有 效取值空间， 而鸟巢的适应度代表变量取不同值所对应的目 10 － 11 ］ 。 标函数。具体的 CS 算法流程详见文献［
m +1 位置 x ij 时所经历的路径。因 s 即 Lévy （ λ） 取决于由式（ 4 ） 和式（ 5 ） 产生的两个正态分布随机数 μ 和 ν， μ 和 ν 可大可小、 可正可负， 故布谷鸟每次按 Lévy 飞行机制随机搜索的路径长
{
σμ =
（ 1 + β） sin（ πβ / 2 ） { ΓΓ } ［ （ 1 + β） / 2］ 2 β
［17 ］ 继续飞行， 这样一个过程就符合 Lévy 飞行模式 。 受布谷 ［10 ］ Yang 等 提出了布 鸟的繁殖行为和α × Lévy （ λ） = α × s， 则 Step 即为布谷鸟在解 m 1 ） x 空间中每次按式（ 从旧鸟巢位置 ij 出发随机搜索新鸟巢
谷鸟搜索（ CS） 算法， 并做了以下三个理想的假定： 1 ） 每只布谷鸟只产一个蛋， 并且随机地放在某一个鸟巢 中； 2 ） 放置在宿主鸟巢中的高质量的布谷鸟蛋将会被孵化 出来产生下一代布谷鸟； 3 ） 布谷鸟可以利用的多种多样的宿主鸟巢的数量 n 是 确定的， 布谷鸟放置在宿主鸟巢中的布谷鸟蛋被发现的概率 0， 1］ 。 是 pa ∈ ［ 在这三个假设的前提下， 布谷鸟寻找鸟巢的路径和位置 更新公式 就可以表示为： +1 xm = xm ij ij + α × Lévy （ λ）