[科普中国]-进化策略

发展

进化策略的思想与进化规划的思想有很多相似之处，但它是在欧洲独立于遗传算法和进化规划而发展起来的。1963年，德国柏林技术大学的两名学生I．Rechenberg和H．P．Schwefel，利用流体工程研究所的风洞做实验，以便确定气流中物体的最优外形。由于当时存在的一些优化策略(如简单的梯度策略)不适于解决这类问题，Rechenberg提出按照自然突变相自然选择的生物进化思想，对物体的外形参数进行随机变化并尝试其效果，进化策略的思想便由此诞生。

当时，人们对这种随机策略无法接受，但他们仍坚持实验。1970年，Rechenberg完成了有关进化策略研究的博士论文并获得博士学位，现为仿生学与进化工程教授。1974年，Schwefel把有关进化策略研究的成果做了归纳整理，他现为计算机科学与系统分析教授。

1990年，在欧洲召开了第一届“基于自然思想的并行问题求解”(PPSN，Parallel ProblemSolving Nature)国际会议。此后，该会每两年举行一次，成为在欧洲召开的有关进化计算的主要国际会议。1

模型最简单形式的进化策略可描述如下：

(1)问题被定义为寻求与函数的极值相关联的实数n维矢量x，F(x)： —R。

(2)从每个可能的范围内随机选择父矢量的初始群体，初始试探的分布具有典型的一致性。

(3)父矢量Xi(i=1，…，P)通过加入一个零均方差的高斯随机变量以及预先选择X的标准偏差来产生子代矢量Xi‘。

(4)通过对误差F(Xi‘)(i=1，…，P)排序以选择和决定保持哪些矢量。哪些拥有最小误差的P矢量成为下一代的新的父代。

(5)产生新的试验数据以及选择最小误差矢量的过程将继续到找到符合条件的答案或者所有的计算已经全部完成为止。2

实现形式1．(1+1)一ES

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

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

2．(μ+1)——ES

(1+1)一ES没有体现群体的作用，具有明显的局限性。随后提出的(μ+1)——ES对其进行了改进，不是在单个个体上进化，而是在μ个个体上进化，但每次进化所获得的新个体数仍然为1。同时增加了重组算子，用于从两个个体中组合出新个体。

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

3．(μ+λ)一ES与(μ，λ)一ES

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

特点进化策略有以下独特之处。

(1)进化策略中的自然选择是按照确定方式进行的，有别于遗传算法和进化规划中的随机选择方式。

(2)进化策略中提供了重组算子，但进化策略中的重组不同于遗传算法中的交换。即它不是将个体的某一部分互换，而是使个体中的每一位发生结合，新个体中的每一位都包含有两个旧个体中的相应信息。3