规则能够进化吗？

在前面的两个例子中，程序的输入（01串或控制字串）在每次循环中会产生微小的随机变化，但程序本身并不变化。而进化算法的一个子类，遗传程序，则是让程序可以像输入一样进化。这样就可以像改善输入/输出一样改善算法。

完成一个任务所需的步骤可以用许多方式表示。遗传程序常用一种名为分析树的信息结构。分析树用树形结构表示操作之间的关系。图6.7给出了一个简单任务的解法的3种不同表示。任务是计算a和b两个变量的乘积然后加3。图中给出的每种表示可以用于不同的场合。公式很紧凑直观。算法是计算机可以执行的命令序列，而分析树则揭示了过程的逻辑结构。

图6.7 用公式、算法和分析树表示同样的逻辑操作

公式：

y=（a×b）+3

算法：

第1步输入变量a和b的值

第2步将a与b的值相乘

第3步将乘积加3

第4步打印y=“第3步得到的值”

第5步结束程序

分析树：

分析树有两种节点，终端节点（或叶节点）和操作节点。图中a、b和3是终端节点，*（乘）和+（加）则是操作节点。终端节点下面不连接任何节点。节点分层，并且最多与一个上层节点和两个下层节点相连。分析树的大小就是节点数量。有且仅有一个节点具有特殊性质，它没有上层节点，并且直接或间接与其他所有节点相连。这个特殊节点称为根节点。图6.7中根节点是+节点。

分析树自底向上解读。图6.7中的树包含3层，最底层包括终端节点a和b。它们连接到第2层的操作节点*。这个结构的意思是a与b相乘，结果放在*节点。第2层包括两个节点，*节点（现在包含的是a乘b的值）和终端节点3。它们连接到顶层的操作节点+。意思是3与*节点保存的值相加，结果放在+节点。由于没有比+更高的节点，+就是根节点，操作完成（答案放在+节点）。

所有公式和算法都可以表示为分析树，并且分析树可以通过维持一个分析树群体进行进化，随机改变节点和连接，然后选择分析树作为新分析树的“父母”。随机改变分析树的一个有效方法是选择节点然后删除节点下面连接的整个子树，将被删除的子树用随机创建的新子树替换。另一种方法是交换群体中两个成员的子树。图6.8展示了（生物）交换的分析树版本。

图6.8 分析树的交换。右上角树的子树“a+4”与左上角树的子树“b”交换，产生出下面的两棵新树

即使是相对简单的算法，如图6.3中那种，分析树也有很多节点，不方便绘制。但如果问题类型合适，并且巧妙应用，遗传程序就能进化出各种分析树，对庞大的算法空间进行探索，为一些极为困难的问题找到创造性答案。

很显然包括遗传程序在内的进化算法都是复杂引擎（图5.2）的具体实现。它们都涉及群体、突变和选择。在后面的几章中我们会看到一系列其他实现。但在此之前，我们先了解一下如何将进化过程可视化。