"进化策略和进化规划课件.pptx"
进化策略和进化规划是机器学习和函数优化领域中的两种重要方法，它们都源于自然进化过程的机制和结果。德国学者 Schwefel 和 Rechenburg 和美国学者 Fogel 分别提出进化策略 ES 和进化规划 EP，这三种方法具有共同的本质，分别强调了自然进化中的不同方面：遗传算法强调染色体的操作，进化策略强调了个体级的行为变化，而进化规划则强调种群级上的行为变化。
进化算法的早期研究可以追溯到 20 世纪 30 年代，通过仿真生物进化过程进行机器学习的研究。早在 1932 年， Cannon 就把自然进化想象为一个学习过程。在 1950 年， Turng 认识到，在机器学习和进化之间存在着明显的关系。1959 年， Friedman 推测，利用变异和选择的仿真可以设计“思想机器”，并且指出下棋的程序可以用这种方法设计。在 1960 年， Cambell 猜想：在导致知识扩张的所有过程中，都要涉及“盲目—变化—选择—幸存”的过程。
进化策略（Evolutionary Strategies）是在 1965 年由 Rechenburg 和 Schwefel 独立提出的。早期的进化策略的种群中只包含一个个体，并且只使用变异操作。在每一代中，变异后的个体与其父代进行比较，并选择较好的一个，这种选择策略被称为（1+1）策略。进化策略中的个体用传统的十进制实型数表示，即：Xt—— 第 t 代个体的数值，N(0,σ)—— 服从正态分布的随机数，其均值为零，标准差为 σ 。
进化策略的一般算法可以描述如下：
（1）问题为寻找实值 n 维矢量 x，使得函数 F(x):Rn→R 取极值。不失一般性，设此程序为极小化过程。
（2）从各维的可行范围内随机选取亲本 xi，i ＝ 1，…，p 的初始值。初始试验的分布一般是均匀分布。
（3）通过对于 x 的每个分量增加零均值和预先选定的标准差的高斯随机变量，从每个亲本 xi 产生子代 x’i。
（4）通过将误差 F(xi) 和 F(x’i)，i ＝ 1，…，p 进行排序，选择并决定哪些矢量保留。具有最小误差的 p 个矢量变成下一代的新亲本。
（5）进行新试验，选择具有最小方差的新子代，一直到获得充分解，或者直到满足某个终止条件。
在这个模型中，把试验解的分量看做个体的行为特性，而不是沿染色体排列的基因。可以和 GA 一样，假设这些表现型特征具有基因根源，但是它们之间的联系实质并没有被弄清楚，所以我们把着重点放在个体的行为特性上。假设不管发生什么遗传变换，所造成各个行为的变化均遵循零均值和某个标准差的高斯分布。由于基因多效性和多基因性，特定基因的改变可以影响许多表现型特征。所以在创造新子代时，较为合适的是同时改变亲本所有分量。
进化策略的最初试验采用上述算法，主要采用单亲本—单子代的搜索，即“（1+1）进化策略 ((1+1)-ES)”，其中单个子代是由单个亲本产生的，它们都被置于生存竞争中，较弱的一个要被挑选出来消去。当把这种算法用于函数优化时，发现它有两个缺点：（1）各维取定常的标准差使得程序收敛到最优解的速度很慢；（2）点到点搜索的脆弱本质使得程序在局部极值附近容易受停滞的影响（虽然此算法表明可以渐近地收敛到全局最优点）。
（μ + 1）-ES：早期的（1 十 1）-ES，没有体现群体的作用，只是单个个体在进化，具有明显的局限性。随后，Rechenberg 又提出（μ+1）-ES，在这种进化策略中，父代有 μ 个个体（μ ＞ 1），并且引入重组（Recombination）算子，使父代个体组合出新的个体。在执行重组时，从 μ 个父代个体中用随机的方法任选两个个体：然后从这两个个体中组合出如下新个体：式中 qi ＝ 1 或 2，它以相同的概率针对 i ＝ 1，2，…，n 随机选取。对重组产生的新个体执行突变操作，突变方式及 σ 的调整与（1+1）-ES 相同。将突变后的个体与父代 μ 个个体相比较，若优于父代最差个体，则代替后者成为下一代 μ 个个体新成员，否则，重新执行重组和突变产生另一新个体，（μ+1）-ES 和（1+1）-ES 具有相同的策略：只产生一个新个体。
