计算机工程 ›› 2009, Vol. 35 ›› Issue (23): 24-26.doi: 10.3969/j.issn.1000-3428.2009.23.009

• 博士论文 • 上一篇    下一篇

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

邓长寿1,2,梁昌勇1   

  1. (1. 合肥工业大学网络系统研究所,合肥 230009;2. 九江学院信息科学与技术学院,九江 332005)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2009-12-05 发布日期:2009-12-05

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

DENG Chang-shou1,2, LIANG Chang-yong1   

  1. (1. Institue of Network System, Hefei University of Technology, Hefei 230009; 2. School of Information Science and Technology, Jiujiang University, Jiujiang 332005)
  • Received:1900-01-01 Revised:1900-01-01 Online:2009-12-05 Published:2009-12-05

摘要: 提出一种混合编码差异演化算法来求解0-1背包问题。通过增加边界约束处理算子和编码映射函数,构建混合编码差异演化算法,求解离散优化问题,并利用贪婪变换方法对演化过程中的不可行解进行修复。仿真实验结果表明了该算法求解0-1背包问题的有效性与适用性。

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

Abstract: 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.

Key words: 0-1 knapsack problem, boundary constraint handling operator, Hybrid Coding Greedy Differential Evolution(HCGDE)

中图分类号: