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

蚁群算法的改进及其在TSP与VRP问题中的应用

作　者: 刘桂青
导　师: 何登旭
学　校: 广西民族大学
专　业: 计算机应用技术
关键词: 蚁群系统蚁群算法改进 TSP 问题 VRP 物流运输组合优化
分类号: TP301.6
类　型: 硕士论文
年　份: 2010年
下　载: 157次
引　用: 0次
阅　读: 论文下载

内容摘要

蚁群算法是通过研究自然界蚂蚁觅食行为而形成的一种新兴群智能算法,具有正反馈机制、并行计算、易于与其他算法相结合等特点。从提出后引起国内外学者的密切关注,并被迅速应用于求解许多组合优化问题且取得较好效果,但由于蚁群算法采用随机选择策略、信息素更新、正反馈机制强化当前最优解等操作来逐步逼近问题全局最优解,导致算法搜索时间长,且极易陷入局部最优并产生停滞现象。为了在保证解质量的前提下提高收敛速度,本文首先对蚁群算法的研究现状和应用、基本原理、数学模型及参数设置等进行总结概述,具体分析了蚁群算法典型代表AS和ACS算法产生缺陷的原因,针对收敛速度慢、易早熟等不足,从信息素初始化、信息素更新和启发因子三方面进行改进,提出一种基于信息素初始化多样性、动态加权更新和启发因子动态增强策略的新的改进蚁群算法(DDS-ACS)。根据车辆路径和物流运输问题的自身特征,对本文改进蚁群算法在选择策略和初始点选取等方面作进一步优化,并将其应用于求解TSP、VRP问题及物流运输问题,通过多个典型TSP、VRP及物流运输实例仿真对比分析,表明本文DDS-ACS算法较AS、ACS及文献中的改进蚁群算法在收敛速度方面有较大提高,在解质量方面有更强的全局搜索能力,体现了本文DDS-ACS算法的优越性,一定程度上证明了本文DDS-ACS算法具有较好的可行性和有效性。

全文目录

摘要  3-4
ABSTRACT  4-7
1 绪论  7-10
  1.1 蚁群算法的产生背景  7-8
  1.2 蚁群算法的研究现状及其应用概述  8-9
  1.3 主要研究内容及结构设置  9-10
2 基本蚁群算法(AS)  10-15
  2.1 算法的原理及模型  10-11
  2.2 算法的实现步骤  11-12
  2.3 算法的流程图  12
  2.4 算法的参数设置及分析  12-13
  2.5 算法的优点与不足  13-15
3 蚁群算法的改进及其成果  15-19
  3.1 五种代表性的改进蚁群算法  15-17
    3.1.1 带精英思想的蚂蚁系统(ASelite)  15
    3.1.2 基于排序策略的蚂蚁系统(ASrank )  15
    3.1.3 蚁群系统（ACS）  15-16
    3.1.4 最大最小蚂蚁系统（MMAS）  16-17
    3.1.5 最优最差蚂蚁系统（BWAS）  17
  3.2 其它改进蚁群算法  17-19
    3.2.1 带变异策略的蚁群算法  17
    3.2.2 基于分布均匀度思想的蚁群算法  17-19
4 一种新的改进蚁群算法及其在 TSP 中的应用  19-25
  4.1 DDS-ACS 算法主要思想  19-23
    4.1.1 初始信息素多样化策略  19-20
    4.1.2 局部信息素动态更新  20-21
    4.1.3 全局信息素动态更新  21-22
    4.1.4 启发因子动态增强  22-23
  4.2 DDS-ACS 算法求解 TSP 问题  23-24
    4.2.1 求解TSP 问题的DDS-ACS 算法步骤  23
    4.2.2 实例仿真及分析  23-24
  4.3 小结  24-25
5 DDS-ACS 算法在 VRP 及物流运输问题中的应用  25-33
  5.1 DDS-ACS 算法求解 VRP 问题  25-30
    5.1.1 VRP 问题的描述及其基本模型  25-26
    5.1.2 VRP 问题的研究现状  26
    5.1.3 蚁群算法求解 TSP 与 VRP 的区别  26-27
    5.1.4 求解 VRP 问题的 DDS-ACS 算法步骤  27
    5.1.5 实例仿真及分析  27-30
  5.2 DDS-ACS 算法求解物流运输问题  30-33
    5.2.1 物流运输基本模型  30
    5.2.2 求解物流运输问题的 DDS-ACS 算法步骤  30-31
    5.2.3 实例仿真及分析  31-33
6 主要结论  33-34
参考文献  34-36
致谢  36-37
攻读学位期间发表的学术论文及参与项目  37

蚁群算法的改进及其在TSP与VRP问题中的应用

内容摘要

全文目录

相似论文