首页 | 本学科首页   官方微博 | 高级检索  
     

求解背包问题的演化算法
引用本文:王熙照,贺毅朝.求解背包问题的演化算法[J].软件学报,2017,28(1):1-16.
作者姓名:王熙照  贺毅朝
作者单位:深圳大学 计算机与软件学院, 广东 深圳518060,河北地质大学 信息工程学院, 河北 石家庄050031
基金项目:国家自然科学基金(71371063); 深圳市知识创新计划基础研究项目(JCYJ20150324140036825); 河北省自然科学基金(F2016403055); 河北省高等学校科学研究计划项目(ZD2016005)
摘    要:背包问题(Knapsack Problem, KP)是一类著名的组合优化问题,也是一类NP难问题,它包括0-1背包问题、有界背包问题、多维背包问题、多背包问题、多选择背包问题、二次背包问题、动态背包问题和折扣背包问题等多种形式,在众多领域有着广泛的应用.演化算法(EAs)是一类有效的快速近似求解KP的算法.本文对近十余年来利用EAs求解KP的研究情况进行一个较为详细的总结,它一方面讨论了利用EAs求解各种KP问题时个体的编码方法与处理不可行解的有效方法,另一方面为今后进一步利用最新提出的EAs求解KP问题提供一个可借鉴的思路.

关 键 词:背包问题  数学模型  演化算法  个体编码  不可行解
收稿时间:2016/9/22 0:00:00
修稿时间:2016/10/24 0:00:00

Evolutionary Algorithms for Knapsack Problems
WANG Xi-Zhao and HE Yi-Chao.Evolutionary Algorithms for Knapsack Problems[J].Journal of Software,2017,28(1):1-16.
Authors:WANG Xi-Zhao and HE Yi-Chao
Affiliation:College of Computer Science and Software Engineering, Shenzhen University, Shenzhen 518060, China and College of Information and Engineering, Hebei GEO University, Shijiazhuang 050031, China
Abstract:Knapsack problem (KP) is a well-known combinatorial optimization problem which includes 0-1 KP, bounded KP, multi-constraint KP, multiple KP, multiple-choice KP, quadratic KP, dynamic knapsack KP, discounted KP and other types of KPs. KP can be considered as a mathematical model extracted from variety of real fields and therefore has the wide applications. Evolutionary algorithms (EAs) are universally considered as an efficient tool to solve KP approximately and quickly. This paper presents a survey on solving KP by EAs over the past ten years. It not only discusses various KP encoding mechanism and the individual infeasible solution processing but also provides useful guidelines for designing new EAs to solve KPs.
Keywords:knapsack problem  mathematical model  evolutionary algorithm  individual coding  infeasible solution
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号