其他进化算法(new).ppt

《其他进化算法(new).ppt》由会员分享，可在线阅读，更多相关《其他进化算法(new).ppt（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 进化策略,进化策略（Evolutionary Strategies）是在1965年由Rechenbu

2、rg和Schwefel独立提出的。 早期的进化策略的种群中只包含一个个体，并且只使用变异操作。在每一代中，变异后的个体与其父代进行比较，并选择较好的一个，这种选择策略被称为(1+1)-ES。 进化策略中的个体用传统的十进制实型数表示，即： Xt第t代个体的数值， N(0,)服从正态分布的随机数，其均值为零，标准差为。,5.1 进化策略,在这个模型中，把解的分量看做个体的行为特性，而不是沿染色体排列的基因。可以和GA一样，假设这些表现型特征具有基因根源，但是它们之间的联系实质并没有被弄清楚，所以我们把着重点放在个体的行为特性上。 假设不管发生什么遗传变换，所造成各个行为的变化均遵循零均值和某个标

3、准差的高斯分布。 由于基因多效性和多基因性，特定基因的改变可以影响许多表现型特征。所以在创造新子代时，较为合适的是同时改变亲本所有分量。,5.1 进化策略,早期进化策略采用上述算法，主要采用单亲本单子代的搜索，即“（1+1）进化策略(1+1)-ES)”，其中单个子代是由单个亲本产生的，它们都被置于生存竞争中，较弱的一个要被挑选出来消去。 当把这种算法用于函数优化时，发现它有两个缺点： 各维取定常的标准差使得程序收敛到最优解的速度很慢； 点到点搜索的脆弱本质使得程序在局部极值附近容易受停滞的影响（虽然此算法表明可以渐近地收敛到全局最优点）。,5.1 进化策略,( + 1)-ES: 早期的(1十1

4、)-ES，没有体现群体的作用，只是单个个体在进化，具有明显的局限性。随后，Rechenberg又提出(+1)-ES，在这种进化策略中，父代有个个体(1)，并且引入重组(Recombination)算子，使父代个体组合出新的个体。在执行重组时，从个父代个体中用随机的方法任选两个个体：,5.1 进化策略,然后从这两个个体中组合出如下新个体： 式中qi1或2，它以相同的概率针对i1，2，n随机选取。 对重组产生的新个体执行突变操作，突变方式及的调整与(1+1)-ES相同。 将突变后的个体与父代个个体相比较，若优于父代最差个体，则代替后者成为下一代个个体新成员，否则，重新执行重组和突变产生另一新个体，

5、,5.1 进化策略,(+1)-ES和(1+1)-ES具有相同的策略：只产生一个新个体。(+1)-ES的特点在于： (1) 采用群体，其中包含个个体； (2) 增添重组算子，它相当于遗传算法中的交叉算子，从父代继承信息构成新个体。 显然，(+1)-ES比(1+1)-ES有了明显的改进，为进化策略这种新的进化算法奠定良好的基础。,5.1 进化策略,在1973年，Rechenburg把该算法的期望收敛速度定义为对最优点的平均距离与要得到此改善所需要的试验次数之比。 1981年，Schwefel在进化策略中使用多重亲本和子代，这是Rechenburg早期工作（使用多重亲本，但是仅使用单个子代）的发展，

6、后来考察了两种方法，分别表示为(+)-ES和(，)-ES。在前者中，个亲本制造个子代，所有解均参加生存竞争，选出最好的个作为下一代的亲本。在后者中，只有（ ）个子代参加生存竞争，在每代中个亲本被完全取代。,5.1 进化策略,Rechenburg引入了如下想法，在每个新样本的特征分布中附加了一个自适应参数。在这个方法中，每个解矢量不仅包括了n维试验矢量x，而且还包括了扰动矢量，后者给出如何变异x以及它本身如何变异的指令。例如，设x为当前矢量， 为对应于x每个维的方差矢量，于是新的解矢量x， 可以这样产生： N(0,1)表示单个标准高斯随机变量， Ni(0,1)表示第i个独立相同的标准高斯分布，和

7、是影响总体和个体步长的算子集参数。以这种方式，进化策略可以在线地适应误差曲面的宽度，并且更恰当地分配实验次数。,进化策略的基本技术,问题的表达： 为了与突变操作相适应，进化策略有两种表达方式。 (1) 二元表达方式。这种表达方式中个体由目标变量X和标准差两部分组成，每部分又可以有n个分量，即： X和的关系为: 为全局系数，常取1。,进化策略的基本技术,(2) 三元表达方式。为了改善进化策略的收敛速度，Schwefel在二元表达的基础上引入第三个因子坐标旋转角度。个体的描述扩展为(X, , )，即： 三者的关系为： i父代个体i分量与j分量间坐标的旋转角度； j子代新个体i分量与j分量间坐标的旋

8、转角度； 系数，常取0.0873； zi取决于及的正态分布随机数。,进化策略的基本技术,旋转角度i表面上是分量i与j间坐标的旋转角度，实质上它是分量i与分量j之间协方差的体现。 重组 进化策略中的重组(Recombination)算子相当于遗传算法的交叉，它们都是以两个父代个体为基础进行信息交换。进化策略中，重组方式主要有三种： (1)离散重组。先随机选择两个父代个体,进化策略的基本技术,然后将其分量进行随机交换，构成子代新个体的各个分量，从而得出如下新个体： (2) 中值重组。这种重组方式也是先随机选择两个父代个体，然后将父代个体各分量的平均值作为子代新个体的分量，构成的新个体为： 这时，新

9、个体的各个分量兼容两个父代个体信息，而在离散重组中则只含有某一个父代个体的因子。,进化策略的基本技术,(3)混杂(Panmictic)重组。这种重组方式的特点在于父代个体的选择上。混杂重组时先随机选择一个固定的父代个体，然后针对子代个体每个分量再从父代群体中随机选择第二个父代个体。也就是说，第二个父代个体是经常变化的。至于父代两个个体的组合方式，既可以采用离散方式，也可以来用中值方式，甚至可以把中值重组中的1/2改为0,1之间的任一权值。 研究表明，进化策略采用重组后，明显增加算法的收敛速度。 Schwefel建议，对于目标变量X宜用离散重组，对于策略因子及宜用中值重组或混杂中值重组。,进化策

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

11、是局部最优解，从而误导进化策略收敛于次优解而不是最优解。(，)选择舍弃旧的优良个体，容易进化至全局员优解。 (3) (+)选择在保留旧个体的同时，也将进化参数保留下来，不利于进化策略中的自适应调整机制。(，)选择则恰恰相反，可促进这种自适应调整。 实践也证明，(, )-ES优于(+)-ES，前者已成为当前进化策略的主流。,进化策略的基本技术,在(,)-ES中，为了控制群体的多样性和选择的力度，比值/是一个重要参数，它对算法的收敛速度有很大影响。一方面， 不能太小，否则群体太单调(例如1的极端情况)；另一方面， 也不能太大，否则计算工作量过大。通常， 取15或更多一些。 数值的大小，类似于的作用

12、，也要适当。某些研究表明比值/宜取1/7左右。也就是说，若=15，则宜取100。,5.2 进化规划,进化规划(Evolutionary Programming)由Fogel在20世纪60年代所提出。Fogel将仿真进化方法用于由相互竞争的算法所构成的种群，在一系列研究中探索了进化规划的可能性，目的是发展人工智能。Fogel认为，智能行为需要有如下的复合能力： (1)预测它的环境； (2)把预测变成对于给定目标的适当响应。,5.2 进化规划,标准进化规划 进化规划用传统的十进制实数表达问题。在标准进化规划（Standard EP）中，个体的表达形式为： 式中：xi旧个体目标变量X的第i个分量，

13、xi新个体目标变量X的第i个分量， f(X)旧个体X的适应度； N(0, 1)针对第i分量发生的随机数，它服从标准正态分布。,5.2 进化规划,上式表明，新个体是在旧个体的基础上添加一个随机数，添加值的大小与个体的适应度有关：适应度大的个体添加值也大，反之亦然。 根据这种表达方式，进化规划首先由个旧个体产生个新个体。接着从个旧个体及个新个体(2 个个体)中根据适应度挑选出个个体组成新群体。如此反复迭代，直至得到满意结果。 进化规划没有重组或交换这类算子，它的进化主要依赖突变。在标准进化规划中这种突变十分简单，它只需参照个体适应度添加一个随机数。很明显，标准进化规划在进化过程中的自适应调整功能主

14、要依靠适应度f(X)来实现。,5.2 进化规划,Standard EP流程： 生成初始群体； While Not-End Do 突变； 计算个体适应度； 选择产生新群体；( ) = End While,5.2 进化规划,元进化规划 为了增加进化规划在进化过程中的自适应调整功能，人们在突变中添加方差的概念。类似于进化策略，在进化规划中个体的表达采用下述方式： 式中：i旧个体第 i 分量的标准差； i新个体第 i 分量的标准差； N(0, 1)针对第i分量发生的随机数，它服从标准正态分布。,5.2 进化规划,从上式可以看出，新个体也是在旧个体的基础上添加一个随机数，该添加量取决于个体的方差，而方差

15、在每次进化中又有自适应调整。这种进化方式已成为进化规划的主要手段，因此在进化规划前冠以“元”这个术语以表示它为基本方法。 元进化规划(Meta EP)的突变尽管类似于进化策略，但是它们有下述差别: (1)执行顺序不同。进化规划中首先计算新个体的目标变量xi ，计算中沿用旧个体的标准差i ；其次才计算新个体的标准差i ，新的标准差留待下次进化时才用。与之相反，进化策略是先调整标准差，然后再用新的标准差去更改个体的目标变量X。 (2)计算式的不同。进化规划的计算式比进化策略的计算式简单。,5.2 进化规划,旋转进化规划 旋转进化规划(Rmeta EP)进一步扩展进化规划，在表达个体时添加第三个因子

16、协方差，用三元组表示个体，即(X, , )，具体计算如下： X旧个体的目标变量，其内含n个分量； X新个体的目标变量，其内含n个分量； N(0,C)遵从正态分布的随机数，其数学期望为0、其标准差与协方差有关； j相关系数，,进化规划的基本技术,表达方法 采用十进制的实型数表达问题。 X=(x1, x2, , xi, , xn) 由X和组成的二元组(X, )是进化规划最常用的表达形式。有人建议将进化规划再增加一个控制因子 ，构成三元表达式(X, , )，其中 =(1, 2, , j, , n) j是相关系数的单下标表达, 它表示xi和xj 之间的协方差:,进化规划的基本技术,产生初始群体 进化规

17、划中产生初始群体的方法类似于进化策略中随机选择个个体作为进化计算的出发点。 计算适应度 进化规划采用十进制实数表达问题，计算适应度比较简单直观。 突变 突变是进化规划产生新群体的唯一方法，它不采用重组或交换算子。,进化规划的基本技术,选择 在进化规划中，新群体的个体数目等于旧群体的个体数目，选择便是在2 个个体中选择个个体组成新群体。 进化规划的选择采用随机型的q竞争选择法。在这种选择方法中，为了确定某一个体 i 的优劣，我们从新、旧群体的2 个个体中任选q个个体组成测试群体。然后将个体 i 的适应度与q个个体的适应度进行比较，记录个体 i 优于或等于q内各个体的次数，得到个体 i 的得分Wi

18、，即,进化规划的基本技术,上述得分测试分别对2个个体进行，每次测试时重新选择q个个体组成新的测试群体。最后，按个体的得分选择分值高的个个体组成下一代新群体。 q竞争选择法是一种随机选择，总体上讲，优良个体入选的可能性较大。但是由于测试群体q每次都是随机选择的，当q个个体都不甚好时，有可能使较差的个体因得分高而入选。这正是随机选择的本意。 q竞争选择法中q的大小是一个重要参数。若q很大，极端地设q2，则选择变为确定性选择。反之，若q很小，则选择的随机性太大，不能保证优良个体入选。,进化规划的基本技术,终止 进化规划的终止准则与进化策略相同，即根据最大进化代次、最优个体与期望值的偏差、适应度的变化

19、趋势以及最优适应度与最差适应度之差等四个判据。,进化规划的基本技术,进化规划的算法流程： (1)确定问题的表达方式。 (2)随机产生初始群体，并计算其适应度。 (3)用下述操作产生新群体： 1) 突变。对旧个体添加随机量，产生新个体 2) 计算新个体适应度； 3) 选择。挑选优良个体组成新群体。 (4)反复执行(3)，直至满足终止条件，选择最佳个体作为进化规划的最优解。,Fast Evolutionary Programming,Classical Evolutionary Programming:,Fast Evolutionary Programming:,Cauchy density f

20、unction,5.3 遗传规划,遗传算法的局限性： (1)不能描述层次化的问题。 (2)不能描述计算机程序。 (3)缺乏动态可变性。 1992年、美国John R. Koza正式提出遗传规划(Genetic Programming)，用层次化的结构性语言表达问题。 遗传规划的最大特点，是采用层次化的结构表达问题，它类似于计算机程序分行或分段地描述问题。这种广义的计算机程序能够根据环境状态自动改变程序的结构及大小。,5.3 遗传规划,遗传规划的工作步骤可归纳如下： (1)确定个体的表达方式，包括函数集F及终止符集T。 (2)随机产生初始群体。 (3)计算各个体的适应度。 (4)根据遗传参数，用

21、下述操作产生新个体： 1)复制。将已有的优良个体复制，加入新群体中，并相应删除劣质个体 2)交换。将选出的两个个体进行交换，所产生的两个新个体插入新群体中。 3)突变。随机改变个体某一部分，将新个体插入新群体中。 (5)反复执行(3)及(4)直至取得满意结果。,遗传规划的基本技术,问题的表达 遗传规划是用层次结构可变的形式表达问题，在表达中主要用函数和终止符两类组分。简单地说，终止符表示问题的值，函数表示对值的处理。综合在一起，遗传规划的个体表示对各种值(终止符)的处理过程(函数)。 在函数集Ff1, f2, , fn中，函数fi可以是运算符、函数、说明等，具体有： (1) 算术运算符，如+,

22、 -, *, /等。其中除号为防止计算机溢出，规定不允许用零作分母，称保护性除法(Protected Division)，用标记。一旦遇到分母为零时，最简单的处理方法是令其商为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-do等。 (6)控制转移说明，如

23、Go to, Call, Jump等。 (7)变量赋值函数如a:1, Read, Write等。 (8)其他定义的函数。,遗传规划的基本技术,终止符集Tt1, t2, , tn包括各种常数、输入、变量等，具体有： (1)常数，如、180o等， (2)变量，如x, y, z等。 (3)输入，如a, b, c等。 顾名思义，终止符是个体表达的终点。,遗传规划的基本技术,将函数集和终止符集综合在一起，便可形成层次状个体。例如，有下列函数集： F=AND, OR, NOT 和终止符集： T=D0, D1 式中，D0，D1为布尔变量。 上述函数集和终止符集的并集C为： C=AND，OR，NOT，D0，D

24、1,遗传规划的基本技术,C中终止符D0及D1可视为具有0个变量的函数。于是并集C中各函数的变量个数分别为：2，2，l，0，0。从并集C中任选一个函数(假设是OR)，根据该函数的变量数目再从C集选取相应数目的函数(OR要选两个函数)。如此重复，直至选出0个变量的函数，它也就是终止符。 为了形象地表达遗传规划的层次结构，通常采用算法树的形式。现用一个有两个变量的奇-偶判断函数为例。若该函数的变量取值相同，则该函数返回T(真)；否则，该函数返回F(假)。这种布尔型函数的符号表达式为： (NOT(D0) AND NOT(D1) ) OR (D0 AND D1),遗传规划的基本技术,5个内结点为函数集F

25、中的函数元素(OR、AND、AND、NOT、NOT)，4个外结点(叶子)为终止符集T中的布尔变量(D0、 D1、 D0、D1)，根为函数集F中的一个函数，即OR。该树即为数据结构中的算法树。这种算法树常用于表达遗传规划中的个体。,遗传规划的基本技术,初始个体的生成原理 初始群体通过随机方法产生。下图描述了函数“”（具有2个自变量）为根结点的算法树，函数“”是随机地从函数集F中选出的。一般情况下，从函数集F中选出的函数f如果有z(f)个自变量，那么就要从节点发出z(f)条线。然后，对于每条从节点发出的线，从中再按均匀分布随机地选出一个元素作为该条线的尾节点。如果此时选出的是一个函数，则重复执行上

26、述过程。例如若函数“”从并集C中被选出，则函数“”将作为非根内结点，如图三所示。上述过程从上到下、从左到右不断重复，直到一棵完整的树生成为止。,遗传规划的基本技术 初始群体的生成,图二 具有函数“”根结点的算法树（第一次选择）,遗传规划的基本技术 初始群体的生成,图三 具有函数“”非根内结点的算法树(第二次选择),遗传规划的基本技术 初始群体的生成,图四 终止符A、B、C被选出作为叶子的算法树 （第35次选择）,遗传规划的基本技术 初始群体的生成,初始个体生成的几种方法 常用的方法有三种：完全法、生长法和混合法 (1)完全法。用完全法产生的初始个体，每一子叶的深度都等于给定的最大深度（叶子的深

27、度是指叶子距树根的层数，如图四所示的树深度为3）。其实现的方法是：若待定结点的深度小于给定的最大深度，则该结点的选择将限制在函数集内；若待定结点的深度等于给定的最大深度，则该结点仅从终止符集内选择。,遗传规划的基本技术 初始群体的生成,(2)生长法。用生长法产生的初始个体具有不同的形态，每一叶子的深度不一定都等于给定的最大深度。其实现方法是：若待定结点的深度小于给定的最大深度，则该结点的选择将限制在函数集与终止符集组成的并集中；若待定结点的深度等于给定的最大深度，则该结点仅从仅从终止符集内选择。 (3)混合法。混合法是完全法和生长法的综合。其实现方法是：初始个体的深度在2至给定的最大深度之间均

28、匀选取，这时每一种深度下的初始个体数所占百分比n为： n=1/(给定的最大深度21) 在每一深度中，50的初始个体用完全法产生，另50的初始个体用生长法产生。,遗传规划的基本技术 适应性度量,常见的适应性测度有下列四种：原始适应度、标准适应度、调整适应度和归一化适应度。 (1) 原始适应度(Raw Fitness) 原始适应度是问题适应性自然描述的一种度量。例如，人工蚂蚁问题中研究蚂蚁吃掉的食物块数，吃掉的食物块数越多越好，原始适应度便是被蚂蚁吃掉的食物块数。当原始适应度定义为误差时，也就是在一组适应度计算试例中个体返回值与实测值之间的距离之和。如果符号表达式是整数型或浮点型，那么距离之和表现

29、为符号表达式的返回值与实测值之间的距离绝对值的总和。在群体中，子代 t 中某一个体 i 的原始适应度r(i, t) 定义为,遗传规划的基本技术 适应性度量,(2) 标准适应度(Standardized Fitness) 标准适应度 S(i, t) 是原始适应度又一描述，即标准适应度总是表现为数值越小越好。于是有两种情况发生： 对于某些问题，若原始适应度越大越好，则标准适应度可定义如下 式中 rmax 为原始适应度所能达到的最大值。 对于另外一些问题，若原始适应度越低越好，则标准适应度即为原始适应度，即 S(i, t) = r(i, t) 。,遗传规划的基本技术 适应性度量,(3)调整适应度(A

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

31、子,根据适应度有以下几种亲代选择方法： 适应度比例选择法。其含义是个体适应度越高，被选中的概率越大。 贪婪选择法。将个体按归一化适应度从大到小排序，将群体分为、两组，组由归一化适应度较高的优良个体组成；余下的归为组。进行个体选择时，80的时间在组中选择，20的时间在组中选择。,遗传规划的基本技术 -基本算子, 级差选择法。这种方法将个体按适应度的大小分成许多个级别，个体根据群体中个体适应度的级别进行选择。适应度较高的个体具有适当的选择优势。 竞争选择法。首先从群体中随机选出一组个体，然后在该组个体中选出一个具有较高适应度的个体。,遗传规划的基本技术 -基本算子,（2）交叉 交叉操作的实现方法

32、与复制过程相类似，第一个亲代个体根据上述的某种选择方法从群体中选出，第二个亲代个体也采用同样的选择方法从群体中选出，但两者选择过程独立。这样一来，所选出的两个亲代个体结构、大小可能均不相同。交叉时，在每个亲代个体的算法树上分别按均匀概率分布随机选择一个交叉点，于是产生一棵以交叉点为根的子树，该子树包括交换点以下的所有子树。具有这样特点的一颗子树成为一个交叉段。有时，一个交叉段仅是一个叶子。,遗传规划的基本技术 -基本算子,为了生成第一个子代个体，第一个亲代个体删掉其交叉段后，将第二个亲代个体的交叉段插入到它的交叉点处，这样第一个子代个体便产生了。同样，第二个子代个体也是通过第二个亲代个体删掉其

33、交叉段后，将第一个亲代个体的交叉段插入到它的交叉点后而形成。交叉过程如图五、图六和图七所示。,遗传规划的基本技术 -基本算子,图五 两个亲代个体（符号表达式）,NOT,遗传规划的基本技术 -基本算子,图六 两个由亲代个体产生的交叉段,遗传规划的基本技术 -基本算子,图七 两个由亲代个体产生的子代个体,遗传规划的基本技术 -基本算子, 交叉操作的一般特征 由于交叉时整个子树被交换，因此不管亲代个体和交叉点如何选择，交叉所产生的新的（子代）符号表达式总是语法上合法的表达式。 交叉操作的特殊作用 如果群体中相对其它个体来说有一个适应度特别好的个体，复制将促使该个体延续许多代，即使该个体在搜索空间中就

34、整体来讲特别平庸也是如此。在GP算法中，当两个相同的个体进行交叉时，所产生的子代个体一般不相同，除非交叉点恰好相同，但这种机会很小，在GP算法中交叉操作将施加一个偏离同一化趋势的反平衡作用。因此，在GP算法中同一化的发生是不太可能的。,遗传规划的基本技术 -辅助算子,有五个辅助算子：突变、排列、编辑、封装、自残 （1）突变（Mutation） 产生突变的方法是：首先在符号表达式的算法树上随机选定一个结点，该结点称为突变点，突变点可以是树的内结点（即函数），也可以是树的叶子（终止符）；然后删掉突变点和突变点以下的子树，用随机方式产生一棵新子树（方法同初始个体的产生）插入到该突变点处。该新子树由参

35、数控制，控制参数主要是树的大小（用深度表示）。如图八（a）中点3（即D0）被选为突变点，随机生成的子树为NOT(D1)，突变后的树如（b）所示。,遗传规划的基本技术 -辅助算子,图八 个体的突变(a),遗传规划的基本技术 -辅助算子,图八 个体的突变(b),遗传规划的基本技术 -辅助算子,（2）排列（Permutation） 排列操作方法：首先选定一个个体的算法树的内结点（即函数），如果在选定点的函数有k个变量，那么可从k!种可能排列中选出一种；然后对选定点的函数的自变量进行随机排列。如图九所示，图中点4（即“/”）被选为排列点，排列前的树为（a），排列后的树为（b）。,遗传规划的基本技术 -

36、辅助算子,图九 排列操作的方法 (a),遗传规划的基本技术 -辅助算子,图九 排列操作的方法 (b),遗传规划的基本技术 -辅助算子,（3）编辑（Editing） 编辑算子提供了一种编辑和简化符号表达式的手段。编辑操作仅在单个个体上进行，编辑操作的结果是产生一个新的子代个体。编辑操作可反复地将预先建立起来的编辑规则集应用于群体中每个符号表达式上。 一般的编辑规则如下：如果一个函数只有常数自变量，而且它对符号表达式中其他内容不产生负面影响，那么该函数就用具体的函数值来代替。例如，数学表达式12可用3来代替。 此外，编辑操作还应用一套与值域有关的编辑规则集。例如，对于数字值域问题，一个可能的编辑规

37、则为：当一个子表达式自身相减时，则该表达式用零代替。,遗传规划的基本技术 -辅助算子,编辑操作有两种使用方法： 编辑操作完全在外部执行，与GP算法的运行独立，这样可在输出结果中同时观看编辑前和编辑后的个体； 编辑操作在进化过程中运行，这样在输出结果中只可观看编辑后的个体。 编辑操作由一频率参数控制，以确定是否以及如何对每一代实施编辑操作。例如频率参数fed = 1，则表示对每一代实施编辑操作。,遗传规划的基本技术 -辅助算子,（4）封装（Encapsulation） 封装算子用于标明潜在有用的子树，并给它命名以便能在以后得到引用。封装操作仅在单个个体上进行，该个体的选择原则仍同于复制和交换，其

38、结果是产生一个新的封装函数。 封装操作方法：随机选定一个个体的算法树的内节点（即函数点），从原树上将该子树复制下来（但原树仍不变），将该子树定义成一棵可被引用的新函数。这个新的封装函数可当作终止符看，其形状为一棵原来位于选择点的子树，而且在产生时便命以不同的名称。,遗传规划的基本技术 -辅助算子,调用封装函数是将其插入树的选择点处。问题的终止符集随后被增广成包含这些封装函数的终止符集。于是，当实施突变操作时，在突变点处能容纳新的封装函数。例如，考虑下列符号表达式：ABC 在图十中，点3被选为封装操作点，则形成的无自变量的封装函数E0为E0=BC。在原函数中，子树（BC）即被新的封装函数E0代替

39、，产生的结果为AE0，如图十一所示。 封装函数的作用在于：被选为封装函数的子树在新生成的个体中不再因交换操作而被瓦解。,遗传规划的基本技术 -辅助算子,图十 点3被选为封装操作点,遗传规划的基本技术 -辅助算子,图十一 新的字符表达式,遗传规划的基本技术 -辅助算子,（5）自残（Decimation） 对于一些复杂的问题，初始群体适应度的分布可能非常偏倚，自残操作提供了一种快速应付这种形势的方法。自残操作由两个参数控制：一是百分比；二是进行自残操作的时间。例如，自残百分比为10，时间为第0代。这时，当初始代个体适应度一计算完，马上就有10的个体被消灭。自残操作中的个体选择是基于适应度的随机选择

40、，不允许某一个体多次被选择以使剩余群体的多样性得到最大。,遗传规划的基本技术 -终止准则,终止准则一般有两个： 当最大容许进化代数G满足时，进化过程立即停止； 当预先设定的问题求解成功条件满足时，进化过程立即停止。,遗传规划的基本技术 -结果标定,结果标定有三种方法： 找出一个全局最佳个体，该个体在进化中的任一代群体中都会出现。为此，在每一代进化完后，若这一代的最佳个体优于前一代，则这一代的最佳个体取代前一代的最佳个体；否则前一代的最佳个体仍保留。 在进化停止时标定出群体中的一个最佳个体（即末代最佳个体）。即最后一代的最佳个体就是全局最佳个体。 将整个群体或按与适应度成比例选定的一个子群作为最

41、佳结果，子群大小视具体情况而定。,遗传规划的基本技术 -控制参数,GP算法中进化过程由17个参数控制，即： （1）群体内个体数M ； （2）最大进化代数G； （3）复制概率Pr； （4）交换概率Pc； （5）交换点选择时，树的内结点（函数点）选择概率为Pip，树的外结点（终止符点）选择概率为Ptp； （6）交换或其它次要操作时个体算法树最大深度Dcreated ； （7）初始代的个体算法树的最大深度Dinitial； （8）突变概率Pm；,遗传规划的基本技术 -控制参数,（9）排列概率Pp； （10）编辑概率Ped； （11）封装概率Pen； （12）自残百分比Pd； （13）初始种群的产生方法； （14）复制时个体选择和交换时第一亲代个体选择方法； （15）交换时第二亲代个体选择方法； （16）适应度调整； （17）贪婪选择法的选取，低于500时不使用，高于1000个个体时使用。,