EVOLUTIONARY LEARNING
ADVANCES IN THEORIES AND ALGORITHMS
演化学习 理论与算法进展
人民邮电出版社
北京
图书在版编目（CIP）数据
演化学习：理论与算法进展/周志华，俞扬，钱超著.--北京：人民邮电出版社，2021.7
ISBN 978-7-115-55803-9
Ⅰ.①演… Ⅱ.①周…②俞…③钱… Ⅲ.①机器学习—算法 Ⅳ.①TP181
中国版本图书馆CIP数据核字（2021）第017866号
◆著 周志华 俞扬 钱超
责任编辑 贺瑞君
责任印制 周昇亮
◆人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 https://www.ptpress.com.cn
北京市艺辉印刷有限公司印刷
◆开本：787×1092 1/16
印张：20.25 2021年7月第1版
字数：445千字 2021年7月北京第1次印刷
定价：99.80元
读者服务热线：(010)81055552 印装质量热线：(010)81055316
反盗版热线：(010)81055315
广告经营许可证：京东市监广登字20170147号
演化学习利用演化算法求解机器学习中的复杂优化问题，在实践中取得了许多成功，但因其缺少坚实的理论基础，在很长时期内未获得机器学习社区的广泛接受.本书主要内容为三位作者在这个方向上过去二十年中主要工作的总结.
全书共18 章，分为四个部分：第一部分（第1～2 章）简要介绍演化学习和一些关于理论研究的预备知识； 第二部分（第3～6章）介绍用于分析运行时间复杂度和逼近能力这两个演化学习的基本理论性质的通用工具； 第三部分（第 7～12 章）介绍演化学习关键因素对算法性能影响的一系列理论结果，包括交叉算子、解的表示、非精确适应度评估、种群的影响等； 第四部分（13～18 章）介绍一系列基于理论结果启发的具有一定理论保障的演化学习算法.
本书适合对演化学习感兴趣的研究人员、学生和实践者阅读.书中第二部分内容或可为有兴趣进一步探索演化学习理论基础的读者提供分析工具，第三部分内容或有助于读者进一步理解演化学习过程并为新算法设计提供启发，第四部分内容或可为读者解决一些现实机器学习问题提供新的算法方案.
二十年前，本书第一作者与合作者提出了一种“选择性集成”学习方法，对于一组学习器，该方法能产生出仅包含少量个体、泛化性能却超越全体学习器集成的模型.该工作使用了一种常见演化算法——遗传算法.本书一作以为，演化算法这种强大的优化工具应能在许多机器学习任务中发挥作用.但机器学习领域有强烈的理论偏好，而当时演化算法几乎纯粹是“启发式”的：在不少情况下有效，但为何奏效、在何种条件下奏效却并不清楚，因此演化算法难以被主流机器学习界认可，相关论文甚至难以在机器学习主流渠道发表.
本书一作被演化算法的应用成效鼓舞，相信其并非“魔法”，必能建立起相应理论基础，于是决心开展这个方向的研究.2004年，本书二作在一作指导下完成了关于选择性集成学习算法的本科毕业论文，到宁夏贫困地区支教一年后，成为一作的研究生加入该方向研究.他于2011年获博士学位，毕业论文有幸入选了全国百篇优秀博士学位论文和江苏省优秀博士学位论文.本书三作在2009年成为一作的研究生加入该方向研究，并于2015年获博士学位，毕业论文入选了中国人工智能学会优秀博士学位论文和江苏省优秀博士学位论文.本书主要内容就是三位作者在这个方向上过去二十年中主要工作的总结.
全书由四部分组成.第一部分简要介绍演化学习，为分析“运行时间复杂度”和“逼近能力”这两个核心理论问题作准备.第二部分给出用于推导运行时间界的两种通用方法，以及用于刻画逼近性能的一个通用框架，它们是获得后续章节中许多理论结果的工具.第三部分是关于演化过程关键因素对算法性能影响的一系列理论结果，包括交叉算子、解的表示、非精确适应度评估、种群的影响等.第四部分回到选择性集成这个促使作者关心演化算法的起点，给出了性能优越且有理论支撑的算法，并对机器学习中广泛存在的“子集选择”问题给出了一系列有逼近性能保障的演化学习算法.书中第二部分内容或可为有兴趣进一步探索演化学习理论基础的读者提供分析工具，第三部分内容或有助于读者进一步理解演化学习过程并为新算法设计提供启发，第四部分内容或可为一些现实机器学习任务提供新的算法方案.
本书英文版在斯普林格出版社问世后，国内许多同行兴趣甚浓，强烈建议出中文版，人民邮电出版社贺瑞君编辑亦盛情邀请，于是作者在年初抗疫“禁足”期间勉力转著以飨读者.本书的出版要感谢作者的家人、朋友、合作者，以及斯普林格出版社常兰兰女士和阿尔弗雷德·霍夫曼先生的支持.因作者学识浅陋、时间仓促，本书内容错谬之处在所难免，且先著英文后转中文，难免因“先入为主”而致表达僵滞，敬请读者诸君见谅、赐正.
作者
2020年6月于南京
机器学习[周志华，2016]是人工智能的核心领域之一，旨在从数据中学得具有泛化（generalization）能力的模型，以改善系统自身的性能.机器学习正在许多应用中发挥着越来越重要的作用.
为学得一个模型，我们需要一个训练集（training set），其中包含若干个示例（instance）.若每个训练示例均伴随一个输出标记（label），则学习任务属于监督学习（supervised learning），旨在学得一个从示例空间映射到标记空间的模型.根据输出标记的类型，监督学习任务可大致划分为两大类：分类和回归，前者的标记是离散的，取值范围为有限个类别，而后者的标记是连续的.典型的监督学习算法包括决策树（decision tree）、人工神经网络（artificial neural network）、支持向量机（support vector machine）等[周志华，2016].若每个训练示例均未伴随输出标记，则学习任务属于无监督学习（unsupervised learning）.一个典型任务是聚类（clustering），试图将所有示例划分为若干个簇（cluster），使得簇内示例相似度高而簇间示例相似度低.弱监督学习（weakly supervised learning）[Zhou，2017]介于监督学习和无监督学习之间，包括监督信息不完整的半监督学习（semi-supervised learning）和主动学习（active learning）、监督信息不精确的多示例学习（multi-instance learning）、监督信息有时延的强化学习（reinforcement learning）等.
机器学习过程一般由三个部分组成[Domingos，2012]：模型表示（model representation）、模型评估（model evaluation）、模型优化（model optimization），如图 1.1所示.待学习的模型可以有不同的形式，如决策树、人工神经网络、支持向量机等；不同的模型形式拥有不同的特点，对模型的泛化性能会产生很大影响.模型评估关乎如何评价一个模型的“好坏”，这非常重要：一方面，同一模型使用不同的评估标准会导致不同的评判结果；另一方面，机器学习模型往往有很多变化（例如通过设置不同的超参数值），选择一个合适的模型依赖于有效的模型评估.模型优化关乎如何确定参数值，使模型具有良好的泛化性能.
为了解决复杂学习问题，我们往往需要使用非线性模型形式和/或非凸模型评估函数，这导致学习问题常归结为复杂优化问题，其优化目标函数往往具有不可导、不连续、存在多个局部最优解等性质.这些性质可能使得传统优化算法（例如梯度下降法）失效，而其他一些强大的优化算法（例如本书后续讨论的算法）可能会大有用武之地.
演化学习（evolutionary learning）是指利用演化算法（evolutionary algorithm，EA）[Bäck，1996]求解机器学习中的复杂优化问题.
演化算法是指一大类受自然演化启发的启发式随机优化算法，通过考虑“突变重组”和“自然选择”这两个关键因素来模拟自然演化过程.尽管演化算法有很多种实现方法，如遗传算法（genetic algorithm）、遗传编程（genetic programming，GP）、演化策略（evolutionary strategy）等，但一般都能抽象为以下四步：
1.生成一个包含若干初始解（solution）的集合，称为种群（population）；
2.基于当前种群通过变异和交叉产生一些新解；
3.从当前种群和产生的新解中去除一些相对差的解形成新的种群；
4.返回第二步并重复运行，直至满足某个停止条件.
这些步骤体现在演化算法的一般结构中，如图1.2所示.
在使用演化算法求解优化问题之前，我们需要确定如何表示解.例如，若问题是从全集中选择一个子集，则一个解（即一个子集）可以自然地表示为一个布尔向量.如图1.3所示，{v1,v2,...,v8}的一个子集可以用长度为8的一个布尔向量来表示，其中第i位取值为1意味着vi被选择，否则vi未被选择.因此，{v1,v3,v4,v5}可表示为（1,0,1,1,1,0,0,0）.
在确定解的表示（solution representation）方法后，演化算法开始按图 1.2 中的循环结构进行演化.在演化过程中，算法会维持一个种群，并通过迭代地产生新的子代解（offspring solution）、评估这些解、选择更好的解来改善种群中解的质量.变异（mutation）与交叉（crossover/recombination）是两种常用的产生新解的算子.前者通过随机修改一个解产生一个新解，如图1.4所示：在用布尔向量表示的解上执行一位变异（one-bit mutation）算子，即随机选择一位进行翻转.后者通过混合两个或多个解产生新解，如图1.5所示：在两个用布尔向量表示的解上执行单点交叉（one-point crossover）算子，即基于某个随机选择点将两个解的对应部分进行交换.
在子代解生成之后，用适应度（fitness）函数来度量它们的优劣；然后根据某种选择机制，从旧种群包含的父代解（parent solution）和新产生的子代解中选择较优解以构建新的种群.演化将持续，直至满足停止条件.常用的停止条件包括解的质量达到预设值、计算资源（例如运行时间）达到预算上限、解的质量在预设的轮数内不再改进等.
从整个迭代过程可以看出，演化算法在求解优化问题时，仅需以某种方法表示解并能够对解的优劣进行评估以便执行搜索，而无须关注问题的结构信息.尤其在缺乏目标函数的梯度信息、甚至缺乏目标函数的显式表达式时都能使用，仅需能够通过实验或模拟评估解的相对优劣即可.因此，演化算法被视为一种通用优化算法，甚至能以黑箱（black-box）的方式求解优化问题.
由于其通用性，演化算法已经被用于求解机器学习中的复杂优化问题.例如，其已被用于优化神经网络[Yao，1999]，包括优化连接权重、网络结构和学习规则；通过演化得到的人工神经网络模型能获得与手工设计的模型相媲美的性能[Real et al.，2017].然而，尽管演化学习已取得了诸如此类的许多成功，但因其缺少坚实的理论基础，在很长时期内未获得机器学习社区的广泛接受.
在许多机器学习任务中，预期结果通常需同时达到多个要求.例如，特征选择（feature selection）[周志华，2016]试图使用尽可能少的特征去优化某个性能指标；集成学习（ensemble learning）[Zhou，2012]希望个体学习器（individual learner）“好而不同”，即个体学习器要有一定的准确性，同时要有多样性；聚类[周志华，2016]要求同一簇的示例间的距离尽可能小而不同簇的示例间的距离尽可能大；主动学习[周志华，2016]希望选择的未标记示例同时具有不确定性、代表性、多样性.试图同时满足多个要求的一种简单方式是将它们加权形成一个单目标函数，然而合适的权重往往难以事先确定.当我们不知道这些要求的相对重要程度而只能将它们分别作为独立的目标函数时，就面临多目标优化（multi-objective optimization）.多目标优化与单目标优化（single-objective optimization）有很大不同，下面介绍一些基本概念.
多目标优化要求同时优化两个甚至多个目标函数，见定义 1.1.其中，由所有可行解（feasible solution）构成的空间被称为可行域.仅有两个目标函数时，多目标优化亦称二目标优化（bi-objective optimization）.本书将考虑最大化问题（最小化问题可类似地定义）.
定义1.1.多目标优化
给定可行域
以及m个目标函数 f1,f2,...,fm，找到解s∗满足
其中 f（s）=( f1（s），f2（s），...，fm（s）)表示解s的目标向量.
由于目标之间往往存在冲突，即单独优化某个目标可能使其他目标变差，这导致没有一个解能在所有目标上最优.因此，多目标优化的输出是一个解集而非单个解，该解集中的每个解相较其他解都有某方面特定的优势.由于不存在单一的衡量标准，常用帕累托最优（Pareto optimality），见定义1.2，其利用了定义1.3中解之间的占优（domination）关系.
定义1.2.帕累托最优
给定可行域
以及目标空间
，令 f=（f1,f2,...,fm）:
表示目标向量.若某个解不被任意其他解占优，则它是帕累托最优的.所有帕累托最优解的目标向量构成的集合称为帕累托前沿（Pareto front）.
定义1.3.占优
给定可行域
以及目标空间
，令 f=（f1,f2,...,fm）:
表示目标向量.对于两个解s和
，
（1）若
，则s弱占优s′，记为
；
（2）若
且
，则s占优s′，记为
.
若 
和
均不成立，则这两个解不可比.上述定义针对的是多目标最大化，对多目标最小化，可以通过使用符号
和
类似地定义占优关系.
图1.6给出了二目标最大化的一个例子，其中 f1和f2是待最大化的两个目标.图中黑方块和黑点分别表示解和相应的目标向量；可见，可行域共包含8个解.对于解 s2和s5，因为 f1（s2）≥ f1（s5）且 f2（s2）≥ f2（s5），有 
；更严格地说，
，这是因为f1（s2）＞ f1（s5）且 f2（s2）＞ f2（s5）.对于解s2和s3,f1（s2）＜ f1（s3）而 f2（s2）＞ f2（s3），因此它们不可比.在这8个解中，s1、s2、s3和s4是帕累托最优的，它们相应的目标向量 f（s1）、f（s2）、f（s3）和f（s4）构成了帕累托前沿.带有不同目标向量的帕累托最优解以不同的方式达成了多个目标之间的最优权衡.
显然，多目标优化旨在找到一个解集，使其相应目标向量构成的集合能够包含帕累托前沿.为了解决多目标优化问题，一种经典方法是通过给每个目标赋予权重并将它们线性加权求和，从而将多目标优化问题转化为单目标优化问题求解.然而，该方法每次仅能找到一个解，为了找到不同的帕累托最优解需精心调整权重，这是一件相当棘手的事情.
如1.2节所述，演化算法是一类基于种群的优化算法，即在优化过程中维持一个解集，而这个特质恰和多目标优化寻找一个最优解集的要求相配，即演化算法运行一次就可找到多个帕累托最优解，因此演化算法成为目前求解多目标优化问题的一种流行工具[Deb，2001].用于求解多目标优化问题的演化算法被称为多目标演化算法（multi-objective EA），已被用于解决多种机器学习任务中的多目标优化问题，如特征选择[Mukhopadhyay et al.，2014a]、集成学习[Chen and Yao，2010]、聚类[Mukhopadhyay et al.，2014b]、主动学习[Reyes and Ventura，2018]和多标记学习（multi-label learning）[Shi et al.，2014].然而，演化算法的广泛适用性并不能直接提供性能保障，实践中观察到的一些有趣现象与由此而来的对算法本身的疑问亟待从理论上找到答案；这激发了本书将要介绍的一系列研究工作.
本书由四部分组成：预备知识、分析方法、理论透视、学习算法.
第一部分简要介绍了演化学习和一些关于理论研究的预备知识.
为了分析运行时间复杂度（running time complexity）和近似能力（approximation ability）这两个关于随机搜索启发式（randomized search heuristics）的最重要的理论性质[Neumann and Witt，2010；Auger and Doerr，2011]，本书第二部分给出了分析演化算法运行时间界（bound）的两种通用方法，即收敛分析法（convergence-based analysis）和调换分析法（switch analysis），以及刻画演化算法近似性能的一般框架SEIP.这些为获得本书后续介绍的一些理论结果提供了通用工具.
第三部分给出了关于演化算法的一系列理论结果.本书先探讨了如何辨识一个问题类（problem class）中关于某个给定演化算法的边界问题（boundary problem），即找到对于这个算法最简单和最困难的问题.然后，本书探讨了演化算法关键技术要素对其性能的影响，包括交叉算子、解的表示、非精确适应度评估（fitness evaluation）和种群的影响等.最后，本书考察了演化算法在求解机器学习任务中常见的约束优化（constrained optimization）问题时的性能.
第四部分给出了一系列基于理论结果启发的具有一定理论保障的演化学习算法.本书先考虑选择性集成（selective ensemble）任务，即尝试选择出个体学习器子集以获得更好的泛化性能，给出的帕累托优化（Pareto optimization）算法在优化泛化性能的同时最小化学习器数目，其性能显著优于其他著名的选择性集成算法.然后，本书研究了更具一般性的子集选择（subset selection）问题，即选择有限项来优化一个给定的目标函数.本书给出的帕累托优化算法可获得目前已知的最佳多项式时间近似保证（polynomial-time approximation guarantee）.本书进一步为两个扩展子集选择问题给出了帕累托优化算法的变种，均可获得目前已知的最佳多项式时间近似保证.最后，考虑到实际学习任务通常是带噪的且规模很大，本书还为子集选择问题给出了相应的容噪和并行算法.
作者希望第二部分的通用理论工具能为有兴趣探索演化学习理论基础的读者提供帮助，第三部分的理论结果能加深读者对演化学习过程行为的理解且提供一些关于算法设计的洞察，第四部分的算法能在多种机器学习应用中发挥作用.
演化算法是演化学习的优化引擎.本章先介绍一些基础演化算法，然后介绍一些在经典研究中常用的伪布尔函数，以及关于算法运行时间复杂度的基本知识，再介绍如何把演化算法建模成一种数学模型，即马尔可夫链（Markov chain），最后介绍两种经典的运行时间分析方法：适应层分析法（fitness level）和漂移分析法（drift analysis）.
演化算法[Bäck，1996]是一类通用的启发式优化算法，通过考虑“突变重组”和“自然选择”这两个关键因素来模拟自然演化过程.这类算法通过反复修改当前维持的解来产生新解并从中去除差解，从而迭代地改进维持的解的质量.尽管存在许多变种，演化算法还是具有共同的一般流程，如第1章中图1.2所示：
1.生成一个包含若干解的初始种群；
2.基于当前种群通过变异和交叉算子产生新解；
3.评估新产生的子代解；
4.从当前种群和子代解中选择较优解以形成新的种群；
5.返回第二步并重复运行，直至满足某个停止条件.
接下来，本节介绍一些常作为理论分析对象[Neumann and Witt，2010；Auger and Doerr，2011]的演化算法.
算法2.1展示的（1+1）-EA算法是一种在{0,1}n解空间中对伪布尔函数进行最大化的简单演化算法，它仅维持一个解（即种群规模为1），通过使用算法2.1第3行中的逐位变异（bit-wise mutation）算子和第4～6行的选择机制来反复地改进当前解的质量.逐位变异算子对解的每一位以概率 p ∈（0,0.5）独立地进行翻转.当逐位变异算子被替换成一位变异算子，即随机选择解的一位进行翻转时，算法2.1相应地被称为随机局部搜索（randomized local search,RLS）.若选择机制是严格的，即算法2.1第4行变成“if f（s′）＞ f（s）then”，则这两个算法分别被记作（1+1）-EA≠和RLS≠.
上述两种常用变异算子可总结为：
•一位变异，随机选择解s的一位进行翻转；
•逐位变异，对解s的每一位以概率p∈（0,0.5）独立地进行翻转.
注意，当变异概率p未被明确指定时，默认采取常用设置p=1/n.
算法2.2展示的（μ+1）-EA 算法使用规模为 μ的父代种群（parent population）.从算法2.2第1行开始，先构建一个由μ个随机解构成的初始种群，（μ+1）-EA每轮迭代执行如下操作：先执行第3～4行中步骤，对从当前种群中随机选择的一个解进行变异以产生一个新解s′；再执行第5～8行中步骤，若s′不差于当前种群中的最差解，则用其替换最差解.
算法2.3展示的（1+λ）-EA算法使用规模为λ的子代种群（offspring population）.从算法2.3第1行的一个随机解开始，（1+λ）-EA每轮迭代执行如下操作：先执行第3～5行中步骤，独立地变异当前解λ次以产生λ个子代解；然后执行第6～8行中步骤，从当前解和子代解中选择最好解作为下一代解.
算法2.4展示的（μ+λ）-EA算法是一种基于种群的一般演化算法，其父代种群和子代种群规模分别为 μ和λ.该算法维持 μ个解，在每轮迭代中执行如下操作：通过对从当前种群中选择的一个解进行变异产生一个子代解，独立地重复该过程λ次；然后从父代解及子代解中选择μ个解作为下一代种群.注意，用于产生新解和更新种群的选择策略可以是任意的，因此（μ+λ）-EA相当广泛，涵盖了大部分基于种群的演化算法，例如[He and Yao，2002；Chen et al.，2012；Lehre and Yao，2012].
上面介绍的演化算法均针对的是单目标优化，算法2.5展示的简单演化多目标优化法（simple evolutionary multi-objective optimizer,SEMO）[Laumanns et al.,2004]是一种用于同时最大化多个伪布尔函数的简单演化算法.SEMO因其简单而成为首个得到理论分析结果的多目标演化算法.SEMO具有多目标演化算法的一般结构.在算法2.5的第5行，SEMO采用一位变异算子产生新解；第6～8行，SEMO在种群中仅维持非占优（nondominated）解，即未被占优的解.
SEMO存在多种变体.例如，公平演化多目标优化法（fair evolutionary multi-objective optimizer，FEMO）[Laumanns et al.，2004]通过使用一种公平抽样策略（即确保每个解最终产生相同数目的子代解）来加速对最优解集的探索；贪心演化多目标优化法（greedy evo lutionary multi-objective optimizer，GEMO）[Laumanns et al.，2004]通过使用一种贪心选择机制（即仅允许占优一些当前解的新加入解具有繁殖机会）扩展FEMO以获取帕累托前沿方向的最大进步.这些算法均采用一位变异算子执行局部搜索（local search），而通过将SEMO中的一位变异算子替换成逐位变异算子执行全局搜索（global search），便获得了全局简单演化多目标优化法（global SEMO，GSEMO）；也就是说，除了算法2.5第5行变成“在解s上执行逐位变异算子以产生新解s′；”，GSEMO和SEMO完全相同.
本节最后介绍符号O、o、Ω、ω以及Θ，它们被用于表示算法的运行时间如何随着问题规模增长而变化.令 f和g为两个定义在实数空间上的函数，有：
• f（n）=O（g（n））当且仅当∃常数
满足∀n≥n0:|f（n）|≤m·|g（n）|；
• f（n）=o（g（n））当且仅当∀常数
满足∀n≥n0:|f（n）|≤m·|g（n）|；
• f（n）=Ω（g（n））当且仅当g（n）=O（f（n））；
• f（n）=ω（g（n））当且仅当g（n）=o（f（n））；
• f（n）=Θ（g（n））当且仅当 f（n）=O（g（n））且 f（n）=Ω（g（n））.
伪布尔函数类是一个很大的函数类，如定义2.1所述，其仅要求解空间为{0,1}n且目标空间为
.顶点覆盖（vertex cover）和0-1背包（0-1 knapsack）等许多著名的NP难问题均属于此类问题.
定义2.1.伪布尔函数
若函数 f的解空间为{0,1}n，目标空间为
，即 
，则 f为伪布尔函数.
定义2.2中描述的UBoolean函数类由一大类非平凡的伪布尔函数构成，其中每个函数的全局最优解都是唯一的.由于演化算法对称地对待0-位和1-位，于是最优解中的0-位可解释成1-位而不影响演化算法的行为.这使得对于UBoolean中的任意函数，不失一般性，可假定全局最优解为（1，1，...，1），简写为1n.
定义2.2.UBoolean函数
若伪布尔函数
满足
则 f为UBoolean函数.
多种不同结构的伪布尔问题[Droste et al.，1998；He and Yao，2001；Droste et al.，2002]被用于演化算法的理论分析，接下来介绍本书中将用到的几个伪布尔问题.
定义2.3描述的OneMax问题试图最大化一个解中1-位的数目，其最优解是函数值为n的1n.[Droste et al.，2002]已证明，（1+1）-EA算法求解OneMax的期望（expected）运行时间为Θ（nlog n）.
定义2.3.OneMax问题
找到n位的二进制串以最大化
其中si表示s∈{0,1}n的第i位.
定义2.4描述的LeadingOnes问题试图最大化一个解中从首端（即最左端）开始连续1-位的数目，其最优解是函数值为n的1n.[Droste et al.，2002]已证明，（1+1）-EA算法求解LeadingOnes的期望运行时间为Θ（n2）.
定义2.4.LeadingOnes问题
找到n位的二进制串以最大化
其中sj表示s∈{0,1}n的第 j位.
定义2.5描述的Peak问题在除最优解1n以外的所有解上具有相同的适应度，即0.[Oliveto and Witt，2011]已证明，（1+1）-EA算法在解决Peak问题时，需要的运行时间以极大概率为2Ω（n）.
定义2.5.Peak问题
找到n位的二进制串以最大化
其中si表示s∈{0,1}n的第i位.
定义2.6描述的Trap问题的目标为在最优解1n之外，最大化一个解中0-位的数目；最优目标值为 c-n＞ 0，且非最优解的目标值均不超过0.[Droste et al.,2002]已证明，（1+1）-EA求解Trap问题的期望运行时间为Θ（nn）.
定义2.6.Trap问题
找到n位的二进制串以最大化
其中c＞n,si表示s∈{0,1}n的第i位.
接下来，介绍两个二目标伪布尔问题：首一尾零（leading ones trailing zeros，LOTZ）、数一数零（count ones count zeros，COCZ）；它们的目标均为同时最大化两个伪布尔函数.在探究多目标演化算法的性质时，LOTZ和COCZ 问题常被作为研究案例[Giel，2003；Laumanns et al.，2004].
LOTZ 问题的一个目标与 LeadingOnes 问题相同，即最大化从解的首端开始的连续1-位的数目，另一个目标是最大化从解的尾端（即最右端）开始的连续0-位的数目.LOTZ的目标空间可划分成n+1个子集 F0,F1,...,Fi,...,Fn，其中下标i ∈ {0,1,...,n}是两个目标值之和，也就是说，若 f1（s）+ f2（s）=i，则 f（s）∈ Fi[Laumanns et al.,2004].Fn={（0,n）,（1,n-1）,...,（n,0）}是帕累托前沿，相应的帕累托最优解为0n,10n-1,...,1n，其中0n和10n-1分别是（0,0,...,0）和（1,0,...,0）的简写.
定义2.7.LOTZ问题
找到n位的二进制串以最大化
其中sj表示s∈{0,1}n的第 j位.
COCZ 问题的一个目标与 OneMax 问题相同，即最大化解中 1-位的数目，另一个目标是最大化解前半部分中 1-位的数目和后半部分中 0-位的数目之和.可见，两个目标在优化解的前半部分上是一致的，均为最大化其中 1-位的数目，而在优化后半部分上是冲突的.COCZ 的目标空间可划分成 n/2+1个子集 F0,F1,...,Fi,...,Fn/2，其中下标 i ∈{0,1,...,n/2}为解前半部分中的1-位数目；每个 Fi均包含 n/2+1个不同的目标向量（i+ j,i+n/2- j），其中 j ∈ {0,1,...,n/2}为解后半部分中1-位的数目[Laumanns et al.,2004].Fn/2={（n/2,n）,（n/2+1,n-1）,...,（n,n/2）}为帕累托前沿；
为所有帕累托最优解构成的集合，规模为
.
定义2.8.COCZ问题
找到n位的二进制串以最大化
其中问题规模n是偶数，si表示s∈{0,1}n的第i位.
算法求解问题的效能常用运行时间复杂度来刻画，这也是随机搜索启发式的一个基本理论性质[Neumann and Witt，2010；Auger and Doerr，2011].由于适应度评估往往是算法运行过程中代价最大的计算过程，因此用于单目标优化的演化算法的运行时间往往被定义为首次找到一个“期望解”所需的适应度评估（即目标函数 f（·）的计算）次数[Neumann and Witt，2010；Auger and Doerr，2011].
在进行精确分析时，所考虑的期望解为最优解；而对于近似分析，期望解则是满足一定近似保证的解，见定义2.9.此处考虑的是最大化问题，而α-近似可类似地针对最小化问题定义，其中α≥1.
定义2.9.α-近似
给定待最大化的目标函数 f，若 f（s）≥α·OPT，其中α∈[0,1]，则解s具有α-近似比（approximation ratio）.
当演化算法用于求解带噪优化问题时，其运行时间通常被定义为首次找到真实适应度函数f的期望解需要的适应度评估的次数，而非以带噪适应度函数为基准[Droste，2004；Akimoto et al.，2015；Gießen and Kötzing，2016].
对于多目标优化，演化算法的运行时间被定义为找到帕累托前沿或者帕累托前沿的一个近似所需的对目标向量 f的计算次数.找到帕累托前沿意味着对帕累托前沿中的每一个目标向量，至少找到一个相应的帕累托最优解.定义2.10给出了针对多目标优化的近似：找到帕累托前沿的一个近似意味着对于每一个帕累托最优解都存在一个解在每个目标函数上均为α-近似的.
定义2.10.针对多目标优化的α-近似
给定待同时最大化的m个目标函数 f1,f2,...,fm以及某个解集P，若对于帕累托前沿F∗中的任意目标向量
,∃s∈ P满足∀i ∈[m]:
，其中α∈[0,1]，则解集P具有α-近似比.
由于演化算法是随机算法，因此通常考虑运行时间的期望.若未明确提及近似分析，则默认考虑精确分析下的期望运行时间，即找到最优解（针对单目标优化）或者帕累托前沿（针对多目标优化）的期望运行时间.
在演化算法的运行过程中，子代解往往由当前解变化产生，因此该过程可自然地被建模成马尔可夫链[He and Yao,2001,2003a].马尔可夫链是一个随机变量序列
，其中变量ξt+1仅依赖于变量ξt，即P（ξt+1| ξt,ξt-1,...,ξ0）= P（ξt+1| ξt）.因此，马尔可夫链可完全由初始状态ξ0和转移概率P（ξt+1|ξt）所刻画.
不妨用
表示问题的解空间.对于维持m个解（即种群规模为m）的演化算法，搜索空间记为
，其精确规模可参见[Suzuki,1995].将演化算法建模为马尔可夫链有多种方式，其中最直接的方式是将
作为马尔可夫链
的状态空间，即
.令
表示目标状态空间.例如对于单目标优化下的精确分析，当且仅当某个种群至少包含一个最优解时，它属于
.基于马尔可夫链可以自然地模拟演化过程（即演化算法求解问题实例的过程），如图2.1所示，演化算法在运行t轮后的种群Pt对应了马尔可夫链在t时刻的状态ξt.本书将始终考虑离散状态空间，即离散的
.
为了揭示马尔可夫链
（即相应的演化过程）从某个初始状态出发多快能够进入
，接下来定义马尔可夫链的首达时（first hitting time,FHT），即首次到达目标状态空间所需的步数.本书将始终用
和
分别表示状态空间和目标状态空间.
定义2.11.条件首达时
给定从t0时刻开始的马尔可夫链
，其中
，令τ为表示首达时的随机变量，满足
τ的条件期望
称为
从t=t0和
出发的条件首达时（conditional FHT,CFHT）.
定义2.12.分布条件首达时
给定从t0时刻开始的马尔可夫链
，其中
呈某个状态分布π,CFHT的期望
称为
从t=t0和
出发的分布条件首达时（distribution-CFHT,DCFHT）.
若马尔可夫链
在找到目标状态后便不再离开，则称为吸收马尔可夫链（absorbing Markov chain），如定义2.13所述.对于任意一条非吸收马尔可夫链，总能构造出一条对应的吸收马尔可夫链：模仿给定的非吸收马尔可夫链；一旦找到目标状态，便始终停留在该状态.因此，构造出的吸收马尔可夫链与相应的非吸收马尔可夫链的首达时相同.为方便讨论，假定演化算法总能被建模为吸收马尔可夫链.
定义2.13.吸收马尔可夫链
若马尔可夫链
满足
则称为吸收马尔可夫链.
若演化算法采用非时变算子，则相应演化过程可被建模成齐次马尔可夫链（homogeneous Markov chain），即状态转移概率不依赖于时间t的马尔可夫链.
定义2.14.齐次马尔可夫链
若马尔可夫链
满足
则称为齐次马尔可夫链.
下面介绍关于马尔可夫链CFHT和DCFHT的一些性质[Norris，1997].
引理2.1
给定马尔可夫链
，有
引理2.2
给定吸收马尔可夫链
，有
其中
是
的分布.
引理2.3
给定齐次马尔可夫链
，有
给定某个演化算法，其求解问题时的运行时间可看作首次找到目标种群所需的适应度评估次数；而对于相应的马尔可夫链，其首达时对应演化算法所需的轮数.因此，演化算法从 ξ0和ξ0～ π0开始的期望运行时间分别等于 m1+m2·
和m1+m2· 
，其中m1和m2分别为初始种群评估和算法每轮迭代所需的适应度评估次数，二者分别与父代和子代种群规模相关.例如，对于（1+1）-EA,m1= 1且m2= 1；对于（1+λ）-EA,m1=1且m2=λ.若初始种群没有指定，则默认其满足均匀分布πu，也就是说，期望运行时间为m1+m2·
=m1+m2· 
.
为了分析演化算法在求解问题时的运行时间，可将其建模成马尔可夫链，然后分析首达时.本节将介绍分析马尔可夫链首达时的一些常用方法.
适应层分析法[Wegener，2002]是分析采用精英（elitist）保留策略[1]的演化算法期望运行时间的一种方法.优化问题的解空间根据适应度被划分成若干层集（level set），这些层集的次序由它们包含解的适应度决定.定义2.15形式化地给出了针对最大化问题的划分.
定义2.15.＜f-划分
给定最大化问题
及目标子空间为 
的解空间 
，若
，则关系
成立.解空间
的一个＜f-划分是将
划分成非空集合
，满足
，且
.
层集直观上形成了“阶梯”，而采用精英保留策略的演化算法在更新种群时会始终保留已找到的最好解，即只会“往上”爬.基于此，运行时间的上界（upper bound）可通过把离开每一级“台阶”的最长时间累加起来计算，即悲观地假定单步跳跃只能到达相邻的更高层集，如图2.2（a）所示.类似地，运行时间的下界（lower bound）为离开一级台阶的最短时间，即乐观地假定单步跳跃就能到达目标层集，如图2.2（b）所示.
图2.2适应层分析法示意，其中vi和ui分别表示离开层集
的概率的下界和上界
定理2.1给出了适应层分析法的形式化描述.当演化算法的种群规模大于1时，
意为种群ξt中的最好解属于解空间
.注意，为了统一上下界的表述，我们对原始定理作了一些等价的变换.
定理2.1.适应层分析法[Wegener,2002]
对于采用精英保留策略的演化算法，其求解问题 f的过程被建模成马尔可夫链
，令 
是一个 ＜f-划分.
，令 
|
.该条链的DCFHT满足
定理2.2描述了精制适应层分析法（refinedfitness level）[Sudholt，2013].
定理2.2.精制适应层分析法[Sudholt,2013]
对于采用精英保留策略的演化算法，其求解问题 f的过程被建模成马尔可夫链
，令 
是一个 ＜f-划分.
，令 
i,j 
,
，其中 
.再令常数 
满足 
且
.该条链的DCFHT满足
精制适应层分析法遵循适应层分析法的一般思想，但引入变量 χ以反映演化算法跳跃至更高层的概率分布.当 χ较小时，演化算法大概率会跳过许多层，从而取得大的进步；当 χ较大时，演化算法每一步只能取得小的进步.对于上界和下界分析，当 χ分别取1和0时，精制适应层分析法将退化为原始适应层分析法.因此，原始适应层分析法是精制方法的一个特例.
漂移分析法是另一种分析马尔可夫链DCFHT的工具.它最初被[He and Yao,2001,2004]运用于演化算法的运行时间分析，之后衍生出许多变体[Doerr et al.,2012c; Doerr and Goldberg,2013].本书将使用漂移分析法的加性（additive）和乘性（multiplicative）版本，即定理2.3和定理2.4.要使用漂移分析法，需要先构造一个函数V（x）来度量一个状态x到目标状态空间
的距离，如图2.3所示.
图2.3漂移分析法示意，其中V（·）表示距离函数，即状态·到目标空间
的距离
距离函数V（x）满足
且
，其形式化描述见定义2.16.然后，我们需要考虑每一步在缩短当前状态与
距离上取得的进步，即
.对于加性漂移分析法（additive drift analysis），即定理2.3,DCFHT的上界（下界）可通过将初始距离除以每一步取得进步的下界（上界）获得.当每一步取得的进步与当前到目标空间的距离大致成正比时，乘性漂移分析法（multiplicative drift analysis），即定理2.4，会更容易使用.
定义2.16.距离函数
给定目标子空间为
的状态空间
，若函数V满足
且
，则称为距离函数.
定理2.3.加性漂移分析法[He and Yao,2001,2004]
给定马尔可夫链
和距离函数V（x），若存在实数c1＞0使得
，
则DCFHT满足
若存在实数c2＞0使得
，
则DCFHT满足
定理2.4.乘性漂移分析法[Doerr et al.,2012c]
给定马尔可夫链
和距离函数V（x），若存在实数c＞0使得
，
则DCFHT满足
其中Vmin=min{V（x）|V（x）＞0}.
定理2.5给出的简化负漂移分析法（simplified negative drift analysis）[Oliveto and Witt，2011，2012]，用于证明马尔可夫链首达时的指数级（exponential）下界，其中xt通常由ξt的一个映射表示.它要求满足两个条件：漂移是负的且达常数级大小，即式（2.26）；朝目标状态前进或远离的概率指数级衰减，即式（2.27）.为降低对于常数负漂移的要求，定理2.6给出了考虑自环概率的带自环的简化负漂移分析法（simplified negative drift analysis with self-loops）[Rowe and Sudholt，2014].定理2.7则给出了原始负漂移分析法（negative drift analysis）[Hajek，1982].该方法更强大，因为两个简化版本均能通过其证明而得.
定理2.5.简化负漂移分析法[Oliveto and Witt,2011,2012]
令 xt（t≥ 0）为描述某个状态空间上的随机过程的实值随机变量.若存在区间
，两个常数 δ,∈＞ 0，以及可能依赖于 l= b- a的函数 r（l）（满足1≤r（l）=o（l/log（l））），使得∀t≥0有以下条件成立：
则存在常数c＞ 0使得对于T= min{t≥ 0:xt≤ a | x0 ≥ b},P（T≤ 2cl/r（l））=2-Ω（l/r（l））成立.
定理2.6.带自环的简化负漂移分析法[Rowe and Sudholt,2014]
令 xt（t≥ 0）为描述某个状态空间上的随机过程的实值随机变量.若存在区间
，两个常数 δ,∈＞ 0，以及可能依赖于 l= b- a的函数 r（l）（满足1≤r（l）=o（l/log（l））），使得∀t≥0有以下条件成立：
则存在常数c＞ 0使得对于T= min{t≥ 0:xt≤ a | x0≥ b},P（T≤ 2cl/r（l））=2-Ω（l/r（l））成立.
定理2.7.负漂移分析法[Hajek,1982]
令xt（t≥0）为描述某个状态空间上的随机过程的实值随机变量.选取依赖于参数l的两个实数a（l）和b（l），满足a（l）＜ b（l）.令T（l）为一个随机变量，表示在所有t≥0的时刻中使得xt≤a（l）的最早时刻.若存在λ（l）＞0和p（l）＞0使得
则对于所有时间界L（l）≥0，有
其中
.
[1].算法不会丢弃已找到的最好解.
