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

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

作　　者：吴聪聪 贺毅朝 赵建立 WU Congcong;HE Yichao;ZHAO Jianli(College of Information Engineering,Hebei GEO University,Shijiazhuang 050031,China;School of Electronics&Information Engineering,ChonBuk National University,Jeonju 54896,Korea)

机构地区：[1]河北地质大学信息工程学院,石家庄050031 [2]全北国立大学电子信息工程学院,韩国全州54896

出　　处：《计算机工程与应用》2020年第7期57-66,共10页Computer Engineering and Applications

基　　金：河北省高等学校科学研究计划项目(No.ZD2016005);河北省教育厅科学技术研究重点项目(No.ZD2018043)。

摘　　要：折扣{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的方法。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-1 KP).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.

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

分 类 号：TP301.4[自动化与计算机技术—计算机系统结构]