摘要：
针对基本类电磁机制算法不能够有效解决离散型的背包问题，提出了一种贪婪离散类电磁机制算法。首先，提出一种交叉操作；然后，利用提出的交叉操作对基本类电磁机制算法中的合力计算公式和粒子移动方法进行修改，使其能够适用于离散型问题；最后，引入贪婪算法的机制来处理经过类电磁机制算法迭代得到的解，使这些解满足背包问题的约束条件。通过对3个经典的背包测试问题进行的测试结果表明：该算法可以解决离散型的背包问题，并且具有较优的求解性能。
关键词： 类电磁机制算法；背包问题；离散；约束条件；贪婪算法
中图分类号：TP301.6
文献标志码：A
0引言
类电磁机制（Electromagnetismlike Mechanism， EM）算法[1-2]是Birbil等于2003年提出的一种新型的基于种群随机的全局优化算法。类电磁机制算法与遗传算法类似，其将问题的一个解比作一个带电粒子，在吸引排斥机制的作用下，每个粒子都排斥较差的粒子，同时被较优的粒子吸引，从而找到全局最优的粒子。随着国内外学者对类电磁机制算法的深入研究，该算法的性能得到了提高，同时被很好地应用到了函数优化、资源管理、工程技术等领域[3-9]。但针对离散型问题的研究还比较少，并且算法的性能也不够理想。
背包问题（Knapsack Problem，KP）是一种组合优化的NP完全问题[10]，解决好背包问题具有一定的实际意义。与背包问题类似的问题出现在了商业、组合数学、计算机复杂性理论、密码学和应用数学等领域。对于小规模的背包问题，完全枚举法、分支定界法等一些传统方法可以高效地求解；而对于一些大规模的背包问题，传统优化算法出现了计算量大、求解结果不理想等问题。智能优化算法被应用到背包问题中，很好地解决了这样的问题[11-14]。受此启发，本文提出一种贪婪离散类电磁机制算法，该算法不仅提出了一种交叉操作，可以较好地解决基本类电磁机制算法中的合力计算和粒子移动公式不能离散化的问题，还引入了贪婪算法，有效地处理了背包问题中存在的约束条件。
1相关问题
1.1类电磁机制算法的基本原理
2贪婪离散类电磁机制算法
2.1基本原理
基本类电磁机制算法适用于连续型的优化问题，为了把类电磁机制算法应用到离散型的优化问题中，本文对基本类电磁机制算法进行修改，并且加入贪婪算法的机制，来处理离散型问题的约束条件。
2.1.1初始化
3.3GDEM算法与其他改进EM算法的性能比较
目前对于基本类电磁机制算法的离散化改进较少，典型的有离散类电磁机制算法解决装配序列问题[7]，离散类电磁机制算法解决旅行商（Travelling Salesman Problem， TSP）问题[8]，还有量子类电磁机制（Quantuminspired Electromagnetismlike Mechanism，QEM）算法解决0/1背包问题[9]等。本节利用实例1～3对GDEM算法进行测试，并与文献[9]中的QEM算法进行对比。本次实验最大迭代次数MAXITER=1000，种群规模m=20，实例3的问题规模分别取100，250和500。首先对实例1和实例2分别进行5次求解，记录每一次的物品价值和对应使用的背包容量，具体情况见表2～3。然后对实例3中每一种群体规模都进行10次求解，记录最大值、平均值以及最小值，具体情况见表3。两种算法求解实例3的过程如图3～5所示。
4结语
为了利用类电磁机制算法解决离散型的背包问题，本文提出了一种交叉操作，对基本类电磁机制算法的合力计算方法以及粒子移动方法进行修改，并将贪婪算法中的选择机制引入到算法中，对背包问题中的约束条件进行处理，提出了一种贪婪离散类电磁机制算法。通过对3个常用的背包问题的求解测试，验证了GDEM算法的有效性；同时将GDEM算法的求解结果与其他智能算法进行比较，对比结果说明了GDEM算法具有较优异的性能。
参考文献：
[1]BIRBIL S I， FANG S C. An electromagnetismlike mechanism for global optimization[J]. Journal of Global Optimization，2003，25（3）：263-282.
[2]BIEBIL S I. Stochastic global optimization techniques[D]. Raleigh： North Carolina State University， Department of Industrial Engineering，2002.
[3]单玉乐，曾建潮，谭瑛.一种改进的无局部搜索的类电磁机制算法[J].太原科技大学学报，2010，31（6）：437-440.
[4]李如琦，李芝荣，凌武能，等.基于类电磁机制算法的配电网重构[J].电力系统保护与控制，2012，40（14）：116-120.
[5]张智晟，龚文杰，段晓燕，等.类电磁机制算法在水电站厂内经济运行中的应用研究[J].电工电能新技术，2011，30（4）：17-20.
[6]张科，曹平.复杂边坡非圆弧滑动面求解的类电磁机制算法[J].中南大学学报：自然科学版，2011，42（10）：3125-3130.
[7]孙禄，张春江，高亮，等.基于离散类电磁机制算法的装配序列规划[J].机械科学与技术，2012，31（3）：353-358.
[8]NIKBAKHSH A， MOHSEN G A， REZA T. A discrete binary version of the electromagnetismlike heuristic for solving traveling salesman problem [C]// Advanced Intelligent Computing Theories and Applications： with Aspects of Artificial Intelligence. Berlin： SpringerVerlag， 2008：123-130.
[9]CHOU Y， CHANG C， CHIU C， et al. Classical and quantuminspired electromagnetismlike mechanism for solving 0/1 knapsack problems[C]// Proceedings of the 2010 IEEE International Conference on Systems， Man and Cybernetics. Piscataway， NJ： IEEE Press， 2010：3211-3218.
[10]GAREY M R， JOHNSON D S. Computers and intractability： a guide to the theory of NPcompleteness[M].San Francisco： W.H. Freeman，1979.
[11]吕晓峰，张勇亮，马羚.一种求解01背包问题的改进遗传算法[J].计算机工程与应用，2011，47（34）：44-46.
[12]何小锋，马良.求解01背包问题的量子蚁群算法[J].计算机工程与应用，2011，47（16）：29-31.
[13]厍向阳，朱命昊，赵亚敏.求解0/1背包问题的改进人工鱼群算法研究[J].计算机工程与应用，2011，47（21）：43-46.
[14]马丰宁，谢龙，郑重.求解背包问题的基因属性保留遗传算法[J].天津大学学报，2010，43（11）：1020-1024.
[15]汪定伟，王俊伟，王洪峰，等.智能优化方法[M].北京：高等教育出版社，2007.
[16]徐青鹤，刘士荣，吕强.基于蚁群混沌行为的离散粒子群算法及其应用[J].计算机科学，2010，37（5）：178-180.