一种基于差异演化算法求解折扣{0-1}背包问题的应用研究  

Application of Differential Evolution Algorithm for Solving Discounted {0-1} Knapsack Problem

作　　者：张光桃[1] 梅妍玭[1] ZHANG Guang-tao;Mei Yan-pin(Yangzhou Polytechnic College,Yangzhou 225009,China)

机构地区：[1]扬州职业大学,江苏扬州225009

出　　处：《扬州职业大学学报》2024年第3期42-46,共5页Journal of Yangzhou Polytechnic College

基　　金：江苏省教育科学“十四五”规划课题(D/2021/03/111)。

摘　　要：折扣{0-1}背包问题(Discounted(0-1)Knapsack Problem,D{0-1}KP)是一个经典的组合优化问题。将差异演化算法中实数编码映射为整数编码,进一步完善约束条件,求得D{0-1}KP最优解,并使用动态规划算法对改进算法进行验证,验证结果表明,改进后的差异演化算法能够用于求解数据规模大的D{0-1}KP,并能够得到适应度最高的最优个体,即最优解。在验证之后对差异演化算法中两个重要参数进行测试取值,得出使用差异演化算法求解D{0-1}KP收敛速度快、稳定性好的参数取值范围。The Discounted(0-1)Knapsack Problem(D{0-1}KP)is a classic combinatorial optimization problem.In this paper,the real number coding in differential evolution algorithm is mapped to integer coding,and the constraint conditions are further improved to obtain the optimal solution of D{0-1}KP,and the improved algorithm is verified by dynamic programming algorithm.The verification results show that the improved differential evolutionary algorithm can be used to solve D{0-1}KP with large data scale.And the optimal individual with the highest fitness is the optimal solution.After verification,two important parameters in the differential evolution algorithm are tested and values are obtained,and the range of parameters with fast convergence and good stability for D{0-1}KP is obtained by using the differential evolution algorithm.

关 键 词：背包问题 差异演化算法 编码映射 适应度 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]