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

作     者：吴聪聪 贺毅朝 赵建立 WU Congcong;HE Yichao;ZHAO Jianli

作者机构：河北地质大学信息工程学院石家庄050031 全北国立大学电子信息工程学院韩国全州54896 

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

出 版 物：《计算机工程与应用》 (Computer Engineering and Applications)

年 卷 期：2020年第56卷第7期

页      码：57-66页

摘      要：折扣{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}背包问题 可行解 交叉算子 变异算子 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.3778/j.issn.1002-8331.1904-0218

馆 藏 号：203896272...