摘要
折扣{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.
作者
吴聪聪
贺毅朝
赵建立
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)
出处
《计算机工程与应用》
CSCD
北大核心
2020年第7期57-66,共10页
Computer Engineering and Applications
基金
河北省高等学校科学研究计划项目(No.ZD2016005)
河北省教育厅科学技术研究重点项目(No.ZD2018043)。
关键词
遗传算法
折扣{0-1}背包问题
可行解
交叉算子
变异算子
Genetic Algorithm(GA)
Discounted{0-1}Knapsack Problem(D{0-1}KP)
feasible solutions
crossover operator
mutation operator
