解0-1背包问题的二进制差异演化算法  

Binary differential evolution algorithm for 0-1 knapsack problem

作　　者：蔡鸿英[1] 郝志峰[1,2] 王志刚[1] 郭广寒[1] 

机构地区：[1]华南理工大学数学科学学院,广东广州510640 [2]华南理工大学计算机科学与工程学院,广东广州510640

出　　处：《计算机工程与设计》2009年第7期1716-1718,1721,共4页Computer Engineering and Design

摘　　要：针对传统差异演化算法(DE)无法求解采用二进制编码问题的缺点,通过采用新的变异方法,提出了一种用于求解0-1背包问题的二进制差异演化算法,阐明了该算法求解背包问题的具体实现过程。通过多个0-1背包问题的仿真试验,表明了该算法在求解0-1背包问题时不仅能达到最优解,而且收敛速度快,同时也验证了算法在解决二进制编码问题上的可行性和有效性。Since differential evolution can not solve problems which are binary-coded in binary space, in order to overcome the drawback, through the introduction of new methods of variation, a new binary differential evolution （BDE） algorithm bases on three different roles is presented to solve the 0-1 knapsack problem. Experimental results show that our method behaves better in quality of solution and convergence speed, which validates the effective of our method.

关 键 词：背包问题 差异演化 二进制 蚁群算法 粒子群算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]