Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (32): 12-14.DOI: 10.3778/j.issn.1002-8331.2008.32.004

• 博士论坛 • Previous Articles     Next Articles

Improved differential evolution algorithm for knapsack problem

DENG Chang-shou1,2,LIANG Chang-yong1   

  1. 1.Institute of Computer Network System,Hefei University of Technology,Hefei 230009,China
    2.School of Information Science and Technology,Jiujiang University,Jiujiang,Jiangxi 332005,China
  • Received:2008-07-29 Revised:2008-08-18 Online:2008-11-11 Published:2008-11-11
  • Contact: DENG Chang-shou

求解背包问题的改进差异演化算法

邓长寿1,2,梁昌勇1   

  1. 1.合肥工业大学 计算机网络系统研究所,合肥 230009
    2.九江学院 信息科学与技术学院,江西 九江 332005
  • 通讯作者: 邓长寿

Abstract: An improved differential evolution algorithm was proposed to solve the classical knapsack problem.The selection operation in original differential evolution was adapted to deal with constraints directly.Using a new range encoding mapping,the differential evolution algorithm can be used to deal with discrete optimization problem.The simulation results of the improved differential evolution algorithm show,compared with other evolution algorithm,the improved differential evolution is effective in solving 0-1 Knapsack Problems.

Key words: knapsack problem, differential evolution, range encoding mapping, selection operation

摘要: 提出一种求解0-1背包问题的改进差异演化算法。首先对差异演化算法的选择操作进行修改,得到的改进差异演化算法可以直接有效地处理约束优化问题。其次,利用一种新的区间编码映射机制,将差异演化算法扩展到求解离散领域优化问题。仿真实验结果表明,与其他进化算法相比,改进差异演化算法求解经典背包问题时,求解精度高,收敛速度快,是求解经典背包问题的一种高效算法。

关键词: 背包问题, 差异演化, 区间编码映射, 选择操作