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

《演化算法和蚁群算法的性能分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、寺為；ｆ＾乂葦Ｓｏｕ化ＣｈｉｎａＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ博±学位论文演化算法和蚁群算法的性能分析羅’．．，＇：ｖ．．．’＾ＶＶ山却与．巧苗靖扣式靖请苗擊靖苟装＇诚．．；巧其ｒ＇＂．７．作者姓名＾学科专业计算机软件与理论指导教师周育人教授所在学院计算机科学与工程学院论文提交日期２０１６年４月１２日OnthePerformanceAnalysisofEvolutionaryAlgorithmandAntColonyAlgorit

2、hmADissertationSubmittedfortheDegreeofDoctorofPhilosophyCandidate：PengXueSupervisor：Prof.ZhouYurenSouthChinaUniversityofTechnologyGuangzhou,China分类号：TP301学校代号：10561学号：201210102090华南理工大学博士学位论文演化算法和蚁群算法的性能分析作者姓名：彭雪指导教师姓名、职称：周育人、教授申请学位级别：工学博士学科专业名称：计算机软件与理论研究方向：计算智能论文提交日

3、期：2016年4月12日论文答辩日期：2016年6月7日学位授予单位：华南理工大学学位授予日期：年月日答辩委员会成员：主席：汤庸委员：张平邓辉舫张星明周育人华南理工大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研巧所。，取得的研究成果除了文中特别加＾＾标注引用的内容外本论文不包含任何其他个人或集体己经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名；：日期妒《年月７日学位论文版权使

4、用授权书本学位论文作者完全了解学校有关保留，目Ｐ：研究生在校攻读学、使用学位论文的规定位期间论文王作的知识产权单位属华南理工大学。学校有权保存并向国家有关部口或机构送交论文的复印件和电子版，允许学位论文被查阅（除在保密期内的保密论文外）；学校可Ｗ公布学位论文的全部或部分内容，可Ｗ允许采用影印、缩印或其它复制手段保存、汇编学位论文。本人电子文档的内容和纸质论文的内容相一致。本学位论文属于：□保密（校保密委员会审定为涉密学位论文时间：月日），年＿＿于＾月日解密后适用本授权书。．＿＿＿＿＿＾不保密同

5、意在校园网上发布，，供校内师生和与学校有共享协议的单位浏览；同意将本人学位论文提交中国学术期刊（光盘版）电子杂志社全文出版和编入ＣＮＫＩ《中国知识资源总库》，传播学位论文的全部或部分内容。＂Ｖ＂（请在上相应方框内打）作者签名：日期：指导教师签名：巧日期：摘要仿生随机搜索启发式算法如演化算法和蚁群算法是一类通用的流行算法,它是通过模拟自然界现象、过程和一些生物特征提出来的。这些算法已被广泛地用于解决大量的各种实际问题并且获得了很好的效果。这些算法易于实施并且可以应用到结构不是很清楚的优化问题上。演化算法

6、是受到物种的自然演变的启发而提出的，演化算法通过迭代应用变异、重组和选择算子对问题的解进行优化。蚁群算法来源于真正的蚂蚁具有通过交换信息素从它们的巢穴到食物源的众多路径中找到最短路径的能力。许多实证研究已经证明了这类算法在许多问题上是非常有效的，但是离彻底理解算法的运行机制还是很遥远的。本文从理论研究的角度对演化算法和蚁群算法进行了分析。本文分析了单目标演化算法和蚁群算法在组合优化问题上的近似性能，也分析了多目标演化算法在拟布尔函数上的时间复杂度。本文主要采用常用的随机分析方法和工具进行分析。本文的主要贡献如下：(1)最大独立集问

7、题是图论中的一个经典组合优化问题,也是一类NP完全问题。基于目前的计算理论，除非P=NP，最大独立集问题将不存在多项式时间的确定性算法。许多学者设计出一些有效的近似算法来求解最大独立集问题。演化算法是一类公认的有效的随机算法,其近似性能的理论分析相对较少。本文从理论上分析了一个简单的爬山演化算法(1+1)EA求解最大独立集问题的近似性能。证明了(1+1)EA能够在多项式的期望时间内获得该问题的近似比。对于一类特殊的独立集问题——k-SetPacking问题,本文证明了(1+1)EA可以在多项式期望时间内获得该问题的近似比。最后，文

8、中给出了一个最大独立集问题的实例，并说明在该实例上(1+1)EA能获得比3-flip局部搜索方法更优的解。在这个实例上3-flip局部搜索算法会陷入局部最优，而(1+1)EA能够在多项式期望运行时间找到该实例的全局最优解。(2)长时间以来，演化算法