遗传算法的编码与适应度函数课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《遗传算法的编码与适应度函数课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遗传 算法 编码 适应 函数 课件
- 资源描述:
-
1、遗传算法的编码与适应度函数遗传算法的编码与适应度函数姓名:赵文娟学号:30808120304遗传算法的特点:n(1)遗传算法不是直接作用在参变量集上,而是利用参变量集的某种编码;n(2)遗传算法不是从单个点,而是从一个点的群体开始搜索;n(3)遗传算法利用适应值信息,无需导数或其它辅助信息;n(4)遗传算法利用概率转移规则,而非确定性规则。遗传算法的编码和适应度函数的重要性n遗传编码是整个遗传算法执行的基础n遗传算法的适应度函数 (Fitness Function)的选取直接影响到遗传算法的收敛速度以及能否找到最优解,因为遗传算法在进化搜索中基本不利用外部信息,仅以适应度函数为依据,利用种群每
2、个个体的适应度来进行搜索。 遗传算法的基本定理n模式就是一个相同的构形,它描述的是一个串的子集,这个集合中的串之间在某些位上是相同的。 n一个模式H的阶就是出现在模式中确定位置的数目,记为o(H) 。n一个模式的定义长度是模式中第一个确定位置和最后一个确定位置之间的距离,记为(H)。模式的概念说明 V+=0,1,* 模式,*代表不确定字母. 串长为L的二进制串上的模式共有3l个.一般的,对于基数为k的字母表,共有(k+1)l个模式 例如:串长为7的模式H=*11*0* ,A=0111000是模式H的一个表示。 所有模式并不是以同等机会产生的,有些模式比起其它的更加确定,例如:与0*相比,模式0
3、11*1*在相似性方面是更明确的表示。n一个模式H的阶出现在模式中确定位置的数目 。 例如:模式011*1*的阶为4可记为,o(011*1*)=4 ;模式0*的阶为1 。n一个模式的定义长度模式中第一个确定位置和最后一个确定位置之间的距离 。 例如:模式011*1*的定义长度为4,可记为=4;0*的定义长度为=0。 注:串的阶和定义长度是用于讨论串的相似性的符号。 n在复制阶段,每个串根据它的适应度值进行复制,更确切的说,一个串Ai的复制概率为:n m(H,t+1)= m(H,t)nf(H)/ 其中f(H)是在第t代中模式H的串的平均适应值。n整个群体的平均适应值可记为 /n故模式的复制生长方
4、程可以表示为:m(H,t+1)= m(H,t)/ n一个特定的模式按照其平均适应值与群体的平均适应值之间的比率生长 njfifipi1 njfi1njfi1ffn下面推出一个定量表达式,假设某一特定模式下的适应值高出群体平均适应值以上一个c,c为一常数,则模式的复制生长方程可变为:nm(H,t+1)= m(H,t)=(1+c)m(H,t) 从t=0开始,假设c是一个固定值,可以推得: m(H,t)= m(H,0)(1+c)t t 上式表明,在群体平均适应度以上(以下)的模式将会以指数增长(衰减)的方式被复制。 模式定理n模式的阶和定义长度两个概念提供了一个分析遗传算法中遗传算子对包含在群体中基
5、因块的作用效果的基本的方法。nm=m(H,t),第t代中模式H有m个代表串包含在群体中A(t)中的样本。t不同,m也不同。n模式定理模式定理:遗传算法中,在选择、交叉、编译算子的作用下,具有低阶、短的定义长度,且平均适应度高于群体平均适应度的模式将按指数级增长。遗传算法的编码原则n编码原则一(有意义积木块编码原则):应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案。n编码原则二(最小字符集编码原则):应使用能使问题得到自然表示或描述的最小编码字符集的编码方案常用的编码方法n二进制编码n格雷编码n浮点数编码n符号编码n混合编码二进制编码n简单易行n符合最小字符集编码规则n便于
6、用模式定理进行分析, 因为模式定理就是以二进制编码为基础提出的。格雷编码n格雷编码有这样一个特点:任意两个整数的差是这两个整数所对应的格雷码之间的汉明距离。这个特点是遗传算法使用格雷来进行个体编码的主要原因。n由二进制码到格雷码的转换公式为:n由格雷码到二进制码的转换公式为: 1,.,2, 1,1mmibbgbgiiimm1,.2, 1,1mmigbbgbiiimm浮点数编码n首先,二进制编码存在着连续函数离散化时的映射误差。个体编码长度较短时达不到精度要求;个体编码较长时会使搜索空间急剧扩大。n另外,二进制编码不便于反映所求问题的特定知识,这样就不便于开发针对专门知识的遗传算子。浮点数编码的
7、优点主要有:(1)适合用在遗传算法中表示范围较大的数;(2)适合于精度要求较高的遗传算法;(3)便于较大空间的遗传搜索;(4)改善了遗传算法的计算复杂性,提高了运算效率。符号编码n符号编码是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。这个符号集是一个字母表,如:A,B,C,D,;也可以是一个数字序号表,如1,2,3,;也可以是一个代码表,如:A1,A2,A3,等等。n优点:(1)符合有意义积木块编码原则;(2)便于在遗传算法中利用所求解问题的专门知识;(3)便于遗传算法于相关近似算法之间的混合使用。多参数交叉编码n假设有n个参数,每个参数都采用码长m的二进制编码,取
展开阅读全文