随机启发式搜索算法的性能分析

发布时间：2017-05-02 23:00

  本文关键词：随机启发式搜索算法的性能分析，由笔耕文化传播整理发布。

【摘要】：随机启发式搜索算法如演化算法、蚁群算法及人工免疫算法等是通过模拟大自然现象、过程及一些生物特性等提出的一类通用算法。实践证明,这类随机启发式搜索算法在科学研究及工程实际问题中获得了极大的成功,尤其是针对一些结构不清晰的复杂优化问题,以及在计算资源有限的情况下表现出了卓越的性能。为了更好的理解随机启发式搜索算法的工作机制,进一步指导算法设计及应用,研究人员迫切希望为这类算法建立严密的理论基础。然而,由于随机启发式搜索算法的随机性、群体性等特点,使得算法在运行过程中表现出非常复杂的动态随机行为,增加了理论研究的难度。当前,理论研究成果相对偏少。本文从随机启发式搜索算法的理论研究角度出发,关注随机启发式搜索算法求解优化问题的时间复杂性,以及在NP-完全(难)优化问题上的近似性能;研究问题类型与算法特征之间的关系;进一步探索随机启发式搜索算法求解典型优化问题的有效性,以期完善和增强随机启发式搜索算法的理论基础。本文的主要工作如下:(1)研究了演化算法求解最多叶子生成树问题(MLST)的性能。最多叶子生成树问题是NP完全理论中一个经典的组合优化问题,在网络设计及电路布局等实际问题上有较强的应用背景。该问题是在一个无向连通图中找出一棵生成树,使得生成树中所含叶子节点最多。许多启发式算法如演化算法用于求解该问题。然而,对于演化算法在NP难问题的求解性能方面我们仍知之甚少。本文从理论上研究了演化算法求解MLST问题的近似性能。指出对于MLST问题,算法(1+1)EA能够分别在期望多项式时间2O(nm)和4O(nm)内获得5近似比和3近似比,其中n为无向连通图中的节点数,m为边数。同时,我们研究了(1+1)EA算法在两个MLST问题实例上的性能,并且指出局部搜索算法在该实例上容易陷入局部最优,而(1+1)EA算法能够逃脱局部最优并最终获得最优解。(2)研究了蚁群算法在二次指派问题(QAP)上的性能。二次指派问题是最具挑战性的组合优化问题之一。该问题在物流运输和选址等许多实际问题中有着广泛的应用。理论上研究了ACO算法在极其难的QAP问题上的性能。给出了一个简单的(1+1)MMAA算法在QAP问题上的最坏情况界。并指出对于QAP问题,(1+1)MMAA算法能够获得一定的近似保证。最后,通过构建一个QAP实例,表明蚁群优化算法在该实例上要优于2-exchange局部搜索算法,进一步证实了蚁群算法的有效性。(3)分析比较了基于免疫的超变异算子与标准位变异算子在优化问题上的性能。人工免疫系统在许多复杂的真实优化问题中获得了广泛的应用并取得了极大成功。然而,人工免疫算法的理论研究远远滞后于其在许多领域的应用研究。对于人工免疫算法的运行机制以及其有效性研究还处于探索的初级阶段,当前也迫切需要为这类算法建立坚实的理论基础。本文从理论上分析了一种被用于免疫算法中的连续高频变异算子在优化问题上的性能,并在两个拟布尔函数及两个真实组合优化问题的实例上分析比较了连续高频变异算子与标准位变异算子、局部变异算子的性能,证明了连续高频变异算子在这些实例上要优于标准位变异算子及局部变异算子。也进一步揭示了问题类型与算法特征之间的关系,从理论上证实了连续高频变异算子的有效性。
【关键词】：随机启发式搜索 最优化问题 算法分析 时间复杂度分析 近似性能
【学位授予单位】：华南理工大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP18
【目录】：

• 摘要5-7
• ABSTRACT7-14
• 主要符号表14-15
• 第一章 绪论15-38
• 1.1 引言15-17
• 1.2 随机启发式搜索算法17-24
• 1.2.1 演化算法17-20
• 1.2.2 蚁群算法20-22
• 1.2.3 人工免疫系统22-23
• 1.2.4 其它随机搜索算法23-24
• 1.3 相关工作24-36
• 1.3.1 演化算法时间复杂度和近似性能研究相关工作24-30
• 1.3.2 蚁群优化算法性能研究相关工作30-33
• 1.3.3 基于免疫的B细胞算法性能研究相关工作33-35
• 1.3.4 其它研究成果35-36
• 1.4 本文概述和主要工作36-38
• 第二章 随机启发式搜索算法理论研究基础38-47
• 2.1 引言38
• 2.2 随机启发式搜索算法的计算复杂度38-40
• 2.3 随机启发式搜索算法理论研究方法40-46
• 2.3.1 偏差不等式40-42
• 2.3.2 标准变异42-43
• 2.3.3 适应值划分43-44
• 2.3.4 期望倍增距离减少44-46
• 2.4 小结46-47
• 第三章 演化算法求解最多叶子生成树问题的性能分析47-62
• 3.1 引言47-48
• 3.2 最多叶子生成树问题及(1+1) EA算法48-49
• 3.3 (1+1) EA算法求解MLST问题的近似保证49-51
• 3.4 (1+1) EA算法在两个MLST问题实例上的性能分析51-60
• 3.4.1 在一个MLST实例上(1+1) EA算法优于 1-change邻域局部搜索方法51-55
• 3.4.2 在一个MLST实例上(1+1) EA算法优于 2-change邻域局部搜索方法55-60
• 3.5 小结60-62
• 第四章 蚁群优化算法在二次指派问题上的性能分析62-79
• 4.1 引言62
• 4.2 问题和算法62-65
• 4.2.1 二次指派问题62-63
• 4.2.2 ACO算法63-65
• 4.3 (1+1) MMAA算法求解QAP问题的近似性能分析65-72
• 4.4 (1+1) MMAA算法求解QAP实例的分析72-78
• 4.5 小结78-79
• 第五章 基于免疫的超变异算子与标准位变异算子的性能比较79-99
• 5.1 引言79-80
• 5.2 基本定义及相关算法介绍80-82
• 5.2.1 基本定义80-81
• 5.2.2 算法81-82
• 5.3 基于免疫的超变异算子在一些人工函数上优于标准位变异算子82-87
• 5.3.1 TRAP函数82-84
• 5.3.2 H-IFF函数84-87
• 5.4 基于免疫的超变异、标准位变异及局部变异算子在最大割问题实例上的性能比较87-93
• 5.4.1 最大割问题87-89
• 5.4.2 不同变异算子在实例MC(s, p) 上的行为分析89-93
• 5.5 基于免疫的超变异算子在最小S-T割问题的一个实例上优于标准位变异算子93-97
• 5.5.1 最小s-t割问题93-96
• 5.5.2 变异算子CHM2在实例ST(k, l) 上的分析96-97
• 5.6 小结97-99
• 结论99-101
• 参考文献101-116
• 攻读博士学位期间取得的研究成果116-118
• 致谢118-119

【共引文献】

中国期刊全文数据库 前10条

1 孙慧;;Multiple People Picking Assignment and Routing Optimization Based on Genetic Algorithm[J];科技视界;2014年01期

2 吴果林;李学迁;;求解二次分配问题的预处理快速蚂蚁系统[J];上海理工大学学报;2014年02期

3 王涛;卿鹏;魏迪;漆锋滨;;基于聚类分析的进程拓扑映射优化[J];计算机学报;2015年05期

4 张睿;李树刚;;基于复杂网络的微吧话题流行度预测研究[J];科学技术与工程;2015年17期

5 王长军;徐琪;贾永基;;单机下异构任务调度的解性质研究[J];管理科学学报;2015年07期

6 张宇山;郝志峰;黄翰;林智勇;;进化算法首达时间分析的停时理论模型[J];计算机学报;2015年08期

7 QIAN Chao;YU Yang;ZHOU Zhi-Hua;;Variable solution structure can be helpful in evolutionary optimization[J];Science China(Information Sciences);2015年11期

8 孙慧;张柯;张富金;张纪会;;基于遗传算法的双区型仓库人工拣货路径优化[J];青岛大学学报(工程技术版);2014年01期

9 黄翰;徐威迪;张宇山;林智勇;郝志峰;;基于平均增益模型的连续型(1+1)进化算法计算时间复杂性分析[J];中国科学:信息科学;2014年06期

10 林浩;林澜;;图的最小控制树问题（英文）[J];数学季刊(英文版);2014年01期

中国博士学位论文全文数据库 前4条

1 张宇山;进化算法的收敛性与时间复杂度分析的若干研究[D];华南理工大学;2013年

2 任海豹;QoS保障的基站节能机制研究[D];中国科学技术大学;2014年

3 赖鑫生;演化算法与混合算法的性能研究[D];华南理工大学;2014年

4 张鹤立;分层异构网络中干扰管理、用户连接及自组织技术研究[D];北京邮电大学;2014年

中国硕士学位论文全文数据库 前10条

1 赵婷;三类平行机博弈排序问题的协调机制研究[D];中国海洋大学;2013年

2 陈戈;纯电驱动轿车动力传动系统耦合分析与多目标优化设计[D];合肥工业大学;2013年

3 景莉;现代铁路物流中心功能设计与基于改进SLP方法的功能区布局[D];中南大学;2013年

4 许金辉;面向动态需求的鲁棒性车间布局研究[D];华中科技大学;2013年

5 陈朝霞;NSGA-Ⅱ在多品种变批量军工制造企业数字化车间设备布局的算法研究[D];杭州电子科技大学;2014年

6 范国强;若干排序博弈问题的协调机制研究[D];中国海洋大学;2014年

7 胡丹;两类平行机并行分批排序问题的协调机制和算法研究[D];中国海洋大学;2014年

8 杨艺;求解二次分配问题的鱼群算法研究[D];湘潭大学;2014年

9 康春建;降低数据中心能耗提高网络服务质量优化算法研究[D];天津大学;2014年

10 杨力;众核处理器核级冗余拓扑重构算法研究[D];东华大学;2015年

  本文关键词：随机启发式搜索算法的性能分析，由笔耕文化传播整理发布。

，

本文编号：341822