在20世纪60年代计算机开始步入发展阶段时,研究者们就对在计算机中模拟生物演化过程产生了兴趣,并提出了多种模拟算法,现在这些算法以及之后的许多变种算法被统称为演化算法。演化算法通常被视为一种启发式随机优化算法,用于求解优化问题。由于演化算法的结构简单、在处理具体问题时易于加入启发式想法、并且在许多实际应用中显示出卓越的性能,使得演化算法在工程优化、工业设计、数据挖掘等领域有广泛的应用。然而由于演化算法源于启发式想法并且包含复杂的随机行为,使得很难对其进行理论分析,因而目前还缺乏严格的理论基础,尤其是当演化算法作为优化算法应用时的性能缺乏理论保障。理论基础的缺乏一方面阻碍了演化算法的进一步发展,另一方面也阻碍了演化算法在对计算性能有严格要求的问题上的应用。本文对演化算法的理论基础进行了研究,并在此基础上提出了一种基于演化算法的新型学习算法,主要工作包括：(1)提出一种基于收敛率的演化算法复杂度分析方法,并对多种演化算法在困难问题上的复杂度下界进行了分析。以往的理论研究往往只能对具体的简单演化算法在简单问题上进行分析,缺乏通用分析技术。针对这一问题,本文通过揭示出演化算法收敛率与时间复杂度之间的关系,建立了一种通用的复杂度分析方法。该方法不仅具有通用性,还可推出一些困难问题的复杂度下界。(2)提出一种基于马氏链交换的演化算法复杂度分析方法,并对交叉算子和种群对演化算法性能的影响进行了分析。以往的理论研究大多建立在简单演化算法的基础上,难以对复杂演化算法进行分析。针对这一问题,本文提出一种基于马氏链交换的分析方法,使得对复杂演化算法的分析可以被归约为对简单演化算法的分析和对复杂演化算法单步行为的分析。通过此方法,本文首次分析了在OneMax问题上交叉算子对演化算法性能的影响,并且获得了在该问题上种群演化算法的复杂度紧致下界。(3)提出一种基于隔离函数的演化算法优化性能分析方法,建立了取得优化近似解的一般条件。演化算法在实际应用中通常用于优化问题求解,所求取的解对目标的近似程度是一个关键问题,而以往的理论结果对优化性能难以进行分析。针对这一问题,本文提出一种基于隔离函数的优化性能分析方法。首先通过隔离函数建立一个抽象的演化算法框架,该框架在采用不同类型的隔离函数时可以实例化为多种具体的演化算法。然后以该框架为中介进行分析,可以导出演化算法取得优化近似解的一般条件。本文基于该方法对Set Cover这一NP难问题进行分析,证明了演化算法可以在该问题上达到目前已知最好的近似性能,并揭示出演化算法在该问题上相对于常见的贪婪算法的优势。(4)提出演化Boosting学习框架及多核算法,并用于求解单帧正类扩张学习问题。Boosting是一类著名的机器学习方法,其内嵌的迭代贪婪优化过程使其难以利用多核处理器加速计算。针对这一问题,结合本文理论分析显示出的演化算法相对于贪婪算法的优势,本文提出了演化Boosting学习框架并设计了多核算法,不仅保持了Boosting的优点,还由于采用了演化算法的松耦合结构从而可以有效地利用多核处理器加速学习。本文基于演化Boosting学习框架求解单帧正类扩张问题,获得了比常见机器学习方法更好的性能。