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

欧氏Steiner最小树问题的智能优化算法研究

作　者: 金慧敏
导　师: 马良
学　校: 上海理工大学
专　业: 系统工程
关键词: 欧氏Steiner最小树插入算法递增优化算法遗传算法模拟退火算法蚂蚁算法
分类号: O224
类　型: 硕士论文
年　份: 2005年
下　载: 143次
引　用: 1次
阅　读: 论文下载

内容摘要

欧氏Steiner最小树问题,即在欧氏平面上连接给定原点的最小树长问题,是组合优化中的一个NP难题。难计算是该问题的固有属性,因此目前尚无有效算法对其进行精确求解。但此问题在实际中却有广泛应用,因而寻找其实际而有效的启发式算法就显得颇为重要。近年来,新出现的智能优化算法,如模拟退火算法、遗传算法、禁忌搜索法、人工神经网络法、蚂蚁算法、微粒群算法等,以其独特的优点和机制,引起了国内外学者的广泛重视并掀起了该领域的研究热潮。因此,除研究传统意义上的启发式算法外,本文重点讨论了智能优化算法。传统的启发式算法是建立在对问题有全面清晰的认识基础上,本文的插入算法和递增优化算法也不例外。它们根据欧氏Steiner最小树的性质设计而出,试验结果表明它们具有良好的性能,但也存在着一定的缺陷。转而采用遗传算法、模拟退火算法和蚂蚁算法来求解此问题。遗传算法是一种高度并行、随机和自适应的优化算法,其将问题的求解表示成“染色体”的适者生存过程,从而求得最优解或满意解;模拟退火算法是基于Monte Carlo迭代求解的一种随机寻优算法,其出发点是基于物理学中固体物质的退火过程与组合优化问题之间的相似性;新近出现的蚂蚁算法是一种模仿生物世界中蚂蚁觅食行为的仿生类算法,用蚁群在搜索食物源过程中所体现出来的寻优能力来解决优化问题。本文的具体内容包括:第一章提出了本文的选题背景、研究内容和研究意义。第二章介绍了各种Steiner树问题,重点阐述欧氏Steiner最小树。第三章给出了本文用到的算法工具,包括领域函数、局部搜索、最小生成树等。详细阐述了插入算法和递增优化算法的实现过程,并对问题实例进行测试,依据测试结果对两者进行比较。稍候引出智能优化算法,并进行简要介绍。第四、五、六章分别详述遗传算法、模拟退火算法和蚂蚁算法的有关情况,包括发展历史、原理、流程、构成要素、特征、优缺点等方面,最终给出三种算法的具体实现过程。第七章主要讨论了采用遗传算法、模拟退火算法和蚂蚁算法对不同规模的问题实例进行测试,从运行时间、计算结果值大小和计算结果值稳定性三方面来比较算法的性能。最后还对智能优化算法和传统算法进行比较。第八章对本文内容进行总结,简要评价上述算法,并提出改进的方法。上述5种算法在微机上予以实现。测试所得结果大多优于最小生成树,表现了良好的性能。因欧氏Steiner最小树问题本身所固有的难解特性,其理论和解决方法还没有完全发展成熟,有待进一步研究。

全文目录

中文摘要  2-3
ABSTRACT  3-7
第一章绪论  7-14
  1.1 选题背景  7-8
  1.2 相关概念  8-13
  1.3 本文的研究内容及意义  13-14
第二章欧氏 Steiner 最小树问题  14-23
  2.1 常规的Steiner 树问题  14-16
  2.2 带附加条件的Steiner 树问题  16-17
  2.3 欧氏Steiner 最小树问题  17-23
    2.3.1 问题概述  17-18
    2.3.2 性质  18-20
    2.3.3 拓扑结构  20-23
第三章启发式算法  23-37
  3.1 概述  23-24
  3.2 算法工具  24-26
  3.3 传统算法  26-31
    3.3.1 插入算法  26-27
    3.3.2 递增优化算法  27
    3.3.3 计算试验  27-31
  3.4 智能优化算法  31-37
    3.4.1 各种算法简介  31-36
    3.4.2 智能优化算法特点  36-37
第四章遗传算法  37-46
  4.1 简介  37
  4.2 算法描述  37-41
    4.2.1 构成要素  38-40
    4.2.2 基本流程  40-41
  4.3 遗传算法的基本特征和优缺点  41-44
    4.3.1 基本特征  41-42
    4.3.2 优缺点  42-44
  4.4 遗传算法求解ESMT 问题  44-46
第五章模拟退火算法  46-55
  5.1 简介  46-48
  5.2 算法描述  48-51
    5.2.1 组合优化与物理退火的相似性  49-50
    5.2.2 算法流程  50-51
  5.3 特点  51-52
  5.4 模拟退火算法求解ESMT 问题  52-55
第六章蚂蚁算法  55-67
  6.1 简介  55-57
  6.2 算法描述  57-61
    6.2.1 基本原理  57-60
    6.2.2 基本流程  60-61
  6.3 蚂蚁算法的特征和优缺点  61-65
    6.3.1 系统学特征  61-64
    6.3.2 优缺点  64-65
  6.4 蚂蚁算法求解ESMT 问题  65-67
第七章计算试验  67-80
  7.1 智能优化算法求解原点个数n≤10 时的ESMT 问题  67-70
  7.2 智能优化算法求解原点个数12≤n≤20 时的ESMT 问题  70-73
  7.3 智能优化算法求解原点个数n=50 时的ESMT 问题  73-77
  7.4 智能优化算法试验结果小结  77-78
  7.5 智能优化算法与插入算法比较  78-80
第八章总结  80-86
  8.1 内容总结  80-81
  8.2 算法评价  81-83
  8.3 算法改进  83-86
附录  86-94
参考文献  94-98
在读期间公开发表的论文和承担科研项目及取得成果  98-99
致谢  99

欧氏Steiner最小树问题的智能优化算法研究

内容摘要

全文目录

相似论文