版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
遗传算法的模式理论遗传算法的模式理论1从简单遗传算法的操作中,我们可以看到寻优问题的性能是朝着不断改进的方向发展的。但是我们怎么能知道对某一特定问题使用遗传算法会得到优化或接近优化的解呢?分析遗传算法中的模式理论:模式;复制对模式的影响;交叉对模式的影响;变异对模式的影响;遗传算法有效处理的模式数量。从简单遗传算法的操作中,我们可以看到寻优问题的性能是朝着不断2模式一个模式(Schemata)就是一个描述种群中在位串的某些确定位置上具有相似性的位串子集的相似性模板(SimilarityTemplate)
。例如:求maxf(x)=x2x
{0,31}遗传算法的第0代
在上列种群里的各位串之间,我们能发现具有某种相似性和这种相似性与高适配值之间具有某种因果关系。位串Xi适配值x=0110113f(x)=x2=132=16911000 2457601000 8641001119361模式一个模式(Schemata)就是一个描述种群中在位串的某3
这种因果关系例如:凡是以“1”开始的位串,其适配值就高;以“0”开始的位串的适配值就低。这种相似性正是遗传算法有效工作的因素。根据对种群中高适配置位串之间的相似性的分析,Holland提出了遗传算法的模式理论.这种因果关系例如:凡是以“1”开始的位串,其适配值就高;以4模式为了描述一个模式,在用以表示位串的两个字符的字母{0,1}中加入一个通配符“*”,就构成了一个表示模式用的三个字符的字母表{0,1,*}。因此用三元素字母表{0,1,*}可以构造出任意一种模式。一个模式与一个特定位串相匹配是指:该模式中的1与位串中的1相匹配,模式中的0与位串的0相匹配,模式中的“*”可以匹配位串中的0或1。模式为了描述一个模式,在用以表示位串的两个字符的字母{0,15模式模式00*00匹配了两个位{00100,00000}模式*111*可以和{01110,01111,11110,11111}中的任何一个位串匹配,即与长度为5中间三位为“1”的四个位串匹配;模式0*1**则匹配了长度为5、第一位为0、第三位为1的8个位串{00100,00101,00110,00111,01100,01101,01110,01111}模式6模式的思路为我们提供了一种简单而有效的方法,使能够在有限字母表的基础上讨论有限长位串的严谨定义的相似性。应强调的是,“*”只是一个元符号,既是代表其他符号的一个符号。它不能被遗传算法直接处理,只不过是允许来描述特定长度和特定字母表的位串的所有可能相似性的符号件。模式的思路为我们提供了一种简单而有效的方法,使能够在有限字母7
8
9
10
•
个体是由二值字符集V={0,1}中的元素所组成的一个编码串;
•而模式却是由三值字符集V={0,1,*}中的元素所组成的一个编码串。模式阶(SchemaOrder)——指模式中已有明确含意(二进制字符时指0或1)的字符个数,记做o(s),式中s代表模式。例如,模式(011*1**)含有4个明确含意的字符,其阶次是4,记作o(011*1**)=4;模式(0******)的阶次是1,记作o(0******)=1。•阶次越低,模式的概括性越强,所代表的编码串个体数也越多,反之亦然;•当模式阶次为零时,它没有明确含义的字符,其概括性最强。
•个体是由二值字符集V={0,1}中的元素所组成11模式的定义长度(SchemaDefiningLength)——指模式中第一个和最后一个具有明确含意的字符之间的距离,记作
(s)。例如,模式H(011*l**)的第一个字符为0,最后一个字符为,中间有3个字符,其定义长度为5-1=4,记作
(011*1**)=4;模式H(0******)的长度是0,记作
(0******)=0;模式的定义长度(SchemaDefiningLeng12复制对模式的影响设在给定时间(代)t有N个个体,种群A(t)包含有m个特定模式H,记为
m=m(H,t)在复制过程中,A(t)中的任何一个位串Ai以概率Pi=fi/∑fi被选中并进行复制。复制对模式的影响设在给定时间(代)t有N个个体,种群A(t13因此复制后在下一代群体A(t+1)中,群体内属于模式H(或称与模式H匹配)的个体数目m(H,t+1)可用平均适应度按下式近似计算:式中——第t代属于模式H的所有个体之平均适应度;N——群体中拥有的个体数目。因此复制后在下一代群体A(t+1)中,群体内属于模式H(或14式(2-1)式(2-1)15可见,经过复制操作后,下一代中特定模式的数量H正比于所在位串的平均值与种群平均适配值的比值。时,H的数量将增加;时,H的数量将减少。 种群A(t)中的任一模式H在复制中都将按照式(2-1)的规律变化,即适配值高于种群平均值的模式在下一代中的数量增加;而适配值低于种群平均值的模式在下一代的数量将减少。
这种所有模式的增减在复制中是并行进行的,遗传算法中隐含的并行机制就在于此。可见,经过复制操作后,下一代中特定模式的数量H正比于所在位串16为了进一步分析高于平均适配值的模式数量的增长,假设(c是一个大于零的常数),则式(2-1)可重写为为了进一步分析高于平均适配值的模式数量的增长,假设17从原始种群开始(t=0),并假定是一个稳定的值,则有
可见,对于高于平均适配值的模式的数量将呈指数形
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 资阳2024年四川资阳市精神病医院招聘专业技术人员5人笔试参考题库附带答案详解带解题思路
- 2023年小学教师资格证上海市 《小学教育教学知识与能力》科目单项选择题+材料分析题+写作题真题冲刺卷9月份A卷
- 安全生产标准化安全生产管理制度(2012汇编)
- 我的母亲课件教学
- 教学课件模板教学
- 学校与养老院合作协议书
- 严格执行经济合同管理规定
- 研学承办机构比选合同
- 历史必修二18课课件
- 二年级上册18课课件
- 秋天的校园写作指导课件
- 胸痛单元建设课件
- 2021年成都经开国投集团有限公司校园招聘笔试试题及答案解析
- 园林(景观)施工图读图与识图课件
- 《人生海海》读书笔记PPT
- 物业公司应急管理制度
- 某项目整体园区运营成本经济测算
- 铝合金铸造标准工艺
- 混凝土道路改沥青路面方案
- 先进热障涂层的概述课件
- 泛谈华语流行歌曲歌词的语言现象
评论
0/150
提交评论