演化算法和蚁群算法的性能分析

发布时间：2018-10-26 20:19

【摘要】：仿生随机搜索启发式算法如演化算法和蚁群算法是一类通用的流行算法,它是通过模拟自然界现象、过程和一些生物特征提出来的。这些算法已被广泛地用于解决大量的各种实际问题并且获得了很好的效果。这些算法易于实施并且可以应用到结构不是很清楚的优化问题上。演化算法是受到物种的自然演变的启发而提出的,演化算法通过迭代应用变异、重组和选择算子对问题的解进行优化。蚁群算法来源于真正的蚂蚁具有通过交换信息素从它们的巢穴到食物源的众多路径中找到最短路径的能力。许多实证研究已经证明了这类算法在许多问题上是非常有效的,但是离彻底理解算法的运行机制还是很遥远的。本文从理论研究的角度对演化算法和蚁群算法进行了分析。本文分析了单目标演化算法和蚁群算法在组合优化问题上的近似性能,也分析了多目标演化算法在拟布尔函数上的时间复杂度。本文主要采用常用的随机分析方法和工具进行分析。本文的主要贡献如下:(1)最大独立集问题是图论中的一个经典组合优化问题,也是一类NP完全问题。基于目前的计算理论,除非P=NP,最大独立集问题将不存在多项式时间的确定性算法。许多学者设计出一些有效的近似算法来求解最大独立集问题。演化算法是一类公认的有效的随机算法,其近似性能的理论分析相对较少。本文从理论上分析了一个简单的爬山演化算法(1+1)EA求解最大独立集问题的近似性能。证明了(1+1)EA能够在多项式的期望时间内获得该问题的近似比。对于一类特殊的独立集问题——k-Set Packing问题,本文证明了(1+1)EA可以在多项式期望时间内获得该问题的近似比。最后,文中给出了一个最大独立集问题的实例,并说明在该实例上(1+1)EA能获得比3-flip局部搜索方法更优的解。在这个实例上3-flip局部搜索算法会陷入局部最优,而(1+1)EA能够在多项式期望运行时间找到该实例的全局最优解。(2)长时间以来,演化算法已经被成功的应用于解决多目标最优化问题。然而多目标演化算法(MOEAs)的理论研究主要限于简单的多目标演化算法(SEMO)。Pareto存档演化策略(PAES)是一种简单但重要的多目标演化算法,它是来源于对电信问题的研究。本文首次分析了PAES算法在拟布尔函数上的运行时间,证明了当SEMO算法采用一种简单的变异算子时,PAES算法在PATH函数的性能优于SEMO算法。然而,我们可以发现该算法在著名的LOTZ函数上却不能以压倒性的概率获得它的整个Pareto前沿。之后,本文提出一种改进的Pareto存档演化策略(IPAES)并且证明了IPAES算法可以在多项式运行时间内找到整个LOTZ函数的Pareto前沿。最后,本文分析了IPAES算法采用两种不同的局部变异算子在拟布尔函数上的性能。基于上述分析,我们可以发现对于不同的问题选择合适的局部搜索算子是非常重要的。(3)本文也研究了两种蚁群算法在一类特殊旅行商问题上的近似性能。这类旅行商问题的特点是任意的两个城市之间的距离是1或者2,我们称这种问题是TSP(1,2)问题,这是一个NP完全问题。本文证明了两种蚁群算法能在多项式的运行时间内获得TSP(1,2)问题的3/2的近似比,同时也研究了信息素和启发式信息对算法性能的影响。最后,文中构造了一个TSP(1,2)问题实例并且证明了蚁群算法在这个实例上的性能优于局部搜索算法。
[Abstract]:......
【学位授予单位】：华南理工大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP18

【相似文献】

相关期刊论文 前10条

1 龚文引;谢丹;;针对本科生的演化算法教学探讨[J];计算机时代;2012年07期

2 熊盛武,李元香,康立山,陈毓屏;用演化算法求解抛物型方程扩散系数的识别问题[J];计算机学报;2000年03期

3 曾三友,康立山,丁立新;基于偏序关系的演化算法[J];计算机工程;2001年08期

4 周永华,毛宗源;基于混合杂交与间歇变异的演化算法[J];计算机工程与应用;2003年06期

5 闫震宇,康立山,陈毓屏,付朋辉;一种新的多目标演化算法——稳态淘汰演化算法[J];武汉大学学报(理学版);2003年01期

6 王涛,李歧强;基于空间收缩的并行演化算法[J];中国工程科学;2003年03期

7 何国良,李元香;多个粒子参与交叉的一种动态演化算法[J];计算机工程与应用;2004年08期

8 刘敏忠,邹秀芬,康立山;一种基于偏序排名的高效的多目标演化算法[J];小型微型计算机系统;2004年12期

9 王龙奎,汪祖柱;关于多目标演化算法的策略分析[J];安徽大学学报(自然科学版);2005年03期

10 田丽,林锦国,刘建峰,张光云;基于演化算法的客户关系管理系统研究[J];微处理机;2005年03期

相关会议论文 前3条

1 冯珊;李锋;周凯波;;面向演化算法应用的智能体系统建模与仿真研究[A];西部开发与系统工程——中国系统工程学会第12届年会论文集[C];2002年

2 张文俊;谢晓锋;马君;;并行演化算法在半导体器件综合中的应用[A];2006年全国开放式分布与并行计算学术会议论文集（二）[C];2006年

3 谢柏桥;戴光明;郑蔚;王剑文;;有指导的多目标演化算法在区域星座设计中的应用[A];中国宇航学会深空探测技术专业委员会第四届学术年会论文集[C];2007年

相关博士学位论文 前10条

1 俞扬;演化计算理论分析与学习算法的研究[D];南京大学;2011年

2 库俊华;自适应差分演化算法及其应用研究[D];中国地质大学;2015年

3 彭雪;演化算法和蚁群算法的性能分析[D];华南理工大学;2016年

4 彭晟;演化算法的静电场论模型[D];武汉大学;2011年

5 陈明;演化算法渐近行为的若干问题研究[D];武汉大学;2012年

6 彭飞;实值演化算法投资组合研究[D];中国科学技术大学;2011年

7 万书振;动态环境下差分演化算法研究与应用[D];武汉理工大学;2012年

8 魏波;交互式与自适应演化算法研究[D];武汉大学;2013年

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

10 武志峰;差异演化算法及其应用研究[D];北京交通大学;2009年

相关硕士学位论文 前10条

1 杨颖;一种多差分向量的自适应差分演化算法[D];浙江大学;2015年

2 陈伟;队伍演化算法及其在微波电路设计中的应用[D];杭州电子科技大学;2015年

3 吴昊;多群体并行演化算法的研究[D];南京邮电大学;2015年

4 要婷婷;基于模因演化算法的有限容量弧路径问题研究[D];北京交通大学;2016年

5 邢雪;基于Pi演算的关系演化算法的研究与实现[D];吉林大学;2016年

6 黄星;遗传递增演化算法配筋优化设计[D];湖南大学;2016年

7 温志超;基于演化算法及改进词袋模型的病虫害分类识别技术研究[D];华南农业大学;2016年

8 左磊;改进的差分演化算法研究及其应用[D];华南农业大学;2016年

9 张盛鑫;基于新型变异与交叉算子的差分演化算法研究[D];暨南大学;2016年

10 戴志晃;一种基于熵量守恒的改进演化算法的研究[D];江西理工大学;2010年

，

本文编号：2296837