下载掌阅APP，畅读海量书库
立即打开
1.算法基本思想
演化策略（Evolution Strategy，ES）可用于在连续的搜索空间中搜索多元实值函数 f : R n → R 的最小值，由Rechenberg在1964年提出，并由Schwefel等人完善。它最初只是作为一种工具，在解析法难以解决问题时，用于对一系列实验的自动设计和分析，通过变量的逐步随机调整，使一个物体或系统不论环境噪声如何都进入最优状态，例如在风洞中尝试找到空气阻力最小的理想外形。
与遗传算法类似，演化策略也有选择算子、交叉算子、变异算子。但值得注意的是，演化策略的变异算子依靠的是对向量加上一个正态分布的随机向量，因此这个正态分布的相关参数在演化策略的搜索中起到了关键作用。由Fogel于1960年提出的进化规划（Evolutionary Programming，EP）在思想、流程和求解的问题方面都与演化策略有很多相似之处，但进化规划更为精简。与演化策略最突出的区别是，进化规划没有交叉的算子，直接经过选择和变异产生下一代种群。
2.算法流程
演化策略的变体一般以（ μ/ρ +， λ ）-ES的形式表示，其中 μ 是种群规模， ρ 是从种群中选择的父代个体的数量， λ 是生成的子代个体的数量。“+”或“，”代表使用的选择算子的种类，其中“+”表示子代种群从 μ + λ 个子代个体中选择，为了保持种群规模为 μ ，丢弃掉适应值较低的 λ 个个体，而“，”则表示子代种群完全从 λ 个子代个体中选择，不论好坏丢弃掉父代种群的 μ 个个体，隐含了 λ ≥ μ 的条件。最初的演化策略属于演化策略中最简单的形式，即（1+1）-ES（当 ρ =1时，可忽略 ρ ）。
演化策略流程图和伪代码如图1-6所示。
图1-6 演化策略的流程图和伪代码
第 t 次迭代的变异采样的实例示意图如图1-7所示，变异采用的正态分布可以写作
其中的3个参数含义和作用如下。
●
：均值向量，决定了分布的中心位置，控制变异的搜索区域，即图1-7中圆形区域的圆心对应的向量。
●
：变异强度，用于控制变异的步长，即图1-7中的圆形区域半径。
●
：协方差矩阵，即分布的形状，在算法中决定了变量间的依赖关系和变异的搜索方向之间的相对大小关系，对应于图1-7中的圆形区域的形状（在变量
x
1
和
x
2
的依赖关系不同，以及变异的搜索方向之间的相对大小关系不同时，该圆形区域可能具有不同的离心率、倾角）。
图1-7 二维搜索空间中的ES变异采样
对演化策略的重要改进之一在于自适应调整上述三个正态分布参数，尤其是变异强度和协方差矩阵。关于变异强度的自适应调整，Rechenberg在1973年提出过“1/5成功准则”（the 1/5 success rule），即如果超过1/5的变异都能成功改善解的目标函数值，则需要增大变异强度，否则减小变异强度。Hansen等人研究了协方差矩阵的自适应调整策略，提出演化策略的一种重要变体CMA-ES（Covariance Matrix Adaptation Evolution Strategy）。