改进萤火虫算法求解0-1背包问题

发布时间：2017-10-30 14:45

  本文关键词：改进萤火虫算法求解0-1背包问题

  更多相关文章： 萤火虫算法 0-1背包问题 收敛速度 优化

【摘要】：0-1背包问题是组合优化中经典的NP难题之一,它是一个子集选取问题。学者们曾用回溯算法、动态规划算法,以及多种群智能优化算法来求解,但是都存在算法收敛速度过慢、时空复杂度高等问题。萤火虫算法(GSO,Glowworm Swarm Optimization)是由Krishnanand提出的新型群智能优化随机算法,具有较强的通用性。本文将萤火虫算法应用于解决0-1背包问题,并与动态规划算法做比较。并且对萤火虫优化算法的理论基础和实现方法等方面进行详细介绍的同时分析萤火虫算法存在的优缺点,通过分析,虽然人工萤火虫算法具有捕捉效率高等优点,但也存在着易陷入局部最优,求解精度低等问题。在此基础上,本文对萤火虫优化算法进行了两点改进,首先是对于前期萤火虫吸引度过小的归一化处理:在传统萤火虫算法中,通过公式计算萤火虫的吸引度,由于前期萤火虫距离过大,导致吸引度趋于零。引入归一化处理,对萤火虫的距离进行统一规定使得计算萤火虫吸引度更为合理,加强收敛度;其次是对萤火虫算法后期迭代的改进:对萤火虫算法后期的迭代次数中,由于萤火虫之间的位置逐渐缩小,导致无法定位最优位置,而在极值点附近震荡。引入线性递减的惯性权重,使得函数在迭代后期具有更高的精度,有更多的位置点在极值点附近。提出的改进改进的萤火虫优化算法,提高了基本萤火虫算法的优化能力。改进后的萤火虫优化算法根据基本萤火虫算法的不足,对基本萤火虫算法在前期吸引度和后期迭代上做了改进,并应用于0-1背包问题和一些连续函数。仿真实验结果表明,改进后的萤火虫算法在保证较快的收敛速度的同时,也实现了了算法的全局搜索和局部搜索能力,并表明萤火虫算法在连续空间和离散空间优化的可行性和有效性,具有良好的应用前景。
【关键词】：萤火虫算法 0-1背包问题 收敛速度 优化
【学位授予单位】：西北师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP18
【目录】：

• 摘要8-9
• ABSTRACT9-11
• 1.绪论11-16
• 1.1 课题背景及意义11-13
• 1.2 萤火虫算法的国内外研究现状13-14
• 1.3 论文的创新工作14
• 1.4 本文的目标与组织结构14-16
• 2.基本人工萤火虫优化算法16-25
• 2.1 萤火虫优化算法仿真原理及数学描述16-18
• 2.1.1 萤火虫优化算法仿真原理16-17
• 2.1.2 萤火虫算法数学描述17-18
• 2.2 萤火虫优化算法实现步骤及流程图18-20
• 2.3 萤火虫优化算法应用于 0-1 背包问题20
• 2.3.1 0-1 背包问题描述20
• 2.3.2 动态规划算法等其他算法解 0-1 背包问题分析20
• 2.4 萤火虫优化算法收敛性分析20-22
• 2.5 萤火虫优化算法优缺点22-24
• 2.6 小结24-25
• 3.改进的萤火虫算法25-29
• 3.1 改进方法的描述25-26
• 3.2 改进后的算法步骤26-27
• 3.3 改进萤火虫优化算法实现流程图27-28
• 3.4 小结28-29
• 4.仿真实验结果29-33
• 4.1 萤火虫算法实验参数设置29
• 4.2 测试结果29-31
• 4.3 小结31-33
• 5.改进萤火虫算法在其他问题上的寻优分析33-39
• 5.1 IGSO与GSO在连续函数中测试33-37
• 5.2 小结37-39
• 6.总结与展望39-41
• 参考文献41-46
• 攻读学位期间发表的论文46-47
• 致谢47

【相似文献】

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

，

本文编号：1118038