| 【中文题名】 | 蚂蚁算法在TSP问题中的应用与研究 |
| 【英文题名】 | Application and Research of Ant Colony Algorithm in Travelling Salesman Problem |
| 【学科专业】 | 电路与系统 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-1-22 |
| 【中关键词】 | 蚂蚁算法,组合优化,旅行商问题,信息激素,, |
| 【英关键词】 | ant colony algorithm,combinatorial optimization,TSP,Pheromone, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 | 组合优化是运筹学的重要分支，主要通过对数学方法的研究寻找离散事件的最优编排、分组、次序或筛选等。大多数这类问题通常在多项式时间里无法求解，属于NP完全问题。随着问题规模的扩大，问题空间呈现组合爆炸特征，无法用常规的方法求解。旅行商问题(TSP)就是一个经典的组合优化问题，属于NP完全问题。此类问题目前只能用启发式算法进行求解。
自从上世纪50年代中期创立仿生学以来，人们不断地从生物进化的机理中得到启发，提出了许多用于解决复杂优化问题的新方法，比如神经网络、遗传算法、模拟退火算法、进化规划等，并成功应用于解决实际问题。由意大利学者M．Dorigo，V．Maniezzo，A．Colorni于1992年首先提出的蚂蚁系统(Ant Colony System，ACS)，是一种新颖的仿生进化算法，适用求解复杂组合优化问题。蚂蚁优化算法(Ant Colony Optimization，ACO)是一种随机搜索算法，它基于对自然界真实蚂蚁的集体觅食行为的研究，模拟真实的蚂蚁协作过程。算法由若干个蚂蚁共同构造解路径，通过在解路径上遗留并交换信息素提高解的质量，进而达到优化的目的。目前，蚂蚁系统己成功应用于求解旅... |
| 【论文题纲】 |
|
摘要 |
2-4 |
|
Abstract |
4-8 |
|
第一章 绪论 |
8-12 |
|
1.1 蚂蚁算法基本原理 |
8-9 |
|
1.2 TSP问题简介 |
9-11 |
|
1.3 论文各部分主要内容 |
11-12 |
|
第二章 组合优化问题与仿生优化算法 |
12-21 |
|
2.1 组合优化问题与TSP问题分析 |
12-15 |
|
2.2 仿生优化算法概述与比较 |
15-21 |
|
第三章 基本蚂蚁算法模型 |
21-33 |
|
3.1 基本蚂蚁算法的产生 |
21-22 |
|
3.2 基本蚂蚁算法的原理 |
22-24 |
|
3.3 基本蚂蚁算法的生物学模型 |
24-25 |
|
3.4 基本蚂蚁算法的系统学模型 |
25-27 |
|
3.5 基本蚂蚁算法的数学模型 |
27-30 |
|
3.6 基本蚂蚁算法的改进模型 |
30-33 |
|
第四章 基本蚂蚁算法分析 |
33-39 |
|
4.1 TSP地图规模与最优解的关系 |
33 |
|
4.2 基本蚂蚁算法主要参数分析 |
33-37 |
|
4.2.1 信息素启发因子α与期望启发因子β的分析 |
34-35 |
|
4.2.2 信息素挥发因子ρ的分析 |
35-36 |
|
4.2.3 蚂蚁数量M的分析 |
36 |
|
4.2.4 总信息量Q的分析 |
36-37 |
|
4.3 基本蚂蚁算法复杂度分析 |
37-39 |
|
4.3.1 时间复杂度分析 |
37-38 |
|
4.3.2 空间复杂度分析 |
38-39 |
|
第五章 基本蚂蚁算法的改进思路 |
39-51 |
|
5.1 变参数 |
39-40 |
|
5.2 局部最优搜索策略 |
40 |
|
5.3 信息激素更新方式 |
40-41 |
|
5.4 优化选路算法 |
41-42 |
|
5.5 个体差异策略 |
42-43 |
|
5.6 改进后的算法 |
43-45 |
|
5.7 改进算法程序的运行结果及其优越性 |
45-51 |
|
第六章 总结与展望 |
51-54 |
|
6.1 全文总结 |
51 |
|
6.2 蚂蚁算法的模型改进展望 |
51-52 |
|
6.3 蚂蚁算法的理论分析展望 |
52 |
|
6.4 蚂蚁算法的应用领域展望 |
52-53 |
|
6.5 蚂蚁算法的智能融合展望 |
53-54 |
|
参考文献 |
54-56 |
|
作者在读期间发表论文 |
56-57 |
|
声明 |
57-58 |
|
学位论文版权使用授权书 |
58-59 |
|
致谢 |
59 |
|
| 【DOI】 | LunWen.ID:2.2008.388313 |
