求解背包问题的演化算法

来源：软件学报杂志2017年第1期北京时间：

作者：王熙照,贺毅朝

单位：王熙照，深圳大学 计算机与软件学院, 广东 深圳 51806011,贺毅朝，河北地质大学 信息工程学院, 河北 石家庄 05003102

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

关键词：背包问题;数学模型;演化算法;个体编码;不可行解

基金资助：国家自然科学基金（71371063）；深圳市知识创新计划基础研究项目（JCYJ20150324140036825）；河北省自然科学基金（F2016403055）；河北省高等学校科学研究计划（ZD2016005）