1.1.2 进化策略

1964年，德国柏林工业大学的H. P. Schwefel[15]和I. Rechenberg[16]在研究流体动力学问题时，如弯管形状优化试验，按照自然突变和自然选择的生物进化思想提出了一种适合于实数变量的优化算法——进化策略（ES）。该算法优化能力主要依靠变异算子对物体的外形参数进行随机变化并尝试其效果，后来受GA的启迪，也引入了辅助的杂交算子。

ES的个体表示为Pi(x,σ)，i=1，2，…，n。其中，x=(x1,x2,…,xm)为群体中的一个候选实数解；σ=(σ1,σ2,…,σm)为候选解x变异时的正实数参数，称为“策略参数”；m为优化变量的个数，即优化空间的维数；n为群体规模。Schwefel引入了一种高斯变异算子，如果父代某个个体表示为Pk(x,σ)，1≤k≤n，由该个体变异后的子代个体表示为，其中，，。具体变异过程如下：

式中，α～N(0,1)，βj～N(0,1)，，τ是群体变异步长，τ′是个体变异步长。

从变异式（1-1）和式（1-2）可以看出，ES的变异主要是σ带有随机性的调整，τ和τ′是对调整起关键作用的两个参数，一般

这两个参数是固定不变的，因而实质上，新的候选解是以原来候选解加上一个服从高斯分布的随机变量变异产生的。

在ES中，目标参数和策略参数都需要编码到染色体中。目标参数是指直接涉及适应值计算的参数。策略参数即应用于进化算法中的控制参数，例如种群规模、突变步长、突变频率、交叉位置、交叉频率等。一般而言，策略参数的选取对进化算法的性能有着直接的影响。因此，人们希望策略参数和目标参数在进化的过程中可以同时得到优化，这就是“自适应”的由来。

ES可简单描述如下：

（1）确定问题：寻找n维实值向量x，使函数f(x)取极值。

（2）初始化种群：在各维的可行范围内，一般依据均匀分布随机选择父向量xi(i=1，2，…，n)作为初始群体。

（3）进化：对父向量的每个分量增加一个均值为0和预先选择标准差的高斯随机变量来产生子代向量。

（4）选择：对排序，选择和决定保留哪些向量作为下一代的父代。

（5）终止：重复进化和选择，直到找到符合条件的答案。

ES的实现形式有如下3种。

1. (1+1)-ES

原始的ES被称为(1+1)-ES，原因在于只考虑单个个体的进化，没有体现群体的作用，具有明显的局限性。每次迭代由1个父代个体进化到1个子代个体，并且进化操作只有随机突变一种方式，即利用随机变量修正旧个体。突变方式与进化规划是相似的。

在每次迭代中，对旧个体进行突变得到新个体后，计算新个体的适应度。如果新个体的适应度优于旧个体的适应度，则用新个体代替旧个体，否则不替换。

当把这种算法用于函数优化时，有两个缺点：各维取固定常数的标准差导致程序收敛到最优解的速度很慢，点到点搜索的脆弱本质使得程序在局部极值附近容易受停滞的影响。

2. (μ+1)-ES

随后提出的(μ+1)-ES进行了改进，不是在单个个体上进化，而是在μ个个体上进化，但每次进化所获得的新个体数仍然为1。同时增加了重组算子，用于从两个个体中组合出新个体。

在重组所获得的新个体上再执行突变操作。最后将突变后的个体与μ个父代个体中的最差个体进行比较，如果优于该最差个体，则取代它；否则重新执行重组和突变，产生另一个新个体。

尽管(μ+1)-ES没有得到广泛应用，但这是第一个基于种群的ES，常用于多处理机下的异步并行计算，并引入了交叉算子，把变异步长以内的参数（策略参数）形式作为个体基因的部分参与进化。

3. (μ+λ)-ES与(μ, λ)-ES

(μ+λ)-ES与(μ, λ)-ES都在μ个父代个体上执行重组和变异，产生λ个新个体。二者区别仅在于子代群体的选择上，其中，(μ+λ)-ES从μ个父代个体和λ个新个体的并集中再选择μ个子代个体；(μ，λ)-ES只在λ(>μ)个新个体中选择μ个子代个体。