# 基于遗传算法求解折扣{0-1}背包问题的研究

Translated title of the contribution: Research on genetic algorithms for the discounted {0-1} knapsack problem

Research output: Journal PublicationsJournal Article (refereed)peer-review

38 Citations (Scopus)

## Abstract

At present, the deterministic algorithm based on dynamic programming is the main method for solving the discounted {0-1} knapsack problem (D{0-1}KP). But its complexity is pseudo polynomial time, and when the value coefficients and the weight coefficients of the D{0-1}KP instance are in a large range, the deterministic algorithm is no longer practical. In this paper, we use genetic algorithm with elitist reservation strategy (EGA) to solve the D{0-1}KP. Firstly, we establish two new mathematical models of the D{0-1}KP. Secondly, in order to use EGA to solve the D{0-1}KP based on the first mathematical model, we propose a greedy repair and optimization algorithm (GROA) to deal with the non-normal coding individual. Combining EGA with GROA, we give the first genetic algorithm (FirEGA) for solving the D{0-1}KP. Thirdly, for solving the D{0-1}KP by EGA and the second mathematical model, we propose another algorithm named NROA, which is an greedy repair and optimization algorithm too, to deal with the non-normal coding individual, and give the second genetic algorithm (SecEGA) for solving the D{0-1}KP based on EGA and NROA. Finally, we ascertain the reasonable values of the crossover probability and the mutation probability of the FirEGA and SecEGA on the basis of the computational results of four kinds instances of D{0-1}KP. The computational results show that FirEGA and SecEGA are fit for solving the large instance of the hard D{0-1}KP, and they can obtain an approximation solution whose approximation rate is close to 1. Furthermore, the average performance of FirEGA is more efficient than SecEGA.

Translated title of the contribution Research on genetic algorithms for the discounted {0-1} knapsack problem Chinese (Simplified) 2614-2630 17 计算机学报 = Chinese Journal of Computers 39 12 https://doi.org/10.11897/SP.J.1016.2016.02614 Published - Dec 2016 Yes

## Keywords

• Discounted {0-1} knapsack problem
• Genetic algorithm
• Greedy strategy
• Non-normal coding individual
• Repair and optimization
• 折扣{0-1}背包问题
• 遗传算法
• 非正常编码个体
• 贪心策略
• 修复与优化

## Fingerprint

Dive into the research topics of 'Research on genetic algorithms for the discounted {0-1} knapsack problem'. Together they form a unique fingerprint.