计算机应用 ›› 2013, Vol. 33 ›› Issue (06): 1566-1570.DOI: 10.3724/SP.J.1087.2013.01566

• 先进计算 • 上一篇    下一篇

二进制布谷鸟搜索算法

冯登科,阮奇,杜利敏   

  1. 桂林电子科技大学 广西无线宽带通信与信号处理重点实验室,广西 桂林 541004
  • 收稿日期:2012-12-14 修回日期:2013-01-19 出版日期:2013-06-01 发布日期:2013-06-05
  • 通讯作者: 阮奇
  • 作者简介:冯登科(1987-),男,河南郑州人,硕士研究生,主要研究方向:化工过程模拟与优化、演化算法;阮奇(1956-),男,福建古田人,教授,主要研究方向:化工过程模拟与优化、演化算法;杜利敏(1988-),男,福建漳平人,主要研究方向:化工传质与分离模拟与优化、演化算法。
  • 基金资助:

    福建省教育厅科技基金资助项目(JB08001)

Binary cuckoo search algorithm

FENG Dengke,RUAN Qi,DU Limin   

  1. College of Chemistry and Chemical Engineering, Fuzhou University, Fuzhou Fujian 350108,China
  • Received:2012-12-14 Revised:2013-01-19 Online:2013-06-05 Published:2013-06-01
  • Contact: RUAN Qi

摘要: 为了寻找求解NP完全问题的新算法,采用二进制编码串表示鸟巢的位置,对布谷鸟寻找新鸟巢的Lévy飞行路径分别按照Kennedy和Eberha公式及刘建华公式进行二进制代码变换,引入二进制编码控制系数对变换得到的二进制编码进行混合更新,保留布谷鸟蛋被淘汰的机制等方法将新型高效的布谷鸟搜索(CS)算法改进为二进制布谷鸟搜索(BCS)算法。将BCS算法用于求解背包问题,结果好于遗传算法和几种混合遗传算法;将BCS算法用于求解旅行商问题,结果好于遗传算法、蚁群算法和微粒群算法,但略差于改进的惯性权重自适应调整微粒群优化算法。二进制布谷鸟搜索算法是求解NP完全问题的新型高效算法。

关键词: 二进制, 布谷鸟搜索算法, NP完全问题, 背包问题, 旅行商问题

Abstract: In order to find a new algorithm to solve the NP-complete 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 NP-complete problem, BCS algorithm is a new efficient algorithm.

Key words: binary, Cuckoo Search (CS) algorithm, NP-complete problem, knapsack problem, Traveling Salesman Problem (TSP)

中图分类号: