其他进化算法(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)根据遗传参数,用
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 其他 进化 算法 new
链接地址:https://www.31doc.com/p-4129379.html