【作者】 陈天石；

【导师】 陈国良； 姚新；

【作者基本信息】 中国科学技术大学 ， 计算机软件与理论， 2010， 博士

【摘要】 演化算法是受进化论启发而提出的一大类随机优化算法。该类算法将进化论“物竞天择,适者生存”的思想用于求解优化问题,在计算机科学界得到了广泛而持久的关注。它兴起于上世纪六十年代,蓬勃发展于八十年代和九十年代,最终形成人工智能领域的一个分支—演化计算。总体来说,演化计算是一门实验科学,它的绝大部分工作都立足于模拟实验和实际应用。究其原因,这类算法复杂的随机行为使得严密的理论研究(尤其是计算复杂性研究)难以开展。为了更好地理解演化算法复杂的随机行为从而设计出更高效的演化算法,本文从多个方面开展演化算法的计算复杂性研究,以期增强演化计算领域的理论基础：我们不仅关注更贴近实际的经典演化算法(遗传算法),也关注学术界流行的新型演化算法；我们不仅关注求解传统静态优化问题的演化算法,也关注求解动态优化问题的演化算法；我们不仅关注算法的理论研究,也关注理论结果的实际意义。本文的主要贡献包括：(1)研究了种群经典演化算法的计算复杂性。早期的理论研究常常关注简单但脱离实际的算法模型,这些简化的算法模型距离实际应用中的经典演化算法还有相当大的差距。而本文考虑在算法形式以及运行机制上更贴近实际的种群经典演化算法,为该类算法的时间复杂度分析提出了一种新颖的、系统的方法,并将此方法应用于分析种群规模不同的经典演化算法在若干单峰和多峰优化问题上的时间复杂度。在演化计算领域,上述工作第一次给出了(N+N)经典演化算法(算法的父代种群和子代种群规模相等)时间复杂度的专用分析方法,从而从理论上分析了不同的种群规模对种群演化算法性能的影响。(2)研究了一类新型演化算法(分布评估算法)的计算复杂性。与直接进化种群的经典演化算法不同,这类算法通过在线调整概率模型来间接地进化种群。在分布评估算法兴起和发展的近二十年来,绝大部分研究都局限于实验观察。虽然有少量研究者关注种群分布评估算法的收敛性,但还没有研究者成功地对这类算法的时间复杂度进行过严密的理论研究。本文为分布评估算法的时间复杂度分析提出一种一般性的研究思路。基于该思路,本文分析了独立边缘分布算法(分布评估算法的一种实例)的时间复杂度,并从理论上验证了对算法的概率模型进行“松弛”的必要性和有效性。在演化计算领域,这项工作第一次为分布评估算法的计算复杂性分析提出了一般性的研究思路,并从理论上严密地分析了种群分布评估算法的时间复杂度,为分布评估算法的计算复杂性研究作出了突破性的贡献。(3)研究了在动态优化问题背景下随时间可变的变异率策略(随着算法的运行,变异率参数可发生变化)对经典演化算法性能的影响。在演化计算领域,许多研究者对引入适应性变异率策略、自适应变异率策略来提升算法性能抱有较大期望。而本文通过计算复杂性研究发现,在某些动态优化问题上,任意随时间可变的变异率策略都不比固定变异率策略具本质上的优势。基于这个结果,本文建议在求解动态优化问题时,如果缺乏先验知识,演化算法最好不要使用自适应变异率等可变变异率策略,而是按照奥坎姆剃刀原则使用简单的固定变异率策略。在演化计算领域,这项工作第一次系统地分析了任意随时间可变的(如自适应)变异率对算法计算复杂性的影响,显著加强了演化动态优化方向的理论基础,并有助于深入理解演化算法的性能和变异率间的关系。更多还原

【Abstract】 Evolutionary Algorithms (EAs) are a kind of stochastic optimization algorithms following Darwin’s principle of "Survival of the fittest". EAs have received extensive investigations since 1960s, especially in 1980s and 1990s. Years of efforts spent on designing and studying various EAs have established a branch of artificial intelligence, Evolutionary Computation (EC). Generally speaking, EC is usually considered as a branch of computer science which mainly relies on empirical investigations. That is because carrying out rigorous theoretical analysis on the complex stochastic behaviors of EAs is very difficult. To gain more insight into the stochastic behaviors of EAs so as to design efficient algorithms, this thesis focuses on the computational complexity analysis of EAs. Concretely, we study the computational complexity of EAs from broad perspectives:we not only concern the classic EAs (Genetic Algorithms) that are close enough to practical algorithms, but also concern a novel type of EAs that are popular in academia; we not only study EAs on traditional static optimization problems, but also investigate EAs on dynamic optimization problems; we not only concern the theoretical investigation of the algorithms, but also care about the practical implications of theoretical results. The main contributions of this thesis are summarized as follows:(1) We study the computational complexity of population-based classic EAs. As shown in the first chapter, early theoretical time complexity investigations often focused on simplified but impractical EAs. Unlike these studies, we concentrate on population-based EAs that are closer to practical algorithms utilized in real-world applications. To be specific, we propose a novel approach for analyzing the time complexities of population-based EAs, which will be utilized to analyze classic EAs with different population sizes on both unimodal and multimodal optimization problems. In EC field, this is the first time that a approach dedicated to the time complexity analysis of (N+N) classic EAs (where the parent size equals the offspring size) is proposed. It is also the first time that the impact of different population sizes on the performances of EAs is investigated theoretically.(2) We study the computational complexity of a novel type of EAs named Es-timation of Distribution Algorithms (EDAs). Unlike EAs that evolve populations di-rectly, EDAs indirectly evolves populations by employing online-adjustable probabilis-tic models. Over the past two decades, various EDAs have been proposed and studied. However, most investigations were carried out on the basis of empirical observations. Although some scholars have concerned the convergence properties of EDAs, there is no investigation that analyzes successfully the time complexity of population-based EDAs by rigorous mathematical discussions. In this thesis, we propose a general ap-proach to analyzing the time complexity of EDAs. Following this approach, we an-alyze the time complexity of an instance of EDAs, Univariate Marginal Distribution Algorithm (UMDA). In addition to several time complexity results, it is discovered that the relaxation on the probabilistic model of UMDA is effective for promoting the performance of UMDA, and is necessary for avoiding premature convergence of the probabilistic model. Our investigation has made exceptional contributions to the com-putational complexity of EDAs:this is the first time that a general approach is proposed for analyzing the computational complexities of population-based EDAs; this is also the first time that the time complexity of a population-based EDA is analyzed rigorously.(3) We study the impact of time-variable mutation rate schemes on the perfor-mance of a classic EA in the context of dynamic optimization problems. In EC field, many researchers expect that time-variable mutation rate schemes can potentially pro-mote the performance of classic EAs. However, according to our computational com-plexity analysis, on certain dynamic optimization problems, any time-variable mutation rate scheme is not significantly better than fixed mutation rates. According to this result, this thesis suggests that when solving dynamic optimization problems in the absence of prior knowledge, it would be better to give up self-adaptive mutation rate schemes, and follow the well-known Occam’s razor by utilizing a fixed mutation rate. In EC field, it is the first time that some general results for any time-variable (e.g., self-adaptive) mutation rate scheme are given and proven rigorously, which substantially increases the understanding of the relationship between time-variable mutation rate scheme and the performance of EA, and the role of mutation in the context of dynamic optimization problems.更多还原