10.3778/j.issn.1002-8331.1904-0218
求解折扣{0-1}背包问题的新遗传算法
折扣{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}背包问题、可行解、交叉算子、变异算子
56
TP301.4(计算技术、计算机技术)
河北省高等学校科学研究计划项目;河北省教育厅科学技术研究重点项目
2020-04-09(万方平台首次上网日期,不代表论文的发表时间)
共10页
57-66