求解折扣{0-1}背包问题的新遗传算法

来源：计算机工程与应用杂志2020年第7期北京时间：

作者：吴聪聪，贺毅朝，赵建立

单位：1.河北地质大学 信息工程学院，石家庄 050031；2.全北国立大学 电子信息工程学院，韩国 全州 54896

摘要：折扣{0-1}背包问题（Discounted {0-1} Knapsack Problem，D{0-1}KP）是比0-1背包还要难以求解的NP-hard问题。提出了一种求解D{0-1}KP的新遗传算法GADKP。GADKP针对D{0-1}KP问题本身结构特征，借鉴启发式搜索思想设计了3种有效的交叉算子和1种变异算子。4种算子的操作都能够保证进化过程中解的可行性；3种交叉算子从3个不同的角度提高算法的搜索能力；变异算子采用逐层贪心机制提高个体的局部开发能力。通过4组共40个D{0-1}KP实例测试，和已有的求解D{0-1}KP的遗传算法相比，GADKP求解精度更高，是一种新颖有效的求解D{0-1}KP的方法。

关键词：遗传算法,折扣{0-1}背包问题,可行解,交叉算子,变异算子