遗传算法PPT推荐.ppt
- 文档编号:1426919
- 上传时间:2023-04-30
- 格式:PPT
- 页数:41
- 大小:487KB
遗传算法PPT推荐.ppt
《遗传算法PPT推荐.ppt》由会员分享,可在线阅读,更多相关《遗传算法PPT推荐.ppt(41页珍藏版)》请在冰点文库上搜索。
,2标准遗传算法,2.3遗传算法的若干概念,适应度(Fitness)在研究自然界中生物的遗传和进化现象时,生物学家使用适应度这个术语来度量某个物种对于生存环境的适应程度。
对生存环境适应程度较高的物种将获得更多的繁殖机会,而对生存环境适应程度较低的物种,其繁殖机会就会相对较少,甚至逐渐灭绝。
在遗传算法中,一般通过适应度函数(Fitnessfunction)来衡量某一个体的适应度高低。
2标准遗传算法,解码(Decoding)解码是将遗传算法所搜索到的最优个体的染色体转换成待求解问题的实际最优解的过程,即编码的逆过程。
2.3遗传算法的若干概念,编码(Coding)将一个待求解的问题的实际可行解从其解空间转换到遗传算法所能处理的搜索空间(即个体空间)的过程,就称为编码。
2标准遗传算法,选择操作(Selection)根据各个个体的适应度,按照一定的规则,从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。
一般地,选择操作通过选择算子(SelectionOperator)进行。
2.3遗传算法的若干概念,交叉操作(Crossover)将群体P(t)内的各个个体随机搭配成对,对每一对个体,以某个概率(称为交叉概率,CrossoverRate)遵循某一种规则交换它们之间的部分染色体。
变异操作(Mutation)对群体P(t)中的每一个个体,以某一概率(称为变异概率,MutationRate)改变某一个或某一些基因座上的基因值为其他的等位基因。
2标准遗传算法,2.4遗传算法的应用步骤,
(1)确定决策变量及各种约束条件,即确定出个体的表现型X和问题的解空间。
(2)建立优化模型,确定出目标函数的类型及其数学描述形式或量化方法。
(3)确定表示可行解的染色体编码方法,即确定出个体的基因型X*,及遗传算法的搜索空间。
编码是遗传算法解决问题的先决条件和关键步骤:
不仅决定个体基因的排列形式(从而决定选择与繁殖等操作的作用方式),而且也决定从搜索空间的基因型到解空间的表现型的解码方式(从而决定对GA所获解的翻译与理解);
决定GA搜索的困难度与复杂性;
决定对问题的求解精度。
常用的遗传算法编码方法主要有:
二进制编码、浮点数编码等。
可以证明,二进制编码比浮点数编码搜索能力强,但浮点数编码比二进制编码在变异操作上能够保持更好的种群多样性。
2标准遗传算法,2.4遗传算法的应用步骤,(4)确定解码方法,即确定出由个体基因型X*,到个体表现型X的对应关系和转换方法。
标准遗传算法多采用二进制编码方法,将决策变量用二进制字符串表示,二进制编码串的长度由所求精度决定。
然后将各决策变量的二进制编码串连接在一起,构成一个染色体。
例如:
变量x的定义域为-2,3,要求其精度为10-5,则需要将-2,3分成至少500000个等长小区域,而每个小区域用一个二进制串表示。
于是有,2L=500000,即,向上取整,可得到L=19。
即可用19位二进制串a18a17a0来表示。
例如:
对于二进制编码,其解码过程如下:
若X*的取值范围为Xl,Xr,参数的二进制编码码长为L,码串对应的十进制整数为k,则解码公式为:
式中,Xl,Xr参数最小、最大值;
L参数编码长度;
k二进制串对应的实数值。
2标准遗传算法,(5)确定个体适应度的量化评价方法,就是确定出由目标函数值到个体适应度的转换规则。
标准遗传算法的适应度函数常用一下三种:
2.4遗传算法的应用步骤,直接以待求解的目标函数为适应度函数若目标函数为最大值问题,则Fit(f(X)=f(X)若目标函数为最小值问题,则Fit(f(X)=f(X),界限构造法,优点:
简单直观;
缺点:
其一,可能不满足非负的要求;
其二,某些代求解的函数值分布相差很大,由此得到的平均适应度可能不利于体现种群的平均性能。
若目标函数为最大值问题,则,Cmax为f(x)的最大值估计。
2标准遗传算法,倒数法,若目标函数为最小值问题,则,2.4遗传算法的应用步骤,该方法是第一种方法的改进,但有时存在界限值预先估计困难或估计不精确等问题。
Cmin为f(x)的最小值估计。
若目标函数为最小值问题,则,若目标函数为最大值问题,则,C为目标函数界限的保守估计值。
2标准遗传算法,(6)确定各遗传具体操作方法。
2.4遗传算法的应用步骤,选择算子和选择操作个体选择概率的常用分配方法有以下两种:
A按比例的适应度分配(ProportionalFitnessAssignment)亦可称为选择的蒙特卡罗方法,是利用比例于各个个体适应度的概率决定其子孙的遗留可能性。
若某个个体i,其适应度为fi,则其被选取的概率表示为,显然选择概率大的个体,能多次被选中,它的遗传因子就会在种群中扩大。
B基于排序的适应度分配(Rank-basedFitnessAssignment)在基于排序的适应度分配中,种群按目标值进行排序。
适应度仅仅取决于个体在种群中的序位,而不是实际的目标值。
排序方法比比例方法表现出更好的鲁棒性,它能在一定程度上克服了比例适应度计算的尺度问题和过早收敛问题。
2标准遗传算法,2.5遗传算法的应用步骤,另外,还可采用以下的几种提高遗传算法性能的选择方法:
稳态繁殖(SteadyStateReproduction)在迭代过程中用部分优质新子个体来更新群体中部分父个体,作为下一代种群。
没有重串的稳态繁殖(SteadyStateReproductionwithoutDuplicates)在稳态繁殖的基础上,形成下一代新种群时,使其中的个体不重复。
个体选择概率确定后,可以选用的常用选择算法有轮盘赌选择法(RouletteWheelSelection)、随机遍历抽样法(StochasticUniversalSampling)、局部选择法(LocalSelection)、截断选择法(TruncationSelection)和锦标赛选择法(TournamentSelection)等。
标准遗传算法常用的轮盘赌选择法的原理如右下图所示。
pointer,关于选择算子:
如果对解的质量要求不高,要求收敛快,可取较高的选择强度;
反之,可取较低的选择强度。
标准遗传算法达到收敛的世代数与选择强度成反比。
2标准遗传算法,交叉率及交叉操作,交叉,也可以称为基因重组(Recombination),是遗传算法获取新的优良个体的最重要的手段,决定了遗传算法的全局搜索能力。
一般地,当随机产生的概率大于交叉率,遗传算法就会按一定规则选择两个个体,执行交叉操作。
交叉率的选择决定了交叉的频率,较大的交叉率使各代充分交叉,但群体中的优良模式遭到破坏的可能性增大,以致产生较大的代沟,从而使搜索走向随机化;
交叉率越低,产生的代沟越小,就会使得更多的个体直接复制到下一代,遗传搜索可能陷入停滞状态,一般建议取值范围0.40.9。
对于二进制编码,常用的交叉方法有:
单点交叉、多点交叉和均匀交叉等。
一个单点交叉的例子如下图所示。
2标准遗传算法,变异率及变异操作变异本身是一种局部随机搜索,使遗传算法具有局部的随机搜索能力;
同时使得遗传算法保持种群的多样性,以防止出现非成熟收敛。
一般地,随机产生的概率大于变异率就会触发变异操作。
变异率一般可取0.0010.1。
变异率不能取得太大,如果大于0.5,遗传算法就退化为随机搜索,而遗传算法的一些重要的数学特性和搜索能力也不复存在了。
常用的变异操作方法有:
实值变异法和二进制变异法等。
实值变异法,a(i)以概率1/m取值1,以概率1-1/m取值0,通常m=20,此外,还有部分匹配交叉(PartiallyMatchedCrossover)、顺序交叉(OrderedCrossover)、洗牌交叉(ShuffleCrossover)等等。
二进制变异法,2标准遗传算法,(7)确定遗传算法的有关运行参数,包括群体规模(PopulationSize)、迭代次数(一般取为100500)、选择算子、交叉率、变异率等等。
(8)初始化群体。
初始群体一般随机产生初始值最好能在解空间中均匀采样(收敛速度比较快)对于非二进制编码,还要考虑所生成的染色体是否在可行区域内。
(9)计算群体中个体解码后的适应值。
(10)按照遗传策略,运用所选定的选择、交叉和变异算子作用于群体,生成下一代群体。
(11)判断群体性能是否满足某一指标或是否完成预定迭代次数,不满足则返回(9)。
popsize,取值较小时,提高运算和收敛速度,却降低了群体多样性,可能引起早熟现象,取值较大时,含有较多模式,可提高GA搜索质量,但计算量增大,收敛速度降低,一般取为20100,遗传算法具体步骤,选择编码策略,把参数集合(可行解集合)转换染色体结构空间;
定义适应度函数,便于计算适应值;
确定遗传策略,包括选择群体大小,选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数;
随机产生初始化群体;
计算群体中的个体或染色体解码后的适应值;
按照遗传策略,运用选择、交叉和变异算子作用于群体,形成下一代群体;
判断群体性能是否满足某一指标,或者已完成预定的迭代次数,不满足则返回第五步,或者修改遗传策略再返回第六步,2标准遗传算法,例1利用遗传算法求解区间0,31上的二次函数y=x2的最大值,精度要求达到个位。
3、遗传算法简单举例:
函数极值,分析原问题可转化为在区间0,31中搜索能使y取最大值的点a的问题。
那么,0,31中的点x就是个体,函数值f(x)恰好就可以作为x的适应度,区间0,31就是一个(解)空间。
这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。
函数极值,
(1)设定种群规模,编码染色体,产生初始种群。
将种群规模设定为4;
用5位二进制数编码染色体;
取下列个体组成初始种群S1:
s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)
(2)定义适应度函数,取适应度函数:
f(x)=x2,3、遗传算法简单举例:
函数极值,(3)计算各代种群中的各个体的适应度,并对其染色体进行遗传操作,直到适应度最高的个体(即31(11111))出现为止。
首先计算种群S1中各个体s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)的适应度f(si)。
容易求得:
f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361,3、遗传算法简单举例:
函数极值,再计算种群S1中各个体的选择概率。
选择概率的计算公式为,由此可求得P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31,3、遗传算法简单举例:
函数极值,轮盘赌选择示意图,3、遗传算法简单举例:
函数极值,选择-复制,于是,经选择复制得群体:
s1=11000(24),s2=01101(13)s3=11000(24),s4=10011(19),3、遗传算法简单举例:
函数极值,交叉设交叉率pc=100%,即S1中的全体染色体都参加交叉运算。
设s1与s2配对,s3与s4配对。
分别交换后两位基因,得新染色体:
s1=11001(25),s2=01100(12)s3=11011(27),s4=10000(16),3、遗传算法简单举例:
函数极值,变异设变异率pm=0.001。
这样,群体S1中共有540.001=0.02位基因可以变异。
0.02位显然不足1位,所以本轮遗传操作不做变异。
于是,得到第二代种群S2:
函数极值,第二代种群S2中各染色体的情况,3、遗传算法简单举例:
函数极值,假设这一轮选择-复制操作中,种群S2中的4个染色体都被选中,则得到群体:
s1=11001(25),s2=11011(27)s3=11011(27),s4=10000(16),做交叉运算,让s1与s2,s3与s4分别交换后三位基因,得,s1=11100(28),s2=01001(9)s3=11000(24),s4=10011(19),这一轮仍然不会发生变异。
于是,得第三代种群S3:
s1=11100(28),s2=01001(9)s3=11000(24),s4=10011(19),3、遗传算法简单举例:
函数极值,第三代种群S3中各染色体的情况,3、遗传算法简单举例:
函数极值,设这一轮的选择-复制结果为:
s1=11100(28),s2=11100(28)s3=11000(24),s4=10011(19),做交叉运算,让s1与s4,s2与s3分别交换后两位基因,得,s1=11111(31),s2=11100(28)s3=11000(24),s4=10000(16),这一轮仍然不会发生变异。
于是,得第四代种群S4:
s1=11111(31),s2=11100(28)s3=11000(24),s4=10000(16),3、遗传算法简单举例:
函数极值,显然,在这一代种群中已经出现了适应度最高的染色体s1=11111。
于是,遗传操作终止,将染色体“11111”作为最终结果输出。
然后,将染色体“11111”解码为表现型,即得所求的最优解:
31。
将31代入函数y=x2中,即得原问题的解,即函数y=x2的最大值为961。
函数极值,Y,用粒子群算法对文档中的函数进行运算,例如运算100代,把每一代的最优个体的函数值记录下来,则得到了一个1*100的行矩阵A,同样利用遗传算法对这个函数进行运算,运算100代,得到了一个1*100的行矩阵B,以数字1,2,3,.,100为横坐标,行矩阵A和B分别为纵坐标,利用plot函数在一个坐标系内画出两条曲线,并利用xlabel,ylabel,title等命令给图像加上注释。
发送邮件时间:
2015年1月22日24:
00前纸质作业交到班长处。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遗传 算法