进化算法（EvolutionaryAlgorithms，简称EAs）是受进化论中“物竞天择，适者生存”的思想启发而产生的一大类随机启发式搜索算法。这类算法主要用于求解传统计算方法难以处理的复杂优化问题，在工程优化中得到了广泛的应用，并取得了巨大的成功。当前，有关进化算法的研究大都集中于仿真实验和实际应用，相对而言，其理论基础研究的成果还不多。造成这一局面的主要原因在于进化算法运行的随机性本质，此类算法复杂的随机行为导致对其严格的理论分析很困难。收敛性与时间复杂度分析是进化算法理论基础研究的热点和难点，通过研究进化算法的收敛性与时间复杂性，可以深入了解这类算法的运行机理，从而设计出更高效的进化算法。针对进化算法复杂的随机行为，本文以随机过程理论为基础，对进化算法的收敛性与时间复杂度分析展开了研究。主要研究内容如下：（1）采用新的理论工具分析了二元进化策略的全局收敛和早熟收敛性。离散状态马尔科夫链理论已经广泛应用于进化算法的收敛性和时间复杂度分析中，而连续状态马尔科夫过程理论目前应用还不多。本文引入连续状态马尔科夫过程理论，以测度论为工具，借助公理化的条件数学期望理论推导出关键的转移概率的计算公式，分析了以(1+1)ES为代表的连续型进化算法的收敛性，从理论上证明若采用常变异算子，包括正态分布、柯西分布在内的一大类常用变异分布可使(1+1)ES依概率收敛到全局最优解的ε-邻域；而某些自适应变异算子即使以正态分布、柯西分布为变异分布也会导致(1+1)ES在某些问题求解上陷入早熟收敛，这说明自适应调整机制并非总是有效的。通过数值试验验证了理论分析。（2）对漂移分析进行了严格化。漂移分析（Drift analysis）是分析进化算法时间复杂性的一个强有力工具，由Jun He和Xin Yao于2001年首先引入（见ArtificialIntelligence127(1)(2001)57-85），其后得到了广泛的应用。但是原始文献的核心定理仍存在缺陷：条件过严、证明有误且不够严格等，而这些缺陷一直未见指出。鉴于该定理是漂移分析的理论基础，很有必要加以严格化。本文指出了该定理的不足之处，以测度论为工具，对该定理做了适当的修正与改进，并且给出了一个新的严格的证明。（3）提出了基于停时理论的进化算法首达时间分析模型。漂移分析虽然理论上适用于离散型和连续型进化算法的时间复杂度分析，但是实际上到目前为止，几乎所有应用漂移分析的研究都是针对离散的组合优化问题实例进行的且其理论基础仍有待进一步严格化。本文引入停时理论作为数学工具，将进化算法的首达时间视为停时，借助时齐马氏过程的性质，提出了分析进化算法首达时间的一个新方法，在此框架下，Level-reaching Estimation Technique作为特例得到了严格的证明。为展示如何用该理论方法分析具体问题，以(1+λ)EA求解LeadingOnes函数、PEAK函数和(1+λ)ES求解倾斜平面问题为实例，分析了平均首达时间。结果表明，本文所提出的方法不但适用于离散优化问题也适用于连续优化问题，具有通用性。（4）对若干具有现实背景的组合优化问题分析了进化算法求解的时间复杂性。分析进化算法在具有实际背景的组合优化问题上的时间复杂度是当前的一个研究难点。本文通过设计新的变异算子，用(1+1)EA求解了两个组合优化问题实例——TSP和指派问题，并分析了时间复杂度；针对带约束的组合优化问题，分析了(1+λ)EA在一个0-1背包问题实例上的时间复杂度。这些工作拓展了进化算法计算时间分析的范围，充实了进化算法在具有现实背景的组合优化问题上的时间复杂度研究。