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

改进的蚁群算法在TSP问题上的应用

作　者: 江迎春
导　师: 王江晴
学　校: 中南民族大学
专　业: 计算机应用技术
关键词: TSP问题蚁群算法组合优化模糊集合
分类号: TP301.6
类　型: 硕士论文
年　份: 2009年
下　载: 161次
引　用: 3次
阅　读: 论文下载

内容摘要

旅行商问题(Traveling Salesman Problem,TSP)是近代组合优化领域的一个典型难题。现实生活中的很多问题都可以转化为TSP问题,如邮路问题、通讯网络设计、大规模集成电路的综合布线设计等。因此,对TSP问题的研究具有重要的理论意义和实际应用价值。然而关于TSP问题的完全有效的算法目前尚未找到,这促使人们长期以来不断地探索并积累了大量的算法。本文所用到的蚁群算法也在其中。蚁群算法是受大自然中蚂蚁觅食启发而提出的一种智能仿生算法,具有较强的鲁棒性、分布式计算、易于与其它方法结合等优点。本文提出一种基于模糊集合的改进蚁群算法,该算法根据隶属度对种群进行评价,并依此进行信息素的更新,在求解速度和解的质量上取得一个较好的平衡。通过对改进算法的仿真实验,验证了该算法的可行性及有效性。本文主要的研究工作如下:1.阐述了论文研究的背景及意义,总结了迄今为止出现的求解TSP问题的各种方法,并对常见的求解方法的优缺点进行了详细的分析,最后,分析了蚁群算法国内外研究现状。2.给出了蚁群算法的基本原理、算法模型以及特点。3.提出一种改进的蚁群算法。该算法引入模糊集合的概念,利用隶属度对蚁群寻找到的路径进行模糊评价,并根据模糊评价结果对路径上的信息素进行更新,从而加快了算法收敛速度,提高了算法的性能。4.采用均匀设计法设置改进算法的参数,通过数值实验,验证了改进算法的可行性和有效性。

全文目录

摘要  7-8
ABSTRACT  8-9
第1章绪论  9-17
  1.1 论文选题背景与意义  9-10
  1.2 TSP 问题简介  10-14
    1.2.1 TSP 问题的定义  10-11
    1.2.2 求解TSP 问题的智能优化算法  11-14
  1.3 蚁群算法研究现状  14-15
  1.4 本文主要工作和内容  15-17
第2章蚁群算法  17-27
  2.1 蚁群算法的原理  17-19
    2.1.1 蚁群觅食的特性  17-18
    2.1.2 蚁群算法的基本思想  18-19
  2.2 蚁群算法的模型  19-22
  2.3 蚁群算法的参数分析  22-25
  2.4 蚁群算法的优缺点  25-27
    2.4.1 蚁群算法的优点  25
    2.4.2 蚁群算法的缺点  25-27
第3章一种改进的蚁群算法  27-34
  3.1 改进的蚁群算法FACO 的思想  27-28
  3.2 改进的策略  28-29
    3.2.1 更新规则  28
    3.2.2 信息素的更新  28-29
  3.3 FACO 算法求解TSP 问题  29-34
    3.3.1 FACO 算法框架  29
    3.3.2 初始信息素的设置  29
    3.3.3 确定模糊子集及隶属函数  29-30
    3.3.4 状态转移规则的实现  30
    3.3.5 初始参数的设置  30-31
    3.3.6 FACO 算法的实现  31-34
第4章数值实验及结果分析  34-43
  4.1 实验一  34-38
  4.2 实验二  38-40
  4.3 实验三  40-41
  4.4 实验四  41-42
  4.5 算法分析  42-43
第5章结论与展望  43-44
参考文献  44-48
致谢  48-49
攻读学位期间所发表的学术论文  49

改进的蚁群算法在TSP问题上的应用

内容摘要

全文目录

相似论文