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