一种基于差异演化算法求解折扣{0-1}背包问题的应用研究
Application of Differential Evolution Algorithm for Solving Discounted {0-1} Knapsack Problem
张光桃 1梅妍玭1
作者信息
摘要
折扣{0-1 }背包问题(Discounted(0-1)Knapsack Problem,D { 0-1 } KP)是一个经典的组合优化问题.将差异演化算法中实数编码映射为整数编码,进一步完善约束条件,求得D{0-1 } KP最优解,并使用动态规划算法对改进算法进行验证,验证结果表明,改进后的差异演化算法能够用于求解数据规模大的D{0-1}KP,并能够得到适应度最高的最优个体,即最优解.在验证之后对差异演化算法中两个重要参数进行测试取值,得出使用差异演化算法求解D{0-1} KP收敛速度快、稳定性好的参数取值范围.
Abstract
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 im-proved 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 in-dividual with the highest fitness is the optimal solution.After verification,two important parameters in the dif-ferential evolution algorithm are tested and values are obtained,and the range of parameters with fast conver-gence and good stability for D{ 0-1 } KP is obtained by using the differential evolution algorithm.
关键词
背包问题/差异演化算法/编码映射/适应度Key words
knapsack problems/differential evolution algorithm/encoding mapping/adaptive level引用本文复制引用
出版年
2024
NETL
NSTL
万方数据