第23章 进化规划
进化规划的个体不是采用遗传算法中的字符串表示，而是采用有序的序列表示。它在搜索迭代过程中，使用变异和选择两个算子，没有使用重组或交叉算子。变异是向进化规划中的群体加入新个体的唯一手段，因此设计变异算子要考虑勘探与开发之间的权衡问题。选择操作是采用父代与子代一同竞争的方式，与其他进化算法不同的是，它采用相对适应度进行竞争。标准进化规划使用进化算法的初始化、变异、评估和选择4个部分。本章介绍进化规划的原理及基本操作、实现步骤及流程。
23.1 进化规划的提出
进化规划（Evolutionary Programming，EP）是1962年由美国的Fogel应用模拟进化开发人工智能而提出的[72]，当时并没有引起足够的关注。直到30年后，其子D.B.Fogel对原有算法进行了改进和完善，才使进化规划作为一种进化算法得到广泛应用。自从1992年在美国召开第一届进化规划国际会议以来，每年都举行一次进化规划国际会议。
D. B. Fogel认为，智能可以看作“使得一个系统能够调整其行为，在一定环境中实现其期望目标的属性”。因此，进化规划中的适应度函数与其他进化算法不同，适应度函数是用相对于个体所处环境中该个体的行为误差来衡量的。
与遗传算法中个体的字符串表示不同，在进化规划群体中的个体用有序的序列表示。进化规划在搜索迭代过程中，使用了变异和选择两个算子，没有使用重组或交叉算子。
23.2 进化规划的原理及基本操作
标准进化规划使用进化算法的初始化、变异、评估和选择4个部分，具体说明如下。
1. 种群初始化
在标准进化规划中采用传统十进制实数表达问题，个体的表达形式为
其中，xi为旧个体目标变量X的第i分量；
为新个体目标变量X的第i分量；f（X）为旧个体X的适应度；Ni（0，1）为针对第i分量发生的服从标准正态分布的随机数。
根据上述的个体表达方式，种群初始化要先产生μ个个体，这就是突变。然后再从μ个旧个体和μ个新个体中根据适应度选出μ个个体组成新一代群体。
2. 适应度计算
由于进化规划采用十进制数表达问题，因此个体的适应度计算变得比较简单。
3. 变异算子
变异是向进化规划中的群体加入新个体的唯一手段，因此设计变异算子要考虑勘探（全局搜索）与开发（局部搜索）之间的权衡问题。进化规划也是采用随机搜索，其引入随机性的方法通常是将步长作为从一些概率分布取样得到的噪声函数来计算。
对于基本的进化规划突变操作为
其中，xi、
、Ni（0，1）表示的意义同式（23.1）；Φ（X）为旧个体X的适应度函数；ri为系数，常取0；βi为系数，常取1。
当ri=0，βi=1时，式（23.2）变为
从式（23.3）可以看出，变异是通过父代xi添加步长
来产生子代
，步长取决于一些概率分布取样得到的噪声与个体X的适应度之积。如果个体X的适应度f（X）很大，去直接乘Ni（0，1）会使
远离xi，致使在算法后期无法平稳收敛。故使用f（X）的平方根
或按比例缩小适应度的方法，这样就改写为Φ（X）的形式。当采用Φ（X）代替f（X）时，目标变量X的变动较剧烈，导致难以准确收敛，这是标准进化规划的缺陷。
为了克服标准进化规划变异算子的缺陷，已经开发出多种变异算子。例如，在动态进化规划中，变异算子步长的标准差以特定的个体适应度函数随时间改变；在自适应进化规划中，变异算子通过标准差的最优值和决策变量同步学习使得步长的方差自适应变化等。
从概率分布上考虑，提出了高斯分布、柯西分布、指数分布、混沌分布、勒威分布及组合分布等。
4. 选择算子
在进化规划中变异之后便执行选择操作来选择进入到下一代的个体，具体做法是采用父代与子代一同竞争的方式，与其他进化算法不同的是，它采用相对适应度进行竞争，而不是采用绝对适应度。相对适应度是指个体和一组从父代与子代随机选择的竞争者相比时表现的好坏程度。
进化规划的选择采用随机型的q-竞争选择法，具体选择过程如下。
为了确定某一个体i的优势，先从新群体和旧群体的2μ个个体中，随机取q个个体作为测试群体，再将个体i的适应度与q个个体的适应度分别进行对比，并记录个体i优于或等于q个测试个体的次数，作为个体i的得分Wi。重复上述步骤，直至2μ个个体都有得分W。选择得分大的前μ个个体作为新群体。通常选q大于10，可取q=0.9μ。上述根据得分选择出最优的μ个个体的方法，称为精英选择策略。
此外，根据个体的得分选择出μ个个体，还可使用锦标赛法、比例选择、非线性排序选择、中心选择法等。
23.3 进化规划的实现步骤及流程
进化规划的工作流程包括表达问题、产生初始群体、计算适应度、执行突变、选择操作、反复迭代，直到获得满意的结果。进化规划的具体实现步骤如下。
（1）确定问题的表达式。
（2）随机产生初始群体，并计算其适应度。
（3）执行变异算子和选择算子操作产生新群体。
①突变操作：对旧个体添加随机量，产生新个体。
②计算新个体的适应度。
③选择操作：挑选优良个体组成新群体。
（4）反复执行步骤（3），直至满足终止条件，选择最佳个体作为进化规划的最优解。
进化规划的流程如图23.1所示，其中Gen表示进化的代次。在第0代时，首先根据问题的表达式，随机产生初始群体，并计算其适应度。然后，进入正常迭代循环。在每次迭代中，执行变异操作，计算新个体的适应度。若新个体达到μ个后，从2μ个新、旧个体中择优选出μ个个体构成新一代群体。如此反复迭代，直到满足终止条件。
进化规划的终止条件可采用下述4个判据之一。
（1）最大进化代次数。
（2）最优个体与期望值的偏差。
（3）适应度的变化趋势。
（4）最优适应度与最差适应度之差。
图23.1 进化规划的流程图