计算机应用 ›› 2013, Vol. 33 ›› Issue (09): 2557-2561.DOI: 10.11772/j.issn.1001-9081.2013.09.2557

• 人工智能 • 上一篇    下一篇

基于贪婪离散类电磁机制算法求解背包问题

王建龙,孙合明   

  1. 河海大学 理学院, 南京 211100
  • 收稿日期:2013-04-07 修回日期:2013-05-12 出版日期:2013-09-01 发布日期:2013-10-18
  • 通讯作者: 王建龙
  • 作者简介:王建龙(1988-),男,江苏兴化人,硕士研究生,主要研究方向:智能算法、运筹学;
    孙合明(1970-),男,山东诸城人,副教授,博士,主要研究方向:智能算法、人工智能。

Study Knapsack Problem Based On Greedy Discrete Electromagnetism-like Mechanism Algorithm

WANG Jianlong,SUN Heming   

  1. College of Sciences, Hohai University, Nanjing Jiangsu 211100, China
  • Received:2013-04-07 Revised:2013-05-12 Online:2013-10-18 Published:2013-09-01
  • Contact: WANG Jianlong

摘要: 针对基本类电磁机制算法不能够有效解决离散型的背包问题,提出了一种贪婪离散类电磁机制算法。首先,提出一种交叉操作;然后,利用提出的交叉操作对基本类电磁机制算法中的合力计算公式和粒子移动方法进行修改,使其能够适用于离散型问题;最后,引入贪婪算法的机制来处理经过类电磁机制算法迭代得到的解,使这些解满足背包问题的约束条件。通过对3个经典的背包测试问题进行的测试结果表明:该算法可以解决离散型的背包问题,并且具有较优的求解性能。

关键词: 类电磁机制算法, 背包问题, 离散, 约束条件, 贪婪算法

Abstract: The basic Electromagnetism-like Mechanism (EM) algorithm cannot solve the discrete problems like knapsack problem. A new algorithm called Greedy Discrete Electromagnetism-like Mechanism (GDEM) algorithm was proposed. Firstly, a cross-operating was proposed; then the operating was used to modify the methods of the force calculation and particles movement in the basic EM algorithm; at last, greedy algorithm was introduced to process the constraint condition. Based on the three classical test knapsack problems, the results have shown that GDEM algorithm can solve knapsack problems efficiently.

Key words: Electromagnetism-like Mechanism (EM) algorithm, Knapsack Problem (KP), discrete, constraint condition, greedy algorithm

中图分类号: