作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (7): 164-167. doi: 10.3969/j.issn.1000-3428.2012.07.054

• 人工智能及识别技术 • 上一篇    下一篇

一种求解背包问题的混合差异演化算法

马立肖,赵占芳   

  1. (石家庄经济学院计算机科学系,石家庄 050031)
  • 收稿日期:2011-05-04 出版日期:2012-04-05 发布日期:2012-04-05
  • 作者简介:马立肖(1979-),女,讲师、硕士,主研方向:演化计算;赵占芳,讲师、硕士
  • 基金资助:
    河北省科技厅基金资助项目(072135193)

Hybrid Differential Evolution Algorithm for Solving Knapsack Problem

MA Li-xiao, ZHAO Zhan-fang   

  1. (Department of Computer Science, Shijiazhuang University of Economics, Shijiazhuang 050031, China)
  • Received:2011-05-04 Online:2012-04-05 Published:2012-04-05

摘要: 为增强差异演化算法在求解背包问题时的局部搜索能力,提出拉马克-鲍德温混合差异演化算法。该算法采用双种群协同进化,以差异演化算法为主体,在演化过程中分别引入拉马克进化和鲍德温效应2种局部搜索算子,引导种群进化方向。仿真实验结果表明,该算法求解精度高,收敛速度快,能够高效求解背包问题。

关键词: 背包问题, 差异演化算法, 拉马克进化, 鲍德温效应, 双重编码机制

Abstract: In order to overcome the shortcomings of a poor ability of local search of Differential Evolutional(DE) for solving Knapsack Problem(KP), Lamarckian-Baldwin hybrid DE algorithm is proposed. The algorithm with two populations are based on the original DE, and the local search operator based on Lamarckian evolution and Baldwin effect are adapted to enhance the individual’s ability of local search, which guides the orientation of evolution. Simulation results of the improved DE algorithm show the algorithm has the advantage of rapid converging and high precision and it is effective in solving KP.

Key words: Knapsack Problem(KP), Differential Evolution(DE) algorithm, Lamarckian evolution, Baldwin effect, dual coding mechanism

中图分类号: