《进化优化》第7章遗传规划

编程入门行业动态更新时间:2024-10-26 12:30:29

《进化优化》第7章遗传规划

文章目录

7.1 LISP: 遗传规划的语言
- Lisp程序的交叉
7.2 遗传规划的基础
- 7.2.1 适应度的度量
- 7.2.2 终止准则
- 7.2.3 终止集合
- 7.2.4 函数集合
- 7.2.5 初始化
- 7.2.6 遗传规划的参数
7.3 最短时间控制的遗传规划
7.4 遗传规划的膨胀
7.5 演化实体而非计算机程序
7.6 遗传规划的数学分析

遗传算法和进化算法存在局限：在表示候选解时要与假设的解的结构结合。

遗传规划试图将进化算法一般化成一个算法，这个算法不仅知道由具体结构给定的问题的最好解还能学习到最优的结构。

其他进化算法是对问题的解进行演化，而遗传规划却是针对求解问题的程序进行演化。

遗传规划的基本特征可以总结为三个基本原则：

首先,对计算机程序进行演化的遗传规划能提供求解各种问题的方法.许多工程问题可以用计算机程序、决策树,或网络体系的组织结构求解.
其次，遗传规划不会限制它的解，这与其他进化算法差不多;演化后的程序能自由呈现它的规模,形状以及最适合手头问题的结构.
第三,遗传规划利用归纳法演化计算机程序.这既是优点也是缺点.遗传规划不像人类那样凭借演绎和逻辑的方式构建程序.然而,某些问题并不适合演绎.如果我们想基于一组训练样本来编写计算机程序,采用标准的计算机编程技巧较难达到目的.而这正是遗传规划的运行方式,其他进化算法也是如此.遗传规划以归纳的方式构建最优的计算机程序.

7.1 LISP: 遗传规划的语言

提出问题：计算机程序的进化具有挑战性，因为程序的表示方式通常不能变异和交叉，要让计算机程序进化，需要克服的主要障碍正在于此。

Lisp程序代码用圆括号，函数名并紧跟着的函数自变量写成。例如下面的代码表示x加3：

（+ x 3)

因为数学运算符在输入的前面，这是前缀表示法的一个例子。Lisp的括号中的表达式也称为s-表达式，它是符号表达式的简称。所有的s-表达式都可以被视为函数计算的返回值。计算多个值的s-表达式返回计算得到的最后那个值。（+ x 3）不仅给x加上3，而且将x+3返回给下一个更高层的函数运算。

我们再多举几个例子.下面的代码计算(x＋3)的余弦:

(cos (+ x 3)).

下面的代码计算cos(x ＋3)和 z/14的最小值:

(min (cos (+ x 3))(/ z 14)).

下面的代码是:如果z >4,就将y的值复制给x

(if (>z 4) (setf x y)).

注意，在s-表达式中可以包含其他s-表达式，因此s-表达式有点像集合。在上面的s-表达式中，（> z 4)和（setf x y)都是更高一层(if (>z 4) (setf x y)) 中的一部分。

Lisp代码能够进化的原因在于s-表达式直接与树结构相对应，这个树结构也被称为语法树。例如，用Lisp计算xy + |z| 的一个s-表达式可以写成下面的形式:

(+ (* x y) (abs z)).

这个s-表达式可以用图7.1中的语法树来表示.我们用自底向上的方式来解释图7.1的语法树：

再看一个例子，考虑这样一个函数,当t>5时返回(x ＋y)，否则返回(x＋2＋z):

这个函数用Lisp的记号写成：

(if (> t 5)(+ x y)(+ x 2 z)).

对应的语法树：

Lisp程序的交叉

考虑下面的函数：

这两个函数的语法树如图所示：

随机选择进行交换：

再看另一个例子：

7.2 遗传规划的基础

7.2.1 适应度的度量

在算法7.1中，如何度量适应度?所有进化算法都需要确定这一点.不过,对于遗传规划而言这个决策更复杂.计算机程序需要在不同的输入、不同的初始条件以及不同的环境下都管用.例如,一个程序想找到省油的卫星轨道,它应该对不同的卫星参数以及不同的轨道都管用.所以,在确定一个计算机程序的适应度时,必须用到许多不同的条件.给定一个计算机程序,每一个计算机的输入集合和操作条件会返回它的“子适应度”.如何让这些子适应度结合从而得到计算机程序的单一的适应度度量?应该用平均性能?应该尝试最大化最差情况下的性能?还是应该用这两个性能的某个组合?这些问题自然就引出了多目标优化(第20章),不过,在遗传规划中没有必要采用多目标优化.

7.2.2 终止准则

算法7.1的终止准则是什么样的?所有进化算法都需要回答这个问题(参见8.2节),但对于遗传规划,它可能特别重要.因为在遗传规划中,适应度的度量对计算的要求通常比其他进化算法更高.终止准则能决定遗传规划是否成功.与其他进化算法一样,遗传规划的终止准则可以包括像迭代次数、适应度评价次数、运行时间、最佳适应度值、在几代中最佳适应度值的变化,或整个种群的适应度值的标准差等因素.

7.2.3 终止集合

终止集合描述在语法树的叶子上可以出现的符号，终止集合是演化中的计算机程序的所有可能输入的集合，这个集合包括输入计算机程序的变量。

在终止集合中可以采用随机数，不过，通常随机数生成以后不会改变，这种类型的随机数被称为临时随机常数。

在为遗传规划的应用定义终止集合时，需要掌握一个平衡，如果所用的集合过小，遗传规划就不能有效的解决问题，但是，如果所用的终止集合过大，遗传规划很难在合理的时间内找到一个很好的解。

7.2.4 函数集合

用于计算机程序演化的函数集合是什么样的？

函数集合中标准的数学运算(如,加、减、乘、除、绝对值).
函数集合中可以包含对于特定的优化问题很重要的与问题相关的具体函数(指数函数、对数函数、三角函数、滤波器、积分器、微分器).
在函数集合中可以包含条件测试(如,大于、小于、等于).
如果要用逻辑函数求解特定的优化问题,可以把它们放在函数集合中(如,arnand, or, xor, nor，not).
在函数集合中可以包含变量赋值函数.
在函数集合中可以包含循环语句(如,while循环、for循环).
如果我们为问题创建了一组预定义的函数,在函数集合中可以包含子程序调用.

在遗传规划中,因语法树的进化可能会没有合法的函数自变量,所以需要对某些函数做一点修正．例如,遗传规划可能会演化出s-表达式(/ x 0),它是被零除.这会导致Lisp出错,并因此使遗传规划终止.所以,在Lisp 中标准的除法运算符并不适用,为防止被零除我们可以定义另一个除法算子DIV,同时也防止在被很小的数除时出现的溢出:

7.2.5 初始化

应该如何生成计算机程序的初始种群？

完全法：由完全法生成的程序,其每一个终端节点到顶层节点的节点个数为用户指定的常数Dc.Dc被称为语法树的深度.举例来说,在图7.3中,父代1的深度为3,而父代2的深度为4.图7.3中的父代1是一个完全语法树,因为从每一个终端节点到顶层的加法节点都有3个节点.但父代2不是完全语法树因为它的一些程序分支的深度为4而其他分支的深度仅为3.
生长法：由生长法初始化生成的程序,其每一个终端节点到顶层节点的节点个数小于或等于Dc。.如果由随机初始化生成图7.3中的父代,则父代1可以由完全法或生长法生成,而父代2一定得由生长法生成,因为它不是一个完全语法树.生长法的实施方式可以与完全法的相同,但在生成深度小于Dc的随机节点时,可以生成函数或终端节点.如果生成的是函数节点,语法树会继续生长.与采用完全法一样,当达到最大深度Dc时就生成一个随机终端节点以完成语法树的分支.算法7.3说明采用生长法生成随机计算机程序的递归算法的思路.
对半生长法：对半生长法的初始种群一半用完全法生成,另一半用生长法生成.它还对深度介于2和Dc之间的每一个值,生成相同数量的语法树,其中Dc是用户指定的可允许的最大深度.算法7.4 说明采用对半生长法初始化语法树的思路.

通过对初始化的讨论,我们看到,在进化算法的初始种群中播下某些已经知道的好个体会有益处.这些好个体可能是用户生成的,或者来自别的优化算法,或者另有其他的来源．但播种并不一定能改善进化算法的性能.如果在初始种群中只有几个好个体,而其余的个体是随机生成的较差的个体,则这几个好个体会支配选择过程,差的个体很快会灭绝.这会让进化进入死胡同并过早收敛,这种现象也被称为“庸者生存”[Koza,1992,page 104].不过,这种坏事发生的概率取决于我们所用的选择方法(参见8.7节).如果用轮盘赌选择,选择压力会较大，适应性强的几个个体可能很快在种群中占据优势.如果采用锦标赛选择,选择压力就小得多,适应性强的几个个体支配种群的概率也相应降低.