1.1.3 进化规划

1966年，美国的L. J. Fogel等人[17]在研究人工智能的过程中，为求解预测问题而提出了一种有限状态机进化模型——进化规划（EP）。他认为，智能计算要具有两方面的能力，一方面是预测能力，另一方面是在一定目标指导下对环境做出合理响应的能力。他提出的思想与GA有很多相似之处，但GA更加注重父代与子代在遗传细节上的联系，而EP的侧重点在于父代与子代的表现行为上的进步。在这个进化模型中，这些机器的状态变换表通过在对应的离散、有界集上基于均匀随机分布的规律来修改。EP根据被正确预测的符号数来度量适应值。通过变异，父辈群体中的每个机器产生一个子代，父辈和子代中最好的那一半被选择而生存下来。1995年，L. J. Fogel与其儿子D. B.Fogel[18]在更进一步研究后，将EP拓展到求解实数空间中的优化问题，并在其变异操作中引入正态分布随机数，从而使EP成为一种全局优化搜索方法，并用于人工神经网络的结构学习，并在旅行商问题（Traveling Salesman Problem，TSP）中取得了比较成功的应用。个体的表示同ES，不同之处在于EP不用杂交算子，变异与选择方式也与ES不同。候选解的变异仍按式（1-2）进行，但标准差为：

式中，F(x)为适应度函数，βj、γj为特定参数，一般取为1和0。从式（1-3）可以看出，EP的标准差是根据适应度函数的大小来调整的。

EP模拟生物种群层次上的进化，在进化过程中主要强调生物种群行为上的联系，即强调种群层次上的行为进化而建立父、子代间的行为链，这意味着好的子代才有资格生存，而无论其父代如何，这样做适于选择子代。

EP算法的选择策略采用的是q竞争机制，这也是与ES算法最大的不同，q竞争可以在选择优质解的同时，以一定的随机概率接受少数较差的解。将n个父代进化的n个子代放在一起，从中随机选择不重复的q个个体组成一个组，然后依次对2n个个体与随机挑选出的群组的每个成员进行比较，相比为优的话，则对应的个体的分数加1，最后对分数进行排序，选择分数最高的n个个体。

EP对环境的适应性很强，对于很多不同的优化问题基本都能收敛至较为优秀的解。EP主要有以下几个有别于其他进化计算的显著优点。

（1）GA和ES都有染色体的重组操作，GA以重组为主要的搜索方法，更加注重个体的成长，而EP以变异作为唯一的搜索方法。众所周知，变异具有更强大的“勘探”能力，相对来说，EP更加注重整个群体的进化，与自然界中优胜劣汰的过程相对应。

（2）GA采取二进制编码，而EP采用实数编码，每个个体即代表待优化的一个解，省去了从二进制到十进制的译码过程，不会导致编码位上小的变化却给解带来很大的改变的情况。

（3）EP采用q竞争选择法，如果q选得比较小，则种群多样性比较好，但较差个体以较大概率进入下一代，可能导致收敛速度变慢；而若q选取过大，就成了确定性选择，较优个体全部进入下一代；若q选择得当，则既能兼顾种群多样性又能控制好收敛速度。

和其他进化算法一样，EP存在易陷入局部极值、早熟收敛的缺点。因为虽然EP比较注重种群的整体生长，与生物优胜劣汰的竞争原则大致符合，但是适应度值较大的优势个体以较大的概率进入下一次迭代，而适应度值较小的个体迅速减少，这样一来，随着迭代进化的发展，种群中的个体大多数都是适应度值较大的优势个体，如果这个过程处理不当，可能导致个体之间近亲繁殖使种群丧失多样性，如此将使后面的迭代意义不大，浪费计算量，也使搜索陷入局部优化。

若要增强种群多样性，可以增大种群大小，使个体尽可能地分散在可行域内，但加大种群无疑会付出计算量和算法运行时间成倍增加的代价；也可以增加变异幅度，使个体得以跳出局部极值点，但变异幅度增加会产生大量非法解，或者在迭代后期收敛速度变慢乃至于不收敛；还可以减小竞争选择法则中q的大小来保持种群多样性，但这样一来，每次迭代后，进入下一次迭代的优势个体较少，不能很好地指引种群成长，收敛速度就会相应减慢。