演化策略中的变异与重组算子

20世纪60年代初，柏林工业大学的Rechenberg I和Schwefel H P等在进行风洞实验时，由于在设计中描述物体形状的参数难以用传统的方法进行优化，他们利用生物变异的思想来随机地改变参数值，并得到了很好的结果。随后他们便对这种方法进行了深入的研究和发展，形成了智能优化的另一个分支——演化策略。早期演化策略的种群中只包含1个个体，而且只用变异操作。在每一演化代，首先将种群中的个体进行变异，变异后的个体与其父体比较再选择两者之优。后来，Schwefel H P 在演化策略中引入了重组算子及个体数大于1的种群。

在演化策略中，通常使用固定长度的实数向量作为个体的表示，高斯变异是主要的遗传操作。高斯变异将表示父体的实数向量的每一个分量都加上一个由服从高斯分布的随机变量所产生的随机数以得到一个后代。图1-3说明了高斯变异的效果。

图1-3　高斯变异算子示意图

演化策略中的重组算子将两个父体向量的各个分量平均值作为后代向量的分量，如图1-4所示。

图1-4　重组算子示意图

算法1-3描述了一个典型的演化策略的基本结构。(www.xing528.com)

算法1-3 演化策略的基本结构

演化策略首先创建（通常是随机地）具有N 个个体的初始种群，在对种群中个体计算适应值后，从种群中随机地选择一些个体作为父体，父体的选择不依赖个体的适应值。在具有重组算子的演化策略中，从所选择的父体中，通过重组产生后代，所产生后代的数目大于N，并对所产生的后代进行变异。过程survive P（t）是确定性的，一般有两种方式实现过程survive P（t），一种是允许N 个最好的后代存活，并用这些后代形成下一代种群；另一种是允许后代和父体中的N 个最好的存活，并用存活的个体形成下一代种群。在演化策略中，变异算子是一种主要的遗传算子，重组算子只是起着辅助性的作用。演化策略主要用于优化问题。