• 人工智能 •

### 改进二进制布谷鸟搜索算法求解多维背包问题

1. 1. 西安建筑科技大学 管理学院, 西安710055;
2. 武警工程大学 装备工程学院, 西安710086
• 收稿日期:2014-08-14 修回日期:2014-09-22 出版日期:2015-01-01 发布日期:2015-01-26
• 通讯作者: 张晶
• 作者简介:张晶(1981-),女,陕西西安人,博士,主要研究方向:投资决策、资产管理、运筹学、智能计算;吴虎胜(1986-),男,湖北荆门人,博士研究生,主要研究方向:信息系统工程、智能决策、智能计算、军事装备学.
• 基金资助:

陕西省重点学科专项(E08001,E08003,E08005);陕西省教育厅科研计划项目(2013JK0185);陕西省高校重点研究基地建设专项(DA08046);西安建筑科技大学人才科技基金资助项目(RC1324).

### Modified binary cuckoo search algorithm for multidimensional knapsack problem

1. 1. School of Management, Xi'an University of Architecture and Technology, Xi'an Shaanxi 710055, China;
2. Materiel Engineering Institute, Engineering University of Armed Police Force, Xi'an Shaanxi 710086, China
• Received:2014-08-14 Revised:2014-09-22 Online:2015-01-01 Published:2015-01-26

Abstract:

The Multidimensional Knapsack Problem (MKP) is a typical multi-constraint combinatorial problem. In order to solve this problem, a Modified Binary Cuckoo Search (MBCS) algorithm was proposed. Firstly, with the help of classical binary code transformer, the Binary Cuckoo Search (BCS) algorithm was built; Secondly, the virus evolution mechanism and virus infection operation were introduced into the BCS. Specifically, on one hand, it made the position of bird's nest have mutation mechanism, which could improve the diversity of the population; on another hand, the main groups that consisted of nest position transmitted information cross the vertical generations and guided the global search, while the virus groups transfered evolutionary information cross the same generation through virus infection and guided the local search. These improved the convergence speed and decreased the probability of falling into the local optimum. Thirdly, the hybrid repair strategy for infeasible solutions was designed according to the characteristics of the MKP. At last, comparison experiments among the MBCS algorithm, Quantum Genetic Algorithm (QGA), Binary Particle Swarm Optimization (BPSO) algorithm and BCS algorithm were given on 15 different problems from ELIB and OR_LIB database. The experimental results show that the computational error and standard deviation of MBCS are less than 1% and 170, respectively, which shows the MBCS algorithm can achieve better solutions with good accuracy and robustness than QGA, BPSO and BCS algorithm. It is an effective algorithm in solving NP-hard problems such as the MKP.