摘要
多背包问题(MKP)是一个求解难度极大的背包问题。为了基于差分演化(DE)求解MKP,首先建立了MKP的整数规划模型,在利用模运算构造简单且有效的新型传递函数基础上,提出了一个新颖离散差分演化算法MODDE;基于贪心策略提出了消除MKP不可行解的一个有效算法GROA,由此利用MODDE给出了求解MKP的一种新方法。最后,利用MODDE求解30个国际通用的MKP实例,通过与四个代表性演化算法的比较表明,MODDE不仅计算结果优,而且算法的稳定性强,是求解MKP的一个高效算法。
The multiple knapsack problem(MKP)is a special knapsack problem with great difficulty.In order to solve MKP by differential evolution(DE),this paper firstly established the integer programming model of MKP.Based on a simple and efficient new transfer function based on modulo operation,it proposed a novel discrete differential evolution algorithm MODDE.Then,the method used an efficient algorithm GROA to eliminate the unfeasible solution of MKP by greedy strategy.Therefore,this paper proposed a new method for solving MKP based on MODDE.Finally,it used MODDE to solve 30 international instances of MKP.Comparing with 4 representative evolution algorithms show that MODDE not only has better calculation results,but also has stronger stability.It is indeed an efficient algorithm for solving MKP.
作者
王丽娜
张寒崧
孙菲
高泽贤
贺毅朝
Wang Lina;Zhang Hansong;Sun Fei;Gao Zexian;He Yichao(School of Information Engineering,Shijiazhuang 050031,China;Laboratory of Big Data&Computing Intelligence,Hebei GEO University,Shijiazhuang 050031,China)
出处
《计算机应用研究》
CSCD
北大核心
2023年第8期2334-2339,2360,共7页
Application Research of Computers
基金
河北省自然科学基金资助项目(F2020403013)
河北省高等学校科学技术研究项目(ZD2021016)
河北省高等学校科学技术研究项目青年基金资助项目(QN2019075)
河北地质大学2023年国家预研资助项目(KY202307)。
关键词
演化算法
差分演化
多背包问题
模运算
evolutionary algorithm
differential evolution
multiple knapsack problem
modulo operation
