其他进化算法(new)

《其他进化算法(new)》由会员分享，可在线阅读，更多相关《其他进化算法(new)（76页珍藏版）》请在金锄头文库上搜索。

1、5. 进化算法进化算法1）遗传算法（）遗传算法（Genetic Algorithm，GA），由），由John H. Holland教授等提出；教授等提出；2）进进化化规规划划（Evolutionary Programming, EP），由由Lawrence J. Fogel等人提出；等人提出；3）进进化化策策略略（Evolutionary Strategies, ES），由由Ingo Rechenberg和和Hans-Paul Schwefel提出。提出。4）遗遗传传规规划划（Genetic Programming，GP），由由John R. Koza教授提出。教授提出。5.1 进化策略进化策

2、略进化策略（进化策略（Evolutionary Strategies）是在是在1965年由年由Rechenburg和和Schwefel独立提出的。独立提出的。早期的进化策略的种群中只包含一个个体，并且只使用变异操作。早期的进化策略的种群中只包含一个个体，并且只使用变异操作。在每一代中，变异后的个体与其父代进行比较，并选择较好的一在每一代中，变异后的个体与其父代进行比较，并选择较好的一个，这种选择策略被称为个，这种选择策略被称为(1+1)-ES。进化策略中的个体用传统的十进制实型数表示，即：进化策略中的个体用传统的十进制实型数表示，即：Xt第第t代个体的数值，代个体的数值，N(0,)服从正态分布

3、的随机数，其均值为零，标准差为服从正态分布的随机数，其均值为零，标准差为。5.1 进化策略进化策略在这个模型中，把解的分量看做个体的行为特性，而不是在这个模型中，把解的分量看做个体的行为特性，而不是沿染色体排列的基因。可以和沿染色体排列的基因。可以和GA一样，假设这些表现型特一样，假设这些表现型特征具有基因根源，但是它们之间的联系实质并没有被弄清征具有基因根源，但是它们之间的联系实质并没有被弄清楚，所以我们把着重点放在个体的行为特性上。楚，所以我们把着重点放在个体的行为特性上。假设不管发生什么遗传变换，所造成各个行为的变化均遵假设不管发生什么遗传变换，所造成各个行为的变化均遵循零均值和某个标准

4、差的高斯分布。循零均值和某个标准差的高斯分布。由于基因多效性和多基因性，特定基因的改变可以影响许由于基因多效性和多基因性，特定基因的改变可以影响许多表现型特征。所以在创造新子代时，较为合适的是同时多表现型特征。所以在创造新子代时，较为合适的是同时改变亲本所有分量。改变亲本所有分量。5.1 进化策略进化策略早期进化策略采用上述算法，主要采用单亲本早期进化策略采用上述算法，主要采用单亲本单子代的单子代的搜索，即搜索，即“（1+1）进化策略进化策略(1+1)-ES)”，其中单个子其中单个子代是由单个亲本产生的，它们都被置于生存竞争中，较弱代是由单个亲本产生的，它们都被置于生存竞争中，较弱的一个要被挑

5、选出来消去。的一个要被挑选出来消去。当把这种算法用于函数优化时，发现它有两个缺点：当把这种算法用于函数优化时，发现它有两个缺点：(1)各维取定常的标准差使得程序收敛到最优解的速度很慢；各维取定常的标准差使得程序收敛到最优解的速度很慢；(2)点到点搜索的脆弱本质使得程序在局部极值附近容易受停点到点搜索的脆弱本质使得程序在局部极值附近容易受停滞的影响（虽然此算法表明可以渐近地收敛到全局最优点）。滞的影响（虽然此算法表明可以渐近地收敛到全局最优点）。5.1 进化策略进化策略( + 1)-ES:早期的早期的(1十十1)-ES，没有体现群体的作用，只是单个个体在没有体现群体的作用，只是单个个体在进化，具

6、有明显的局限性。随后，进化，具有明显的局限性。随后，Rechenberg又提出又提出(+1)-ES，在这种进化策略中，父代有在这种进化策略中，父代有个个体个个体(1)，并且引入重组并且引入重组(Recombination)算子，使父代个体组合出新算子，使父代个体组合出新的个体。在执行重组时，从的个体。在执行重组时，从个父代个体中用随机的方法任个父代个体中用随机的方法任选两个个体：选两个个体：5.1 进化策略进化策略然后从这两个个体中组合出如下新个体：然后从这两个个体中组合出如下新个体：式中式中qi1或或2，它以相同的概率针对，它以相同的概率针对i1，2，n随机选取。随机选取。对重组产生的新个体

7、执行突变操作，突变方式及对重组产生的新个体执行突变操作，突变方式及的调整与的调整与(1+1)-ES相同。相同。将突变后的个体与父代将突变后的个体与父代个个体相比较，若优于父代最差个体，个个体相比较，若优于父代最差个体，则代替后者成为下一代则代替后者成为下一代个个体新成员，否则，重新执行重个个体新成员，否则，重新执行重组和突变产生另一新个体，组和突变产生另一新个体，5.1 进化策略进化策略(+1)-ES和和(1+1)-ES具有相同的策略：只产生一个新个体。具有相同的策略：只产生一个新个体。(+1)-ES的特点在于：的特点在于： (1) 采用群体，其中包含采用群体，其中包含个个体；个个体； (2)

8、 增添重组算子，它相当于遗传算法中的交叉算子，从父增添重组算子，它相当于遗传算法中的交叉算子，从父代继承信息构成新个体。代继承信息构成新个体。显然，显然，(+1)-ES比比(1+1)-ES有了明显的改进，为进化策略这有了明显的改进，为进化策略这种新的进化算法奠定良好的基础。种新的进化算法奠定良好的基础。5.1 进化策略进化策略在在1973年，年，Rechenburg把该算法的把该算法的期望收敛速度期望收敛速度定义为定义为对对最优点的平均距离与要得到此改善所需要的试验次数之比最优点的平均距离与要得到此改善所需要的试验次数之比。1981年，年，Schwefel在进化策略中使用多重亲本和子代，这是在

9、进化策略中使用多重亲本和子代，这是Rechenburg早期工作（使用多重亲本，但是仅使用单个子早期工作（使用多重亲本，但是仅使用单个子代）的发展，后来考察了两种方法，分别表示为代）的发展，后来考察了两种方法，分别表示为(+)-ES和和(，)-ES。在前者中，在前者中，个亲本制造个亲本制造个子代，所有个子代，所有解均参加生存竞争，选出最好的解均参加生存竞争，选出最好的个作为下一代的亲本。在个作为下一代的亲本。在后者中，只有后者中，只有（ ）个子代参加生存竞争，在每代中个子代参加生存竞争，在每代中个亲本被完全取代。个亲本被完全取代。5.1 进化策略进化策略Rechenburg引入了如下想法，在每个

10、新样本的特征分布中附加了引入了如下想法，在每个新样本的特征分布中附加了一个一个自适应参数自适应参数。在这个方法中，每个解矢量不仅包括了。在这个方法中，每个解矢量不仅包括了n维试维试验矢量验矢量x，而且还包括了扰动矢量而且还包括了扰动矢量，后者给出如何变异后者给出如何变异x以及它以及它本身如何变异的指令。例如，设本身如何变异的指令。例如，设x为当前矢量，为当前矢量， 为对应于为对应于x每个每个维的方差矢量维的方差矢量，于是新的解矢量于是新的解矢量x， 可以这样产生：可以这样产生：N(0,1)表示单个标准高斯随机变量，表示单个标准高斯随机变量， Ni(0,1)表示第表示第i个独立相同个独立相同的标

11、准高斯分布，的标准高斯分布，和和是影响总体和个体步长的算子集参数。以是影响总体和个体步长的算子集参数。以这种方式，进化策略可以在线地适应误差曲面的宽度，并且更恰这种方式，进化策略可以在线地适应误差曲面的宽度，并且更恰当地分配实验次数。当地分配实验次数。进化策略的基本技术进化策略的基本技术问题的表达：问题的表达：为了与突变操作相适应，进化策略有两种表达方式。为了与突变操作相适应，进化策略有两种表达方式。(1) 二元表达方式二元表达方式。这种表达方式中个体由目标变量。这种表达方式中个体由目标变量X和标准差和标准差两两部分组成，每部分又可以有部分组成，每部分又可以有n个分量，即：个分量，即：X和和的

12、的关系为关系为:为全局系数，常取为全局系数，常取1。进化策略的基本技术进化策略的基本技术(2) 三元表达方式三元表达方式。为了改善进化策略的收敛速度，。为了改善进化策略的收敛速度，Schwefel在二元在二元表达的基础上引入第三个因子表达的基础上引入第三个因子坐标旋转角度坐标旋转角度。个体的描述个体的描述扩展为扩展为(X, , )，即：即：三者的关系为：三者的关系为：i父代个体父代个体i分量与分量与j分量间坐标的旋转角度；分量间坐标的旋转角度；j子代新个体子代新个体i分量与分量与j分量间坐标的旋转角度；分量间坐标的旋转角度；系数，常取系数，常取0.0873；zi取决于取决于及及的正态分布随机数

13、。的正态分布随机数。进化策略的基本技术进化策略的基本技术旋转角度旋转角度i表面上是分量表面上是分量i与与j间坐标的旋转角度，实质上它是间坐标的旋转角度，实质上它是分量分量i与分量与分量j之间协方差的体现。之间协方差的体现。重组重组进化策略中的重组进化策略中的重组(Recombination)算子相当于遗传算法的交算子相当于遗传算法的交叉，它们都是以两个父代个体为基础进行信息交换。进化叉，它们都是以两个父代个体为基础进行信息交换。进化策略中，重组方式主要有三种：策略中，重组方式主要有三种：(1)离散重组离散重组。先随机选择两个父代个体。先随机选择两个父代个体进化策略的基本技术进化策略的基本技术然

14、后将其分量进行随机交换，构成子代新个体的各个分量，从而得然后将其分量进行随机交换，构成子代新个体的各个分量，从而得出如下新个体：出如下新个体：(2) 中值重组中值重组。这种重组方式也是先随机选择两个父代个体，然后将。这种重组方式也是先随机选择两个父代个体，然后将父代个体各分量的平均值作为子代新个体的分量，构成的新个体父代个体各分量的平均值作为子代新个体的分量，构成的新个体为：为：这时，新个体的各个分量兼容两个父代个体信息，而在离散重组中这时，新个体的各个分量兼容两个父代个体信息，而在离散重组中则只含有某一个父代个体的因子。则只含有某一个父代个体的因子。进化策略的基本技术进化策略的基本技术(3)

15、混杂混杂(Panmictic)重组重组。这种重组方式的特点在于父代个体。这种重组方式的特点在于父代个体的选择上。混杂重组时先随机选择一个固定的父代个体，的选择上。混杂重组时先随机选择一个固定的父代个体，然后针对子代个体每个分量再从父代群体中随机选择第二然后针对子代个体每个分量再从父代群体中随机选择第二个父代个体。也就是说，第二个父代个体是经常变化的。个父代个体。也就是说，第二个父代个体是经常变化的。至于父代两个个体的组合方式，既可以采用离散方式，也至于父代两个个体的组合方式，既可以采用离散方式，也可以来用中值方式，甚至可以把中值重组中的可以来用中值方式，甚至可以把中值重组中的1/2改为改为0,

16、1之间的任一权值。之间的任一权值。研究表明，进化策略采用重组后，明显增加算法的收敛速度。研究表明，进化策略采用重组后，明显增加算法的收敛速度。Schwefel建议，对于目标变量建议，对于目标变量X宜用离散重组，对于策略因子宜用离散重组，对于策略因子及及宜用中值重组或混杂中值重组。宜用中值重组或混杂中值重组。进化策略的基本技术进化策略的基本技术选择：选择：进化策略的选择有两种：一为进化策略的选择有两种：一为(+)选择，另一为选择，另一为(, )选选择。择。(+)选择是从选择是从个父代个体及个父代个体及个子代新个体中确定个子代新个体中确定性地择优选出性地择优选出个个体组成下一代新群体。个个体组成下

17、一代新群体。(, )选择是从选择是从个子代新个体中确定性地择优桃选个子代新个体中确定性地择优桃选个个体个个体(要求要求)组组成下一代群体，每个个体只存活一代，随即被新个体顶替。成下一代群体，每个个体只存活一代，随即被新个体顶替。粗略地看，似乎粗略地看，似乎(+)选择最好，它可以保证最优个体存选择最好，它可以保证最优个体存活，使群体的进化过程呈单调上升趋势。但是，深入分析活，使群体的进化过程呈单调上升趋势。但是，深入分析后发现后发现(+)选择具有下述缺点：选择具有下述缺点：进化策略的基本技术进化策略的基本技术(1) (+)选择保留旧个体，它有时会是过时的可行解，妨碍算法选择保留旧个体，它有时会是

18、过时的可行解，妨碍算法向最优方向发展。向最优方向发展。(，)选择全部舍弃旧个体，使算法始终从新选择全部舍弃旧个体，使算法始终从新的基础上全方位进化。的基础上全方位进化。(2) (+)选择保留旧个体，有时是局部最优解，从而误导进化策选择保留旧个体，有时是局部最优解，从而误导进化策略收敛于次优解而不是最优解。略收敛于次优解而不是最优解。(，)选择舍弃旧的优良个体，选择舍弃旧的优良个体，容易进化至全局员优解。容易进化至全局员优解。(3) (+)选择在保留旧个体的同时，也将进化参数选择在保留旧个体的同时，也将进化参数保留下来，不保留下来，不利于进化策略中的自适应调整机制。利于进化策略中的自适应调整机制

19、。(，)选择则恰恰相反，可选择则恰恰相反，可促进这种自适应调整。促进这种自适应调整。 实践也证明，实践也证明，(, )-ES优于优于(+)-ES，前者已成为当前进化前者已成为当前进化策略的主流。策略的主流。进化策略的基本技术进化策略的基本技术在在(,)-ES中，为了控制群体的多样性和选择的力度，比中，为了控制群体的多样性和选择的力度，比值值/是是一个重要参数，它对算法的收敛速度有很大影响。一个重要参数，它对算法的收敛速度有很大影响。一方面，一方面， 不能太小，否则群体太单调不能太小，否则群体太单调(例如例如1的极端情的极端情况况)；另一方面，；另一方面， 也不能太大，否则计算工作量过大。通也不

20、能太大，否则计算工作量过大。通常，常， 取取15或更多一些。或更多一些。 数值的大小，类似于数值的大小，类似于的作用，的作用，也要适当。某些研究表明比值也要适当。某些研究表明比值/宜取宜取1/7左右。也就是说，左右。也就是说，若若=15，则，则宜取宜取100。5.2 进化规划进化规划进化规划进化规划(Evolutionary Programming)由由Fogel在在20世纪世纪60年代所提出。年代所提出。Fogel将仿真进化方法用于由相互竞争的算法将仿真进化方法用于由相互竞争的算法所构成的种群，在一系列研究中探索了进化规划的可能性，所构成的种群，在一系列研究中探索了进化规划的可能性，目的是发

21、展人工智能。目的是发展人工智能。Fogel认为，智能行为需要有如下的认为，智能行为需要有如下的复合能力：复合能力： (1)预测它的环境；预测它的环境； (2)把预测变成对于给定目标的适当响应。把预测变成对于给定目标的适当响应。5.2 进化规划进化规划标准进化规划标准进化规划进化规划用传统的十进制实数表达问题。在标准进化规划进化规划用传统的十进制实数表达问题。在标准进化规划（Standard EP）中，个体的表达形式为：中，个体的表达形式为：式中：式中：xi旧个体目标变量旧个体目标变量X的第的第i个分量，个分量， xi新个体目标变量新个体目标变量X的第的第i个分量，个分量， f(X)旧个体旧个体

22、X的适应度；的适应度； N(0, 1)针对第针对第i分量发生的随机数，它服从标准正态分布。分量发生的随机数，它服从标准正态分布。5.2 进化规划进化规划上式表明，新个体是在旧个体的基础上添加一个随机数，上式表明，新个体是在旧个体的基础上添加一个随机数，添加值的大小与个体的适应度有关：适应度大的个体添加添加值的大小与个体的适应度有关：适应度大的个体添加值也大，反之亦然。值也大，反之亦然。根据这种表达方式，进化规划首先由根据这种表达方式，进化规划首先由个旧个体产生个旧个体产生个新个新个体。接着从个体。接着从个旧个体及个旧个体及个新个体个新个体(2 个个体个个体)中根据适中根据适应度挑选出应度挑选出

23、个个体组成新群体。如此反复迭代，直至得到个个体组成新群体。如此反复迭代，直至得到满意结果。满意结果。进化规划没有重组或交换这类算子，它的进化主要依赖突进化规划没有重组或交换这类算子，它的进化主要依赖突变。在标准进化规划中这种突变十分简单，它只需参照个变。在标准进化规划中这种突变十分简单，它只需参照个体适应度添加一个随机数。很明显，标准进化规划在进化体适应度添加一个随机数。很明显，标准进化规划在进化过程中的自适应调整功能主要依靠适应度过程中的自适应调整功能主要依靠适应度f(X)来实现。来实现。5.2 进化规划进化规划Standard EP流程：流程：1.生成初始群体；生成初始群体；2.While

24、 Not-End Do1)突变；突变；2)计算个体适应度；计算个体适应度；3)选择产生新群体；选择产生新群体；( ) = 3.End While5.2 进化规划进化规划元进化规划元进化规划为了增加进化规划在进化过程中的自适应调整功能，人们在突变中为了增加进化规划在进化过程中的自适应调整功能，人们在突变中添加方差的概念。类似于进化策略，在进化规划中个体的表达采添加方差的概念。类似于进化策略，在进化规划中个体的表达采用下述方式：用下述方式：式中：式中：i旧个体第旧个体第 i 分量的标准差；分量的标准差； i新个体第新个体第 i 分量的标准差；分量的标准差； N(0, 1)针对第针对第i分量发生的随

25、机数，它服从标准正态分布。分量发生的随机数，它服从标准正态分布。5.2 进化规划进化规划从上式可以看出，新个体也是在旧个体的基础上添加一个随机数，从上式可以看出，新个体也是在旧个体的基础上添加一个随机数，该添加量取决于个体的方差，而方差在每次进化中又有自适应调该添加量取决于个体的方差，而方差在每次进化中又有自适应调整。这种进化方式已成为进化规划的主要手段，因此在进化规划整。这种进化方式已成为进化规划的主要手段，因此在进化规划前冠以前冠以“元元”这个术语以表示它为基本方法。这个术语以表示它为基本方法。元进化规划元进化规划(Meta EP)的突变尽管类似于进化策略，但是它们有下述的突变尽管类似于进

26、化策略，但是它们有下述差别差别:(1)执行顺序不同。进化规划中首先计算新个体的目标变量执行顺序不同。进化规划中首先计算新个体的目标变量xi ，计计算中沿用旧个体的标准差算中沿用旧个体的标准差i ；其次才计算新个体的标准差其次才计算新个体的标准差i ，新的标准差留待下次进化时才用。与之相反，进化策略是先调整新的标准差留待下次进化时才用。与之相反，进化策略是先调整标准差标准差，然后再用新的标准差然后再用新的标准差去更改个体的目标变量去更改个体的目标变量X。(2)计算式的不同。进化规划的计算式比进化策略的计算式简单。计算式的不同。进化规划的计算式比进化策略的计算式简单。5.2 进化规划进化规划旋转进

27、化规划旋转进化规划旋转进化规划旋转进化规划(Rmeta EP)进一步扩展进化规划，在表达个体时添加第三个因进一步扩展进化规划，在表达个体时添加第三个因子子协方差，用三元组表示个体，即协方差，用三元组表示个体，即(X, , )，具体计算如下：具体计算如下：X旧个体的目标变量，其内含旧个体的目标变量，其内含n个分量；个分量；X新个体的目标变量，其内含新个体的目标变量，其内含n个分量；个分量；N(0,C)遵从正态分布的随机数，其数学期望为遵从正态分布的随机数，其数学期望为0、其标准差与协方差有其标准差与协方差有关；关；j相关系数，相关系数，进化规划的基本技术进化规划的基本技术表达方法表达方法采用十进

28、制的实型数表达问题。采用十进制的实型数表达问题。X=(x1, x2, , xi, , xn)由由X和和组成的二元组组成的二元组(X, )是进化规划最常用的表达形式。有是进化规划最常用的表达形式。有人建议将进化规划再增加一个控制因子人建议将进化规划再增加一个控制因子 ，构成三元表达式构成三元表达式(X, , )，其中其中 =(1, 2, , j, , n)j是相关系数的是相关系数的单下下标表达表达, 它表示它表示xi和和xj 之之间的的协方差方差:进化规划的基本技术进化规划的基本技术产生初始群体产生初始群体进化规划中产生初始群体的方法类似于进化策略中随机选择进化规划中产生初始群体的方法类似于进化

29、策略中随机选择个个体作为进化计算的出发点。个个体作为进化计算的出发点。计算适应度计算适应度进化规划采用十进制实数表达问题，计算适应度比较简单直观。进化规划采用十进制实数表达问题，计算适应度比较简单直观。突变突变突变是进化规划产生新群体的唯一方法，它不采用重组或交换突变是进化规划产生新群体的唯一方法，它不采用重组或交换算子。算子。进化规划的基本技术进化规划的基本技术选择选择在进化规划中，新群体的个体数目在进化规划中，新群体的个体数目等于旧群体的个体数目等于旧群体的个体数目，选择便是在选择便是在2 个个体中选择个个体中选择个个体组成新群体。个个体组成新群体。进化规划的选择采用随机型的进化规划的选择

30、采用随机型的q竞争选择法。在这种选择方竞争选择法。在这种选择方法中，为了确定某一个体法中，为了确定某一个体 i 的优劣，我们从新、旧群体的的优劣，我们从新、旧群体的2 个个体中任选个个体中任选q个个体组成测试群体。然后将个体个个体组成测试群体。然后将个体 i 的适应的适应度与度与q个个体的适应度进行比较，记录个体个个体的适应度进行比较，记录个体 i 优于或等于优于或等于q内内各个体的次数，得到个体各个体的次数，得到个体 i 的得分的得分Wi，即，即进化规划的基本技术进化规划的基本技术上述得分测试分别对上述得分测试分别对2个个体进行，每次测试时重新选择个个体进行，每次测试时重新选择q个个体组个个

31、体组成新的测试群体。最后，按个体的得分选择分值高的成新的测试群体。最后，按个体的得分选择分值高的个个体组个个体组成下一代新群体。成下一代新群体。q竞争选择法是一种随机选择，总体上讲，优良个体入选的可能性竞争选择法是一种随机选择，总体上讲，优良个体入选的可能性较大。但是由于测试群体较大。但是由于测试群体q每次都是随机选择的，当每次都是随机选择的，当q个个体都不个个体都不甚好时，有可能使较差的个体因得分高而入选。这正是随机选择甚好时，有可能使较差的个体因得分高而入选。这正是随机选择的本意。的本意。q竞争选择法中竞争选择法中q的大小是一个重要参数。若的大小是一个重要参数。若q很大，极端地设很大，极端

32、地设q2，则选择变为确定性选择。反之，若则选择变为确定性选择。反之，若q很小，则选择的随机性很小，则选择的随机性太大，不能保证优良个体入选。太大，不能保证优良个体入选。进化规划的基本技术进化规划的基本技术终止终止进化规划的终止准则与进化策略相同，即根据进化规划的终止准则与进化策略相同，即根据最大进化代次最大进化代次、最优个体与期望值的偏差最优个体与期望值的偏差、适应度的变化趋势适应度的变化趋势以及以及最优适最优适应度与最差适应度之差应度与最差适应度之差等四个判据。等四个判据。进化规划的基本技术进化规划的基本技术进化规划的算法流程：进化规划的算法流程：(1)确定问题的表达方式。确定问题的表达方式

33、。(2)随机产生初始群体，并计算其适应度。随机产生初始群体，并计算其适应度。(3)用下述操作产生新群体：用下述操作产生新群体：1) 突变。对旧个体添加随机量，产生新个体突变。对旧个体添加随机量，产生新个体2) 计算新个体适应度；计算新个体适应度；3) 选择。挑选优良个体组成新群体。选择。挑选优良个体组成新群体。(4)反复执行反复执行(3)，直至满足终止条件，选择最佳个体作为进化规划，直至满足终止条件，选择最佳个体作为进化规划的最优解。的最优解。Fast Evolutionary ProgrammingClassical Evolutionary Programming:Fast Evoluti

34、onary Programming:Cauchy density function5.3 遗传规划遗传规划遗传算法的局限性遗传算法的局限性：(1)不能描述层次化的问题。不能描述层次化的问题。(2)不能描述计算机程序。不能描述计算机程序。(3)缺乏动态可变性。缺乏动态可变性。1992年、美国年、美国John R. Koza正式提出遗传规划正式提出遗传规划(Genetic Programming)，用层次化的结构性语言表达问题。用层次化的结构性语言表达问题。遗传规划的最大特点，是采用层次化的结构表达问题，它类似于计算遗传规划的最大特点，是采用层次化的结构表达问题，它类似于计算机程序分行或分段地描述

35、问题。这种广义的计算机程序能够根据环机程序分行或分段地描述问题。这种广义的计算机程序能够根据环境状态自动改变程序的结构及大小。境状态自动改变程序的结构及大小。5.3 遗传规划遗传规划遗传规划的工作步骤可归纳如下：遗传规划的工作步骤可归纳如下：(1)确定个体的表达方式，包括函数集确定个体的表达方式，包括函数集F及终止符集及终止符集T。(2)随机产生初始群体。随机产生初始群体。(3)计算各个体的适应度。计算各个体的适应度。(4)根据遗传参数，用下述操作产生新个体：根据遗传参数，用下述操作产生新个体：1)复制。将已有的优良个体复制，加入新群体中，并相应删除劣复制。将已有的优良个体复制，加入新群体中，

36、并相应删除劣质个体质个体2)交换。将选出的两个个体进行交换，所产生的两个新个体插入交换。将选出的两个个体进行交换，所产生的两个新个体插入新群体中。新群体中。3)突变。随机改变个体某一部分，将新个体插入新群体中。突变。随机改变个体某一部分，将新个体插入新群体中。(5)反复执行反复执行(3)及及(4)直至取得满意结果。直至取得满意结果。遗传规划的基本技术遗传规划的基本技术问题的表达问题的表达遗传规划是用层次结构可变的形式表达问题，在表达中主要用遗传规划是用层次结构可变的形式表达问题，在表达中主要用函数函数和和终止符终止符两类组分。简单地说，终止符表示问题的值，函数表示两类组分。简单地说，终止符表示

37、问题的值，函数表示对值的处理。综合在一起，遗传规划的个体表示对各种值对值的处理。综合在一起，遗传规划的个体表示对各种值(终止符终止符)的处理过程的处理过程(函数函数)。 在函数集在函数集Ff1, f2, , fn中，函数中，函数fi可以是运算符、函数、说明可以是运算符、函数、说明等，具体有：等，具体有：(1) 算术运算符，如算术运算符，如+, -, *, /等。其中除号为防止计算机溢出，规定等。其中除号为防止计算机溢出，规定不允许用零作分母，称保护性除法不允许用零作分母，称保护性除法(Protected Division)，用标用标记。一旦遇到分母为零时，最简单的处理方法是令其商为记。一旦遇到

38、分母为零时，最简单的处理方法是令其商为1、或是、或是重新选择算术运算符。重新选择算术运算符。遗传规划的基本技术遗传规划的基本技术(2)超越函数，如超越函数，如sin, cos, tan, log, exp等。其中等。其中log要防止处理小于或要防止处理小于或等于零的数值，称保护性对数，记为等于零的数值，称保护性对数，记为Rlog其处理方法类似于。其处理方法类似于。(3)布尔运算符，如布尔运算符，如AND、OR或或NOT等。等。(4)条件表达式，如条件表达式，如If-then-else, Switch-Case等。等。(5)循环表达式如循环表达式如Do-until, while-do, For-

39、do等。等。(6)控制转移说明，如控制转移说明，如Go to, Call, Jump等。等。(7)变量赋值函数如变量赋值函数如a:1, Read, Write等。等。(8)其他定义的函数。其他定义的函数。遗传规划的基本技术遗传规划的基本技术终止符集终止符集Tt1, t2, , tn包括各种常数、输入、变量等，包括各种常数、输入、变量等，具体有：具体有：(1)常数，如常数，如、180o等，等，(2)变量，如变量，如x, y, z等。等。(3)输入，如输入，如a, b, c等。等。顾名思义，终止符是个体表达的终点。顾名思义，终止符是个体表达的终点。遗传规划的基本技术遗传规划的基本技术将函数集和终止

40、符集综合在一起，便可形成层次状个体。例如，将函数集和终止符集综合在一起，便可形成层次状个体。例如，有下列函数集：有下列函数集：F=AND, OR, NOT和终止符集：和终止符集：T=D0, D1式中，式中，D0，D1为布尔变量。为布尔变量。上述函数集和终止符集的并集上述函数集和终止符集的并集C为：为：C=AND，OR，NOT，D0，D1遗传规划的基本技术遗传规划的基本技术C中终止符中终止符D0及及D1可视为具有可视为具有0个变量的函数。于是并集个变量的函数。于是并集C中中各函数的变量个数分别为：各函数的变量个数分别为：2，2，l，0，0。从并集从并集C中任中任选一个函数选一个函数(假设是假设是

41、OR)，根据该函数的变量数目再从根据该函数的变量数目再从C集集选取相应数目的函数选取相应数目的函数(OR要选两个函数要选两个函数)。如此重复，直至。如此重复，直至选出选出0个变量的函数，它也就是终止符。个变量的函数，它也就是终止符。为了形象地表达遗传规划的层次结构，通常采用算法树的形式。为了形象地表达遗传规划的层次结构，通常采用算法树的形式。现用一个有两个变量的奇现用一个有两个变量的奇-偶判断函数为例。若该函数的变偶判断函数为例。若该函数的变量取值相同，则该函数返回量取值相同，则该函数返回T(真真)；否则，该函数返回；否则，该函数返回F(假假)。这种布尔型函数的符号表达式为：。这种布尔型函数的

42、符号表达式为：(NOT(D0) AND NOT(D1) ) OR (D0 AND D1)遗传规划的基本技术遗传规划的基本技术5个内结点为函数集个内结点为函数集F中的函数元素中的函数元素(OR、AND、AND、NOT、NOT)，4个外结个外结点点(叶子叶子)为终止符集为终止符集T中的布尔变量中的布尔变量(D0、 D1、 D0、D1)，根为函数集根为函数集F中中的一个函数，即的一个函数，即OR。该树即为数据结该树即为数据结构中的算法树。这种算法树常用于表构中的算法树。这种算法树常用于表达遗传规划中的个体。达遗传规划中的个体。遗传规划的基本技术遗传规划的基本技术初始个体的生成原理初始个体的生成原理

43、初始群体通过随机方法产生。下图描述了函数初始群体通过随机方法产生。下图描述了函数“”（具有（具有2个自个自变量）为根结点的算法树，函数变量）为根结点的算法树，函数“”是随机地从函数集是随机地从函数集F中选中选出的。一般情况下，从函数集出的。一般情况下，从函数集F中选出的函数中选出的函数f如果有如果有z(f)个自变量，个自变量，那么就要从节点发出那么就要从节点发出z(f)条线。然后，对于每条从节点发出的线，条线。然后，对于每条从节点发出的线，从中再按均匀分布随机地选出一个元素作为该条线的尾节点。如从中再按均匀分布随机地选出一个元素作为该条线的尾节点。如果此时选出的是一个函数，则重复执行上述过程。

44、例如若函数果此时选出的是一个函数，则重复执行上述过程。例如若函数“”从并集从并集C中被选出，则函数中被选出，则函数“”将作为非根内结点，如将作为非根内结点，如图三所示。上述过程从上到下、从左到右不断重复，直到一棵完图三所示。上述过程从上到下、从左到右不断重复，直到一棵完整的树生成为止。整的树生成为止。 遗传规划的基本技术遗传规划的基本技术 初始群体的生成初始群体的生成图二图二 具有函数具有函数“”根结点的算法树（第一次选择）根结点的算法树（第一次选择）遗传规划的基本技术遗传规划的基本技术 初始群体的生成初始群体的生成图三图三 具有函数具有函数“”非根内结点的算法树非根内结点的算法树(第二次选择

45、第二次选择)遗传规划的基本技术遗传规划的基本技术 初始群体的生成初始群体的生成图四图四 终止符终止符A、B、C被选出作为叶子的算法树被选出作为叶子的算法树（第（第35次选择）次选择）遗传规划的基本技术遗传规划的基本技术 初始群体的生成初始群体的生成初始个体生成的几种方法初始个体生成的几种方法 常用的方法有三种：常用的方法有三种：完全法、生长法完全法、生长法和和混合法混合法 (1)完全法完全法。用完全法产生的初始个体，每一子叶的深度都。用完全法产生的初始个体，每一子叶的深度都等于给定的最大深度（叶子的深度是指叶子距树根的层数，等于给定的最大深度（叶子的深度是指叶子距树根的层数，如图四所示的树深度

46、为如图四所示的树深度为3）。其实现的方法是：若待定结点）。其实现的方法是：若待定结点的深度小于给定的最大深度，则该结点的选择将限制在函的深度小于给定的最大深度，则该结点的选择将限制在函数集内；若待定结点的深度等于给定的最大深度，则该结数集内；若待定结点的深度等于给定的最大深度，则该结点仅从终止符集内选择。点仅从终止符集内选择。 遗传规划的基本技术遗传规划的基本技术 初始群体的生成初始群体的生成 (2)生长法生长法。用生长法产生的初始个体具有不同的形态，每一叶子的深度不。用生长法产生的初始个体具有不同的形态，每一叶子的深度不一定都等于给定的最大深度。其实现方法是：若待定结点的深度小于给一定都等于

47、给定的最大深度。其实现方法是：若待定结点的深度小于给定的最大深度，则该结点的选择将限制在函数集与终止符集组成的并集定的最大深度，则该结点的选择将限制在函数集与终止符集组成的并集中；若待定结点的深度等于给定的最大深度，则该结点仅从仅从终止符中；若待定结点的深度等于给定的最大深度，则该结点仅从仅从终止符集内选择。集内选择。 (3)混合法混合法。混合法是完全法和生长法的综合。其实现方法是：初始个体的。混合法是完全法和生长法的综合。其实现方法是：初始个体的深度在深度在2至给定的最大深度之间均匀选取，这时每一种深度下的初始个体至给定的最大深度之间均匀选取，这时每一种深度下的初始个体数所占百分比数所占百分

48、比n为：为： n=1/(给定的最大深度给定的最大深度21) 在每一深度中，在每一深度中，50的初始个体用完全法产生，另的初始个体用完全法产生，另50的初始个体用生的初始个体用生长法产生。长法产生。 遗传规划的基本技术遗传规划的基本技术 适应性度量适应性度量 常见的适应性测度有下列四种：常见的适应性测度有下列四种：原始适应度原始适应度、标准适应度标准适应度、调整调整适应度适应度和和归一化适应度归一化适应度。 (1) 原始适应度原始适应度(Raw Fitness) 原始适应度是问题适应性自然描述的一种度量。例如，人工蚂蚁原始适应度是问题适应性自然描述的一种度量。例如，人工蚂蚁问题中研究蚂蚁吃掉的食

49、物块数，吃掉的食物块数越多越好，原问题中研究蚂蚁吃掉的食物块数，吃掉的食物块数越多越好，原始适应度便是被蚂蚁吃掉的食物块数。当原始适应度定义为误差始适应度便是被蚂蚁吃掉的食物块数。当原始适应度定义为误差时，也就是在一组适应度计算试例中个体返回值与实测值之间的时，也就是在一组适应度计算试例中个体返回值与实测值之间的距离之和。如果符号表达式是整数型或浮点型，那么距离之和表距离之和。如果符号表达式是整数型或浮点型，那么距离之和表现为符号表达式的返回值与实测值之间的距离绝对值的总和。在现为符号表达式的返回值与实测值之间的距离绝对值的总和。在群体中，子代群体中，子代 t 中某一个体中某一个体 i 的原始

50、适应度的原始适应度r(i, t) 定义为定义为遗传规划的基本技术遗传规划的基本技术 适应性度量适应性度量 (2) 标准适应度标准适应度(Standardized Fitness)标准适应度标准适应度 S(i, t) 是原始适应度又一描述，即标准适应度总是表是原始适应度又一描述，即标准适应度总是表现为数值越小越好。于是有两种情况发生：现为数值越小越好。于是有两种情况发生： 对于某些问题，若原始适应度越大越好，则标准适应度可定义对于某些问题，若原始适应度越大越好，则标准适应度可定义如下如下 式中式中 rmax 为原始适应度所能达到的最大值。为原始适应度所能达到的最大值。 对于另外一些问题，若原始适

51、应度越低越好，则标准适应度即对于另外一些问题，若原始适应度越低越好，则标准适应度即为原始适应度，即为原始适应度，即 S(i, t) = r(i, t) 。遗传规划的基本技术遗传规划的基本技术 适应性度量适应性度量 (3)调整适应度调整适应度(Adjusted Fitness) 子代子代 t 中个体中个体 i 的调整适应度的调整适应度 a(i, t) 由标准适应度计算而得，即由标准适应度计算而得，即 通常通常 , 则则 ,且调整适应度值越大，且调整适应度值越大，个体越优良。个体越优良。 遗传规划的基本技术遗传规划的基本技术 适应性度量适应性度量 (4)归一化适应度归一化适应度(Normalize

52、d Fitness) 归一化适应度归一化适应度 由调整适应度计算而得，由调整适应度计算而得， 即即 适应度值越大，个体越优良。适应度值越大，个体越优良。 遗传规划的基本技术遗传规划的基本技术 -基本算子基本算子 （1） 复制复制 当复制操作发生时，一个亲代个体繁殖一个后代个体。复当复制操作发生时，一个亲代个体繁殖一个后代个体。复制过程由两部分组成：首先，根据适应度按照不同的选择制过程由两部分组成：首先，根据适应度按照不同的选择方法从群体中选出一个亲代个体；其次，被选出的亲代个方法从群体中选出一个亲代个体；其次，被选出的亲代个体在未经任何变化的条件下从当前代复制到新一代中。体在未经任何变化的条件

53、下从当前代复制到新一代中。 遗传规划的基本技术遗传规划的基本技术 -基本算子基本算子根据适应度有以下几种亲代选择方法：根据适应度有以下几种亲代选择方法： 适应度比例选择法适应度比例选择法。其含义是个体适应度越高，被选中。其含义是个体适应度越高，被选中的概率越大。的概率越大。 贪婪选择法贪婪选择法。将个体按归一化适应度从大到小排序，将群。将个体按归一化适应度从大到小排序，将群体分为体分为、两组，两组，组由归一化适应度较高的优良个体组成；组由归一化适应度较高的优良个体组成；余下的归为余下的归为组。进行个体选择时，组。进行个体选择时，80的时间在的时间在组中选组中选择，择，20的时间在的时间在组中选

54、择。组中选择。遗传规划的基本技术遗传规划的基本技术 -基本算子基本算子 级差选择法级差选择法。这种方法将个体按适应度的大小分成许多个。这种方法将个体按适应度的大小分成许多个级别，个体根据群体中个体适应度的级别进行选择。适应级别，个体根据群体中个体适应度的级别进行选择。适应度较高的个体具有适当的选择优势。度较高的个体具有适当的选择优势。 竞争选择法竞争选择法。首先从群体中随机选出一组个体，然后在该。首先从群体中随机选出一组个体，然后在该组个体中选出一个具有较高适应度的个体。组个体中选出一个具有较高适应度的个体。遗传规划的基本技术遗传规划的基本技术 -基本算子基本算子 （2）交叉）交叉 交叉操作的

55、实现方法交叉操作的实现方法与复制过程相类似，第一个亲代个体根据上述的某种选择方法从与复制过程相类似，第一个亲代个体根据上述的某种选择方法从群体中选出，第二个亲代个体也采用同样的选择方法从群体中选群体中选出，第二个亲代个体也采用同样的选择方法从群体中选出，但两者选择过程独立。这样一来，所选出的两个亲代个体结出，但两者选择过程独立。这样一来，所选出的两个亲代个体结构、大小可能均不相同。交叉时，在每个亲代个体的算法树上分构、大小可能均不相同。交叉时，在每个亲代个体的算法树上分别按均匀概率分布随机选择一个交叉点，于是产生一棵以交叉点别按均匀概率分布随机选择一个交叉点，于是产生一棵以交叉点为根的子树，该

56、子树包括交换点以下的所有子树。具有这样特点为根的子树，该子树包括交换点以下的所有子树。具有这样特点的一颗子树成为一个交叉段。有时，一个交叉段仅是一个叶子。的一颗子树成为一个交叉段。有时，一个交叉段仅是一个叶子。 遗传规划的基本技术遗传规划的基本技术 -基本算子基本算子为了生成第一个子代个体，第一个亲代个体删掉其交叉段为了生成第一个子代个体，第一个亲代个体删掉其交叉段后，将第二个亲代个体的交叉段插入到它的交叉点处，这后，将第二个亲代个体的交叉段插入到它的交叉点处，这样第一个子代个体便产生了。同样，第二个子代个体也是样第一个子代个体便产生了。同样，第二个子代个体也是通过第二个亲代个体删掉其交叉段后

57、，将第一个亲代个体通过第二个亲代个体删掉其交叉段后，将第一个亲代个体的交叉段插入到它的交叉点后而形成。交叉过程如图五、的交叉段插入到它的交叉点后而形成。交叉过程如图五、图六和图七所示。图六和图七所示。 遗传规划的基本技术遗传规划的基本技术 -基本算子基本算子 图五图五 两个亲代个体（符号表达式）两个亲代个体（符号表达式）NOT遗传规划的基本技术遗传规划的基本技术 -基本算子基本算子图六图六 两个由亲代个体产生的两个由亲代个体产生的交叉交叉段段 遗传规划的基本技术遗传规划的基本技术 -基本算子基本算子图七图七 两个由亲代个体产生的子代个体两个由亲代个体产生的子代个体遗传规划的基本技术遗传规划的基

58、本技术 -基本算子基本算子 交叉操作的一般特征交叉操作的一般特征由于交叉时整个子树被交换，因此不管亲代个体和交叉点如何选择，由于交叉时整个子树被交换，因此不管亲代个体和交叉点如何选择，交叉所产生的新的（子代）符号表达式总是语法上合法的表达式。交叉所产生的新的（子代）符号表达式总是语法上合法的表达式。 交叉操作的特殊作用交叉操作的特殊作用如果群体中相对其它个体来说有一个适应度特别好的个体，复制将如果群体中相对其它个体来说有一个适应度特别好的个体，复制将促使该个体延续许多代，即使该个体在搜索空间中就整体来讲特别促使该个体延续许多代，即使该个体在搜索空间中就整体来讲特别平庸也是如此。在平庸也是如此。

59、在GP算法中，当两个相同的个体进行交叉时，所产算法中，当两个相同的个体进行交叉时，所产生的子代个体一般不相同，除非交叉点恰好相同，但这种机会很小，生的子代个体一般不相同，除非交叉点恰好相同，但这种机会很小，在在GP算法中交叉操作将施加一个偏离同一化趋势的反平衡作用。因算法中交叉操作将施加一个偏离同一化趋势的反平衡作用。因此，在此，在GP算法中同一化的发生是不太可能的。算法中同一化的发生是不太可能的。 遗传规划的基本技术遗传规划的基本技术 -辅助算子辅助算子 有五个辅助算子：有五个辅助算子：突变、排列、编辑、封装、自残突变、排列、编辑、封装、自残 （1）突变（）突变（Mutation） 产生突变

60、的方法是：首先在符号表达式的算法树上随机选定产生突变的方法是：首先在符号表达式的算法树上随机选定一个结点，该结点称为突变点，突变点可以是树的内结点一个结点，该结点称为突变点，突变点可以是树的内结点（即函数），也可以是树的叶子（终止符）；然后删掉突（即函数），也可以是树的叶子（终止符）；然后删掉突变点和突变点以下的子树，用随机方式产生一棵新子树变点和突变点以下的子树，用随机方式产生一棵新子树（方法同初始个体的产生）插入到该突变点处。该新子树（方法同初始个体的产生）插入到该突变点处。该新子树由参数控制，控制参数主要是树的大小（用深度表示）。由参数控制，控制参数主要是树的大小（用深度表示）。如图八（

61、如图八（a）中点中点3（即（即D0）被选为突变点，随机生成的子被选为突变点，随机生成的子树为树为NOT(D1)，突变后的树如（突变后的树如（b）所示。所示。 遗传规划的基本技术遗传规划的基本技术 -辅助算子辅助算子图八图八 个体的突变个体的突变(a)(a) 遗传规划的基本技术遗传规划的基本技术 -辅助算子辅助算子图八图八 个体的突变个体的突变(b)(b) 遗传规划的基本技术遗传规划的基本技术 -辅助算子辅助算子 （2）排列（）排列（Permutation）排列操作方法：首先选定一个个体的算法树的内结点（即排列操作方法：首先选定一个个体的算法树的内结点（即函数），如果在选定点的函数有函数），如果

62、在选定点的函数有k个变量，那么可从个变量，那么可从k!种可种可能排列中选出一种；然后对选定点的函数的自变量进行随能排列中选出一种；然后对选定点的函数的自变量进行随机排列。如图九所示，图中点机排列。如图九所示，图中点4（即（即“/”）被选为排列点，）被选为排列点，排列前的树为（排列前的树为（a），），排列后的树为（排列后的树为（b）。）。 遗传规划的基本技术遗传规划的基本技术 -辅助算子辅助算子图九图九 排列操作的方法排列操作的方法 (a) 遗传规划的基本技术遗传规划的基本技术 -辅助算子辅助算子图九图九 排列操作的方法排列操作的方法 (b) 遗传规划的基本技术遗传规划的基本技术 -辅助算子辅助

63、算子 （3）编辑（）编辑（Editing）编辑算子提供了一种编辑和简化符号表达式的手段。编辑操作仅在单个编辑算子提供了一种编辑和简化符号表达式的手段。编辑操作仅在单个个体上进行，编辑操作的结果是产生一个新的子代个体。编辑操作可反个体上进行，编辑操作的结果是产生一个新的子代个体。编辑操作可反复地将预先建立起来的编辑规则集应用于群体中每个符号表达式上。复地将预先建立起来的编辑规则集应用于群体中每个符号表达式上。一般的编辑规则如下：如果一个函数只有常数自变量，而且它对符号表一般的编辑规则如下：如果一个函数只有常数自变量，而且它对符号表达式中其他内容不产生负面影响，那么该函数就用具体的函数值来代替。达

64、式中其他内容不产生负面影响，那么该函数就用具体的函数值来代替。例如，数学表达式例如，数学表达式12可用可用3来代替。来代替。此外，编辑操作还应用一套与值域有关的编辑规则集。例如，对于数字此外，编辑操作还应用一套与值域有关的编辑规则集。例如，对于数字值域问题，一个可能的编辑规则为：当一个子表达式自身相减时，则该值域问题，一个可能的编辑规则为：当一个子表达式自身相减时，则该表达式用零代替。表达式用零代替。遗传规划的基本技术遗传规划的基本技术 -辅助算子辅助算子编辑操作有两种使用方法：编辑操作有两种使用方法：编辑操作完全在外部执行，与编辑操作完全在外部执行，与GP算法的运行独立，这样可算法的运行独立

65、，这样可在输出结果中同时观看编辑前和编辑后的个体；在输出结果中同时观看编辑前和编辑后的个体；编辑操作在进化过程中运行，这样在输出结果中只可观看编辑操作在进化过程中运行，这样在输出结果中只可观看编辑后的个体。编辑后的个体。编辑操作由一频率参数控制，以确定是否以及如何对每一编辑操作由一频率参数控制，以确定是否以及如何对每一代实施编辑操作。例如频率参数代实施编辑操作。例如频率参数fed = 1，则表示对每一代实则表示对每一代实施编辑操作。施编辑操作。 遗传规划的基本技术遗传规划的基本技术 -辅助算子辅助算子 （4）封装（）封装（Encapsulation）封装算子用于标明潜在有用的子树，并给它命名以

66、便能在封装算子用于标明潜在有用的子树，并给它命名以便能在以后得到引用。封装操作仅在单个个体上进行，该个体的以后得到引用。封装操作仅在单个个体上进行，该个体的选择原则仍同于复制和交换，其结果是产生一个新的封装选择原则仍同于复制和交换，其结果是产生一个新的封装函数。函数。封装操作方法：随机选定一个个体的算法树的内节点（即封装操作方法：随机选定一个个体的算法树的内节点（即函数点），从原树上将该子树复制下来（但原树仍不变），函数点），从原树上将该子树复制下来（但原树仍不变），将该子树定义成一棵可被引用的新函数。这个新的封装函将该子树定义成一棵可被引用的新函数。这个新的封装函数可当作终止符看，其形状为一

67、棵原来位于选择点的子树，数可当作终止符看，其形状为一棵原来位于选择点的子树，而且在产生时便命以不同的名称。而且在产生时便命以不同的名称。 遗传规划的基本技术遗传规划的基本技术 -辅助算子辅助算子调用封装函数是将其插入树的选择点处。问题的终止符集调用封装函数是将其插入树的选择点处。问题的终止符集随后被增广成包含这些封装函数的终止符集。于是，当实随后被增广成包含这些封装函数的终止符集。于是，当实施突变操作时，在突变点处能容纳新的封装函数。例如，施突变操作时，在突变点处能容纳新的封装函数。例如，考虑下列符号表达式：考虑下列符号表达式：ABC在图十中，点在图十中，点3被选为封装操作点，则形成的无自变量

68、的封被选为封装操作点，则形成的无自变量的封装函数装函数E0为为E0=BC。在原函数中，子树（在原函数中，子树（BC）即被新的即被新的封装函数封装函数E0代替，产生的结果为代替，产生的结果为AE0，如图十一所示。如图十一所示。封装函数的作用在于：封装函数的作用在于：被选为封装函数的子树在新生成的被选为封装函数的子树在新生成的个体中不再因交换操作而被瓦解个体中不再因交换操作而被瓦解。 遗传规划的基本技术遗传规划的基本技术 -辅助算子辅助算子图十图十 点点3被选为封装操作点被选为封装操作点 遗传规划的基本技术遗传规划的基本技术 -辅助算子辅助算子图十一图十一 新的字符表达式新的字符表达式 遗传规划的

69、基本技术遗传规划的基本技术 -辅助算子辅助算子（5）自残（）自残（Decimation） 对于一些复杂的问题，初始群体适应度的分布可能非常偏对于一些复杂的问题，初始群体适应度的分布可能非常偏倚，自残操作提供了一种快速应付这种形势的方法。自残倚，自残操作提供了一种快速应付这种形势的方法。自残操作由两个参数控制：一是百分比；二是进行自残操作的操作由两个参数控制：一是百分比；二是进行自残操作的时间。例如，自残百分比为时间。例如，自残百分比为10，时间为第，时间为第0代。这时，当代。这时，当初始代个体适应度一计算完，马上就有初始代个体适应度一计算完，马上就有10的个体被消灭。的个体被消灭。自残操作中的

70、个体选择是基于适应度的随机选择，不允许自残操作中的个体选择是基于适应度的随机选择，不允许某一个体多次被选择以使剩余群体的多样性得到最大。某一个体多次被选择以使剩余群体的多样性得到最大。 遗传规划的基本技术遗传规划的基本技术 -终止准则终止准则终止准则一般有两个：终止准则一般有两个：1.当最大容许进化代数当最大容许进化代数G满足时，进化过程立即停止；满足时，进化过程立即停止；2.当预先设定的问题求解成功条件满足时，进化过程立即停当预先设定的问题求解成功条件满足时，进化过程立即停止。止。 遗传规划的基本技术遗传规划的基本技术 -结果标定结果标定 结果标定有三种方法：结果标定有三种方法：找出一个全局

71、最佳个体，该个体在进化中的任一代群体中找出一个全局最佳个体，该个体在进化中的任一代群体中都会出现。为此，在每一代进化完后，若这一代的最佳个都会出现。为此，在每一代进化完后，若这一代的最佳个体优于前一代，则这一代的最佳个体取代前一代的最佳个体优于前一代，则这一代的最佳个体取代前一代的最佳个体；否则前一代的最佳个体仍保留。体；否则前一代的最佳个体仍保留。在进化停止时标定出群体中的一个最佳个体（即末代最佳在进化停止时标定出群体中的一个最佳个体（即末代最佳个体）。即最后一代的最佳个体就是全局最佳个体。个体）。即最后一代的最佳个体就是全局最佳个体。将整个群体或按与适应度成比例选定的一个子群作为最佳将整个

72、群体或按与适应度成比例选定的一个子群作为最佳结果，子群大小视具体情况而定。结果，子群大小视具体情况而定。遗传规划的基本技术遗传规划的基本技术 -控制参数控制参数 GP算法中进化过程由算法中进化过程由17个参数控制，即：个参数控制，即：（1）群体内个体数）群体内个体数M ；（2）最大进化代数最大进化代数G；（3）复制概率复制概率Pr；（4）交换概率交换概率Pc；（5）交换点选择时，树的内结点（函数点）选择概率为交换点选择时，树的内结点（函数点）选择概率为Pip，树的外结点树的外结点（终止符点）选择概率为（终止符点）选择概率为Ptp；（6）交换或其它次要操作时个体算法树最大深度交换或其它次要操作时

73、个体算法树最大深度Dcreated ；（7）初始代的个体算法树的最大深度初始代的个体算法树的最大深度Dinitial；（8）突变概率突变概率Pm； 遗传规划的基本技术遗传规划的基本技术 -控制参数控制参数（9）排列概率）排列概率Pp；（10）编辑概率编辑概率Ped；（11）封装概率封装概率Pen；（12）自残百分比自残百分比Pd； （13）初始种群的产生方法；初始种群的产生方法； （14）复制时个体选择和交换时第一亲代个体选择方法；）复制时个体选择和交换时第一亲代个体选择方法； （15）交换时第二亲代个体选择方法；）交换时第二亲代个体选择方法； （16）适应度调整；）适应度调整； （17）贪婪选择法的选取，低于）贪婪选择法的选取，低于500时不使用，高于时不使用，高于1000个个体时使用。个个体时使用。