进化算法介绍

自然界生物在周而复始的繁衍中，基因的重组、变异等，使其不断具有新的性状，以适应复杂多变的环境，从而实现进化。进化算法精简了这种复杂的过程而抽象出一套数学模型，用较为简单的编码方式来表现复杂的现象，并通过简化的遗传过程来实现对复杂搜索空间的启发式搜索，最终能够在较大的概率下找到全局最优解，同时天然地支持并行计算。下图展示了常规遗传算法 (左侧) 和在并行计算下的遗传算法 (右侧) 的基本流程

要努力呦

14702人浏览 · 2022-09-01 16:40:14

要努力呦 · 2022-09-01 16:40:14 发布

本文摘自Geatpy库

一、进化算法概述

自然界生物在周而复始的繁衍中，基因的重组、变异等，使其不断具有新的性状，以适应复杂多变的环境，从而实现进化。

进化算法精简了这种复杂的过程而抽象出一套数学模型，用较为简单的编码方式来表现复杂的现象，并通过简化的遗传过程来实现对复杂搜索空间的启发式搜索，最终能够在较大的概率下找到全局最优解，同时天然地支持并行计算。

下图展示了常规遗传算法 (左侧) 和在并行计算下的遗传算法 (右侧) 的基本流程。

图中COREn 表示计算核心。不同的计算核心处理不同的单个子种群 (当然也可以处理多个子种群)，种群间互相独立进行进化 (区域模型)，种群间进行个体迁移和种群竞争。这只是其中一种并行计算遗传算法，另外还有全局模型和本地模型。

除了种群间可以并行计算外，种群内的若干个个体之间也可以实现并行计算。因此遗传算法具有很强的并行性。

值得注意的是：在进化算法中，重组和交叉并不是同一个概念，交叉是重组的一种。

对于常规遗传算法，在计算开始时，根据设计的编码规则随机初始化许多个体 (形成一个或多个种群)，然后评估种群中个体的适应度，并根据适应度来选择一些个体到交配池，然后对交配池中的个体进行一定概率的重组和变异产生育种后代。至此，环境中同时存在父代和育种种群，此时需要从中选择出一些个体最终得到新一代种群。

在这个过程里面出现了两次选择：

第一次是从当前种群中选择出一些个体参与重组和变异等进化操作；

第二次是在父代和重组变异得到的育种后代中选择一些个体保留到下一代，这个阶段的选择也有时候被称为“重插入”或者“环境选择”。

但很多时候这两次选择之中的某一次经常会在算法描述中被省略掉，这并不意味着只有一次选择，本质上依旧是存在两次选择。

下图展示了经典遗传算法和经典差分进化算法的流程对比：

左图是经典的遗传算法流程图，可以看到它里面只出现了一次选择。实际上，它在重组和变异得到育种个体之后，无条件地代替了父代个体而形成新一代种群，这本质上也是一次选择，只是在选择中把父代所有个体都淘汰掉了。

这种做法也有一定的弊端：收敛速度较慢。

因此有不少加入了“精英保留”的改进型遗传算法，比如把育种种群的绝大部分个体（小于全部）代替父代中等数量的非最优个体而得到新一代种群；

另外还有把父代个体和育种个体合并，在统一的、相同的环境下进行择优选择一半个体得到新一代种群；

差分进化里面的一种经典做法是按照个体的索引顺序，每个育种个体只与其相同位置上的父代个体进行优胜劣汰保留其中一个，从而得到新一代种群。

由图也可以看出，进化算法和传统的搜索和优化算法有着显著不同，最明显的差异是：

• 进化算法具有天然的并行性，它可以并行地搜索一组点，而不是一个点。

• 进化算法使用的是概率转换规则，并非确定性转换规则。

• 进化算法不需要额外的信息，只有目标函数和相应的适应度影响搜索方向。

• 进化算法鲁棒性强，可以与各种算法轻松地结合在一起。

• 进化算法可以整合其他优化算法的优点，比如利用其他优化算法的优化结果来生成初始种群，这种二次搜索方式在很多场合下可以大幅度提高搜索效率。

• 进化算法可以给特定的问题提供多样化的搜索结果，让用户自己选择。比如在多目标优化的进化算法里，算法给出的是一组帕累托最优解。这些最优解可以作为多组备选方案。

选择、重组和变异是进化算法提供的经典操作算子。很多改进的进化算法都是围绕他们展开的。或许在命名上可能十分多样化，但万变不离其宗，本质上也能够被归入到这几类操作算子当中

二、编码

编码的设计是使用进化算法解决实际问题中极为关键的要素。

编码就是将问题的解空间映射到编码空间 (即搜索空间) 上的过程。

而由编码空间向问题的解空间的映射就成为解码。

编码的方式对搜索过程影响较大。

按照编码结果的数据类型分类，编码可以是：一维或二维的数据列、二进制数据列或字符串等。

按照映射方式来分类，编码可以是：简单映射编码、多重映射编码、排列编码、树编码等。一般而言编码需要满足以下三个原则：

1) 完备性：问题的解空间中所有的点都可以映射到编码空间中的点 (即染色体)。

2) 可靠性：编码得到的染色体必须对应问题空间中的某一个潜在解。

3) 非冗余性 (不强制要求)：染色体和潜在解之间必须一一对应

三、适应度评价

适应度是指种群个体” 适应环境的能力”。适应度的计算同样是使用遗传算法中的极为关键的要素。它指定了问题解的搜索方向，并直接关系到搜索效率和最终解的质量好坏。

对于已建立的数学模型，一般可以采用目标函数值作为适应度值。为了应对最小化和最大化的两种相反的优化目标，一般遵循最小化约定，即” 目标函数值越大，适应度越小”。某些版本是倒过来的，在算法内固定一种标准即可。

适应度的值必须是非负实数。某些问题中求出来的个体目标函数值有正有负，甚至是复数。因此有必要对目标函数与适应度函数之间建立合理的映射关系，保证适应度值是非负的，并且适应度增大的方向与目标函数的优化方向一致。

我们还可以对目标函数作线性变换、指数变换、幂指数变换、截断处理等得到适应度。这些变换都会对种群的多样性和算法的收敛速度带来影响。例如：

上图进行了目标函数和适应度函数的指数变换，并且使其符合” 目标函数值越大，适应度越小” 的约定，同时，适应度大的个体将会” 更加优秀”。指数变换可以突出优秀个体，加速搜索最优解的速度，但不利于种群多样性的保留。

在适应度计算中我们常常引入” 罚函数” 来解决带复杂约束的优化问题。” 罚函数” 通过对非可行解施加惩罚，以此来降低不符合约束条件的” 非可行解” 个体在下一代中的生存概率。在遗传算法中我们不完全否定非可行解。因为在搜索空间中非可行解有可能非常接近最优可行解。

下面介绍一种基于等级划分的适应度分配计算 (Rank-based fitness assignment)：

这种适应度计算方法不是直接对目标函数进行变换来计算的个体的适应度的，而是先根据目标函数值来对个体进行排序，然后根据个体在排序中的位置来确定其适应度。

这种适应度计算方法克服了基于目标函数变换来计算适应度值所带来的放缩问题 (因适应度放缩不当而导致的选择压力 (其概念详见下一节) 过小导致的搜索收敛过慢或过分放大优势个体的适应度而导致的搜索收敛过快)。基于等级划分的适应度分配计算在整个种群中设定了统一的比例，并提供了一种控制选择压力的简单有效的办法。

基于等级划分的适应度分配计算比简单的基于比例或目标函数变换的适应度计算更加健壮，所以，它是值得选择的方法。

这种适应度计算中涉及单目标函数值的线性排序 [1] 与非线性排序 [2] 两种方式：

1) 线性排序：

设种群规模 (即种群个体数) 为Nind，i 为个体在种群中的位置i = 1, 2, ..., Nind，根据个体的目标函数值从大到小对个体进行排序，设SP 为选择压力。则个体的适应度计算如下：

线性排序中选择压力SP的值必须在 [1.0,2.0] 之间。

文献 [1] 中有这种线性排序的详细分析。

其选择强度、多样性损失、选择方差 (这些概念详见下一节) 的计算如下：

2) 非线性排序：

文献 [2] 中引入了一种使用非线性排序的新方法。使用非线性排序比线性排序方法允许设定更高的选择压力。

其中X 为下面多项式的根：

非线性排序允许选择压力SP 的值在 [1, Nind - 2] 之间。

上面的适应度计算方法都是对单目标问题而言的。然而，在许多现实问题中，为评估个体的质量好坏，必须考虑多个标准才能确定个体的优越性。这就涉及到多目标的优化问题。我们可以通过线性加权法把多个单目标的目标函数值加权得到多目标的目标函数值，进而使用上面所述的一些单目标问题的适应度计算方法。也可以采用特殊的方法，如帕累托非支配排序法等。

四、选择

在第一节“概述”中提到在进化算法中存在两个阶段的选择。第一次是参与进化操作的个体的选择。这个阶段的选择可以是基于个体适应度的、也可以是完全随机地选择交配个体。一旦个体被选中，那么它们就会参与交叉、变异等进化操作。未被选中的个体不会参与到进化操作中。

第二次是常被称为“重插入”或“环境选择”的选择，它是指在个体经过交叉、变异等进化操作所形成的子代（或称“育种个体”）后用某种方法来保留到下一代从而形成新一代种群的过程。这个选择过程对应的是生物学中的” 自然选择”。它可以是显性地根据适应度（再次注意：适应度并不等价于目标函数值）来进行选择的，也可以是隐性地根据适应度（即不刻意去计算个体适应度）来选择。例如在多目标优化的 NSGA-II 算法 [1] 中，父代与子代合并后，处于帕累托分层中第一层级的个体以及处于临界层中的且拥挤距离最大的若干个个体被保留到下一代。这个过程就没有显性地去计算每个个体的适应度。

1.重插入方案

重插入方案有以下两种：

1) 全局重插入 (Global reinsertion)：

这种插入算法适用于在第一次选择阶段使用除了本地选择外的其他选择算法的情况。假如在第一次选择阶段使用了本地选择算法，那么重插入中就不能用全局重插入算法了。

• 育种个体与父代个体一样多，直接用所有的育种个体生成新一代种群 (完全重插入)。

• 育种个体比父代个体少，把育种个体随机均匀地替换父代的个体 (均匀重插入)。

• 育种个体比父代个体少，取代适应度较低的父代个体 (精英重插入)。

• 育种个体比父代个体多，重新插入适应度较高的育种个体 (精英保留重插入)

• 父子两代合并的竞争选择，即在父代个体和育种个体同时并存的情况下从两代种群的所有个体中选择合适数量的个体保留到下一代。

• 一对一生存者竞争选择。

完全重插入是最简单的重插入算法。最经典最简单的遗传算法 (Simple GA) 用的就是这种重插入方法。然而最坏的情况是：父代中最优秀的个体并没有繁殖产生优秀的个体，此时在重插入时又被最差的个体替代，因此种群丢失了精英，使得算法的收敛能力强。因此在多数情况下，推荐使用精英重新插入、精英保留重新插入或是父子两代合并竞争选择等带精英策略的方法。

2) 本地重插入 (Local reinsertion)：

在前面章节中介绍过本地选择算法，它在有界邻域中选择个体。那么育种后代的重插入也应该发生在相同的邻域中。这是一种基于位置信息的重插入算法，重插入时使用的邻域要跟本地选择中的一样。

以下的方法是可行的：

• 把育种个体随机均匀地替换其所在邻域内的父代个体。

• 把育种个体替换其所在邻域内的最差的父代个体。

• 把更适合插入到相邻邻域的育种个体替换相邻邻域中的最差的父代个体。

• 把更适合插入到相邻邻域的育种个体随机均匀地替换相邻邻域中的父代个体。

2.选择操作

下面是一些选择操作有关的术语：

选择压力 (selective pressure)：与所有个体的平均选择概率相比，最优个体被选中的概率。偏差 (bias)：个体标准化的适应度预期期望再生概率之差的绝对值。

个体扩展 (spread)：在进行选择时，比较优秀个体可能会被多次选择。该参数就限定了最多可以被重复选择的个数。

多样性损失 (loss of diversity)：进行选择操作后，未被选择的个体数目占种群个体总数的比例。

选择强度 (selection intensity)：把标准高斯分布用在选择操作后的种群个体平均适应度的期望值。选择强度越大，进化算法的最优化搜索的收敛速度就越快，但也往往意味着多样性的损失。 选择方差 (selection variance)：把标准高斯分布用在选择操作后的种群个体适应度的方差。

选择操作一般是基于个体的适应度来计算的 (详见上一节)，下面介绍一些经典的选择算子：

1) 轮盘赌选择 (Roulette wheel selection)：

轮盘赌选择是一种有回放的随机抽样选择法。种群的个体被映射到区间的连续片段，每个个体所在片段的长度与其适应度成比例。生成随机数，根据其所落在的片段选择对应的个体，并重复该过程直到获得所需数量的个体。

所选择的个体为：2, 1, 5, 3, 8, 2。

轮盘赌选择算法实现了零偏差 (bias) 但不保证最小个体扩展 (spread)，因此，上面的例子中，2 号个体被选择了两次 (有可能所选的个体全部都是同一个)。

2) 随机抽样选择 (Stochastic universal sampling)：

随机抽样选择实现了零偏差同时保证最小个体扩展。种群的个体被映射到区间的连续片段，每个个体所在片段的长度与其适应度成比例 (这里跟轮盘赌是相同的)。用一组等距离的指针随机地指向上述区间，每个指针所指的个体即为要选择的个体。指针间的距离是1/Nsel (Nsel 为要选择的个体数)，第一个指针的位置由[0, 1/Nsel) 范围内的随机数给出。

假设要选择 6 个个体，那么指针间的距离则为1/6 ≃ 0.167，选择情况如下图：

所选择的个体为：1, 2, 3, 5, 6, 9。

轮盘赌选择和随机抽样选择都属于轮盘赌模型 (或称基于适应度比例的选择模型)，但后者通常能够得到更想要得到的结果，种群多样性也得以保证。

某些人认为随机抽样选择是不考虑个体的适应度、纯粹依靠随机数的结果来进行个体选择，这种想法是极其错误的。这种选择方法实际上会让进化算法变为盲目随机搜索，而无法发挥适应度应该起到的指导搜索方向的作用。

3) 锦标赛选择 (Tournament selection)：

该选择算法模仿淘汰赛制，每次从种群中挑选Tour 个个体进行比较，从中选出一个最好的个体加入被选集合。重复该操作，直到被选集合的大小达到需要选择的个体数。、

Tour 即为竞赛规模。在文献 [2] 中，可以看到锦标赛选择的相关理论分析。

选择强度：

多样性损失：

选择方差：

4) 截断选择 (Truncation selection)：

截断选择是与前面的几种选择算法比较不一样的算法。它更接近于生物学里的” 人工育种”，适用于大规模种群的个体选择。

在截断选择中，根据适应度对种群个体进行分类。设定截断阈值为 Trunc(表示选择作为父母的个体的比例)，低于阈值的个体不会产生后代。

” 选择强度” 这个术语就经常用在截断选择中，” 选择强度” 和截断阈值之间的关系非常密切。在文献 [1] 中可以看到截断选择的相关理论分析。

5) 本地选择 (Local selection)：

在本地选择算法中，每个个体处在一个约束环境中 (称为” 本地邻域”)。

个体仅与同一邻域内的个体相互作用。

邻域是根据种群的结构来定义的，可以是线性的、二维的或者是三位及更加复杂的。

邻域之间的距离决定了邻域的大小，而邻域的大小决定了种群个体之间遗传信息的传播速度，即决定了种群是快速繁殖还是维持高度的种群多样性。

[VBS91] 的模拟中得出了类似的结果，在较小的邻域中进行的本地选择比在较大的邻域中要好。

选择算法依赖于适应度的计算，不同的适应度计算方法会使得种群个体的适应度呈现不一样的分布特征，从而影响到选择操作的效果。

6) 基向量选择：

在差分进化算法中，差分进化操作是由差分变异基向量 Xr0 和差分向量 Xr1 以及 Xr2 共同作用得到。其中差分变异基向量的索引 r0 是从个体索引序列 [0, 1, 2, ..., N − 1] 中抽选出来的。在差分变异前一共要抽选出与种群个体数等量的基向量。

因此在这种情况下的选择会跟前面的选择方法有一个不同之处：它不能控制选择的数目。除了可以直接使用前面提到的轮盘赌选择、随机抽样选择以及锦标赛选择等选择算法来得到基向量的索引序列之外，在差分进化中还常使用精英个体选择以及随机补偿选择两种选择方式：

A. 精英个体索引复制:

它将根据种群个体的适应度得到精英个体的索引，然后复制该索引若干份直至达到所需选择的个体数，最后返回一个全是精英个体索引的序列。

B. 随机补偿选择:

在差分进化算法中，非常鼓励索引值互异，即各个索引在相同位置上的序号与原种群个体的索引序列是不一致的。例如基向量索引的第一位不能为 0，第二位不能为 1，第三位不能为 2……以此类推（索引序列从 0 数起）。这样能够避免差分进化发生退化现象。因此随机补偿法根据以下公式产生基向量索引 r0：

其中 N 为种群的个体数，i 为种群个体索引，i = 0, 1, 2, ..., N，rg 为 [1, N − 1] 之间的整数。它在每一代的进化中会被重新生成一次。根据该式得到的 r0 可以保证与目标索引 i 互异。

7) 一对一生存者竞争选择:

这种选择算法需要两个种群。两个种群的每个个体只与在另一个种群中相同位置的个体进行适应度比较，适应度高者被选中。当然这个算法可以扩展到多个种群。或者是可以把一个大种群等分为若干个小的子种群，让子种群的个体参与一对一生存者竞争选择。如图所示：

图中有两个种群，圆圈内标注的是个体的适应度，橙色的便是根据一对一生存者竞争选择的被选中的个体。

1) 全局重插入 (Global reinsertion)：

2) 本地重插入 (Local reinsertion)：

2.选择操作

1) 轮盘赌选择 (Roulette wheel selection)：

2) 随机抽样选择 (Stochastic universal sampling)：

3) 锦标赛选择 (Tournament selection)：

4) 截断选择 (Truncation selection)：

5) 本地选择 (Local selection)：

1) 重组算法的代表——离散重组算法 (Discrete recombination)：

2) 实数值重组 (Real valued recombination)：

2.1) 中间重组：

2.2) 线性重组：

3) 模拟二进制交叉：

4) 值互换重组——交叉 (Values exchanged recombination——crossover)：

4.1) 减少代理交叉 (Crossover with reduced surrogate)：

4.2) 部分匹配交叉 (PMX, partially matched crossover)：

4) 互换突变 (Exchanged mutation)：

参考文献

[1] Deb K , Pratap A , Agarwal S , et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):0-197.

[2] Blickle T , Thiele L . A Comparison of Selection Schemes Used in Evolutionary Algorithms[J]. Evolutionary Computation, 1996, 4(4):361-394

五、重组

进化算法中的重组有时俗称为” 交叉”，但系统地看，重组包含了交叉。

重组算法是改进进化算法最有效的环节，它通过结合交配群体中包含的遗传信息产生新的个体。因为进化算法中有二进制编码、实值编码、排列编码、树编码等，因此必须也有与编码方式相适应的不同的重组算法。

重组概率：

如果某个重组算子又称为“交叉”，那么“重组概率”在其看来可以称作“交叉概率”。

重组概率主要有 2 种，一种是染色体重组概率，即对于任意一组配对的染色体而言，其发生重组的概率；另一种是条件重组概率，又称片段重组概率，它是指在满足染色体重组概率的条件下，重组算子在染色体上发生作用的最小片段（“最小作用片段”）将要发生重组的概率。

与变异算子的变异概率不同，不同的重组算子所侧重强调哪一种重组概率会有所区别，在使用的时候要看清楚是指哪一种概率。

有关“最小作用片段”详细的相关定义如下：

定义 1. 给定一个重组算法，当它作用在染色体上的某片段时，如果该片段不能再细分成互相独立的多个片段，那么称这个片段为该重组算子在染色体上的最小作用片段。

例如，在模拟二进制交叉中，该交叉算子作用与染色体的最小片段为染色体上的每一位元素。因此它的“最小作用片段”的长度为 1。在该交叉算子中，最小作用片段对应的交叉概率固定地设为 0.5，因此在该交叉算子中，侧重强调的是第一种交叉概率，即染色体发生交叉的概率。

又例如，在差分进化算法的二项式分布交叉中，交叉概率指的是上文所说的第二种，即最小作用片段发生交叉的概率。而第一种概率则固定地设为 1。

某些交叉算子还会设立一种额外的交叉概率，比如均匀分布交叉。它里面不是上文所说的两种交叉概率（即把它们都固定地设为 1），而是设立了额外的一个交叉概率：比如交叉得到的 child 1 的染色体的某一位有 0.5 的概率等于 parent 1 染色体的相同位置的元素；另外 0.5 的概率等于 parent 2 染色体的相同位置的元素。

下面介绍几种经典的重组算法：

1) 重组算法的代表——离散重组算法 (Discrete recombination)：

离散重组算法在个体间执行变量值的交换，在生成交配个体时，交配个体中每个变量可以等概率地挑选一个父个体对应变量作为自身的值。其几何特征表现如下，离散重组产生了父代所在的超立方体的角：

考虑以下两个个体，每个个体有 3 个变量 (3 维)：

父个体 1：13 24 5

父个体 2：124 3 24

生成的 child 1 和 child 2 的染色体分别可以是：124 24 24 和 13 24 5。

与离散重组非常相似的是均匀分布交叉。但稍有不同的是在均匀分布交叉中，一旦确定了交叉后的 child 1 的染色体的元素值，那么 child 2 的染色体元素值也随之确定。

2) 实数值重组 (Real valued recombination)：

实值重组算法可以实现对元素为实数值的染色体之间的重组，它包括中间重组、线性重组、扩展线性重组、模拟二进制交叉等。

2.1) 中间重组：

中间重组是一种仅适用于实数变量个体的重组算法。这里后代的变量值是在父辈变量的区间上选择的。生成子代个体的公式如下：

其中，αi 是[−d, 1 + d] 之间的随机数，它是一个随机均匀选择的比例因子。

参数d 的值代表可能产生的后代的区域大小。

d = 0 表示后代的变量值的区域大小与父代是一样的，此时称为”(标准的) 中间重组”。但是，由于后代的大多数变量不是在可能区域的边界上生成的，因此变量所覆盖的面积有可能会越来越小。因此，仅用d = 0 的标准中间重组就会发生这种变量空间收缩现象。因此，通过设置更大的d 值可以防止这种现象。一般设置d = 0.25，此时可以在统计学上保证后代的变量值的范围不会缩小。如图所示：

例如父个体染色体为：

父个体 1：0.4 1.2 -0.3

父个体 2：0.2 0.7 0.6

生成的子个体染色体可以是：0.3 0.9 0.4。

中间重组能够稍微超出父代所在的超立方体的边界，如图所示：

2.2) 线性重组：

线性重组类似与中间重组。产生子代个体的公式如下：

对比中间重组可见，线性重组只有一个α，即所有个体的α 是一样的。并且α 同样是[−d, 1 + d] 之间的随机数，代表随机均匀选择的比例因子。

对于d 的解析跟中间重组是一样的。

线性重组产生的后代，其变量是在父代所在的直线上，如图所示：

另外还有扩展线性重组，其详细介绍可以参见文献 [1]。

3) 模拟二进制交叉：

模拟二进制交叉 (Simulated Binary Crossover, SBX)[3] 由父代 xa 和 xb 生成以下后代：

其中 n 为染色体长度，βk 是由下面的概率密度函数生成的随机数：

其中 η 是任意的非负实数。η 的取值必须不小于 0。可以用下面的公式得到 β：

当然也可以采用其他方法来得到 β，比如采用服从标准正态分布的随机数，此时模拟二进制交叉就变成了“正态分布交叉”[4]。

细心观察不难发现，为什么“模拟二进制交叉”和“正态分布交叉”都被称为是“交叉”，而前面的“中间重组”、“线性重组”称为“重组”，但除了中间过程所用到的方法不同外，它们整体上看又比较相似，且有区别与单纯的值互换重组 (即严格意义上的交叉)。此外，如果翻看了下一节 (变异)，会发现差分变异从整体上看也跟上面的若干重组算法有着很大的相似之处，但差分变异被称作是变异而非重组。实际上，差分变异加上交叉算子可以被称为一种重组算子，有些流派甚至直接称差分变异为一种交叉算子，这其实是可以接受的。

如果要严格对这些算子分类，那目前来看是没多大必要的，在很多文献中“重组” 和“交叉”两个概念是相互混用的，至于差分变异与重组，尽管有着很大相似性，但若真要究其本质，重组也可以算作一种变异，因此本文档也不对其进行重新划分，继续把差分变异归为变异，以沿袭传统的说法。而对于“模拟二进制交叉”、“正态分布交叉” 以及类似的非单纯值互换的重组，尽管其原名是“交叉”，但本文仍把它们归类为“重组”而非“交叉”。而对于“离散重组”，它虽然是值互换的重组，本应当严格归类为 “交叉”，但考虑到重组包含交叉这一理念，因此继续把其归类为“重组”。事实上，一切交叉算子都可称其为重组算子。甚至一切重组算子也可以不太严谨地直接称其为交叉算子，这都是可以接受的。

4) 值互换重组——交叉 (Values exchanged recombination——crossover)：

这种重组方式就是两个父代个体交换染色体片段产生新个体的过程，因此也称为交叉操作。交叉操作中，个体的染色体编码可以是实值、也可以是二进制，比如：

[0 1 0 1 1 1 0 1] 和 [1.1 2.0 3.4 2.7 1.6] 这些类型的染色体都可以进行交叉操作，一般更多地用在二进制或格雷码编码的个体中。

交叉有分单点、双点和多点交叉。它们是根据交叉点的数量分类的。其中多点交叉的示意图如下：

此外还有均匀交叉、洗牌交叉，这里就不一一赘述了。这里要介绍一下” 减少代理” 交叉和部分匹配交叉：

4.1) 减少代理交叉 (Crossover with reduced surrogate)：

上面的交叉算法的交叉结果可能会产生和父代性状一样的个体，如果在遗传算法中想让交叉得到的子代中更多的个体拥有与父代个体不一样的性状，这时就可以用减少代理的交叉算法。

减少代理交叉算法尽可能地产生全新性状的个体，这是通过限制交叉点的位置来实现的——控制交叉点只出现在父代两个交叉个体的基因值不同的地方

4.2) 部分匹配交叉 (PMX, partially matched crossover)：

对于组合优化问题，染色体中每一位的值都是独一无二的，称为“排列编码”。

这意味着不能使用简单的交叉算法。PMX 可基于单点交叉也可基于两点交叉。本文档默认它是基于两点交叉的，因此它先随机产生两个交叉点，定义两点之间的基因片段为匹配区域，交换 2 个父代的匹配区域的基因，并对匹配区域外出现的重复基因进行替换。详见文献 [2]

文献 [2] 中还详细讲述了循环交叉 (CX, cycle crossover)、顺序交叉 (OX1, order crossover)、基于顺序的交叉 (OX2, order-based crossover)、基于位置的交叉 (POS, positionbased crossover)、投票重组交叉 (VR, voting recombination crossover) 以及位置交替交叉 (AP, alternating-position crossover)。在文中能进一步找到其详细算法的描述文档，这里就不一一赘述了。

参考文献

[1] Muhlenbein H . The Breeder Genetic Algorithm-a provable optimal search algorithm and its application[C]// Applications of Genetic Algorithms, IEE Colloquium on. IEEE Xplore, 1994.

[2] Khan I H. Assessing Different Crossover Operators for Travelling Salesman Problem[J]. International Journal of Intelligent Systems Technologies & Applications, 2015, 7(11):19- 25.

[3] Agrawal R B , Deb K , Agrawal R B . Simulated Binary Crossover for Continuous Search Space[J]. Complex Systems, 2000, 9(3):115-148.

[4] ZHANG Min. Research on evolutionary algorithms for constrained optimization and multiobjective optimization[D]. Hefei: University of Science and Technology of China, 2008.

六、变异

变异是指通过改变染色体中的一部分元素来形成新的染色体的过程。它能够提高种群的多样性，降低进化算法陷入局部最优解的风险。

变异概率：

变异概率 p 是用于控制变异发生几率的变量，变异概率主要有 2 种，一种是染色体变异概率，即对于任意一条染色体而言，其发生变异的概率（默认为 1）；

另一种是条件变异概率，又称片段变异概率，它是指在满足染色体变异概率的条件下，变异算子在染色体上发生作用的最小片段（“最小作用片段”）将要发生变异的概率。一般来说进化算法只考虑第二种变异概率，(前一种变异概率默认为 1)，因此第二种变异概率我们简称其为“变异概率”，其详细的相关定义与定理如下：

定义 1. 给定一个变异算法，当它作用在染色体上的某片段时，如果该片段不能再细分成互相独立的多个片段，那么称这个片段为该变异算子在染色体上的最小作用片段。

例如：对于二进制染色体的变异算子，它是作用在染色体的一个位（即一个“比特”）——将 0 变 1 或 1 变 0。因此染色体的位就是这种变异的最小作用片段。

又例如：对于两点互换变异算子，当它作用在一个排列编码的染色体上时，从染色体上随机选择两个位进行元素互换，因此该变异的最小作用片段为整条染色体。

定理 1. 变异算子最小作用片段的长度由具体的变异算子决定，这个长度可以是固定的也可以是不固定的。

定理 2. 给定一个变异算法，其在染色体上的最小作用片段可以有多个，长度可以唯一也可以不唯一。

定义 2. 给定一个变异算法，在其最小作用片段上发生这种变异的概率称为该变异算子的片段变异概率，进化算法中主要侧重强调这类变异概率，因此把它简称“变异概率”。

定理 3. 给定一个变异算法，其所有的最小作用片段对应的变异概率可以是相同的也可以是不相同的。

定义 3. 给定一个变异算法，把其有多少个发生了变异的最小作用片段的期望值称为该染色体的变异期望次数。

例如：对于多项式变异算子，假如想要一条染色体上有2个位的元素发生多项式变异，那么此时的变异期望次数是 2。

定理 4. 给定一条染色体和一个变异算子，该染色体的变异期望次数等于所有最小作用片段对应的变异概率之和。

例如：多项式变异算子常常会默认设定变异概率等于一个整数/染色体长度。这个整数其实就等于染色体发生多项式变异的位数的期望值。

下面介绍几种常见的变异算法。

1) 二进制染色体突变：

在二进制进化算法中，变异非常简单，只需根据变异概率反转染色体的每一位元素 (0->1 或 1->0) 即可。

2) 连续进化算法的变异：

连续进化算法是指染色体的每一位是实数。此时变异的方法非常多，常见的有：

2.1) 均匀变异：

均匀变异是指变异的结果服从均匀分布。它包括以当前值为中心点的均匀变异以及以搜索域中央为中心点的均匀变异。均匀变异提供一个 α 参数来调节变异的大小。α 确定了均匀变异的范围。

2.2) 高斯变异：

高斯变异是指变异的结果服从正态分布。它包括以当前值为中心点的高斯变异以及以搜索域中央为中心点的高斯变异。高斯变异提供一个 σ(正态分布的标准差) 来控制变异的大小。但它并不像均匀变异那样可以严格限制变异的范围，在大样本情况下，变异结果落在中心点附近长度为 α 的邻域的概率约为 68.27%；落在中心点附近长度为 3α 的邻域的概率约为 99.73%。

2.3) 多项式变异：

在多项式变异中，当前元素值以一定概率加上一个服从多项式概率分布的值得到一个邻近值，详见文献 [1]。

2.4) 差分变异：

差分变异操作将一个可缩放且随机选择的向量差分量加到基向量中。下面的式子展示了将三个不同且随机选择的向量结合以产生一个变异向量 vi,g：

其中 F 是缩放因子，值取正实数，一般取 (0,1] 之间的随机数，它可以控制种群的进化率。

r0 是基向量索引，它可以通过多种选择方式来确定 (详见前面的“选择”一节)。r0 一般是随机选取的且不同于目标向量索引 i 的索引。差分向量的索引 r1 和 r2 也彼此互不相同，并且它们也不同于基向量和目标向量的索引。下面是在一个 2 维决策空间中构造变异向量 vi,g 的示意图：

差分变异跟上面的变异算子有个很大的不同之处是它需要参照不止一个个体染色体来进行变异。这跟重组是极为相似的，因此有些流派直接称差分变异为一种交叉算子。本文档认为差分变异实质上是重组概率为1的三父体重组算法，因为若加上差分变异之后所需要进行的按概率和父代个体的交叉操作之后，整体上看就是一个完全意义上的重组算子了。正因为单是就差分变异而言，它不需要重组概率，因此仍将其归类为 “变异”。