.基于模运算的新颖离散差分演化算法求解多背包问题  

Novel discrete differential evolution algorithm based on modulo operation for solving multiple knapsack problem

作　　者：王丽娜 张寒崧 孙菲 高泽贤 贺毅朝 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)

机构地区：[1]河北地质大学信息工程学院,石家庄050031 [2]河北地质大学大数据与计算智能实验室,石家庄050031

出　　处：《计算机应用研究》2023年第8期2334-2339,2360,共7页Application Research of Computers

基　　金：河北省自然科学基金资助项目(F2020403013);河北省高等学校科学技术研究项目(ZD2021016);河北省高等学校科学技术研究项目青年基金资助项目(QN2019075);河北地质大学2023年国家预研资助项目(KY202307)。

摘　　要：多背包问题(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.

关 键 词：演化算法 差分演化 多背包问题 模运算 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]