学位论文 > 优秀研究生学位论文题录展示

改进的蚁群优化算法及其在TSP中的应用

作　者: 吴志峰
导　师: 胡小兵
学　校: 重庆大学
专　业: 运筹学与控制论
关键词: 蚁群优化蚁群算法信息素交税蚁群算带路径评估蚁群算法
分类号: TP301.6
类　型: 硕士论文
年　份: 2009年
下　载: 167次
引　用: 0次
阅　读: 论文下载

内容摘要

意大利学者M.Dorigo,V.Maniezzo和A.Colorni于1992年通过模拟蚂蚁的觅食行为提出了一种基于种群的模拟进化算法--蚁群算法,并成功应用于求解著名的TSP问题,而后渗透到多个应用领域,从解决一维静态优化问题到解决多维动态组合优化问题,从离散范围内的研究逐渐拓展到连续范围内的研究,如在系统控制、人工智能、模式识别、生产调度等方面。本文主要围绕蚁群算法的改进及其在TSP中的应用展开,就如何改进蚁群算法、抑制算法出现停滞、以及在TSP中的应用进行了深入研究。文章的主要研究工作如下:针对蚁群算法容易早熟、收敛速度慢等缺点,提出了两种改进的蚁群算法。1、基于交税的蚁群算法。首先在蚂蚁搜索过程中采用动态伪随机比例选择机制,在搜索的前期,保证了搜索的范围较大,在搜索后期,保证了算法的收敛性;同时,根据缴纳个人所得税的方式,在进行全局信息素更新的时候,每隔一段时间,当前最优路径再缴纳一定的信息素税,从而提高了算法搜索较好解的能力。2、带路径评估的蚁群算法。所有蚂蚁每完成一次路径搜索,记录下每只蚂蚁搜索到的路径长度,根据改进的标准方差计算公式来评估当前搜索的情况,决定是否要进行信息素全局更新;同时,采用区间压缩函数,如果在一段搜索时间内没有出现更优的解,可能出现了早熟现象,这时,对所有路径上的信息素压缩,调整蚂蚁对每个城市的搜索概率。通过仿真试验,并与蚂蚁系统和蚁群系统进行比较,试验结果表明,这两种改进的算法在避免早熟方面、搜索最优解和稳定性等方面具有较好的表现。最后,对全文的研究工作进行了总结,并展望了蚁群优化算法进一步还要研究的课题。

全文目录

摘要  3-4
ABSTRACT  4-8
1 绪论  8-15
  1.1 引言  8
  1.2 蚁群优化算法  8-12
    1.2.1 蚁群行为描述  8-10
    1.2.2 蚁群优化算法的机制原理  10-12
    1.2.3 蚁群优化算法特点  12
  1.3 蚁群优化算法研究现状  12-13
  1.4 本文主要工作  13-15
2 基本蚁群算法  15-22
  2.1 引言  15
  2.2 旅行商问题（TSP）  15
  2.3 基本蚁群算法  15-21
    2.3.1 基本蚁群算法的机制原理  15-17
    2.3.2 基本蚁群算法数学模型  17-19
    2.3.3 基本蚁群算法的具体实现  19-21
  2.4 本章小结  21-22
3 蚁群优化（ACO）元启发式及其收敛性  22-34
  3.1 引言  22
  3.2 蚁群优化元启发式算法  22-28
    3.2.1 人工蚂蚁与真实蚂蚁异同  22-23
    3.2.2 蚁群优化元启发式  23-28
  3.3 蚁群优化的收敛性  28-33
    3.3.1 蚁群优化收敛性概述  28
    3.3.2 保证收敛到最优的ACO 算法  28-33
  3.4 本章小结  33-34
4 蚁群算法的改进算法  34-49
  4.1 引言  34
  4.2 蚁群算法的优点与不足  34
  4.3 蚁群算法的改进  34-38
    4.3.1 精华蚂蚁系统  34-35
    4.3.2 基于排列的蚂蚁系统  35
    4.3.3 最大最小蚂蚁系统  35-36
    4.3.4 蚁群系统  36-37
    4.3.5 各种蚁群算法的比较  37-38
  4.4 基于交税的蚁群算法(RACA)  38-42
    4.4.1 引言  38
    4.4.2 RACA 算法设计  38-40
    4.4.3 RACA 算法的实现过程  40
    4.4.4 仿真实验  40-42
  4.5 带路径评估的蚁群算法(REACA)  42-48
    4.5.1 引言  42
    4.5.2 REACA 算法设计  42-44
    4.5.3 REACA 算法实现  44-46
    4.5.4 仿真实验  46-48
  4.6 本章小结  48-49
5 总结与展望  49-51
  5.1 总结  49
  5.2 展望  49-51
致谢  51-52
参考文献  52-55
附录  55

改进的蚁群优化算法及其在TSP中的应用

内容摘要

全文目录

相似论文