Computer Engineering and Applications ›› 2020, Vol. 56 ›› Issue (7): 57-66.DOI: 10.3778/j.issn.1002-8331.1904-0218

Previous Articles     Next Articles

New Genetic Algorithm for Discounted {0-1} Knapsack Problem

WU Congcong, HE Yichao, ZHAO Jianli   

  1. 1.College of Information Engineering, Hebei GEO University, Shijiazhuang 050031, China
    2.School of Electronics & Information Engineering, ChonBuk National University, Jeonju 54896, Korea
  • Online:2020-04-01 Published:2020-03-28

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

吴聪聪,贺毅朝,赵建立   

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

Abstract:

Discounted {0-1} Knapsack Problem(D{0-1}KP) is a NP-hard problem, which is more difficult to be solved than 0-1 Knapsack Problem(0-1KP). A new genetic algorithm named GADKP for solving D{0-1}KP is proposed. Three specialized crossover operators and one mutation operator for D{0-1}KP are designed in GADKP. In the four operators, heuristic search techniques are applied. The chromosome generated in the four operators are guaranteed feasible for D{0-1}KP. The three crossover operators improve the search ability of the algorithm from three different angles; according to the problem characteristics of D{0-1}KP, the mutation operator uses the layer-by-layer greedy mechanism to improve the exploitation ability. It tests four sets with 40 instances of D{0-1}KP and compare GADKP with the existing GA based approaches. The results show GADKP is an effective algorithm for solving D{0-1}KP.

Key words: Genetic Algorithm(GA), Discounted {0-1} Knapsack Problem(D{0-1}KP), feasible solutions, crossover operator, mutation operator

摘要:

折扣{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}背包问题, 可行解, 交叉算子, 变异算子