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

蚁群算法理论、应用及其与其它算法的混合

作　者: 高尚
导　师: 杨静宇
学　校: 南京理工大学
专　业: 模式识别与智能系统
关键词: 蚁群算法整数规划聚类问题 K-均值算法模拟退火算法遗传算法混沌粒子群优化算法旅行商问题
分类号: TP301
类　型: 博士论文
年　份: 2005年
下　载: 5300次
引　用: 22次
阅　读: 论文下载

内容摘要

意大利学者Dorigo M．，Maniezzo V．和Colorni A．于1992年通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法—蚁群优化(ACO)。该算法的出现引起了学者们的极大关注，在过去短短十多年的时间里，已在组合优化、网络路由、函数优化、数据挖掘、机器人路径规划等领域获得了广泛的应用，并取得了较好的效果。本论文围绕蚁群算法的理论及其应用，就如何解决非线性整数规划问题、连续性优化问题、聚类问题、与其它算法混合以及收敛性进行了较为深入、系统的研究。本文的主要研究成果包括： (1) 提出了一种新的蚁群算法来求解无约束的整数规划问题。蚂蚁在整数空间内运动，同时在路径上留下激素，以此引导搜索方向。对蚁群算法参数的合理选取进行了实验分析，给出了算法参数选取的基本原则。数值试验计算结果表明该方法比较有效，并具有通用性。对几个典型的整数规划问题，如武器-目标分配、多处理机调度、可靠性优化等问题，根据各问题的特点，采用了不完全相同方法，并与其他方法作了比较，效果比较有效。提出了一种求解旅行商问题的多样信息素的蚁群算法。根据蚁群算法信息素更新的特性，把蚁群的三种不同的信息素更新方式混合在一起，既利用了局部信息，又考虑了整体信息，将局部搜索和全局搜索相结合，使收敛性得到提高。旅行商问题的仿真实验结果表明了该混合算法的有效性。提出一种解决连续优化问题的蚁群算法。把连续解空间分成若干空间网格点，采用蚁群算法找出信息量大的空间网格点，缩小变量范围，继续找出信息量大的空间网格点，直到网格的间距小于预先给定的精度。 (2) 对模式识别中典型问题-聚类问题进行了研究，提出了两种求解聚类问题的蚁群算法。一种方法是模拟蚂蚁寻食过程，蚂蚁在模式样本到聚类中心的路径上留下外激素，外激素引导聚类过程；另一种是与K-均值算法混合，利用K-均值方法的结果作为初值，根据分类结果更新信息素。测试数据显示与K-均值算法混合的算法效果相当好。 (3) 提出了与模拟退火算法混合的两种算法。一种是在模拟退火算法中运用蚁群算法思想找邻域的解，称为蚁群模拟退火算法，并用该算法解决圆排列问题；另一种是由模拟退火算法生成初始信息素分布，然后由蚁群算法根据累计更新的信息素找出若干组解后，再经过模拟退火算法在邻域内找另外一个解的操作，得到更有效的解，称为模拟退火蚁群算法，并用该算法解决旅行商问题。 (4) 根据蚁群算法与遗传算法的特性，提出了与遗传算法混合的蚁群算法。由遗传算法生成初始信息素分布，在蚂蚁算法寻优中，采用遗传算法的交叉和变异的策略，得到更有效的解。

全文目录

摘要  5-7
Abstract  7-10
目录  10-14
1 绪论  14-24
  1.1 引言  14
  1.2 蚁群算法的基本原理  14-18
  1.3 蚁群算法理论研究现状  18-20
  1.4 蚁群算法应用研究现状  20-21
  1.5 本文的主要工作  21-22
  1.6 本文的内容安排  22-24
2 求解整数规划的蚁群算法  24-44
  2.1 求解一般非线性整数规划的蚁群算法  24-28
    2.1.1 引言  24
    2.1.2 求解非线性整数规划的蚁群算法  24-26
    2.1.3 算例分析  26-28
  2.2 武器-目标分配问题的蚁群算法  28-31
    2.2.1 引言  28
    2.2.2 武器-目标分配问题  28-29
    2.2.3 武器-目标分配问题的蚁群算法  29-30
    2.2.4 仿真结果  30-31
  2.3 多处理机调度问题的蚁群算法  31-35
    2.3.1 引言  31
    2.3.2 多处理机调度问题数学模型  31-32
    2.3.3 解多处理机调度问题模拟退火算法  32-33
    2.3.4 解多处理机调度问题蚁群算法  33
    2.3.5 算法比较  33-35
  2.4 可靠性优化的蚁群算法  35-41
    2.4.1 引言  35
    2.4.2 最优冗余优化模型及解法  35-36
    2.4.3 可靠性优化的模拟退火算法  36-37
    2.4.4 可靠性优化的遗传算法  37-38
    2.4.5 可靠性优化的蚁群算法  38-39
    2.4.6 算例分析  39-41
  2.5 求解旅行商问题的多样信息素的蚁群算法  41-43
    2.5.1 信息素更新的三个模型  41
    2.5.2 多样信息素更新规则  41-42
    2.5.3 算法测试  42-43
  2.6 本章小结  43-44
3 连续优化问题的蚁群算法研究  44-47
  3.1 无约束非线性最优化问题  44
  3.2 连续优化问题的蚁群算法  44-46
  3.3 数值分析  46
  3.4 本章小结  46-47
4 聚类问题的蚁群算法  47-52
  4.1 引言  47
  4.2 聚类问题的数学模型  47
  4.3 解聚类问题的K均值算法  47-48
  4.4 解聚类问题的模拟退火算法  48
  4.5 解聚类问题的蚁群算法及数值分析  48-50
    4.5.1 解聚类问题的蚁群算法  48-49
    4.5.2 数值分析  49-50
  4.6 解聚类问题的与K-均值算法混合的蚁群算法及数值分析  50-51
    4.6.1 解聚类问题的K-均值算法混合的蚁群算法  50-51
    4.6.2 数值分析  51
  4.7 本章小结  51-52
5 与模拟退火算法混合  52-60
  5.1 引言  52
  5.2 解圆排列问题的蚁群模拟退火算法  52-57
    5.2.1 圆排列问题及与旅行商问题等价  52-53
    5.2.2 解旅行商问题的模拟退火算法  53-54
    5.2.3 几种算法的比较  54-56
    5.2.4 算例分析  56-57
  5.3 解旅行商问题的模拟退火蚁群算法  57-59
    5.3.1 混合的基本思想  57
    5.3.2 找邻域解策略  57-58
    5.3.3 模拟退火蚁群算法  58
    5.3.4 算法测试  58-59
  5.4 本章小结  59-60
6 与遗传算法混合  60-65
  6.1 引言  60
  6.2 基本遗传算法  60
  6.3 蚁群算法与遗传算法的混合  60-63
    6.3.1 混合的基本思想  60-61
    6.3.2 遗传算法的变异操作  61-62
    6.3.3 遗传算法的交叉操作  62
    6.3.4 遗传蚁群算法  62-63
  6.4 算法测试  63-64
  6.5 本章小结  64-65
7 与混沌理论混合  65-70
  7.1 引言  65
  7.2 混沌及运动特性  65
  7.3 基本蚁群算法改进  65-67
    7.3.1 混沌初始化  65-67
    7.3.2 选择较优解  67
    7.3.3 混沌扰动  67
  7.4 混沌蚁群算法  67-68
  7.5 算法测试  68-69
  7.6 本章小结  69-70
8 与粒子群算法混合  70-92
  8.1 粒子群算法基本理论  70-71
  8.2 模拟退火思想的粒子群算法  71-74
    8.2.1 几种模拟退火思想的粒子群算法  71-73
    8.2.2 算法测试  73-74
  8.3 背包问题的混合粒子群优化算法  74-78
    8.3.1 背包问题数学模型  74
    8.3.2 解0-1背包问题的混合粒子群算法  74-76
    8.3.3 数值仿真与分析  76-78
  8.4 混沌粒子群优化算法研究  78-82
    8.4.1 基本粒子群算法不足  78-79
    8.4.2 混沌粒子群优化算法  79-80
    8.4.3 算法测试  80-82
  8.5 粒子群优化算法在其他方面应用  82-84
    8.5.1 指派问题的粒子群优化算法  82
    8.5.2 武器-目标分配问题的粒子群优化算法  82-83
    8.5.3 解聚类问题的粒子群算法  83-84
  8.6 蚁群算法与粒子群优化算法的混合  84-91
    8.6.1 引言  84-85
    8.6.2 求解旅行商问题的混合粒子群优化算法  85-88
    8.6.3 求解旅行商问题粒子群-蚁群算法  88-91
  8.7 本章小结  91-92
9 最短路的蚁群算法收敛性分析  92-100
  9.1 引言  92
  9.2 最短路的蚁群算法收敛性分析  92-94
  9.3 仿真算例  94-99
  9.4 本章小结  99-100
结束语  100-103
致谢  103-104
参考文献  104-110
附录  110-111

蚁群算法理论、应用及其与其它算法的混合

内容摘要

全文目录

相似论文