主题：【原创】和风满袖兄一篇：谈谈遗传规划 -- 好兵帅克

以达尔文进化思想为基础发展起来的一系列算法技术统称为进化算法（EA，evolutionary algorithms），包括遗传算法，进化策略，进化规划，遗传规划等，其中最典型和应用最广泛的是遗传算法。进化算法的基本原理是选择和改变，它区别于其他搜索（优化）方法有两个显著特征：首先这些算法都是基于种群（population）的；其次在种群中个体（individual）之间存在竞争。

进化计算的一般优点在于：1.采用编码技术表示对象（就是所求解的问题啦）的结构，对对象的数学描述形式要求不严格（连续、可微、单峰等），能够很方便用计算机程序实现；2.基于生物进化理论和自然选择策略实现自组织优化过程；3.通过种群搜索实现多区域并行进化，寻优效率高。

兄弟我感兴趣的是遗传规划（genetic programming）。自计算机出现以来，计算机科学的一个重要目标就是让计算机自动进行程序设计，即只要明确地告诉计算机要解决的问题，而不需要告诉它如何去做，遗传规划（Genetic Programming，GP）或者称为遗传编程就是在这一领域的尝试。遗传规划不象GA中将问题解编码成固定长度的二进制或十进制字符串，而是使用一种更为灵活的方式――分层结构来表示解空间，这些分层结构的叶节点是问题的原始变量，中间节点则是组合这些原始变量的函数。这样，GP就克服了在表示方式上的局限，能够对群体中独立的程序个体进行操作，自动生成解决问题的程序。

相对于GA，GP采用的是一种更为自然的表示方式，因此是一种应用领域更为广泛的遗传或进化搜索技术。日本ATR研究中心的H.de Garis甚至提出GP不仅可以演化计算机程序，而且可以演化任何复杂系统，直至人的大脑这么复杂的东东。

在经典的遗传规划中，染色体个体为包含函数集和终止符集的层次结构，其中函数集包括运算符号、数学函数、条件表达式等等，终止符集包括变量（如描述系统的输入、状态变量）、常数、无参函数等等。函数集和终止符集也可以是您自己针对问题定义的关系式和运算符，反正定义这些的目的就是要把研究的对象描述清楚。那怎么就算是描述清楚了呢？也就是说，函数集与终止符集的构造必须满足Koza所说的闭合性和充分性。闭合性确保GP中产生语法上正确的个体，即根据设定算子产生出来的个体对这个问题来说都必须是一个有意义的解。充分性就是说，问题的所有有意义的解都应该可以用所提供的终止符与函数的组和完全表示出来。

应用遗传规划解决问题时，应首先确定：①函数集；②终止符集；③适应度；④控制运行的参数（及变量）；⑤表明结果的方法和终止运行的准则。

（这段不感兴趣可以不看。）

在经典的GP算法中，初始群体（第0代）中的个体是随机生成的由给定的函数和终止符构成的程序组合，生长过程中可以限定树型结构叶节点的深度，当所有子节点为终止符时生长停止。遗传编程的基本操作包括复制、交叉、变异等。其中，复制操作即基于适应度随机地选择1个个体，将其拷贝到下一代群体中，个体的适应度越大，它被选中的概率越大。而交叉操作是从2个随机选取的父代个体中产生2个子代个体，2个交叉点分别在父代个体中随机选取。突变操作是随机选中父代个体上的突变点，该结点处的子树就被删除，而后应用类似于生成初始个体的生长方法生成新的子树。经过群体进化，最终确定一个个体程序作为遗传规划的运行结果。遗传规划传统上依照遗传算法思想设计遗传算子，用非定长层次结构反映求解问题的特征。

使用GP算法解决优化问题必须也只须具备两个前提：

1.该问题可以确定地判定解的优劣，即能够给出适应度准则；

2.问题的解必须能够能成功地用函数集与终止符集表示。

再拿GA和GP比较一下。如果GP的树状个体简化成为不分叉的一条链，链中所有的元素都是一位数，然后把链的长度固定下来，这就是GA中的染色体结构。可见，与GA的数值自组织优化过程相比，GP算法是一个更灵活的变结构自组织优化过程，问题的可行解是由遗传操作算子通过动态地改变个体结构和数值而获得的。这是多么flexible的一个东东啊。

在算法领域，GP的理想状态是，假如你给定一个计算目标，然后提供一堆足够的子程序、函数、过程什么的，它能够自己给你组合起来形成一个完整的程序实现这个目标，还是结构非常完美的一个程序。在路径规划这类问题上，已经有很多应用的结果了。也有很多paper把它叫做遗传编程的。一般的，我觉得在软件科学领域把它叫做遗传编程的比较多；在优化计算领域把它叫做遗传规划的比较多。我觉得叫遗传规划比较好听，而且听起来跟其它EA的关系比较密切一点。

可是它就那么好吗？那为什么大家都不怎么用呢？对于搜索问题来说，flexibility和complexity总是矛盾的。在GP应用过程中，如果函数集和终止符集的元素较多，搜索空间呈现组合膨胀，搜索时间过长，不能得到理想的结果。因此现在GP算法的收敛速度还是个大问题，不过这个问题归根到底还是可以在发展过程中解决的嘛，没见cpu越来越快，内存越来越大了吗？