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

蚁群优化算法及其应用研究

作　者: 何雪海
导　师: 胡小兵
学　校: 重庆大学
专　业: 计算数学
关键词: 蚁群算法组合优化元启发式算法旅行商问题自适应转移概率
分类号: TP301.6
类　型: 硕士论文
年　份: 2011年
下　载: 115次
引　用: 2次
阅　读: 论文下载

内容摘要

组合优化问题的解决在理论和实际应用领域都有非常重要的地位。随着问题规模的扩大,因为计算复杂度的问题,如果使用确定性算法很多组合问题的最优解是无法实现的。蚁群优化元启发式算法是一种专门针对难解的离散优化问题的理想方法,它能在合理的时间得到能够接受的解。蚁群优化算法具有正反馈、分布式、鲁棒性强、易于与其它算法结合的优点。理论上讲,经过适当转化,蚁群优化算法可以解决任何组合优化问题。从最初的蚂蚁系统发展到现在众多的改进蚁群算法,蚁群算法在性能上已经取得了很大的进步。其应用已经涵盖了组合优化、连续函数优化、网络路由、机器学习、图像处理等众多学科。本文主要围绕蚁群优化的原理、基本蚁群算法的改进、蚁群优化理论。就如何改进蚁群算法性能,如何改进算法的全局搜索能力进行了深入的研究。此外还总结了蚁群优化应用规则和使用蚁群优化求解问题的一般步骤,最后给出了一些典型的应用实例。主要研究成果如下:提出一种改进蚁群算法,在转移概率公式中引入一个新的自适应因子以避免算法陷入局部最优解。随着迭代次数的增加,该因子有利于蚂蚁探索较弱信息素浓度的边而避免信息素浓度过度积累。这一特性使蚂蚁在迭代后期仍能以较高概率搜索到更好的解。仿真实验显示,改进后算法对解决旅行商问题有更优的全局搜索能力。

全文目录

中文摘要  3-4
英文摘要  4-7
1 引言  7-10
  1.1 组合优化问题概述  7-8
  1.2 蚁群优化算法研究现状  8-9
  1.3 本论文的主要工作  9-10
2 蚁群优化数学模型  10-17
  2.1 蚁群觅食行为及优化  10-13
  2.2 基于TSP 的蚁群优化数学模型  13-16
  2.3 基于TSP 的蚁群算法基本步骤  16
  2.4 本章小结  16-17
3 基本蚁群算法的改进  17-27
  3.1 精英蚂蚁系统  17
  3.2 基于排列的蚂蚁系统  17-18
  3.3 最大最小蚁群算法  18-19
  3.4 蚁群系统算法  19-20
  3.5 基于自适应调节转移概率的蚁群算法  20-23
  3.6 其它改进策略  23-25
    3.6.1 引入变异  23-24
    3.6.2 引入随机扰动策略的蚁群算法  24
    3.6.3 路径选择策略的改进  24-25
    3.6.4 与其他算法的融合  25
  3.7 本章小结  25-27
4 蚁群优化理论  27-31
  4.1 算法收敛性分析  27-28
  4.2 蚁群优化模型参数的选择  28-30
    4.2.1 启发式因子α、β的分析  28-29
    4.2.2 对挥发系数ρ的分析  29
    4.2.3 蚂蚁群体数目m  29-30
  4.3 本章小结  30-31
5 蚁群算法的其它应用  31-38
  5.1 蚁群算法的使用规则  31-33
    5.1.1 构建图  31-32
    5.1.2 信息素的定义  32
    5.1.3 启发式信息的定义  32
    5.1.4 探索与开发的平衡  32-33
  5.2 应用蚁群算法求解问题的步骤  33
  5.3 二次分配问题  33-35
  5.4 背包问题  35
  5.5 大学课程时间表问题  35-36
  5.6 机器学习问题——分类规则学习  36-37
  5.7 本章小结  37-38
6 结论与展望  38-40
  6.1 结论  38
  6.2 展望  38-40
致谢  40-41
参考文献  41-45
附录  45
  攻读学位期间发表的论文  45

蚁群优化算法及其应用研究

内容摘要

全文目录

相似论文