解0-1背包问题的混合编码贪婪DE算法  

Mixed Coding Greedy Differential Evolution Algorithm for 0-1 Knapsack Problem

作　　者：邓长寿[1,2] 梁昌勇[1] 

机构地区：[1]合肥工业大学网络系统研究所,合肥230009 [2]九江学院信息科学与技术学院,九江332005

出　　处：《计算机工程》2009年第23期24-26,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(70771037);江西省教育厅科学技术基金资助项目(GG09347)

摘　　要：提出一种混合编码差异演化算法来求解0-1背包问题。通过增加边界约束处理算子和编码映射函数,构建混合编码差异演化算法,求解离散优化问题,并利用贪婪变换方法对演化过程中的不可行解进行修复。仿真实验结果表明了该算法求解0-1背包问题的有效性与适用性。Hybrid Coding Greedy Differential Evolution（HCGDE） algorithm is proposed for 0-1 knapsack problem. A new operator, boundary-constraint handling operator, and a coding mapping function are embedded into the original Differential Evolution（DE） to construct a hybrid coding DE algorithm, which expands the continuous domain of DE to the discrete domain. During the evolution process, it uses the greedy transform algorithm to fix the infeasible solutions. Results of the numerical experiment show it is effective and useful in solving 0-1 knapsack problem.

关 键 词：0—1背包问题 边界约束处理算子 混合编码贪婪差异演化 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]