进化策略和进化规划课件

《进化策略和进化规划课件》由会员分享，可在线阅读，更多相关《进化策略和进化规划课件（42页珍藏版）》请在金锄头文库上搜索。

1、进化策略和进化规划,德国学者Schwefel和Rechenburg美国学者Fogel分别提出进化策略ES和进化规划EP。这三种方法具有共同的本质，分别强调了自然进化中的不同方面：遗传算法强调染色体的操作，进化策略强调了个体级的行为变化。而进化规划则强调种群级上的行为变化。现在学术界把遗传算法GA、进化策略ES和进化规划EP通称为进化算法EC。,8.1 进化算法的早期研究,进化算法起源于20世纪30年代的通过仿真生物进化过程进行机器学习的研究。早在1932年，Cannon就把自然进化想象为一个学习过程。与自然进化过程的机制和结果稍微不同是，Cannon不是通过维持一个特定的种群来进行搜索，而是对

2、单个个体反复进行随机试验。到了1950年，Turng认识到，在机器学习和进化之间存在着明显的关系。1959年，Friedman推测，利用变异和选择的仿真可以设计“思想机器”，并且指出下棋的程序可以用这种方法设计。在1960年，Cambell猜想：在导致知识扩张的所有过程中，都要涉及“盲目变化选择幸存”的过程。此后，一些学者逐渐将进化理论用于随机工程控制、机器学习和函数优化等领域。,8.2 进化策略,进化策略（Evolutionary Strategies）是在1965年由Rechenburg和Schwefel独立提出的。 早期的进化策略的种群中只包含一个个体，并且只使用变异操作。在每一代中，变

3、异后的个体与其父代进行比较，并选择较好的一个，这种选择策略被称为（1+1）策略。 进化策略中的个体用传统的十进制实型数表示，即： Xt第t代个体的数值， N(0,)服从正态分布的随机数，其均值为零，标准差为。,8.2 进化策略,进化策略的一般算法可以描述如下： 问题为寻找实值n维矢量x，使得函数F(x):RnR取极值。不失一般性，设此程序为极小化过程。 从各维的可行范围内随机选取亲本xi，i1，p的初始值。初始试验的分布一般是均匀分布。 通过对于x的每个分量增加零均值和预先选定的标准差的高斯随机变量，从每个亲本xi产生子代xi。 通过将误差F(xi)和F(xi)，i1，p进行排序，选择并决定哪

4、些矢量保留。具有最小误差的p个矢量变成下一代的新亲本。 进行新试验，选择具有最小方差的新子代，一直到获得充分解，或者直到满足某个终止条件,8.2 进化策略,在这个模型中，把试验解的分量看做个体的行为特性，而不是沿染色体排列的基因。可以和GA一样，假设这些表现型特征具有基因根源，但是它们之间的联系实质并没有被弄清楚，所以我们把着重点放在个体的行为特性上。 假设不管发生什么遗传变换，所造成各个行为的变化均遵循零均值和某个标准差的高斯分布。 由于基因多效性和多基因性，特定基因的改变可以影响许多表现型特征。所以在创造新子代时，较为合适的是同时改变亲本所有分量。,8.2 进化策略,进化策略的最初试验采用

5、上述算法，主要采用单亲本单子代的搜索，即“（1+1）进化策略(1+1)-ES)”，其中单个子代是由单个亲本产生的，它们都被置于生存竞争中，较弱的一个要被挑选出来消去。 当把这种算法用于函数优化时，发现它有两个缺点： 各维取定常的标准差使得程序收敛到最优解的速度很慢； 点到点搜索的脆弱本质使得程序在局部极值附近容易受停滞的影响（虽然此算法表明可以渐近地收敛到全局最优点）。,8.2 进化策略,( + 1)-ES: 早期的(1十1)-ES，没有体现群体的作用，只是单个个体在进化，具有明显的局限性。随后，Rechenberg又提出(+1)-ES，在这种进化策略中，父代有个个体(1)，并且引入重组(Re

6、combination)算子，使父代个体组合出新的个体。在执行重组时，从个父代个体中用随机的方法任选两个个体：,8.2 进化策略,然后从这两个个体中组合出如下新个体： 式中qi1或2，它以相同的概率针对i1，2，n随机选取。 对重组产生的新个体执行突变操作，突变方式及的调整与(1+1)-ES相同。 将突变后的个体与父代个个体相比较，若优于父代最差个体，则代替后者成为下一代个个体新成员，否则，重新执行重组和突变产生另一新个体，,8.2 进化策略,(+1)-ES和(1+1)-ES具有相同的策略：只产生一个新个体。(+1)-ES的特点在于： (1) 采用群体，其中包含个个体； (2) 增添重组算子，

7、它相当于遗传算法中的交叉算子，从父代继承信息构成新个体。 显然，(+1)-ES比(1+1)-ES有了明显的改进，为进化策略这种新的进化算法奠定良好的基础。,8.2 进化策略,在1973年，Rechenburg把该算法的期望收敛速度定义为对最优点的平均距离与要得到此改善所需要的试验次数之比。 1981年，Schwefel在进化策略中使用多重亲本和子代，这是Rechenburg早期工作（使用多重亲本，但是仅使用单个子代）的发展，后来考察了两种方法，分别表示为(+)-ES和(，)-ES。在前者中，个亲本制造个子代，所有解均参加生存竞争，选出最好的个作为下一代的亲本。在后者中，只有（ ）个子代参加生存

8、竞争，在每代中个亲本被完全取代。这就是说，对于每一代，每个解张成的生命是有限的。增加种群大小，就在固定数目的世代中增加了优化速率。,8.2 进化策略,Rechenburg引入了如下想法，在每个新样本的特征分布中附加了一个自适应参数。在这个方法中，每个解矢量不仅包括了n维试验矢量x，而且还包括了扰动矢量，后者给出如何变异x以及它本身如何变异的指令。例如，设x为当前矢量， 为对应于x每个维的方差矢量，于是新的解矢量x， 可以这样产生： N(0,1)表示单个标准高所随机变量， Ni(0,1)表示第i个独立相同的标准高斯分布，和是影响总体和个体步长的算子集参数。以这种方式，进化策略可以在线地适应误差曲

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

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

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

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

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

14、00。,8.3 进化规划,进化规划(Evolutionary Programming)由Fogel在20世纪60年代所提出。Fogel将仿真进化方法用于由相互竞争的算法所构成的种群，在一系列研究中探索了进化规划的可能性，目的是发展人工智能。Fogel认为，智能行为需要有如下的复合能力： (1)预报它的环境； (2)把预报变成对于给定目标的适当响应。,8.3 进化规划,标准进化规划 进化规划用传统的十进制实数表达问题。在标准进化规划（Standard EP）中，个体的表达形式为： 式中：xi旧个体目标变量X的第i个分量， xi新个体目标变量X的第i个分量， f(X)旧个体X的适应度； N(0,

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

16、ard EP流程： 生成初始群体； While Not-End Do 突变； 计算个体适应度； 选择； 组成新群体 End While,8.3 进化规划,元进化规划 为了增加进化规划在进化过程中的自适应调整功能，人们在突变中添加方差的概念。类似于进化策略，在进化规划中个体的表达采用下述方式： 式中：i旧个体第 i 分量的标准差； i新个体第 i 分量的标准差； N(0, 1)针对第i分量发生的随机数，它服从标准正态分布。,8.3 进化规划,从上式可以看出，新个体也是在旧个体的基础上添加一个随机数，该添加量取决于个体的方差，而方差在每次进化中又有自适应调整。这种进化方式已成为进化规划的主要手段，因此在进化规划前冠以“元”这个术语以表示它为基本方法。 元进化规划(Met