进化策略的进展及优势

进化策略（Evolution Strategies，ES）是一类仿效自然界进化规律以解决参数优化问题的方法。它是20世纪60年代在德国发展起来的^[57，58]，当初主要用于试验流体动力学问题，如弯管形状优化^[59]。由于当时现有的优化算法不适于解决这类问题，Renchenberg提出按照自然突变和自然选择的生物进化思想，对物体的外形参数进行随机变化并尝试其结果。后来，Schwefel系统地推广了Renchenberg的二元进化策略[又称（1+1）-ES]，建立了多元进化策略，即（μ+λ）-ES和（μ，λ）-ES。早期的进化策略可以被看成使用浮点数表达，只使用变异作为其遗传算子的演化程序，它们已经应用于各种连续可变参数的优化问题。只是在近来，它们被扩展到各种问题上。进化策略的结构见表2-2。

表2-2 进化策略的算法过程

ES是最早引入自适应机制的算法^[60]。它与最广为人知的遗传算法相比，在编码、种群规模、交叉、变异和选择等方面有很多不同。

（1）编码 在进化策略中，目标参数和策略参数都需要编码到染色体中。目标参数是指直接涉及适应值计算的参数^[61]。策略参数即应用于进化算法中的控制参数，例如种群规模、突变步长、突变频率、交叉位置、交叉频率等。一般而言，策略参数的选取对进化算法的性能有着直接的影响。因此，人们希望策略参数和目标参数在进化的过程中可以同时得到优化，这就是“自适应”的由来。与经典遗传算法采用二进制编码不同，进化策略采用实数编码将目标变量直接编码到染色体中。它的另一个重要特征是将策略参数也编码到染色体中。一般来说，遗传算法的编码方式比进化策略有着更大的灵活性，这或许是遗传算法应用更为广泛的原因之一。(www.xing528.com)

（2）变异算子 与遗传算法不同，变异算子是进化策略的主要算子。在经典进化策略中，变异是通过给目标参数上加上一个服从正态分布的随机数来实现的。这一特别的变异机制使得ES能够进化本身的策略参数，在搜索的过程中，开发利用了适宜的内在模式和好的适应值之间的一个隐含的关联，由此所导致的根据适应值曲面的拓扑特性而使策略参数得到进化的机制，被称为自适应机制。

（3）交叉操作 交叉操作是提供两个不同个体之间交换信息的机制。与遗传算法不同，交叉算子在进化策略中并不是必需的。文献^[60]中介绍了四种交叉操作，在此不再赘述。通常来说，在一代群体中，所有的父代个体具有相同的交叉概率，即参加交叉的父代是通过均匀随机数来确定的。在离散交叉情况下，子代的成员向量的每一维都是随机继承某个父代，相当于遗传算法中交叉点数量可变的交叉算子。文献^[62]认为交叉操作可以有效地提高进化策略的性能，但是出于方便和效率方面的考虑，许多应用中均不采用交叉算子。

（4）选择方法ES中的选择方式是完全确定性的。（μ，λ）-ES是从λ个子代个体中选择μ个最好的个体作为下一代的父代；（μ+λ）-ES是从λ个子代个体和μ个父代中个体选择μ个最好的个体作为下一代的父代，即精英选择方法，从而保证了性能的改进是单调的，但是该选择方法无法适应变动的环境，不利于实施策略参数的自适应机制。因此，（μ，λ）-ES在今天更受到推崇。文献[60]认为，比率μ/λ≈1/7是最优的。