求解0-1背包问题的烟花算法

发布时间：2020-03-31 06:28

【摘要】：背包问题作为运筹学中典型的NP难解问题,生活中许多问题都可以归为此类,因此,对该问题的求解无论是在理论上,还是在实践中都具有重要意义。目前随着问题规模的增大,对此类问题的研究就有了更高的要求,而经典的优化方法更显得无能为力。可喜的是,随着群智能优化算法的发展,也为解决此类问题开辟了新的思路。群智能优化算法作为一种求解高维度和高复杂性优化问题的有效方法,它是通过模拟生物群体间个体的相互作用及信息交流而衍生出的一种新型算法。烟花算法是通过模拟燃放烟花时烟花在空中的爆炸过程而实现的。因为该算法的参数较少,执行过程简单,尤其在解决高维复杂优化问题上具有一定优势,所以目前已被广泛关注。当然,也可以利用该算法求解背包问题。本论文主要做了如下的研究工作:1.给出了基于Logistic混沌映射和Sigmoid函数的烟花算法,并将其应用于求解经典0-1背包问题。对于基本烟花算法来说,首先,烟花的初始化过程采用了有利于进行全局探索的随机搜索方式,可是往往较难进行细致的局部开发。故这里采用被广泛应用的Logistic混沌映射进行初始化,从而初始烟花的分布位置更加均匀,且搜索能力更强;其次,烟花的爆炸半径不利于搜索速度与求解精度的平衡,故引入Sigmoid函数来构造递减的爆炸半径,使得在迭代前期,爆炸半径保持更长时间的较大值,进行充分的全局探索,在迭代后期,爆炸半径保持更长时间的较小值,进行细致的局部开发,平衡了搜索速度与求解精度;最后,对标准测试函数进行测试,并与其它算法进行对比,实验结果表明改进算法的性能更优;并且将其应用于求解经典0-1背包问题,实验结果证明改进算法在解决实际优化问题上是有效的。2.提出利用Kent映射、余弦函数和交叉变异思想改进基本烟花算法,并将其应用于求解折扣0-1背包问题。首先,为了解决基本烟花算法的随机搜索问题,采用了与Logistic混沌映射同构的Kent映射规则来提高搜索精度;其次,利用余弦函数设计了分段爆炸半径,使得半径在前1/2迭代过程中保持递减,后1/2迭代过程中及时适当增大来避免烟花陷入局部最优,这样就可以利用对爆炸半径的计算方法达到有目的的对于爆炸方向进行引导,从而避免了盲目性,节省了搜索时间;接着,利用交叉变异思想对高斯变异过程进行了改进来优化变异过程,从而进一步提升了算法寻优性能。最后,对标准测试函数和折扣0-1背包进行了求解,仿真结果表明,所提算法比其它群智能算法的结果更优,达到了改进算法性能的目的。
【学位授予单位】：西安理工大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP18

【相似文献】

相关期刊论文 前10条

1 田秀芹;;求解0-1背包问题算法研究[J];现代经济信息;2017年07期

2 钱淑渠;武慧虹;林妤;;求解高维动态背包问题的克隆修复免疫算法[J];计算机工程;2017年09期

3 于洋;;浅析利用动态规划法求解0-1背包问题[J];计算机光盘软件与应用;2015年03期

4 史岚;张义宏;吕建辉;;基于绝对贪心和预期效率的0-1背包问题优化[J];计算机应用研究;2014年03期

5 赵学武;刘向娇;王兴;刘兵杰;;求解0-1背包问题的遗传算法[J];南阳师范学院学报;2014年06期

6 刘朝霞;;求解0-1背包问题的两种算法设计[J];阴山学刊(自然科学版);2014年03期

7 王杉林;杨雪绒;;解二次背包问题的一个线性化方法[J];兰州文理学院学报(自然科学版);2014年05期

8 乐天;;遗传算法求解0/1背包问题的综述[J];浙江海洋学院学报(自然科学版);2013年01期

9 朱婷婷;陈伟;陈娟娟;孙文浩;;一类连续可分离背包问题的直接算法[J];运筹学学报;2013年01期

10 王志刚;夏慧明;王明刚;郭广寒;;求解多维背包问题的改进二进制粒子群算法[J];数学的实践与认识;2013年19期

相关会议论文 前10条

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

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

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

4 武继刚;乔占科;;制定大型生产计划的一个贪心算法[A];1996中国控制与决策学术年会论文集[C];1996年

5 王跃虎;周武艺;;基于背包序列的图像加密算法[A];第十二届全国图象图形学学术会议论文集[C];2005年

6 罗景峰;;均匀设计在鱼群算法参数设定中的应用[A];第四届中国智能计算大会论文集[C];2010年

7 马雅凡;王海洋;隋琪;;基于QoS的服务选择研究[A];2005通信理论与技术新进展——第十届全国青年通信学术会议论文集[C];2005年

8 武聪;赵鑫;;基于遗传算法的背包问题[A];2008'中国信息技术与应用学术论坛论文集（二）[C];2008年

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

10 何翠红;区益善;;用结构遗传算法进行非平稳函数优化[A];1997中国控制与决策学术年会论文集[C];1997年

相关博士学位论文 前9条

1 秦进;二次多背包问题及其扩展问题的启发式算法研究[D];华中科技大学;2017年

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

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

4 李剑;微粒群算法及其在物流系统中的应用研究[D];华中科技大学;2008年

5 冀淑慧;基于SDP松弛的整数规划凸化方法研究[D];复旦大学;2012年

6 李艳艳;0-1规划问题的连续化方法研究及应用[D];大连理工大学;2009年

7 王凤华;多路径传输管理技术的研究[D];北京邮电大学;2014年

8 王炼红;人工免疫优化与分类算法及其应用研究[D];湖南大学;2009年

9 崔司千;STDMA多跳无线网络分布式时隙共享策略研究[D];哈尔滨工业大学;2016年

相关硕士学位论文 前10条

1 庞润娟;求解0-1背包问题的烟花算法[D];西安理工大学;2019年

2 刘梦佳;基于Memetic算法的多维背包问题研究[D];昆明理工大学;2018年

3 马宁;凹函数下在线背包问题的研究[D];大连理工大学;2018年

4 林百川;求解动态约束背包问题的改进原对偶遗传算法研究[D];东北大学;2017年

5 付源翼;一种动态多目标背包问题及其算法研究[D];东北大学;2017年

6 温亚楠;L1范数正则化连续二次背包问题算法研究[D];沈阳航空航天大学;2018年

7 陈乌吉玛;基于综合背包问题的混合贪婪算法的研究[D];吉林大学;2017年

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

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

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

，

本文编号：2608704