| 【中文题名】 | 基于蚁群优化算法的TSP问题研究 |
| 【英文题名】 | Research on Ant Colony Algorithm for Solving Traveling Salesman Problem |
| 【学科专业】 | 计算机应用技术 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2005-4-13 |
| 【中关键词】 | 人工智能,蚁群优化算法,群体智能,TSP问题,信息素, |
| 【英关键词】 | Artificial Intelligence,Ant Colony Optimization,Swarm Intelligence,Traveling Salesman Problem,Pheromone, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 | TSP问题(traveling salesman problem)是一个组合优化方面的问题，已经成为并将继续成为测试组合优化新算法的标准问题。从理论上讲，使用穷举法不但可以求解TSP问题，而且还可以求出该问题的最优解。但是对现有的计算机来说，使用常规的穷举法在如此庞大的搜索空间中寻求最优解，几乎是不可能的。所以，各种求TSP问题近似解的优化算法应运而生了，本文所用到的蚁群优化算法也在其中。
蚁群算法作为一类启发式算法，已经成功地应用于求解TSP问题。蚂蚁通过分泌信息素来加强较好路径上的信息素的强度，同时按照路径上的信息素强度来选择下一步所选择的路径，好的路径将会被越来越多的蚂蚁选择，因此更多的信息素将会覆盖较好的路径，最终所有的蚂蚁都集中到了好的路径上。蚂蚁的这种基于信息素的正反馈原理正是整个算法的关键所在。
首先，本文对蚁群系统算法(ACS)的全局收敛性和关键参数的设置进行了深入的研究。ACS寻优性质优良，但搜索时间长、收敛速度慢、容易收敛到局部最优解，从而使其进一步推广应用受到局限。我们通过对算法的全局收敛性以及算法的全局搜索能力进行深入的理论研究，从改善算法全局收敛性的角度提出了... |
| 【论文题纲】 |
|
中文摘要 |
2-3 |
|
ABSTRACT |
3-9 |
|
第1章 引言 |
9-11 |
|
1.1 问题的提出 |
9 |
|
1.2 本文研究内容 |
9-10 |
|
1.3 本文的组织 |
10-11 |
|
第2章 蚁群优化算法 |
11-24 |
|
2.1 优化算法 |
11-14 |
|
2.1.1 基本概念和术语 |
11 |
|
2.1.2 优化算法 |
11-14 |
|
2.2 群体智能简介 |
14-15 |
|
2.3 蚁群系统及其研究概述 |
15-19 |
|
2.3.1 蚁群系统简介 |
15-17 |
|
2.3.2 蚁群系统研究现状 |
17-18 |
|
2.3.3 蚁群系统的应用领域 |
18-19 |
|
2.4 TSP问题简介 |
19-21 |
|
2.4.1 TSP问题的定义 |
19-20 |
|
2.4.2 TSP问题的实用价值 |
20 |
|
2.4.3 TSP问题的理论意义 |
20 |
|
2.4.4 所有求解TSP问题的方法的简介 |
20-21 |
|
2.5 基本蚁群优化算法模型 |
21-22 |
|
2.6 基本蚁群优化算法描述 |
22-23 |
|
2.7 基本蚁群优化算法的缺陷 |
23-24 |
|
第3章 蚁群优化算法中参数的设置及收敛性的研究 |
24-34 |
|
3.1 参数的设置 |
24-30 |
|
3.1.1 关键参数介绍 |
24 |
|
3.1.2 不同参数设置的试验 |
24-26 |
|
3.1.2.1 信息素挥发度的设置 |
24-25 |
|
3.1.2.2 蚁群数量的设置 |
25 |
|
3.1.2.3 启发式因子的选择设置 |
25-26 |
|
3.1.3 试验结果和结论 |
26-30 |
|
3.1.3.1 信息素挥发度 |
26-27 |
|
3.1.3.2 蚁群数量的设置 |
27-29 |
|
3.1.3.3 启发式因子的选择设置 |
29-30 |
|
3.2 收敛性的研究 |
30-34 |
|
3.2.1 收敛性定理 |
30-33 |
|
3.2.2 改善收敛性的途径 |
33-34 |
|
第4章 蚁群优化算法的改良 |
34-48 |
|
4.1 理论基础 |
34-36 |
|
4.1.1 路径选择机制 |
34 |
|
4.1.2 信息素更新机制 |
34-35 |
|
4.1.3 权函数 |
35 |
|
4.1.4 阈限原理 |
35-36 |
|
4.2 算法的改进 |
36-40 |
|
4.2.1 改良的初步设想 |
36-37 |
|
4.2.2 改良的途径 |
37-39 |
|
4.2.2.1 增加最小信息素设置 |
37 |
|
4.2.2.2 信息素更新机制的改良 |
37-38 |
|
4.2.2.3 路径选择机制的改良 |
38 |
|
4.2.2.4 权函数的自适应调整 |
38-39 |
|
4.2.3 改良后的算法模型 |
39-40 |
|
4.3 改良算法的实验及结果分析 |
40-47 |
|
4.3.1 实验简述 |
40-41 |
|
4.3.2 相关参数设置 |
41-44 |
|
4.3.2.1 信息素挥发度 |
42 |
|
4.3.2.2 蚁群数量的设置 |
42-43 |
|
4.3.2.3 启发式因子的选择设置 |
43-44 |
|
4.3.3 实验结果分析 |
44-47 |
|
4.3.3.1 实验结果 |
44-45 |
|
4.3.3.2 实验结果分析 |
45-47 |
|
4.3.3.2.1 全局最优路径分析 |
45-46 |
|
4.3.3.2.2 局部最优路径分析 |
46-47 |
|
4.4 本章小结 |
47-48 |
|
第5章 改良后蚁群优化算法的实现 |
48-51 |
|
5.1 初步设想 |
48 |
|
5.2 算法重点详述 |
48-51 |
|
第6章 结论和展望 |
51-52 |
|
参考文献 |
52-55 |
|
攻读硕士学位期间公开发表的学术论文 |
55-56 |
|
致谢 |
56 |
|
| 【DOI】 | LunWen.ID:2.2008.387257 |
