求解多维背包的改进差分进化算法  

Improved differential evolution algorithm for solving multidimensional knapsacks

作　　者：韩丽萍 潘大志[1] HAN Liping;PAN Dazhi(School of Mathematics and Information,China West Normal University,Nanchong Sichuan 637009,China)

机构地区：[1]西华师范大学数学与信息学院,四川南充637009

出　　处：《智能计算机与应用》2023年第12期98-101,106,共5页Intelligent Computer and Applications

基　　金：国家自然科学基金(11871059);四川省教育厅自然科学基金(18ZA0469)。

摘　　要：针对多维背包问题,提出了一种改进的差分进化(IDE)算法。该算法保留了基本差分进化算法的交叉策略,同时将特定维数的0-1变异融入其中;为提高算法的收敛性,设计了最大和最小可装入背包的物品数量模型,作为对后续操作产生解的一个条件判断,从而缩小了搜索范围及时间;最后,通过对10个背包测试集进行测试,并与贪心二进制狮群优化(GBLSO)算法、混合粒子群(HPSO)算法进行比较。结果表明,该算法能较好的求得最优解,具有更快的收敛速度及更高的精度。An improved differential evolution(IDE)algorithm is proposed for the multidimensional backpack problem.The algorithm retains the crossover strategy of the basic differential evolution algorithm while incorporating the 0-1 variant of a specific number of dimensions.In order to improve the convergence of the algorithm,a model of the maximum and minimum number of items that can be loaded into the knapsack is designed to serve as a conditional judgment on the subsequent operations to produce a solution,thus narrowing down the scope of the search and its time.Finally,the algorithm is tested by examining a test set of 10 knapsacks and compared to the Greedy Binary Lion Swarm Optimization(GBLSO)algorithm,and Hybrid Particle Swarm(HPSO)algorithm for comparison.The results show that the algorithm can find the optimal solution better,with faster convergence speed and higher accuracy.

关 键 词：多维背包问题 差分进化算法 组合优化 最大、最小装入背包物品数 

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