GA遗传算法简介解读.ppt_第1页
GA遗传算法简介解读.ppt_第2页
GA遗传算法简介解读.ppt_第3页
GA遗传算法简介解读.ppt_第4页
GA遗传算法简介解读.ppt_第5页
免费预览已结束,剩余24页可下载查看

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、主要内容,一、遗传算法概述 二、遗传算法的基本操作 三、遗传算法原理 四、遗传算法的应用,1、遗传算法起源,遗传算法(Genetic Algorithm, GA)是由美国的J. Holland教授于1975年在他的专著自然界和人工系统的适应性中首先提出的,它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。GA来源于达尔文的进化论、魏茨曼的物种选择学说和孟德尔的群体遗传学说。其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索全局最优解的算法。,一、遗传算法概述,2、生物进化理论和遗传学基本知识,一、遗传算法概述,(1) 达尔文的自然选择说,遗传(heredity): 子代和父

2、代具有相同或相似的性状,保证物种的稳定性,变异(variation): 子代与父代,子代不同个体之间总有差异,是生命多样性的根源,生存斗争和适者生存: 具有适应性变异的个体被保留,不具适应性变异的个体被淘汰,一、遗传算法概述,2、生物进化理论和遗传学基本知识,(2) 遗传学基本概念和术语,基因(gene):染色体的一个片段,染色体(Chromosome):问题中个体的某种字符串形式的编码表示,种群(Population):个体的集合,该集合内的个体数称为种群的大小,基因型(genetype):基因组合的模型,染色体的内部表现,表现型(phenotype):染色体决定性状的外部表现,个体 染色体

3、 9 - 1001,一、遗传算法概述,2、生物进化理论和遗传学基本知识,(2) 遗传学基本概念和术语,进化(evolution):个体逐渐适应生存环境,不断改良品质的过程,适应度(fitness):反映个体性能的一个数量值,编码(coding):从表现型到基因型的映射,解码(decoding):从基因型到表现性的映射,适应度函数(fitness function): 问题中的全体个体与其适应度之间的一个对应关系,一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。,1 选择-复制(selection-reproduction),二、遗传算法的基本操作,选择-复制指的就是以一定的概率从种

4、群中选择若干个体并进行复制的操作, 轮盘赌选择(roulette wheel selection) 随机遍历抽样(stochastic universal selection) 局部选择(local selection) 截断选择(truncation selection) 锦标赛选择(tournament selection),选择概率P(xi)的计算公式为:,常用选择-复制方法:,1 选择-复制(selection-reproduction),二、遗传算法的基本操作,例:轮盘赌选择,解 (1)计算选择概率和累计概率,1 选择-复制(selection-reproduction),二、遗传算

5、法的基本操作,复制操作能从旧种群中选择出优秀者,但不能创造新的染色体!,(2)在0-1之间产生一个随机数,0.507893 6 0.070221 1 0.545929 8 0.784567 9 0.446930 6 0.291198 5 0.716340 8 0.271901 4 0.371435 6 0.854641 10,2 交叉(crossover)基因重组,二、遗传算法的基本操作,交叉就是互换两个染色体某些位上的基因,s1=01000101, s2=10011011 可以看做是原染色体s1和s2的子代染色体,例:设染色体s1=01001011, s2=10010101,交换其后4位基因

6、,即,单点交叉,2 交叉(crossover)基因重组,二、遗传算法的基本操作,其它常用的交叉方法:,多点交叉(multiple-point crossover) 均匀交叉(uniform crossover) 部分匹配交叉(Partially Matched Crossover) 顺序交叉(Ordered Crossover) 循环交叉(Cycle Crossover),交叉模拟了生物进化过程中的繁殖现象,通过两个染色体的交换组合,来产生新的优良品种!,3 变异(mutation),变异就是改变染色体某个(些)位上的基因,例如,设染色体s=11001101,将其第三位上的0变为1, 即 s=

7、11001101 11101101= s。 s也可以看做是原染色体s的子代染色体,变异运算用来模拟生物在自然的遗传环境中由于各种偶然因素引起的基因突变.若只有选择和交叉,而没有变异,则无法在初始基因组合以外的空间进行搜索,使进化过程在早期就陷入局部解而进入终止过程,从而影响解的质量!,二、遗传算法的基本操作,三、遗传算法的原理,标准遗传算法流程框图,适者生存,关键,三、遗传算法的原理,算法中的一些控制参数: 种群规模: 最大换代数: 交叉率(crossover rate): 参加交叉运算的染色体个数占全体染色体总数的比例,记为Pc 取值范围一般为0.40.99 变异率(mutation rat

8、e): 发生变异的基因位数所占全体染色体的基因总位数的比例,记为Pm 取值范围一般为0.00010.1,三、遗传算法的原理,标准遗传算法(Standard genetic algorithm, SGA),Step1 在搜索空间U上定义一个适应度函数f(x),给定种群规模N,交叉率Pc和变异率Pm,代数T;,Step2 随机产生U中的N个个体s1, s2, , sN,组成初始种群S=s1, s2, , sN,置代数计数器t=1;,Step3 计算S中每个个体的适应度f(x);,Step4 若终止条件满足,则取S中适应度最大的个体作为所求结果,算法结束。否则,转Step5;,Step5 按选择概率

9、P(xi)所决定的选中机会,每次从S中随机选定1个个体并将其复制,共做N次,然后将复制所得的N个染色体组成群体S1;,Step6 按交叉率Pc所决定的参加交叉的染色体数c,从S1中随机确定c个染色体,配对进行交叉操作,并用产生的新染色体代替原染色体,得群体S2;,Step7 按变异率Pm所决定的变异次数m,从S2中随机确定m个染色体,分别进行变异操作,并用产生的新染色体代替原染色体,得群体S3;,Step8 将群体S3作为新一代种群,即用S3代替S,t = t+1,转步Step3;,三、遗传算法的原理,标准遗传算法(Standard genetic algorithm, SGA),四、遗传算法

10、的应用,1、遗传算法的应用领域,(1)组合优化 (2)函数优化 (3)自动控制 (4)生产调度 (5)图像处理 (6)机器学习 (7)人工生命 (8)数据挖掘,2、遗传算法的应用举例,四、遗传算法的应用,例:求下列一元函数的最大值:,x-1,2,求解结果精确到6位小数。,四、遗传算法的应用,用微分法求解:,当i为奇数时xi对应局部极大值点,i为偶数时xi对应局部极小值 x19即为区间-1,2内的最大值点,此时,函数最大值f(x19)比f(1.85)=3.85稍大,四、遗传算法的应用,用遗传算法求解:,分析:由于区间长度为3,求解结果精确到6位小数,因此可将自变量定义区间划分为3106等份。又因

11、为221 3106 222 ,所以本例的二进制编码长度至少需要22位,编码过程实质上是将区间-1,2内对应的实数值转化为一个二进制串(b21b20b0)。,求解过程:,(1)编码,表现型: x 基因型: 二进制编码,串长22位,几个术语,基因型:1000101110110101000111,表现型:0.637197,编码,解码,个体(染色体),基因,四、遗传算法的应用,(2)生成初始种群,用遗传算法求解:,方式:随机生成长度为22的二进制制串 数量:种群的大小(规模),如30,50, 1111010011100001011000 1100110011101010101110 101010001

12、1110010000100 1011110010011100111001 0001100101001100000011 0000011010010000000000 ,四、遗传算法的应用,(3)计算适应度,用遗传算法求解:,不同的问题有不同的适应度计算方法,本例直接用目标函数作为适应度函数,计算x的函数值(适应度):,(4)遗传操作,选择:轮盘赌选择法 交叉:单点交叉 变异:小概率变异,四、遗传算法的应用,用遗传算法求解:,(5)模拟结果,设置的参数: 种群大小50,交叉概率0.75 变异概率0.05,最大代数200,得到的最佳个体: smax= xmax=1.8506 f(xmax)=3.8503,遗传算法的本质,遗传算法本质上是对染色体模式所进行的一系列运算,即通过选择算子将当前种群中的优良模式遗传到下一代种群中,利用交叉算子进行模式重组,利用变异算子进行模式突变。通过这些遗传操作,模式逐步向较好的方向进化,最终得到问题的最优解。,小结,1、遗传算法优点:,搜索过程不直接作用在变量上,而是对参数集进行了编码的个体上 搜索过程是迭代的过程,具有并行性 利用概率转移规则,可在一个不确定的空间上寻优 不是从一点出发沿一条线搜索,而是在整个空间上搜索,从而找到全局最优解 对搜索空间无任何特殊要求(连通,凸性) 容错能力强,2、遗传算法存在的问题:,编码问题:编码选择不当使G

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论