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

doi:10.3778/j.issn.1002-8331.1904-0218

Abstract

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

WU Congcong, HE Yichao, ZHAO Jianli. New Genetic Algorithm for Discounted {0-1} Knapsack Problem[J]. Computer Engineering and Applications, 2020, 56(7): 57-66.

吴聪聪，贺毅朝，赵建立. 求解折扣{0-1}背包问题的新遗传算法[J]. 计算机工程与应用, 2020, 56(7): 57-66.

[1]	ZHOU Yuanling, HU Xiaobing, JIANG Daiyu, LI Hang. Research on Optimization Algorithm of Workshop Scheduling Based on Improved NSGA-II [J]. Computer Engineering and Applications, 2021, 57(19): 274-281.
[2]	LI Rong, HE Xingshi, YANG Xinshe. Application of Moth Algorithm Based on Differential Evolution in Power Dispatch [J]. Computer Engineering and Applications, 2021, 57(13): 258-268.
[3]	QIN Qin, LIANG Chengji. Optimization of Equipment Coordination Scheduling with Considering Buffer Space in Automated Container Terminal [J]. Computer Engineering and Applications, 2020, 56(6): 262-270.
[4]	LIANG Chengji, YU Jian. Research on Dispatching of Container Terminals Quay Crane Scheduling with Interference Constraints [J]. Computer Engineering and Applications, 2020, 56(10): 273-278.
[5]	LI Erchao, CHEN Ruiting. Improved MOEA/D Algorithm Based on Adaptive Mutation Operator and Neighborhood Size [J]. Computer Engineering and Applications, 2019, 55(9): 49-55.
[6]	YAO Yiwen, JIANG Shujuan, BO Lili. Survey of Mutation-Based Fault Location [J]. Computer Engineering and Applications, 2019, 55(20): 1-12.
[7]	DONG Hao1, ZHANG Haiping2, LI Zhongjin1, LIU Hui1. Computation Offloading for Service Workflow in Mobile Edge Computing [J]. Computer Engineering and Applications, 2019, 55(2): 36-43.
[8]	HU Shijuan, LU Haiyan, HUANG Yang, XU Kaibo. Improved Genetic Algorithm for Solving Multiple Traveling Salesman Problem with Balanced Workload [J]. Computer Engineering and Applications, 2019, 55(17): 150-155.
[9]	LIAO Xiongying1，2, LI Jun1，2, LUO Yangkun1，2, LI Bo1，2. Differential evolution algorithm based on adaptive mutation operator [J]. Computer Engineering and Applications, 2018, 54(6): 128-134.
[10]	BIAN Jinghong1, HE Xingshi1, FAN Qinwei1, YI Baomin2. New BP neural network based on adaptive flower pollination algorithm [J]. Computer Engineering and Applications, 2018, 54(3): 50-56.
[11]	XIAO Suqiong1，2, LUO Ke1，2. Krill Herd optimization algorithm with reverse-learning and local-learning behavior [J]. Computer Engineering and Applications, 2018, 54(18): 34-39.
[12]	XUE Meng, JIANG Shujuan, WANG Rongcun. Systematic review of test data generation based on intelligent optimization algorithm [J]. Computer Engineering and Applications, 2018, 54(17): 16-23.
[13]	LOU Gaoxiang, CAI Zongyan, LIU Qingtao. Application of new hybrid algorithm in mixed model assembly scheduling [J]. Computer Engineering and Applications, 2018, 54(16): 254-259.
[14]	WANG Xinyue, GUO Jianquan. Subsidy strategy model of multi-period closed-loop hybrid system under carbon tax [J]. Computer Engineering and Applications, 2018, 54(14): 236-240.
[15]	YANG Xiaojian, XU Xiaoting, LI Rongyu. Genetic chicken swarm optimization algorithm for solving high-dimensional optimization problems [J]. Computer Engineering and Applications, 2018, 54(11): 133-139.

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics