下载掌阅APP，畅读海量书库
立即打开
进化规划（Evolutionary Programming，EP）是进化计算的一个分支，起源于20世纪60年代，是通过模拟自然进化过程得到的一种随机搜索方法。在最初的发展中，进化规划并没有得到足够的重视。直到20世纪90年代，D.B.Fogel将进化规划思想拓展到实数空间，使其能够用来求解实数空间中的优化计算问题，并在变异运算中引入正态分布技术，从而使进化规划成为一种优化搜索算法，并作为进化计算的一个分支在实际领域中得到了广泛的应用。进化规划可应用于求解组合优化问题和复杂的非线性优化问题，它只要求所求问题是可计算的，使用范围比较广。
进化规划算法进化过程的基本流程如下：
种群初始化（随机分布个体）→变异（更新个体）→适应度计算（评价个体）→选择（群体更新）。
作为进化计算的一个重要分支，进化规划算法具有进化计算的一般流程。在进化规划中，不使用平均变异方法，而大多使用高斯变异算子，实现种群内个体的变异，保持种群中丰富的多样性。高斯变异算子根据个体适应度获得高斯变异的标准差，适应度差的个体变异范围大，扩大搜索的范围；适应度高的个体变异范围小，表明在当前位置处局部小范围的搜索，以实现变异操作。在选择操作上，进化规划算法采用父代与子代一同竞争的方式，采用锦标赛选择算子最终选择适应度较高的个体。
与其他进化计算相比，进化规划也有其自己的特点。虽然同为进化计算，都是对生物进化过程的模拟，但是在进化规划算法中，不使用交叉、重组之类体现个体之间相互作用的算子，而变异操作是最重要的操作。
进化规划算法的基本流程如下。
① 初始化种群，假设其种群规模为 N 。
② 进入迭代操作。
③ 通过高斯变异算子，生成 N 个新个体。
④ 计算父代与子代个体的适应度值。
⑤ 令父代与子代个体（共2 N 个）一同参加锦标赛选择，最后依据积分和排名选择较好的 N 个个体，组成下一代的种群。
⑥ 记录种群中的最优解。
⑦ 判断是否满足停止条件，如果是，则输出最优解，并退出；反之，则跳转到步骤③继续迭代。
进化规划算法的工作流程如图2-13所示。
图2-13 进化规划算法流程图
进化规划的基本思想是源于对自然界中生物进化过程的一种模仿，主要构成要素包括染色体构造、适应度评价、变异算子、选择算子、停止条件。其中，染色体构造、适应度评价和停止条件与遗传算法中的类似，这里不再赘述。
在进化规划算法中，变异操作是最重要的操作，也是唯一的搜索方法，这是进化规划的独特之处。在标准进化规划中，变异操作使用的是高斯变异（Gauss Mutation）算子。在变异过程中，计算每个个体适应度函数值的线性变换的平方根获得该个体变异的标准差 σ i ，将每个分量加上一个服从正态分布的随机数。
X 为染色体个体解的目标变量， σ 为高斯变异的标准差。每部分都有 L 个分量，即染色体的 L 个基因位。
染色体由目标变量 X 和标准差 σ 两部分组成，( X , σ )=(( x 1 , x 2 ,…, x L ), σ )。
形式如下：
X ( t +1)= X ( t )+ N (0, σ )
X 和 σ 之间的关系是：
式中，
F
(
X
(
t
))表示当前个体的适应度值，这里越是靠近目标解的个体适应度值越小；
N
(0,
σ
)是概率密度为
的高斯随机变量；系数
β
i
和
γ
i
是待定参数，一般将
β
和
γ
的值设为1和0。通过式（2-6）变量
X
的每一个分量就可以达到不同的变异效果。
在进化规划中，选择机制的作用是根据适应度函数值从父代和子代集合的2 N 个个体中选择 N 个较好的个体组成下一代种群，其形式化表示为 s ： I 2 N → I N 。选择操作是按照一种随机竞争的方式进行的。进化规划中选择算子主要有依概率选择、锦标赛选择和精英选择三种。锦标赛选择方法是进化规划中比较常用的方法。
基于锦标赛的选择操作的具体过程如下。
① 将 N 个父代个体组成的种群 P ( t )和 P ( t )经过一次变异运算后产生的 N 个子代个体组成的种群 P′ ( t )合并在一起，组成一个共含有2 N 个个体的集合 P ( t )∪ P′ ( t )，记为 I 。
② 对每个个体 x i ∈ I ，从 I 中随机选择 q 个个体，并将 q 个个体的适应度函数值 F j ( j ∈(1, 2, … , q ))与 x i 的适应度函数值相比较，计算出这 q 个个体中适应度函数值比 x i 的适应度差的个体的数目 w i ，并把 w i 作为 x i 的得分，其中 w i ∈(0,1,…, q )。
③在所有的2 N 个个体都经过了这个比较过程后，按每个个体的得分 w i 进行排序；选择 N 个具有最高得分的个体作为下一代种群。
这里要注意， q ≥1是选择算法的参数。为了使锦标赛选择算子更好地发挥作用，需要设定适当的用于比较的个体数 q 。 q 的取值较大时，偏向确定性选择，当 q =2 N 时，确定地从2 N 个个体中将适应度值较高的 N 个个体选出，容易带来早熟等弊端；相反， q 的取值较小时，偏向于随机性选择，使得适应度的控制能力下降，导致大量低适应度的个体被选出，造成种群退化。因此，为了既能保持种群的先进性，又可以避免确定性选择带来的早熟的弊端，需要依据具体问题，合适地选取 q 值。
从上面的选择操作过程可以知道，在进化过程中，每代种群中相对较好的个体被赋予了较大的得分，能够被保留到下一代的群体中。
进化规划以 D 维实数空间上的优化问题为主要处理对象，对生物进化过程的模拟主要着眼于物种的进化过程，主要的个体操作算子是变异算子，所以它不使用交叉算子等个体重组方面的操作算子。相比遗传算法，由于只使用变异算子，不用交叉算子，进化规划算法不注重个体之间的信息交互，而是着眼于依据自身信息进行的个体更新。所以，变异算子的选择显得尤为重要。对于平时使用的均匀变异算子在这里不能达到很好的效果，因为它属于完全随机的一种变异行为，没有考虑到自身信息，容易丧失优秀个体的先进性，不利于算法的快速收敛。所以，标准进化规划算法中常采用高斯变异算子，它是在个体的某个（或多个）基因位上加上一个服从高斯变异的随机数 N (0, σ i )，而其方差的确定与个体本身的适应度相关。在充分考虑到自身优劣性的信息后，高斯变异算子使得适应度较差的个体变异范围较大，而相对靠近全局最优解的优秀个体则采用较小的变异，保证其先进性。进化规划直接以问题的可行解作为个体的表现形式，无须再对个体进行编码处理，也无须再考虑随机扰动因素对个体的影响，更便于进化规划在实际中的应用。
在遗传算法中，选择算子的对象是父代经过交叉变异后生成的子代个体，在生成子代后，父代个体即被抛弃。由于是随机搜索的一类智能算法，通过交叉、变异后的个体，不可避免地会出现一些退化现象，而相对较为优秀的父代个体的信息将无法得到保留，这影响了算法的收敛。
相比遗传算法，进化规划算法将父代和子代一同加入选择，使得父代中的优秀个体也有可能得到保留，继续进化。而参与竞争个体的数目的合理设定，则平衡了选择的确定性与随机性，使得选择既能保留群体中的优秀信息，又能将一小部分适应度差的个体被选中，用来扩充种群的多样性。进化规划中的选择运算着重于群体中各个体之间的竞争选择，但当竞争数目 q 较大时，这种选择就类似于进化策略中的确定选择过程，而当竞争数目 q 较小时，这种选择又趋向于随机选择，难以保证群体的优化。
本节以图像中的物体聚类分析为例，介绍用进化规划算法解决聚类问题的仿生计算方法。与常规搜索算法相比较，进化规划在每次迭代过程中都保留一群候选解，从而有较大的机会摆脱局部极值点，可求得多个全局最优解；种群中的个体分别独立进化，不需要相互之间进行信息交换，具有并行处理特性，易于并行实现；在确定进化方案之后，算法将利用进化过程中得到的信息自行组织搜索；基于自然选择策略，优胜劣汰；具备根据环境的变化自动发现环境的特征和规律的能力，不需要事先描述问题的全部特征，可用来解决未知结构的复杂问题。也就是说，算法具有自组织、自适应、自学习等智能特性。除此之外，进化规划的优点还包括过程性、不确定性、非定向性、内在学习性、整体优化、稳健性等多个方面。
在进化规划中，采用符号编码，位串长度为 L ，搜索空间是一个 L 维空间，与此相对应，搜索点就是一个 L 维向量。算法中，组成进化群体的每个染色体 X 就直接用这个 L 维向量来表示。
例如，对于待聚类的样品图（见图2-14），图中每个个体包含一种分类方案。 L 取12位，基因代表样品所属的类号（1～4），基因位的序号代表样品的编号，基因位的序号是固定的，也就是说某个样品在染色体中的位置是固定的，而每个样品所属的类别随时在变化。如果基因位为 n ，则其对应第 n 个样品，而第 n 个基因位所指向的基因值代表第 n 个样品的归属类号。
图2-14 待聚类样品图
假设初始某个个体的染色体编码为（1，3，4，1，2，4，2，3，1，3，2，1），其含义为：第5、7、11个样品被分到第2类；第2、8、10个样品被分到第3类；第1、4、9、12个样品被分到第1类；第3、6个样品属于第4类。这时还处于假设分类情况，不是最优解，如表2-4所示。
表2-4 初始某个个体的染色体编码
函数Calfitness()的结果为适应度值m_pop( i ).fitness，代表每个个体优劣的程度。其计算过程类似于遗传算法一节中适应度值的计算方法。计算公式如下：
式中，centerNum为聚类类别总数，
n
i
为属于第
i
类的样品总数，
为属于第
i
类的第
j
个样品的特征值，
C
i
为第
i
个类中心，其计算公式为：
m_pop( i ).fitness越大，说明这种分类方法的误差越小，即其适应度值越大。
通过让每个子代个体的每一个分量newpop( i ).string(1, j )，加上一个服从 N (0, σ i )的正态分布随机数，以达到变异的效果，即
newpop( i ).string(1, j )=newpop( i ).string(1, j )+ N (0, σ i )
将父代m_pop与子代newpop组合在一起，成为totalpop，并从中任选 q 个个体组成测试群体，将测试个体的序号存在competitor中。然后将totalpop( i )的适应度与这 q 个测试个体的适应度进行比较，记录totalpop( i )优于或等于 q 内各个体的次数，得到totalpop( i )的得分score。
① 设置相关参数。
初始化初始种群中的个体个数popSize。从对话框得到用户输入的最大迭代次数MaxIter、聚类中心数centerNum，以及进行锦标赛竞争时用来进行比较的个体数 q 。
② 获得所有样品个数及特征。
③ 调用GenIniPop()函数，群体初始化。
④ 调用CalFitness()函数，计算每一个个体的适应度值m_pop( i ).fitness。
⑤ 生成下一代群体。
调用Mutation()函数，对所有个体，循环每一个基因位，对该位基因进行变异运算，按照高斯变异产生1～centerNum的一个数赋值给该位，生成子代群体。
⑥ 计算新生成的子代群体的适应度值。
⑦ 将父代与子代个体组成totalpop，并根据适应度值进行排序。
⑧ 调用Selection()函数，随机从totalpop中选择 q 个个体。循环每一个个体，让每个个体与这 q 个个体逐个进行适应度值的比较。以这 q 个个体中适应度值低于当前个体适应度值的个数作为当前个体的得分。最后选择评分最高的popSize个个体，作为下一代的父代。
⑨ 调用FindBW()函数保留精英个体，若新生成的子代群体中的最优个体适应度值低于总的最优个体适应度值（相互之间距离越近，适应度值越小），则用当前最好的个体替换总的最好的个体。
⑩ 若已经达到最大迭代次数，则进行下一步，退出循环；否则，返回第⑤步“生成下一代群体”继续运行。
⑪ 输出结果，返回给各个样品的类别号。
该算法的基本流程如图2-15所示。
图2-15 基于进化规划算法的聚类问题流程图
（1）初始化各个参数
其中，函数DisSelDlg()和InputClassDlg()用来由用户输入距离计算类型、类中心数、最大迭代次数、种群大小和进行锦标赛竞争时用来进行比较的个体数。
参数初始化效果如图2-16所示。
图2-16 参数设置对话框
（2）群体初始化
调用GenIniPop()函数初始化群体，随机生成全体群体的染色体值。
相关代码如下：
（3）变异算子
对所有个体，对染色体中的每一位进行变异运算，生成子代群体。
（4）评价群体
调用CalFitness()，计算每个个体的适应度值，这里以fitness值作为适应度值。
（5）排序
将父代与子代个体组合在一起，并根据适应度值排序。
（6）选择算子
执行锦标赛选择算子，从totalpop中选择popSize个个体，作为下一代的父代。具体过程是：从totalpop中随机选择 q 个个体，作为竞赛的比较个体，然后分别令totalpop中的每个个体与这 q 个个体进行适应度值的比较，如果某个个体totalpop( i )的适应度值高于一个竞赛个体，则其分数加1分。待每个个体都进行了这一过程以后，都会有自己的得分。这样，选择得分较高的popSize个个体，作为下一代的父代。
编程代码如下：
（7）寻找最优个体
（8）返回最优解
到达最大迭代次数后，输出最优个体的聚类情况。
分类结果与最优解出现的代数如图2-17所示。
图2-17 效果图