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

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

Solution to knapsack problem based on greedy discrete electromagnetism-like mechanism algorithm

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.