一种新的改进人工蜂群算法及其在旅行商问题中的应用

发布时间：2017-05-23 21:09

  本文关键词：一种新的改进人工蜂群算法及其在旅行商问题中的应用，由笔耕文化传播整理发布。

【摘要】：人工蜂群算法是一种能够解决大多数优化问题的新思维方法,具有重要学术意义和现实应用价值。但因其复杂性,目前的研究成果比较分散且缺乏系统性。因此,针对人工蜂群算法的不足,同时结合前人的研究,本文采用理论与数值仿真相结合的研究方法,提出了比较集中和系统的改进人工蜂群算法,同时证明了该改进算法的有效性和收敛性。最后将改进人工蜂群算法应用于旅行商问题,结果显示改进人工蜂群算法具有良好的性能。具体研究内容为:(1)详细描述蜜蜂的采蜜过程,借鉴相关文献总结出了经典人工蜂群算法的基本过程。为了快速理解经典人工蜂群算法,给出了相关专业术语的定义。得出了算法的基本步骤,并画出了算法的流程图,总结了经典人工蜂群算法的不足。(2)运用反学习方法以及改进的“S”型分组方法,构造初始种群,并用灵敏度-信息素方式代替原有的轮盘赌选择方式,设计了一种自适应调整因子的函数以强化收敛速度和保证种群的多样性,提出改进的人工蜂群算法。并选择了CEC13版本最新的14个测试函数,分别以20维和40维,与其它五种算法进行数值仿真比较。结果表明:改进的人工蜂群算法有效地解决了搜索速度慢、群体多样性差和易陷入局部最优等缺陷,在集中性和稳定性方面都取得了更好的效果。(3)证明改进人工蜂群算法种群状态序列是有限齐次的Markov链。然后,依据改进的概率选择公式,证明整个种群的进化方向是单调的,并且改进人工蜂群算法中的Markov链种群序列以概率1收敛于全局最优解集。最后利用下鞅收敛定理,证明改进人工蜂群算法的几乎处处强收敛性。(4)将改进人工蜂群算法应用到旅行商问题。结果显示:相对经典人工蜂群算法,改进人工蜂群算法总是先达到最优路径且最优路径更短。这说明改进人工蜂群算法的有效性。
【关键词】：改进人工蜂群算法 改进“S”型分组 灵敏度-信息素 自适应调整因子 收敛性分析 旅行商问题
【学位授予单位】：四川理工学院
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP18
【目录】：

• 摘要6-7
• Abstract7-11
• 第一章 绪论11-20
• 1.1 研究背景和意义11-14
• 1.2 研究现状14-18
• 1.3 主要内容和创新点18-19
• 1.4 论文结构和后续章节安排19-20
• 第二章 经典人工蜂群算法20-25
• 2.1 基本过程20-22
• 2.2 算法步骤及其流程图22-23
• 2.3 小结23-25
• 第三章 改进人工蜂群算法及其数值仿真25-42
• 3.1 改进的人工蜂群算法及其流程图25-32
• 3.1.1 基于反学习理论的初始种群构造25-26
• 3.1.2 基于“S”型分组的子种群分组26-27
• 3.1.3 灵敏度-信息素选择方式27-28
• 3.1.4 自适应调整因子的搜索方式28-30
• 3.1.5 改进人工蜂群算法的流程图30-32
• 3.2 数值仿真32-41
• 3.2.1 收敛曲线图形及分析34-40
• 3.2.2 平均值和标准差的比较40
• 3.2.3 总运行时间的比较40-41
• 3.3 小结41-42
• 第四章 改进人工蜂群算法的收敛性分析42-46
• 4.1 改进人工蜂群算法的Markov性42-43
• 4.2 改进人工蜂群算法的依概率收敛性43-44
• 4.3 改进人工蜂群算法的几乎处处强收敛性44-45
• 4.4 小结45-46
• 第五章 改进人工蜂群算法应用于旅行商问题46-53
• 5.1 旅行商问题46-47
• 5.2 利用改进人工蜂群算法求解旅行商问题47-52
• 5.3 小结52-53
• 总结与展望53-55
• 参考文献55-63
• 攻读学位期间发表的学术论文及研究成果63-64
• 致谢64-65
• 附录65-72
• 附录1 均值和标准差65-68
• 附录2 六种算法的运行时间表（单位：秒）68-70
• 附录3 时间减少率70-71
• 附录4 TSP的标准测试库中eil51的51个城市坐标71
• 附录5 eil51优化路径以及优化路径长度71-72

【相似文献】

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

1 王大志;汪定伟;闫杨;;一类多旅行商问题的计算及仿真分析[J];系统仿真学报;2009年20期

2 莫愿斌;刘贺同;王勤;;旅行商问题的综述教学研究[J];中国科教创新导刊;2008年08期

3 苏丽杰,聂义勇;现实旅行商问题[J];小型微型计算机系统;2005年04期

4 顾大权;徐四林;袁媛;汪晋;;求解旅行商问题的一个有效算法[J];解放军理工大学学报(自然科学版);2006年02期

5 陈文兰;戴树贵;;旅行商问题算法研究综述[J];滁州学院学报;2006年03期

6 江贺;张宪超;陈国良;;有向黑白旅行商问题[J];计算机学报;2007年03期

7 管琳;白艳萍;;用分支定界算法求解旅行商问题[J];中北大学学报(自然科学版);2007年02期

8 黄可为;汪定伟;;热轧计划中的多旅行商问题及其计算方法[J];计算机应用研究;2007年07期

9 张敏;金琴玲;;旅行商问题的一种新解法[J];重庆职业技术学院学报;2008年01期

10 高春涛;;求解旅行商问题的几种解法[J];边疆经济与文化;2010年05期

中国重要会议论文全文数据库 前10条

1 冯纯伯;;旅行商问题的一种解法[A];1991年控制理论及其应用年会论文集（下）[C];1991年

2 张雷;郑维敏;;广义旅行商问题、放映员问题和一类调度模型[A];1996年中国控制会议论文集[C];1996年

3 胡巧华;吴怀宇;陈乔礼;陈媛;;一种求解旅行商问题的启发交叉算子的研究[A];第25届中国控制会议论文集（中册）[C];2006年

4 张辉;王锡淮;肖健梅;;基于改进蚁群算法的旅行商问题[A];2007中国控制与决策学术年会论文集[C];2007年

5 李大卫;王梦光;;热轧调度与多旅行商问题[A];1996年中国控制会议论文集[C];1996年

6 刘春波;潘丰;杨丹;;基于改进的蚁群算法在中国旅行商问题中的求解[A];2007中国控制与决策学术年会论文集[C];2007年

7 冯纯伯;蒋珉;;应用模拟电场法解旅行商问题[A];1993年控制理论及其应用年会论文集[C];1993年

8 李丽;程玉荣;牛奔;;离散人工蜂群算法求解旅行商问题[A];第十三届中国管理科学学术年会论文集[C];2011年

9 孙启瑞;李俊;丁健;戴先中;;新型访问域部分重叠的多旅行商问题的GA求解[A];2013年中国智能自动化学术会议论文集（第四分册）[C];2013年

10 韩爱丽;朱大铭;;旅行商问题的一种新DNA编码方案[A];2006年全国理论计算机科学学术年会论文集[C];2006年

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

1 张梦颖;不确定因素下路径规划问题研究[D];中国科学技术大学;2016年

2 谭阳;求解广义旅行商问题的若干进化算法研究[D];华南理工大学;2013年

3 王刚;两类圈问题的算法研究[D];国防科学技术大学;2013年

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

1 刘欣欣;旅行商问题的基因片段插入算法研究[D];闽南师范大学;2015年

2 陈玲;基于PSO-GA混合算法的时间优化的旅行商问题的研究[D];合肥工业大学;2015年

3 赵丽娜;带油耗的单商品取送货旅行商问题研究[D];沈阳师范大学;2016年

4 毛巍;一种新的改进人工蜂群算法及其在旅行商问题中的应用[D];四川理工学院;2016年

5 徐东镇;蚁群算法及其在广义旅行商问题求解中的应用[D];合肥工业大学;2007年

6 黄厚生;求解旅行商问题的新方法研究[D];天津大学;2005年

7 王玲丽;随机存储下的有容量限制的广义旅行商问题[D];上海交通大学;2012年

8 高峰;求解多目标旅行商问题的进化算法研究[D];华东师范大学;2013年

9 覃锦华;求解旅行商问题的进化算法[D];西安电子科技大学;2008年

10 李天龙;基于自组织优化算法的多旅行商问题的求解与应用[D];浙江大学;2010年

  本文关键词：一种新的改进人工蜂群算法及其在旅行商问题中的应用，，由笔耕文化传播整理发布。

本文编号：389126