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

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

来源：计算机工程与应用, 2020, 56(07): 57-66.

• 遗传算法
• 折扣{0-1}背包问题
• 可行解
• 交叉算子
• 变异算子

折扣{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的方法。

• 单位
  电子信息工程学院; 河北地质大学