Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (3): 656-662.

### New simplified model of discounted {0-1} knapsack problem and solution by genetic algorithm

1. School of Mathematics and Information, China West Normal University, Nanchong Sichuan 637009, China
• Received:2018-07-31 Revised:2018-09-13 Online:2019-03-10 Published:2019-03-11
• Contact: 杨洋
• Supported by:
This work is partially supported by the National Natural Science Foundation of China (11371015), the Natural Science Foundation of Sichuan Provincial Department of Education (18ZA0469), the Doctoral Startup Fund of China West Normal University (12B022), the Science Research Team Program of China West Normal University (CXTD2015-4), the Student's Platform for Innovation and Entrepreneurship Training Program of Sichuan Province (201810638085).

### 折扣{0-1}背包问题的简化新模型及遗传算法求解

1. 西华师范大学 数学与信息学院, 四川 南充 637009
• 作者简介:杨洋(1993-),男,四川资阳人,硕士研究生,CCF会员,主要研究方向:数学建模、智能算法;潘大志(1974-),男,四川三台人,教授,博士,主要研究方向:智能计算、算法设计;刘益(1959-),男,四川南充人,副教授,硕士,主要研究方向:应用数学、数学哲学;谭代伦(1971-),男,重庆铜梁人,教授,硕士,主要研究方向:数学建模、运筹优化。
• 基金资助:
国家自然科学基金资助项目（11371015）；四川省教育厅自然科学基金资助项目（18ZA0469）；西华师范大学博士启动基金资助项目（12B022）；西华师范大学校级科研团队项目（CXTD2015-4）；四川省大学生创新创业训练计划支持项目（201810638085）。

Abstract: Current Discounted {0-1} Knapsack Problem (D{0-1}KP) model takes the discounted relationship as a new individual, so the repair method must be adopted in the solving process to repair the individual coding, making the model have less solving methods. In order to solve the problem of single solving method, by changing the binary code expression in the model, an expression method with discounted relationship out of individual code was proposed. Firstly, if and only if each involved individual encoding value was one (which means the product was one), the discounted relationship was established. According to this setting, a Simplified Discounted {0-1} Knapsack Problem (SD{0-1}KP) model was established. Then, an improved genetic algorithm-FG (First Gentic algorithm) was proposed based on Elitist Reservation Strategy (EGA) and GREedy strategy (GRE) for SD{0-1}KP model. Finally, combining penalty function method, a high precision penalty function method-SG (Second Genetic algorithm) for SD{0-1}KP was proposed. The results show that the SD{0-1}KP model can fully cover the problem domain of D{0-1}KP. Compared with FirEGA (First Elitist reservation strategy Genetic Algorithm), the two algorithms proposed have obvious advantages in solving speed. And SG algorithm introduces the penalty function method for the first time, which enriches the solving methods of the problem.

CLC Number: