论文题目: 基于蚁群优化算法的TSP问题研究
论文类型: 硕士论文
论文专业: 计算机应用技术
作者: 孙骏
导师: 熊盛武
关键词: 人工智能,蚁群优化算法,群体智能,问题,信息素
文献来源: 武汉理工大学
发表年度: 2005
论文摘要: TSP问题(traveling salesman problem)是一个组合优化方面的问题，已经成为并将继续成为测试组合优化新算法的标准问题。从理论上讲，使用穷举法不但可以求解TSP问题，而且还可以求出该问题的最优解。但是对现有的计算机来说，使用常规的穷举法在如此庞大的搜索空间中寻求最优解，几乎是不可能的。所以，各种求TSP问题近似解的优化算法应运而生了，本文所用到的蚁群优化算法也在其中。 蚁群算法作为一类启发式算法，已经成功地应用于求解TSP问题。蚂蚁通过分泌信息素来加强较好路径上的信息素的强度，同时按照路径上的信息素强度来选择下一步所选择的路径，好的路径将会被越来越多的蚂蚁选择，因此更多的信息素将会覆盖较好的路径，最终所有的蚂蚁都集中到了好的路径上。蚂蚁的这种基于信息素的正反馈原理正是整个算法的关键所在。 首先，本文对蚁群系统算法(ACS)的全局收敛性和关键参数的设置进行了深入的研究。ACS寻优性质优良，但搜索时间长、收敛速度慢、容易收敛到局部最优解，从而使其进一步推广应用受到局限。我们通过对算法的全局收敛性以及算法的全局搜索能力进行深入的理论研究，从改善算法全局收敛性的角度提出了一系列改良途径；同时对蚁群算法中参数α、β、ρ的作用作了理论上的研究，对算法参数的最优化配置进行丁分析，并利用Ei151这一典型的TSP问题进行了仿真实验，得出了比较适当参数配置方案。 在此之后，本文介绍了蚁群算法中一种新的信息素更新和路径选择机制并应用于求解TSP问题。在ACS基础上，改良的蚁群算法采用了更为高效的信息素更新和路径选择机制，使得改进后算法的全局收敛速度得到明显的提高；通过增加全局最小信息素强度的设置以及对权函数进行自适应调整改进了算法的搜索能力，扩宽了算法的搜索空间，使改进后算法更容易收敛到全局最优解；并通过实验证明了其有效性。 最后，本文对改进后的蚁群算法的实现进行了简单阐述，并针对蚁群算法的前景进行了展望。
论文目录:
中文摘要
ABSTRACT
第1章 引言
1.1 问题的提出
1.2 本文研究内容
1.3 本文的组织
第2章 蚁群优化算法
2.1 优化算法
2.1.1 基本概念和术语
2.1.2 优化算法
2.2 群体智能简介
2.3 蚁群系统及其研究概述
2.3.1 蚁群系统简介
2.3.2 蚁群系统研究现状
2.3.3 蚁群系统的应用领域
2.4 TSP问题简介
2.4.1 TSP问题的定义
2.4.2 TSP问题的实用价值
2.4.3 TSP问题的理论意义
2.4.4 所有求解TSP问题的方法的简介
2.5 基本蚁群优化算法模型
2.6 基本蚁群优化算法描述
2.7 基本蚁群优化算法的缺陷
第3章 蚁群优化算法中参数的设置及收敛性的研究
3.1 参数的设置
3.1.1 关键参数介绍
3.1.2 不同参数设置的试验
3.1.2.1 信息素挥发度的设置
3.1.2.2 蚁群数量的设置
3.1.2.3 启发式因子的选择设置
3.1.3 试验结果和结论
3.1.3.1 信息素挥发度
3.1.3.2 蚁群数量的设置
3.1.3.3 启发式因子的选择设置
3.2 收敛性的研究
3.2.1 收敛性定理
3.2.2 改善收敛性的途径
第4章 蚁群优化算法的改良
4.1 理论基础
4.1.1 路径选择机制
4.1.2 信息素更新机制
4.1.3 权函数
4.1.4 阈限原理
4.2 算法的改进
4.2.1 改良的初步设想
4.2.2 改良的途径
4.2.2.1 增加最小信息素设置
4.2.2.2 信息素更新机制的改良
4.2.2.3 路径选择机制的改良
4.2.2.4 权函数的自适应调整
4.2.3 改良后的算法模型
4.3 改良算法的实验及结果分析
4.3.1 实验简述
4.3.2 相关参数设置
4.3.2.1 信息素挥发度
4.3.2.2 蚁群数量的设置
4.3.2.3 启发式因子的选择设置
4.3.3 实验结果分析
4.3.3.1 实验结果
4.3.3.2 实验结果分析
4.3.3.2.1 全局最优路径分析
4.3.3.2.2 局部最优路径分析
4.4 本章小结
第5章 改良后蚁群优化算法的实现
5.1 初步设想
5.2 算法重点详述
第6章 结论和展望
参考文献
攻读硕士学位期间公开发表的学术论文
致谢
发布时间: 2005-04-13
参考文献
- [1].基于免疫算法的TSP问题求解[D]. 冯舒怡.天津大学2016
- [2].遗传算法求解TSP问题的研究与改进[D]. 邓先习.东北大学2008
- [3].基于免疫算法的TSP问题求解[D]. 吴昳恬.苏州大学2010
- [4].动态TSP遗传算法研究[D]. 贺朝新.中南民族大学2010
- [5].一类大规模TSP问题的遗传算法研究[D]. 徐纳.西安电子科技大学2011
- [6].向量编码遗传算法求解TSP问题的研究[D]. 刘道军.中南民族大学2008
- [7].基于TSP的改进遗传算法研究及系统实现[D]. 张雪峰.东北师范大学2009
- [8].基于单亲遗传算法的TSP问题研究[D]. 许文方.合肥工业大学2006
- [9].基于改进的遗传算法求解TSP问题[D]. 于丰瑞.内蒙古农业大学2016
- [10].改进的遗传算法求解TSP问题的应用与研究[D]. 葛海明.江西理工大学2016
相关论文
- [1].蚁群优化算法及其应用[D]. 寇晓丽.西安电子科技大学2006
- [2].蚁群优化算法的改进及应用[D]. 付宇.上海海事大学2006
- [3].蚂蚁算法在TSP问题中的应用与研究[D]. 廖兴新.四川大学2006
- [4].一种改进的蚁群算法[D]. 张良红.山东大学2006
- [5].改进的蚁群算法在TSP问题上的应用[D]. 张毅.吉林大学2005
- [6].蚁群——粒子群优化算法混合求解TSP问题[D]. 闵克学.吉林大学2005
- [7].蚁群优化算法及其应用研究[D]. 李闻.湖南大学2005
- [8].蚁群算法的改进与应用[D]. 秦玲.扬州大学2004