第八章进化策略和进化规划PPT课件

1、进化策略和进化规划进化策略和进化规划德国学者德国学者Schwefel和和Rechenburg美国学者美国学者Fogel分别提分别提出出进化策略进化策略ES和和进化规划进化规划EP。这三种方法具有共同的。这三种方法具有共同的本质，分别强调了自然进化中的不同方面：遗传算法本质，分别强调了自然进化中的不同方面：遗传算法强调染色体的操作，进化策略强调了个体级的行为变强调染色体的操作，进化策略强调了个体级的行为变化。而进化规划则强调种群级上的行为变化。现在学化。而进化规划则强调种群级上的行为变化。现在学术界把遗传算法术界把遗传算法GA、进化策略、进化策略ES和进化规划和进化规划EP通称通称为进化算法为进

2、化算法EC。8.1 进化算法的早期研究进化算法的早期研究进化算法起源于进化算法起源于20世纪世纪30年代的通过仿真生物进化过程进行机器年代的通过仿真生物进化过程进行机器学习的研究。早在学习的研究。早在1932年，年，Cannon就把自然进化想象为一个学习就把自然进化想象为一个学习过程。与自然进化过程的机制和结果稍微不同是，过程。与自然进化过程的机制和结果稍微不同是，Cannon不是通不是通过维持一个特定的种群来进行搜索，而是对单个个体反复进行随过维持一个特定的种群来进行搜索，而是对单个个体反复进行随机试验。到了机试验。到了1950年，年，Turng认识到，在机器学习和进化之间存认识到，在机器学

3、习和进化之间存在着明显的关系。在着明显的关系。1959年，年，Friedman推测，利用变异和选择的仿推测，利用变异和选择的仿真可以设计真可以设计“思想机器思想机器”，并且指出下棋的程序可以用这种方法，并且指出下棋的程序可以用这种方法设计。在设计。在1960年，年，Cambell猜想：在导致知识扩张的所有过程中，猜想：在导致知识扩张的所有过程中，都要涉及都要涉及“盲目盲目变化变化选择选择幸存幸存”的过程。此后，一些学者的过程。此后，一些学者逐渐将进化理论用于随机工程控制、机器学习和函数优化等领域。逐渐将进化理论用于随机工程控制、机器学习和函数优化等领域。8.2 进化策略进化策略进化策略（进化策

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

5、，其均值为零，标准差为服从正态分布的随机数，其均值为零，标准差为。8.2 进化策略进化策略进化策略的一般算法可以描述如下：进化策略的一般算法可以描述如下：问题为寻找实值问题为寻找实值n维矢量维矢量x，使得函数，使得函数F(x):RnR取取极值。不失一极值。不失一般性，设此程序为极小化过程。般性，设此程序为极小化过程。从各维的可行范围内随机选取亲本从各维的可行范围内随机选取亲本xi，i1，p的初始值。初的初始值。初始试验的分布一般是均匀分布。始试验的分布一般是均匀分布。通过对于通过对于x的每个分量增加零均值和预先选定的标准差的高斯随的每个分量增加零均值和预先选定的标准差的高斯随机变量，从每个亲本

6、机变量，从每个亲本xi产生子代产生子代xi。通过将误差通过将误差F(xi)和和F(xi)，i1，p进行排序，选择并决定哪进行排序，选择并决定哪些矢量保留。具有最小误差的些矢量保留。具有最小误差的p个矢量变成下一代的新亲本。个矢量变成下一代的新亲本。(1) 进行新试验，选择具有最小方差的新子代，一直到获得充分解，进行新试验，选择具有最小方差的新子代，一直到获得充分解，或者直到满足某个终止条件或者直到满足某个终止条件8.2 进化策略进化策略在这个模型中，把试验解的分量看做个体的行为特性，而在这个模型中，把试验解的分量看做个体的行为特性，而不是沿染色体排列的基因。可以和不是沿染色体排列的基因。可以和

7、GA一样，假设这些表现一样，假设这些表现型特征具有基因根源，但是它们之间的联系实质并没有被型特征具有基因根源，但是它们之间的联系实质并没有被弄清楚，所以我们把着重点放在个体的行为特性上。弄清楚，所以我们把着重点放在个体的行为特性上。假设不管发生什么遗传变换，所造成各个行为的变化均遵假设不管发生什么遗传变换，所造成各个行为的变化均遵循零均值和某个标准差的高斯分布。循零均值和某个标准差的高斯分布。由于基因多效性和多基因性，特定基因的改变可以影响许由于基因多效性和多基因性，特定基因的改变可以影响许多表现型特征。所以在创造新子代时，较为合适的是同时多表现型特征。所以在创造新子代时，较为合适的是同时改变

8、亲本所有分量。改变亲本所有分量。8.2 进化策略进化策略进化策略的最初试验采用上述算法，主要采用单亲本进化策略的最初试验采用上述算法，主要采用单亲本单子代单子代的搜索，即的搜索，即“（1+1）进化策略进化策略(1+1)-ES)”，其中单个子，其中单个子代是由单个亲本产生的，它们都被置于生存竞争中，较弱代是由单个亲本产生的，它们都被置于生存竞争中，较弱的一个要被挑选出来消去。的一个要被挑选出来消去。当把这种算法用于函数优化时，发现它有两个缺点：当把这种算法用于函数优化时，发现它有两个缺点：各维取定常的标准差使得程序收敛到最优解的速度很慢；各维取定常的标准差使得程序收敛到最优解的速度很慢；(1)

9、点到点搜索的脆弱本质使得程序在局部极值附近容易受停点到点搜索的脆弱本质使得程序在局部极值附近容易受停滞的影响（虽然此算法表明可以渐近地收敛到全局最优滞的影响（虽然此算法表明可以渐近地收敛到全局最优点）。点）。8.2 进化策略进化策略( + 1)-ES:早期的早期的(1十十1)-ES，没有体现群体的作用，只是单个个体在进，没有体现群体的作用，只是单个个体在进化，具有明显的局限性。随后，化，具有明显的局限性。随后，Rechenberg又提出又提出(+1)-ES，在这种进化策略中，父代有，在这种进化策略中，父代有个个体个个体(1)，并且引入，并且引入重组重组(Recombination)算子，使父代

10、个体组合出新的个体。算子，使父代个体组合出新的个体。在执行重组时，从在执行重组时，从个父代个体中用随机的方法任选两个个个父代个体中用随机的方法任选两个个体：体：8.2 进化策略进化策略然后从这两个个体中组合出如下新个体：然后从这两个个体中组合出如下新个体：式中式中qi1或或2，它以相同的概率针对，它以相同的概率针对i1，2，n随机选取。随机选取。对重组产生的新个体执行突变操作，突变方式及对重组产生的新个体执行突变操作，突变方式及的调整与的调整与(1+1)-ES相同。相同。将突变后的个体与父代将突变后的个体与父代个个体相比较，若优于父代最差个体，个个体相比较，若优于父代最差个体，则代替后者成为下

11、一代则代替后者成为下一代个个体新成员，否则，重新执行重个个体新成员，否则，重新执行重组和突变产生另一新个体，组和突变产生另一新个体，8.2 进化策略进化策略(+1)-ES和和(1+1)-ES具有相同的策略：只产生一个新个体。具有相同的策略：只产生一个新个体。(+1)-ES的特点在于：的特点在于： (1) 采用群体，其中包含采用群体，其中包含个个体；个个体； (2) 增添重组算子，它相当于遗传算法中的交叉算子，从父增添重组算子，它相当于遗传算法中的交叉算子，从父代继承信息构成新个体。代继承信息构成新个体。显然，显然，(+1)-ES比比(1+1)-ES有了明显的改进，为进化策略这种有了明显的改进，

12、为进化策略这种新的进化算法奠定良好的基础。新的进化算法奠定良好的基础。8.2 进化策略进化策略在在1973年，年，Rechenburg把该算法的期望收敛速度定义为对把该算法的期望收敛速度定义为对最优点的平均距离与要得到此改善所需要的试验次数之比。最优点的平均距离与要得到此改善所需要的试验次数之比。1981年，年，Schwefel在进化策略中使用多重亲本和子代，这是在进化策略中使用多重亲本和子代，这是Rechenburg早期工作（使用多重亲本，但是仅使用单个子早期工作（使用多重亲本，但是仅使用单个子代）的发展，后来考察了两种方法，分别表示为代）的发展，后来考察了两种方法，分别表示为(+)-ES相

13、相(，)-ES。在前者中，。在前者中，个亲本制造个亲本制造个子代，所有解均个子代，所有解均参加生存竞争，选出最好的参加生存竞争，选出最好的个作为下一代的亲本。在后者个作为下一代的亲本。在后者中，只有中，只有（ ）个子代参加生存竞争，在每代中）个子代参加生存竞争，在每代中个亲个亲本被完全取代。这就是说，对于每一代，每个解张成的生本被完全取代。这就是说，对于每一代，每个解张成的生命是有限的。增加种群大小，就在固定数目的世代中增加命是有限的。增加种群大小，就在固定数目的世代中增加了优化速率。了优化速率。8.2 进化策略进化策略Rechenburg引入了如下想法，在每个新样本的特征分布中附加了引入了如

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29、第i分量发生的随机数，它服从标准正态分布。分量发生的随机数，它服从标准正态分布。) 1 , 0() 1 , 0(iiiiiiiiNNxx8.3 进化规划进化规划从上式可以看出，新个体也是在旧个体的基础上添加一个随机数，从上式可以看出，新个体也是在旧个体的基础上添加一个随机数，该添加量取决于个体的方差，而方差在每次进化中又有自适应调该添加量取决于个体的方差，而方差在每次进化中又有自适应调整。这种进化方式已成为进化规划的主要手段，因此在进化规划整。这种进化方式已成为进化规划的主要手段，因此在进化规划前冠以前冠以“元元”这个术语以表示它为基本方法。这个术语以表示它为基本方法。元进化规划元进化规划(M

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

31、的不同。进化规划的计算式比进化策略的计算式简单。8.3 进化规划进化规划旋转进化规划旋转进化规划旋转进化规划旋转进化规划(Rmeta EP)进一步扩展进化规划，在表达个体时添加第三个进一步扩展进化规划，在表达个体时添加第三个因子因子协方差，用三元组表示个体，即协方差，用三元组表示个体，即(X, , )，具体计算如下：，具体计算如下：X旧个体的目标变量，其内含旧个体的目标变量，其内含n个分量；个分量；X新个体的目标变量，其内含新个体的目标变量，其内含n个分量；个分量；N(0,C)遵从正态分布的随机数，其数学期望为遵从正态分布的随机数，其数学期望为0、其标准差与协方差有、其标准差与协方差有关；关；

32、j相关系数，相关系数，) 1 , 0() 1 , 0(), 0(jjjjiiiiNNCNXXjiijjc进化规划的基本技术进化规划的基本技术表达方法表达方法采用十进制的实型数表达问题。采用十进制的实型数表达问题。X=(x1, x2, , xi, , xn)由由X和和组成的二元组组成的二元组(X, )是进化规划最常用的表达形式。有是进化规划最常用的表达形式。有人建议将进化规划再增加一个控制因子人建议将进化规划再增加一个控制因子 ，构成三元表达式，构成三元表达式(X, , )，其中，其中 =(1, 2, , j, , n)j是相关系数的单下标表达是相关系数的单下标表达, 它表示它表示xi和和xj

33、之间的协方差之间的协方差:jiijjc进化规划的基本技术进化规划的基本技术产生初始群体产生初始群体进化规划中产生初始群体的方法类似于进化策略中随机选择进化规划中产生初始群体的方法类似于进化策略中随机选择个个体作为进化计算的出发点。个个体作为进化计算的出发点。计算适应度计算适应度进化规划采用十进制实数表达问题，计算适应度比较简单直观。进化规划采用十进制实数表达问题，计算适应度比较简单直观。突变突变突变是进化规划产生新群体的唯一方法，它不采用重组或交换突变是进化规划产生新群体的唯一方法，它不采用重组或交换算子。算子。进化规划的基本技术进化规划的基本技术选择选择在进化规划中，新群体的个体数目在进化规

34、划中，新群体的个体数目等于旧群体的个体数目等于旧群体的个体数目，选择便是在选择便是在2 个个体中选择个个体中选择个个体组成新群体。个个体组成新群体。进化规划的选择采用随机型的进化规划的选择采用随机型的q竞争选择法。在这种选择方竞争选择法。在这种选择方法中，为了确定某一个体法中，为了确定某一个体 i 的优劣，我们从新、旧群体的的优劣，我们从新、旧群体的2 个个体中任选个个体中任选q个个体组成测试群体。然后将个体个个体组成测试群体。然后将个体 i 的适的适应度与应度与q个个体的适应度进行比较，记录个体个个体的适应度进行比较，记录个体 i 优于或等于优于或等于q内各个体的次数，得到个体内各个体的次数

35、，得到个体 i 的得分的得分Wi，即，即qjjiiffifW101其他优于或等于进化规划的基本技术进化规划的基本技术上述得分测试分别对上述得分测试分别对2个个体进行，每次铡试时重新选择个个体进行，每次铡试时重新选择q个个体组个个体组成新的测试群体。最后，按个体的得分选择分值高的成新的测试群体。最后，按个体的得分选择分值高的个个体组个个体组成下一代新群体。成下一代新群体。q竞争选择法是一种随机选择，总体上讲，优良个体入选的可能性竞争选择法是一种随机选择，总体上讲，优良个体入选的可能性较大。但是由于测试群体较大。但是由于测试群体q每次都是随机选择的，当每次都是随机选择的，当q个个体都不个个体都不甚

36、好时，有可能使较差的个体因得分高而入选。这正是随机选择甚好时，有可能使较差的个体因得分高而入选。这正是随机选择的本意。的本意。q竞争选择法中竞争选择法中q的大小是一个重要参数。若的大小是一个重要参数。若q很大，极端地设很大，极端地设q2，则选择变为确定性选择。反之，若，则选择变为确定性选择。反之，若q很小，则选择的随机性很小，则选择的随机性太大，不能保证优良个体入选。通常太大，不能保证优良个体入选。通常q在在10以上，可取以上，可取0.9。进化规划的基本技术进化规划的基本技术终止终止进化规划的终止准则与进化策略相同，即根据进化规划的终止准则与进化策略相同，即根据最大进化代次最大进化代次、最优个

37、体与期望值的偏差最优个体与期望值的偏差、适应度的变化趋势适应度的变化趋势以及以及最优适最优适应度与最差适应度之差应度与最差适应度之差等四个判据。等四个判据。进化规划的基本技术进化规划的基本技术进化规划的算法算法流程：进化规划的算法算法流程：(1)确定问题的表达方式。确定问题的表达方式。(2)随机产生初始群体，并计算其适应度。随机产生初始群体，并计算其适应度。(3)用下述操作产生新群体：用下述操作产生新群体：1) 突变。对旧个体添加随机量，产生新个体突变。对旧个体添加随机量，产生新个体2) 计算新个体适应度；计算新个体适应度；3) 选择。挑选优良个体组成新群体。选择。挑选优良个体组成新群体。(4

38、)反复执行反复执行(3)，直至满足终止条件，选择最佳个体作为进化规划的，直至满足终止条件，选择最佳个体作为进化规划的最优解。最优解。遗传规划遗传规划遗传算法的局限性：遗传算法的局限性：(1)不能描述层次化的问题。不能描述层次化的问题。(2)不能描述计算机程序。不能描述计算机程序。(3)缺乏动态可变性。缺乏动态可变性。1992年、美国年、美国John R. Koza正式提出遗传规划正式提出遗传规划(Genetic Programming)，用层次化的结构性语言表达问题。用层次化的结构性语言表达问题。遗传规划的最大特点，是采用层次化的结构表达问题，它类似于计算遗传规划的最大特点，是采用层次化的结构

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

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

41、简单地说，终止符表示问题的值，函数表示对值的处理。综合在一起，遗传规划的个体表示对各种值对值的处理。综合在一起，遗传规划的个体表示对各种值(终止符终止符)的处理过程的处理过程(函数函数)。 在函数集在函数集Ff1, f2, , fn中，函数中，函数fi可以是运算符、函数、说明等，可以是运算符、函数、说明等，具体有：具体有：(1) 算术运算符算术运算符，如，如+, -, *, /等。其中除号为防止计算机溢出，规定不等。其中除号为防止计算机溢出，规定不允许用零作分母，称保护性除法允许用零作分母，称保护性除法(Protected Division)，用标记。，用标记。一旦遇到分母为零时，最简单的处理方法是令其商为一旦遇到分母为零时，最简单的处理方法是令其商为1、或是重、或是重新选择算术运算符。新选择算术运算符。遗传规划的基本技术遗传规划的基本技术(2)超越函数，如超越函数，如sin, cos, tan, log, exp等。其中等。其中log要防止处理小于或要防止处理小于或等于零的数值，称保护性对数，记为等于零的数值，称保护性对数，记为Rlog其处理方法类似于。其处理方法类似于。(3)布尔运