第24章　进化策略

24.1　进化策略的提出

进化策略（Evolution Strategy，ES）是1963年由德国柏林技术大学Rechenberg提出的，目的是为了用优化算法解决风洞中的流体力学的实验优化问题^[74]。进化策略提出时，这种优化算法没有群体，只有一个个体，由该个体变异仅产生一个下一代的新个体，所以这样的优化算法被称为（1+1）-进化策略。后来被Schwefel进一步发展的进化策略（ES），称为基于“进化的进化”^[75]。

进化策略的每个个体的进化包括基因型特征的进化和控制基因型进化的策略参数的进化，这就是所谓“进化的进化”的含义。进化策略的变异个体只有在变异结果的适应度增加的条件下才能被接受。此外，可以有多余两个亲代来产生子代。

进化策略已应用于参数优化、控制设计、神经网络训练、计算机安全等领域。

24.2　进化策略的基本原理

1. （1+1）-进化策略

进化策略中的个体用传统的十进制实数表示为

X^t+1=X^t+N（0，σ）（24.1）

其中，X^t为第t代个体的数值；N（0，σ）为零均值、标准差为σ、正态分布的随机数。

进化策略中的个体也可以用包含两个变量的二元组（X，σ）来表示。从式（24.1）可以看出，新个体X^t+1是在旧个体X^t的基础上，添加一个独立随机变量N（0，σ）。如果新个体的适应度优于旧个体，则用新个体代替旧个体；否则放弃这个新个体，重新产生下一代新个体。

由于（1+1）-进化策略进化操作只使用变异一种形式，仅使用一个个体，难以提高个体的适应能力。因此这是一种最简单的进化策略。

2. （μ+1）-进化策略

为了克服（1+1）-进化策略单个个体存在的不足，Rechenberg又提出了（μ+1）-进化策略，被称为多元进化策略。在父代中有μ（＞1）个个体，又引入了重组算子，使用父代个体组合出新个体。重组操作是用随机方法从μ个父代个体中选出两个个体。然后利用这两个个体组合出新个体，再对该个体执行与（1+1）-进化策略相同的变异操作。

将变异操作后的个体与父代μ个个体进行对比，如果优于父代中最差的个体，则代替它后成为下一代μ个个体的新成员；否则重新执行重组和变异操作产生另一个新个体。

（μ+1）-进化策略与（1+1）-进化策略不同之处表现在两方面：一是采用包括μ个个体的群体；二是增加重组算子，便于从父代继承信息构成新个体。

3. （μ+λ）-ES及（μ，λ）-ES

1975年，Schwefel又相继提出了（μ+λ）-ES和（μ，λ）-ES。这两种进化策略都采用含有μ个个体的父代群体，并通过重组和突变产生λ个新个体。它们的差别仅在于下一代群体的组成上，（μ+λ）-ES是在原有μ个个体及新产生的λ个新个体中再择优选择μ个个体作为下一代群体。而（μ，λ）-ES是只在新产生的λ个新个体中再择优选择μ个个体作为下一代群体，这就要求λ＞μ。

由于（μ，λ）-ES使每个个体的寿命只有一代，更新进化很快，特别适合于目标函数有噪声干扰或优化程度明显受迭代次数影响的优化问题。因此，（μ，λ）-ES得到了广泛应用。

24.3　进化策略的基本操作

进化策略的基本操作包括问题表达、初始群体生成、适应度计算、重组操作、变异操作、选择操作、终止操作。

1. 问题表达

进化策略采用十进制实数表达问题，通常有二元、三元两种问题表达方式。

1）二元表达方式

个体由目标变量X和标准差σ二元组成，每个元又可由n个分量构成。具体形式可表示为

（X，σ）=（（x₁，x₂，…，x_i，…，x_n），（σ₁，σ₂，…，σ_i，…，σ_n））（24.2）

目标变量X和标准差σ满足

其中，（x_i，σ_i）为父代个体的第i分量；为子代新个体的第i分量；N（0，1）为服从正态分布的随机数；N_i（0，1）为针对第i分量重新产生一次正态分布的随机数；τ′为全局系数，一般取1；τ为局部系数，一般取1。

2）三元表达方式

在二元表达方式中再引入坐标旋转角度α作为第三个因子，这样个体的三元表达方式变为（X，σ，α），具体表示为

（X，σ，α）=（（x₁，x₂，…，x_i，…，x_n），（σ₁，σ₂，…，σ_i，…，σ_n），（α₁，α₂，…，α_j，…，α_m））（24.4）

个体（X，σ，α）中三者的关系为

其中，α_j为父代个体第i分量与第j分量之间坐标的旋转角度；为子代新个体第i分量与第j分量之间坐标的旋转角度；β为系数，常取0.01＜β＜0.1；z_i为取决于σ′和α′的正态分布随机数；其余符号同式（24.3）。

2. 初始群体生成

初始群体由μ个个体组成，每个个体（X，σ，α）可包含n个α_i、σ_i分量及n·（n-1）/2个α_j分量。初始群体用随机方法生成，可从可行域选择某一初始点（X（0），σ（0），α（0））出发，经过多次突变生成μ个初始个体。

初始个体的标准差σ（0）利用下式计算：

其中，ΔX为初始点到最优点的距离；n为个体所含分量的个数。由于ΔX在初始时不便确定，取σ（0）不宜太大，尽管如此，在进化过程中通过个体的自适应调整仍可使搜索点很快散布在可行域内。

3. 适应度计算

进化策略采用十进制实数表达问题，因此，比起遗传算法和进化规划，适应度计算变得更加直观、简便、容易。对于有约束条件的处理，主要采用重复试凑法。当新个体生成时，将其代入约束条件检验是否满足约束条件。若满足则接纳为新个体；否则，舍去该新个体。通过重组、突变再产生一个新个体。

4. 重组

进化策略的重组操作相当于遗传算法中的交叉。重组有以下3种方法。

（1）离散重组。先随机选择两个父代个体（X¹，σ¹）及（X²，σ²），再将其分量随机进行交换，构成子代新个体的各个分量，从而得到新个体（X，σ）。因为新个体的分量是从两个父代个体随机选取的，所以x_i的分量不一定等于σ_i的分量。

（2）中值重组。先随机选择两个父代个体，再将父代个体分量的平均值作为子代新个体的各个分量，从而得到新个体。这样，新个体的各个分量兼容两个父代个体的信息，但在中值重组中只含有某一个父代个体的因子。

（3）混杂重组。先随机选择一个固定的父代个体，然后对子代个体每个分量再从父代群体中随机选择第二个父代个体。这样，第二个父代个体是经常变化的。父代两个个体的组合可以用离散方式，也可以用中值方式，甚至可以把中值重组中的1/2改为［0，1］范围内的任一权值。

5. 突变

进化策略的突变是在旧个体基础上添加一个随机量，形成的新个体为

其中，τ、τ′分别为全局步长系数及局部步长系数，通常τ及τ′取1；β为涉及旋转角度的系数，一般β取5°。

按Schwefel的建议，上述系数可以这样计算：，，β=π×1/180≈0.0873，n为个体中含有分量的数目。

若取消旋转因子，进化策略突变的个体表达式由三元组变为二元组，即

若进一步简化，σ_i都相同时，最简单的突变的个体表达式变为

其中，。

进化策略在执行突变过程中，一方面要防止σ_i在进行过程中变为0致使x_i进化停止；另一方面要防止旋转角度α_j在可行域［-π，π］之外。为此，要经常检查σ_i及α_j是否符合规定，由此引入下述操作：

及

其中，ε_σ为大于0的一个小数。

6. 选择

进化策略中的选择有两种：一种是（μ+λ）选择；另一种是（μ，λ）选择。（μ+λ）选择是从μ个父代个体及λ个子代新个体中确定性地择优选择出μ个个体组成下一代新群体。（μ，λ）选择是从λ个子代新个体中确定性地择优选择μ个个体（要求λ＞μ）组成下一代群体。

实践表明，（μ，λ）-ES优于（μ+λ）-ES，已成为进化策略的主流。在（μ，λ）-ES中，为了控制群体的多样性和选择的力度，比值μ/λ是一个重要参数，它对算法的收敛速度影响很大。研究表明，μ/λ宜取1/7左右，若取μ=15，则宜取λ=100。

7. 终止

对于进化策略的终止条件，Schwefel提出用最优个体与最差个体之比来决定算法是否终止。只要最优适应度与最差适应度的差值或相对差小于允许值，就令算法终止。

24.4　进化策略的实现步骤及流程

进化策略的实现步骤如下。

（1）确定问题的表达方式。

（2）随机生成初始群体，并计算适应度。

（3）根据选定的进化策略，用下述操作产生新群体。

①重组。将两个父代个体变换目标变量和随机因子，产生新个体。

②突变。对重组后的新个体添加随机量，产生新个体。

③计算新个体的适应度。

④选择。根据选定的选择策略，挑选优良个体组成下一代新群体。

（4）反复执行步骤（3），直至达到终止条件，选择最佳个体作为进化策略的结果。

进化策略算法的流程如图24.1所示，其中Gen表示进化的代次，在第0代，根据问题确定采用二元组或三元组表达方式，随机产生μ个初始个体，并计算它们的适应度。然后依次执行重组和突变操作，产生新个体。j为新个体数目，重组和突变执行λ次，产生λ个新个体。计算新个体的适应度，再根据选择策略，从（μ+λ）个体或λ个新个体中选择μ个个体组成新群体。这样就完成了一代进化。重复这样的进化过程，直至满足终止条件。