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.

Key words: evolutionary computation, Binary Cuckoo Search (BCS) algorithm, virus mechanism, Multidimensional Knapsack Problem (MKP), combinatorial optimization

摘要：

针对多约束组合优化问题——多维背包问题(MKP),提出了一种改进二进制布谷鸟搜索(MBCS)算法.首先,采用经典的二进制代码变换公式构建了二进制布谷鸟搜索(BCS)算法.其次,引入病毒生物进化机制和病毒感染操作,一方面赋予布谷鸟鸟巢位置自变异机制增加种群多样性;一方面将布谷鸟鸟巢位置所组成的主群体的纵向全局搜索和病毒群体的横向局部搜索进行动态结合,进一步提高了算法的收敛速度,降低了陷入局部极值的概率.再次,针对MKP特点设计了不可行解的混合修复策略.最后将MBCS算法同量子遗传算法(QGA)、二进制粒子群优化(BPSO)算法、BCS算法就来源于ELIB数据库和OR_LIB数据库的15个算例进行了仿真对比.实验结果表明,所提算法计算误差均小于1%,标准差小于170,相比这3种算法具有相对更好的寻优精度和求解稳定性,是一种求解多维背包等NP难问题有效的算法.

关键词: 进化计算, 二进制布谷鸟搜索算法, 病毒机制, 多维背包问题, 组合优化