基于区域分割的差分进化算法求解0-1背包问题  

The Differential Evolution Algorithm Based on Domain Partition for Solving 0-1 Knapsack Problem

作　　者：钟培华[1] 吴志远[1] 胡建根[1] 朱丽[1] 

机构地区：[1]江西农业大学理学院,江西南昌330045

出　　处：《江西师范大学学报（自然科学版）》2012年第4期364-369,共6页Journal of Jiangxi Normal University(Natural Science Edition)

基　　金：江西省教育厅省级教改基金(JXJG-10-4-22);江西农业大学青年基金(1574;2971)资助项目

摘　　要：为了更有效地求解0-1背包问题,提出了基于区域分割的差分进化算法(PDE).为保证变异算子的封闭性,对传统差分进化算法(DE)的变异算子进行了修改.引入区域分割算法以后,解空间中一些没有希望的点被移除,缩小了最优解的搜索范围,增加了找到最优解的概率.将区域分割和贪婪算法相结合,用搜索到的最好解替换了种群中目标函数值最差的个体,保证了种群的多样性.数值实验表明:该算法比文献中的DE算法更稳健,全局搜索能力更强,能以更大的概率找到背包问题的最优解.In order to solve the 0-1 knapsack problems more effectively, a new differential evolution algorithm based on domain partition method is proposed. The mutation operator of traditional differential evolution algorithm （DE） is modified to guarantee the closure of mutation operation. With the domain partition method introduced in and some hopeless points removed off, the searching field of the optimal solution is reduced. Accordingly, the probability of finding the optimal solution is improved. To ensure the diversity of population, the solution with the least object function value is replaced by the best feasible solution found by the domain partition method combined with greedy method. Numerical experiments show that the new aigorithm is of more robustness, of better global searching ability, and of greater probability to find the optimal solution of knapsack problem than those algorithms mentioned in the literatures.

关 键 词：背包问题 差分进化算法 分割 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]