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

自适应的并行蚁群算法及其应用

作　者: 章春芳
导　师: 陈崚
学　校: 扬州大学
专　业: 计算机应用技术
关键词: 并行蚁群算法信息交流 MPI 并行计算优化问题
分类号: TP301.6
类　型: 硕士论文
年　份: 2006年
下　载: 572次
引　用: 4次
阅　读: 论文下载

内容摘要

蚁群算法(Ant Colony Algorithm)是一种新型的求解复杂优化问题的模拟进化算法,它是由意大利学者M.Dorigo等人受到自然界中真实蚁群集体行为的启发而首先提出来的。大量实验结果表明,它在解决许多组合优化问题时都能表现出较好的求解能力,经过了许多国内外学者不断地对其进行扩展和改进,蚁群算法正经历着一个不断发展和完善的过程。大量模拟实验表明,对于中小规模的应用问题,蚁群算法一般能够在许可的时间范围内获得满意解,而对于大规模或超大规模的求解任务,简单的串行蚁群算法则力不从心。另外,简单串行蚁群算法在应用过程中一个比较突出的问题是它容易产生早熟现象,这主要是因为在搜索初期,众多蚂蚁个体的运动较为随机,所以蚂蚁很难在较短时间内从复杂无章的路径中找出一条较好的路径。但是如果一味加快收敛速度容易出现停滞现象,即搜索进行到一定程度后,所有个体所发现的解完全一致,不能对解空间进一步地搜索。这些缺点将严重地影响蚁群算法的应用。因此,人们利用蚁群算法固有的并行特性,将并行技术与传统的蚁群算法相结合,从而来提高蚁群算法的效率和减少蚁群算法早熟现象的发生。本文在分析蚁群算法的原理及性能的基础上,指出了影响并行蚁群算法性能的关键因素为:确定信息交流的对象、交流的内容和交流周期,给出了优化这三个因素的具体策略,在此基础上提出了自适应的并行蚁群算法。在确定信息交流对象方面,为了克服传统并行蚁群算法中处理机无规律地选择信息交流对象的缺点,我们提出了基于适应度排序、基于子种群的收敛系数等策略。在信息交流内容方面,我们提出了新的交流策略,使得处理机之间除了交流局部最优解之外,可以交流具有较高信息素的超顶点,还可以交流信息素矩阵,以利用子群体上信息素的正负反馈作用来改变子群体的进化环境。在确定信息交流周期方面,我们提出了根据解的多样性和收敛系数来自适应地调节信息交流周期的策略,以增强算法的搜索能力。这些不同的信息交流策略将形成不同的并行策略,从而得到不同的并行蚁群算法。本文将这些自适应的并行蚁群算法应用于频率分配问题、二次分配问题、旅行商问题;并采用MPI绑定C语言进行编程,对实验得到的数据进行了比较和分析,证明了我们所提出的自适应并行蚁群算法能够在解的多样性和收敛速度之间取得很好的平衡,具有较强的优化能力、更快的处理速度,适合于解决大规模的、复杂的优化问题。

全文目录

中文摘要  3-4
英文摘要  4-9
第一章绪论  9-14
  1.1 研究背景  9-11
  1.2 主要工作  11-13
  1.3 论文组织  13-14
第二章并行处理技术  14-21
  2.1 并行计算机体系结构  14-15
    2.1.1 并行计算机结构模型  14
    2.1.2 并行计算机访存模型  14-15
  2.2 并行算法  15
  2.3 并行计算性能测评  15-17
  2.4 并行程序设计  17-20
    2.4.1 并行编程模型  17-18
    2.4.2 分布存储系统并行编程  18-20
  2.5 本章小结  20-21
第三章并行蚁群算法  21-41
  3.1 蚁群算法  21-28
    3.1.1 蚁群算法的基本原理  21-23
    3.1.2 基本蚁群系统的实现技术  23-26
    3.1.3 蚁群算法的扩展  26-28
  3.2 引入并行蚁群算法的理由  28-32
    3.2.1 蚁群算法固有的并行性  29-30
    3.2.2 解决蚁群算法的早熟收敛现象  30
    3.2.3 硬件技术的支持  30-31
    3.2.4 其它算法并行化的启发  31-32
  3.3 并行蚁群算法概述  32-40
    3.3.1 并行蚁群算法的基本框架  32-33
    3.3.2 并行蚁群算法的研究现状  33-38
    3.3.3 影响算法性能的因素  38-40
  3.4 本章小结  40-41
第四章自适应并行蚁群算法  41-55
  4.1 自适应并行蚁群算法的基本思想  41
  4.2 确定信息交流对象的策略  41-45
    4.2.1 基于适应度排序的策略  42
    4.2.2 基于处理机上最优解间的距离的策略  42-43
    4.2.3 基于子种群的收敛系数的策略  43-44
    4.2.4 基于最优蚂蚁个体的邻接距离的策略  44-45
  4.3 处理机间信息交流的内容  45-51
    4.3.1 交流局部最优解的策略  45-47
    4.3.2 交流信息素的策略  47-49
    4.3.3 交流超顶点的策略  49-51
  4.4 动态调节信息交流周期  51-53
    4.4.1 基于解的多样性的策略  52-53
    4.4.2 基于收敛系数的策略  53
  4.5 本章小结  53-55
第五章自适应并行蚁群算法的应用及实验结果  55-85
  5.1 频率分配问题（FAP）  55-70
    5.1.1 问题描述  55-56
    5.1.2 基于进化稳定策略的蚁群算法  56-59
    5.1.3 求解频率分配问题的自适应并行蚁群算法的实现  59-66
    5.1.4 算法描述  66-67
    5.1.5 试验结果及分析  67-70
  5.2 二次分配问题（QAP）  70-78
    5.2.1 问题描述  70
    5.2.2 求解 QAP 的基本蚁群算法  70-71
    5.2.3 求解 QAP 问题的信息素多种反馈作用的并行蚁群算法  71-73
    5.2.4 算法性能分析  73-76
    5.2.5 试验结果及分析  76-78
  5.3 旅行商问题（TSP）  78-84
    5.3.1 问题描述  78-79
    5.3.2 基于信息素递减的蚁群算法  79-80
    5.3.3 求解 TSP 问题的基于超顶点交流策略的自适应并行蚁群算法  80-82
    5.3.4 试验结果及分析  82-84
  5.4 本章小结  84-85
第六章总结与展望  85-89
  6.1 我们的工作和贡献  85-87
  6.2 将来的工作  87-89
参考文献  89-96
致谢  96-97
攻读硕士学位期间发表的学术论文和参加的研究工作  97

自适应的并行蚁群算法及其应用

内容摘要

全文目录

相似论文