求解背包问题的演化算法

发布时间：2018-05-25 08:29

  本文选题：背包问题 + 数学模型　； 参考：《软件学报》2017年01期

【摘要】：背包问题(knapsack problem,简称KP)是一类著名的组合优化问题,也是一类NP难问题,它包括0-1背包问题、有界背包问题、多维背包问题、多背包问题、多选择背包问题、二次背包问题、动态背包问题和折扣背包问题等多种形式,在众多领域有着广泛的应用.演化算法(EAs)是一类有效的快速近似求解KP的算法.对近10余年来利用EAs求解KP的研究情况进行了较为详细的总结,一方面讨论了利用EAs求解各种KP问题时个体的编码方法与处理不可行解的有效方法,另一方面,为今后进一步利用最新提出的EAs求解KP问题提供了一条可借鉴的思路.
[Abstract]:Knapsack problem is a famous combinatorial optimization problem and NP-hard problem. It includes 0-1 knapsack problem, bounded knapsack problem, multidimensional knapsack problem, multi-selection knapsack problem, quadratic knapsack problem. Dynamic knapsack problem and discount knapsack problem are widely used in many fields. Evolutionary algorithm (Eas) is a kind of efficient fast approximate solution to KP. In this paper, the research on solving KP by EAs in recent 10 years is summarized in detail. On the one hand, the coding method of individual and the effective method of dealing with infeasible solution when solving various KP problems with EAs are discussed, on the other hand, It provides a useful way to solve KP problem by using the latest EAs in the future.
【作者单位】： 深圳大学计算机与软件学院;河北地质大学信息工程学院;
【基金】：国家自然科学基金(71371063) 深圳市知识创新计划基础研究项目(JCYJ20150324140036825) 河北省自然科学基金(F2016403055) 河北省高等学校科学研究计划(ZD2016005)~~
【分类号】：TP301.6

【相似文献】

相关期刊论文 前10条

1 何文明,朱起定;背包问题的循环及并行解[J];湘潭师范学院学报(社会科学版);2000年03期

2 任瑞征,严蔚敏;整数背包问题的应用及其算法研究[J];小型微型计算机系统;2001年02期

3 叶俊,刘贤德,韩露;基于博弈论的背包问题优化算法[J];华中科技大学学报(自然科学版);2003年09期

4 罗小虎,赵雷;一个解决0/1背包问题的蚁群方法[J];苏州大学学报(工科版);2004年01期

5 宋翔,聂义勇,储诚斌;无限制背包问题的爬山算法[J];小型微型计算机系统;2004年07期

6 谢涛,陈火旺,康立山;二次背包问题的一种快速解法[J];计算机学报;2004年09期

7 王喜凤;浅析0/1背包问题[J];电脑知识与技术;2004年29期

8 华中生,张斌;求解可分离连续凸二次背包问题的直接算法[J];系统工程与电子技术;2005年02期

9 宋海洲;魏旭真;;求解0-1背包问题的混合遗传算法[J];华侨大学学报(自然科学版);2006年01期

10 熊伟清;魏平;王小权;;蚁群算法求解多维0/1背包问题[J];计算机工程与科学;2006年10期

相关会议论文 前6条

1 乔善平;朱波;赵玲;;基于移动Agent的0-1背包问题分布式求解[A];2008'中国信息技术与应用学术论坛论文集（一）[C];2008年

2 高尚;;背包问题的分布估计算法[A];2013年中国智能自动化学术会议论文集（第五分册）[C];2013年

3 徐俊杰;忻展红;;粒子群优化在0/1背包问题中的应用[A];中国运筹学会第七届学术交流会论文集（上卷）[C];2004年

4 姜宇;苏中滨;郑萍;;求解O/1背包问题的算法综述[A];黑龙江省计算机学会2009年学术交流年会论文集[C];2010年

5 刘裴寰;姜青山;王备战;史亮;;基于K均值聚类求解多维背包问题的算法[A];第二十三届中国数据库学术会议论文集（技术报告篇）[C];2006年

6 李伟;吕克伟;;类背包DH问题的比特安全性研究[A];第28次全国计算机安全学术交流会论文集[C];2013年

相关博士学位论文 前2条

1 黄斌超;限制性多重背包问题的研究[D];云南大学;2015年

2 TRUONG KHAC TUNG;[D];湖南大学;2013年

相关硕士学位论文 前10条

1 史如意;带流量约束的星型图背包问题[D];浙江大学;2015年

2 孙飞;改进萤火虫算法求解0-1背包问题[D];西北师范大学;2015年

3 聂大干;森林优化算法的改进及离散化研究[D];兰州大学;2016年

4 包宗藩;风力驱动优化算法及其应用研究[D];广西民族大学;2016年

5 潘夏福;混合蚁群算法求解0-1背包问题[D];厦门大学;2008年

6 朱阅岸;解0-1背包问题的算法比较和改进[D];暨南大学;2011年

7 史今驰;背包问题的实用求解算法研究[D];山东大学;2005年

8 郑杨凡;基于属性论的0-1背包问题算法研究[D];上海海事大学;2005年

9 李其;有偿在线背包问题的研究[D];大连理工大学;2012年

10 孟晓笑;并行环境下0-1背包问题的解决策略[D];湖北大学;2011年

，

本文编号：1932773