论文题目: 欧氏Steiner最小树问题的智能优化算法研究
论文类型: 硕士论文
论文专业: 系统工程
作者: 金慧敏
导师: 马良
关键词: 欧氏最小树,插入算法,递增优化算法,遗传算法,模拟退火算法,蚂蚁算法
文献来源: 上海理工大学
发表年度: 2005
论文摘要: 欧氏Steiner最小树问题,即在欧氏平面上连接给定原点的最小树长问题,是组合优化中的一个NP难题。难计算是该问题的固有属性,因此目前尚无有效算法对其进行精确求解。但此问题在实际中却有广泛应用,因而寻找其实际而有效的启发式算法就显得颇为重要。近年来,新出现的智能优化算法,如模拟退火算法、遗传算法、禁忌搜索法、人工神经网络法、蚂蚁算法、微粒群算法等,以其独特的优点和机制,引起了国内外学者的广泛重视并掀起了该领域的研究热潮。因此,除研究传统意义上的启发式算法外,本文重点讨论了智能优化算法。传统的启发式算法是建立在对问题有全面清晰的认识基础上,本文的插入算法和递增优化算法也不例外。它们根据欧氏Steiner最小树的性质设计而出,试验结果表明它们具有良好的性能,但也存在着一定的缺陷。转而采用遗传算法、模拟退火算法和蚂蚁算法来求解此问题。遗传算法是一种高度并行、随机和自适应的优化算法,其将问题的求解表示成“染色体”的适者生存过程,从而求得最优解或满意解;模拟退火算法是基于Monte Carlo迭代求解的一种随机寻优算法,其出发点是基于物理学中固体物质的退火过程与组合优化问题之间的相似性;新近出现的蚂蚁算法是一种模仿生物世界中蚂蚁觅食行为的仿生类算法,用蚁群在搜索食物源过程中所体现出来的寻优能力来解决优化问题。本文的具体内容包括:第一章提出了本文的选题背景、研究内容和研究意义。第二章介绍了各种Steiner树问题,重点阐述欧氏Steiner最小树。第三章给出了本文用到的算法工具,包括领域函数、局部搜索、最小生成树等。详细阐述了插入算法和递增优化算法的实现过程,并对问题实例进行测试,依据测试结果对两者进行比较。稍候引出智能优化算法,并进行简要介绍。第四、五、六章分别详述遗传算法、模拟退火算法和蚂蚁算法的有关情况,包括发展历史、原理、流程、构成要素、特征、优缺点等方面,最终给出三种算法的具体实现过程。第七章主要讨论了采用遗传算法、模拟退火算法和蚂蚁算法对不同规模的问题实例进行测试,从运行时间、计算结果值大小和计算结果值稳定性三方面来比较算法的性能。最后还对智能优化算法和传统算法进行比较。第八章对本文内容进行总结,简要评价上述算法,并提出改进的方法。上述5种算法在微机上予以实现。测试所得结果大多优于最小生成树,表现了良好的性能。因欧氏Steiner最小树问题本身所固有的难解特性,其理论和解决方法还没有完全发展成熟,有待进一步研究。
论文目录:
中文摘要
ABSTRACT
第一章 绪论
1.1 选题背景
1.2 相关概念
1.3 本文的研究内容及意义
第二章 欧氏 Steiner 最小树问题
2.1 常规的Steiner 树问题
2.2 带附加条件的Steiner 树问题
2.3 欧氏Steiner 最小树问题
2.3.1 问题概述
2.3.2 性质
2.3.3 拓扑结构
第三章 启发式算法
3.1 概述
3.2 算法工具
3.3 传统算法
3.3.1 插入算法
3.3.2 递增优化算法
3.3.3 计算试验
3.4 智能优化算法
3.4.1 各种算法简介
3.4.2 智能优化算法特点
第四章 遗传算法
4.1 简介
4.2 算法描述
4.2.1 构成要素
4.2.2 基本流程
4.3 遗传算法的基本特征和优缺点
4.3.1 基本特征
4.3.2 优缺点
4.4 遗传算法求解ESMT 问题
第五章 模拟退火算法
5.1 简介
5.2 算法描述
5.2.1 组合优化与物理退火的相似性
5.2.2 算法流程
5.3 特点
5.4 模拟退火算法求解ESMT 问题
第六章 蚂蚁算法
6.1 简介
6.2 算法描述
6.2.1 基本原理
6.2.2 基本流程
6.3 蚂蚁算法的特征和优缺点
6.3.1 系统学特征
6.3.2 优缺点
6.4 蚂蚁算法求解ESMT 问题
第七章 计算试验
7.1 智能优化算法求解原点个数n≤10 时的ESMT 问题
7.2 智能优化算法求解原点个数12≤n≤20 时的ESMT 问题
7.3 智能优化算法求解原点个数n=50 时的ESMT 问题
7.4 智能优化算法试验结果小结
7.5 智能优化算法与插入算法比较
第八章 总结
8.1 内容总结
8.2 算法评价
8.3 算法改进
附录
参考文献
在读期间公开发表的论文和承担科研项目及取得成果
致谢
发布时间: 2009-06-02
参考文献
- [1].图的Steiner最小树问题的算法与应用研究[D]. 王小龙.南京邮电大学2015
- [2].Steiner树问题中正则点分布与Steiner点性质[D]. 梁兆健.国防科学技术大学2004
- [3].基于多目标遗传算法求解Steiner树问题[D]. 栾威.东北大学2008
- [4].遗传算法在最小steiner生成树问题中的研究和应用[D]. 陈智豪.安徽工业大学2012
- [5].含有导数的智能优化算法求解水文水质参数优化问题[D]. 张梦倩.长安大学2018
- [6].最大流问题及欧几里德Steiner树问题初探[D]. 刁强强.青海师范大学2016
- [7].群智能优化算法在路径规划中的应用研究[D]. 马千知.陕西师范大学2010
- [8].欧几里德2-连通Steiner网络问题研究[D]. 李美丽.西北工业大学2004
- [9].烟花爆炸算法改进及其性能测试研究[D]. 李婷婷.华中科技大学2010
- [10].基于智能优化算法的面向业务承接的运输优化问题研究[D]. 温莹莹.东华大学2005
相关论文
- [1].图的Steiner最小树构建及其布线应用[D]. 董君.复旦大学2014
- [2].图的Steiner最小树问题的算法与应用研究[D]. 王小龙.南京邮电大学2015
- [3].遗传算法在最小steiner生成树问题中的研究和应用[D]. 陈智豪.安徽工业大学2012
- [4].网络中Steiner树问题的量子与智能优化算法研究[D]. 孙晓.山东大学2012
- [5].基于可视化实验的Steiner树问题的全局优化算法研究[D]. 叶坤.河南科技大学2012
- [6].基于多目标遗传算法求解Steiner树问题[D]. 栾威.东北大学2008
- [7].度约束最小生成树算法[D]. 焦森林.西安电子科技大学2008
- [8].欧几里德距离下的最短2-连通Steiner网络[D]. 彭书英.西北工业大学2005
- [9].Steiner树问题中正则点分布与Steiner点性质[D]. 梁兆健.国防科学技术大学2004
- [10].欧几里德2-连通Steiner网络问题研究[D]. 李美丽.西北工业大学2004