求解多维背包问题的蚁群-拉格朗日松弛混合优化算法

发布时间：2017-12-13 09:31

  本文关键词：求解多维背包问题的蚁群-拉格朗日松弛混合优化算法

  更多相关文章： 多维背包问题 蚁群优化 拉格朗日松弛 核问题

【摘要】：针对多维背包问题(MKP)NP-hard、约束强的特点,提出一种高效的蚁群-拉格朗日松弛(LR)混合优化算法.该算法以蚁群优化(ACO)为基本框架,并基于LR对偶信息定义了一种MKP效用指标.ACO使得整体算法具有全局搜索能力,所设计的效用指标将MKP的优化目标与约束条件有机地融合在一起.该指标一方面可以用来定义MKP核问题,降低问题规模;另一方面,可以用作ACO的启发因子,引导算法在有希望的解区域中强化搜索.在大量标准算例上的测试结果表明,所提出算法的鲁棒性较好;与其他已有算法相比,在求解质量和求解效率方面均具有很强的竞争力.
【作者单位】： 西安交通大学电子与信息工程学院;
【基金】：国家自然科学基金项目(61105126) 中国博士后科学基金项目(2014M560784)
【分类号】：TP18
【正文快照】： 0引言多维背包问题(MKP)是运筹学领域一经典的组合优化问题,被证明是一种NP-hard问题,其求解目标是在满足各项资源约束的前提下,从候选对象集中找出可以使目标价值达到最大的对象子集[1].MKP具有广泛的工程背景,可以用来描述资本预算、资源分配、分布式数据库处理等实际问题[2

【参考文献】

中国期刊全文数据库 前4条

1 欧阳海滨;高立群;孔祥勇;刘宏志;;一种求解0-1背包问题的二进制修正和声搜索算法[J];控制与决策;2014年07期

2 王凌;王圣尧;方晨;;一种求解多维背包问题的混合分布估计算法[J];控制与决策;2011年08期

3 张晓霞;唐立新;;一种新的求解MMKP问题的ACO&PR算法[J];控制与决策;2009年05期

4 喻学才;张田文;;多维背包问题的一个蚁群优化算法[J];计算机学报;2008年05期

【共引文献】

中国期刊全文数据库 前10条

1 李枝勇;马良;张惠珍;;求解多维背包问题的改进布谷鸟搜索算法[J];控制工程;2016年07期

2 戴永寿;李韶光;李立刚;于肖雯;;基于改进k-means和遗传算法的油田特种车辆优化调度[J];计算机应用;2016年S1期

3 刘静宜;韩海燕;;求解带有利用率惩罚背包问题的参数自适应差分进化算法[J];科技视界;2016年16期

4 任志刚;赵松云;黄姗姗;梁永胜;;求解多维背包问题的蚁群-拉格朗日松弛混合优化算法[J];控制与决策;2016年07期

5 钱淑渠;叶永强;武慧虹;;贪婪封装二进制差分进化算法求解高维背包问题[J];控制与决策;2016年05期

6 Lin Zhang;Kaili Rao;Ruchuan Wang;;T-QoS-aware based parallel ant colony algorithm for services composition[J];Journal of Systems Engineering and Electronics;2015年05期

7 王小彤;侯立刚;苏成利;;一种改进的蚁群算法求解多维背包问题[J];辽宁石油化工大学学报;2015年04期

8 王勇臻;陈燕;李桃迎;张金松;;元胞分布估计算法求解高维0/1背包问题[J];小型微型计算机系统;2015年06期

9 吴虎胜;张凤鸣;战仁军;李浩;梁晓龙;;利用改进的二进制狼群算法求解多维背包问题[J];系统工程与电子技术;2015年05期

10 孟祥虎;胡蓉;钱斌;;求解带时间窗车辆路径问题的有效混合PBIL算法[J];系统工程理论与实践;2014年10期

【二级参考文献】

中国期刊全文数据库 前8条

1 李若平;欧阳海滨;高立群;邹德旋;;学习型和声搜索算法及其在0-1背包问题中的应用[J];控制与决策;2013年02期

2 覃朝勇;黄景文;郑建国;莫国莉;;求解背包问题的混合量子进化算法[J];小型微型计算机系统;2011年02期

3 贺毅朝;寇应展;陈致明;;求解多选择背包问题的改进差分演化算法[J];小型微型计算机系统;2007年09期

4 杨广益;欧阳智敏;全惠云;;松驰互补的分布估计算法求解多维背包问题[J];计算机工程与应用;2007年12期

5 周树德;孙增圻;;分布估计算法综述[J];自动化学报;2007年02期

6 刘华蓥,林玉娥,刘金月;基于蚁群算法求解0/1背包问题[J];大庆石油学院学报;2005年03期

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

8 于永新,张新荣;基于蚁群系统的多选择背包问题优化算法[J];计算机工程;2003年20期

【相似文献】

中国期刊全文数据库 前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年

中国博士学位论文全文数据库 前1条

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

中国硕士学位论文全文数据库 前10条

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

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

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

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

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

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

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

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

9 钟海林;背包问题的一种新算法：降维递归算法[D];江西师范大学;2008年

10 赵培怡;改进群体智能算法及其在背包问题中的应用[D];山东大学;2007年

，

本文编号：1284683