求解背包问题的演化算法

• 作者: 王熙照 贺毅朝
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 背包问题 数学模型 演化算法 个体编码 不可行解
• 年，卷（期）: 2017,（1）
• 所属期刊栏目: 理论计算机科学
• 页码范围: 1-16
• 页数: 16页
• 分类号: TP301
• 字数: 13077字
• 语种: 中文
• DOI: 10.13328/j.cnki.j0s.005139

摘要

背包问题(knapsack problem,简称KP)是一类著名的组合优化问题,也是一类NP难问题,它包括0-1背包问题、有界背包问题、多维背包问题、多背包问题、多选择背包问题、二次背包问题、动态背包问题和折扣背包问题等多种形式,在众多领域有着广泛的应用.演化算法(EAs)是一类有效的快速近似求解KP的算法.对近10余年来利用EAs求解KP的研究情况进行了较为详细的总结,一方面讨论了利用EAs求解各种KP问题时个体的编码方法与处理不可行解的有效方法,另一方面,为今后进一步利用最新提出的EAs求解KP问题提供了一条可借鉴的思路.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	贺毅朝	河北地质大学信息工程学院	22	110	6.0	9.0
2	王熙照	深圳大学计算机与软件学院	7	104	5.0	7.0