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

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