版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
遗传算法的编码与适应度函数姓名:赵文娟学号:30808120304遗传算法的编码与适应度函数姓名:赵文娟1遗传算法的特点:(1)遗传算法不是直接作用在参变量集上,而是利用参变量集的某种编码;(2)遗传算法不是从单个点,而是从一个点的群体开始搜索;(3)遗传算法利用适应值信息,无需导数或其它辅助信息;(4)遗传算法利用概率转移规则,而非确定性规则。遗传算法的特点:(1)遗传算法不是直接作用在参变量集上,而是2遗传算法的编码和适应度函数的重要性遗传编码是整个遗传算法执行的基础遗传算法的适应度函数(FitnessFunction)的选取直接影响到遗传算法的收敛速度以及能否找到最优解,因为遗传算法在进化搜索中基本不利用外部信息,仅以适应度函数为依据,利用种群每个个体的适应度来进行搜索。
遗传算法的编码和适应度函数的重要性遗传编码是整个遗传算法执行3遗传算法的基本定理模式就是一个相同的构形,它描述的是一个串的子集,这个集合中的串之间在某些位上是相同的。一个模式H的阶就是出现在模式中确定位置的数目,记为o(H)。一个模式的定义长度是模式中第一个确定位置和最后一个确定位置之间的距离,记为(H)。遗传算法的基本定理模式就是一个相同的构形,它描述的是一个串的4模式的概念说明
V+={0,1,*}—模式,*代表不确定字母.串长为L的二进制串上的模式共有3l个.一般的,对于基数为k的字母表,共有(k+1)l个模式例如:串长为7的模式H=*11*0**,A=0111000是模式H的一个表示。
所有模式并不是以同等机会产生的,有些模式比起其它的更加确定,例如:与0******相比,模式011*1**在相似性方面是更明确的表示。模式的概念说明V+={0,1,*}—模式,*代表不确5一个模式H的阶——出现在模式中确定位置的数目。例如:模式011*1**的阶为4可记为,o(011*1**)=4;模式0******的阶为1。一个模式的定义长度——模式中第一个确定位置和最后一个确定位置之间的距离。例如:模式011*1**的定义长度为4,可记为=4;0******的定义长度为=0。
注:串的阶和定义长度是用于讨论串的相似性的符号。
一个模式H的阶——出现在模式中确定位置的数目。6在复制阶段,每个串根据它的适应度值进行复制,更确切的说,一个串Ai的复制概率为:
m(H,t+1)=m(H,t)·n·f(H)/
其中f(H)是在第t代中模式H的串的平均适应值。整个群体的平均适应值可记为/n故模式的复制生长方程可以表示为:m(H,t+1)=m(H,t)·/
一个特定的模式按照其平均适应值与群体的平均适应值之间的比率生长
在复制阶段,每个串根据它的适应度值进行复制,更确切的说,一个7遗传算法的编码与适应度函数课件8下面推出一个定量表达式,假设某一特定模式下的适应值高出群体平均适应值以上一个c,c为一常数,则模式的复制生长方程可变为:m(H,t+1)=m(H,t)=(1+c)·m(H,t)从t=0开始,假设c是一个固定值,可以推得:m(H,t)=m(H,0)·(1+c)t上式表明,在群体平均适应度以上(以下)的模式将会以指数增长(衰减)的方式被复制。下面推出一个定量表达式,假设某一特定模式下的适应值高出群体平9模式定理模式的阶和定义长度两个概念提供了一个分析遗传算法中遗传算子对包含在群体中基因块的作用效果的基本的方法。m=m(H,t),第t代中模式H有m个代表串包含在群体中A(t)中的样本。t不同,m也不同。模式定理:遗传算法中,在选择、交叉、编译算子的作用下,具有低阶、短的定义长度,且平均适应度高于群体平均适应度的模式将按指数级增长。模式定理模式的阶和定义长度两个概念提供了一个分析遗传算法中遗10遗传算法的编码原则编码原则一(有意义积木块编码原则):应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案。编码原则二(最小字符集编码原则):应使用能使问题得到自然表示或描述的最小编码字符集的编码方案遗传算法的编码原则编码原则一(有意义积木块编码原则):应使用11常用的编码方法二进制编码格雷编码浮点数编码符号编码混合编码常用的编码方法二进制编码12二进制编码简单易行符合最小字符集编码规则便于用模式定理进行分析,因为模式定理就是以二进制编码为基础提出的。二进制编码简单易行13格雷编码格雷编码有这样一个特点:任意两个整数的差是这两个整数所对应的格雷码之间的汉明距离。这个特点是遗传算法使用格雷来进行个体编码的主要原因。由二进制码到格雷码的转换公式为:由格雷码到二进制码的转换公式为:
格雷编码格雷编码有这样一个特点:任意两个整数的差是这两个整数14浮点数编码首先,二进制编码存在着连续函数离散化时的映射误差。个体编码长度较短时达不到精度要求;个体编码较长时会使搜索空间急剧扩大。另外,二进制编码不便于反映所求问题的特定知识,这样就不便于开发针对专门知识的遗传算子。浮点数编码首先,二进制编码存在着连续函数离散化时的映射误差。15浮点数编码的优点主要有:(1)适合用在遗传算法中表示范围较大的数;(2)适合于精度要求较高的遗传算法;(3)便于较大空间的遗传搜索;(4)改善了遗传算法的计算复杂性,提高了运算效率。浮点数编码的优点主要有:16符号编码符号编码是指个体染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。这个符号集是一个字母表,如:{A,B,C,D,…};也可以是一个数字序号表,如{1,2,3,…};也可以是一个代码表,如:{A1,A2,A3,…}等等。优点:(1)符合有意义积木块编码原则;(2)便于在遗传算法中利用所求解问题的专门知识;(3)便于遗传算法于相关近似算法之间的混合使用。符号编码符号编码是指个体染色体编码串中的基因值取自一个无数值17多参数交叉编码假设有n个参数,每个参数都采用码长m的二进制编码,取各参数编码串中的最高位联在一起,作为个体编码的前n位编码、再取次高位联在一起作为个体第二组n位编码,….,再取最后一位联在一起作为编码的最后n位。这种编码方式中,各个参数的局部编码结构就不易被遗传算子破坏掉,它适合于各参数之间的相互关系较弱,特别是某一各或少数几个参数其主要作用时的优化问题。
多参数交叉编码假设有n个参数,每个参数都采用码长m的二进制编18适应度函数传算法中使用适应度这个概念来度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最有解的优良程度。适应度高的个体遗传到下一代的可能性比较大,而适应度比较低的个体遗传到下一代的概率相对小一些。度量个体适应度的函数称为适应度函数。适应度函数传算法中使用适应度这个概念来度量群体中各个个体在优19目标函数与适应度函数遗传算法的一个特点就是它仅使用所求问题的目标函数值就可得到下一步的有关搜索信息。而对目标函数值的使用是通过评价个体的适应度来体现的。评价个体适应度的过程一般是:(1)对个体编码串进行解码处理后,可得到个体的表现型;(2)有个体表现型可计算出对应个体的目标函数值;(3)根据最优化问题的类型,有目标函数值按一定转换规则求出个体的适应度。目标函数与适应度函数遗传算法的一个特点就是它仅使用所求问题的20最优化问题最优化问题可以分为两大类,一类为求目标函数的全局最大值,另一类为求目标函数的全局最小值。对于目标函数最小值的优化问题可转化为:minf(X)=max(-f(X))当优化目标是函数的最大值,并且目标函数总取正时,可以直接设定个体适应度F(x)为:F(x)=f(x)最优化问题最优化问题可以分为两大类,一类为求目标函数的全局最21遗传算法的编码与适应度函数课件22注:Cmax和Cmin最好与种群无关注:Cmax和Cmin最好与种群无关23遗传算法的编码与适应度函数课件24我们希望在遗传算法运行的初期,算法能对一些适应度较高的个体进行控制,降低其适应度与其他个体适应度之间的差异程度,从而限制复制数量,以维护群体的多样性。在遗传运算后期,算法能对个体适应度进行适当放大,扩大最佳个体适应度与其它适应度之间的差异程度,以提高个体之间的竞争性。目前常用的个体适应度尺度变换方法主要有三种:线性尺度变换、乘幂尺度变换、指数尺度变换。我们希望在遗传算法运行的初期,算法能对一些适应度较高的个体进25线性尺度变换F’=aF+b,F为原适应度;F’为变换后的新适应度,a和b位系数。系数a和b直接影响到这个尺度变换的大小,所以对其选择有一定的要求,一般要满足以下条件:F’avg=Favg,这条要求是为了保证群体中适应度接近于平均适应度的个体能够有期待的数量被遗传到下一代种群中。F’max=C·Favg,C为最佳个体的期望复制数量。这条要求是为了保证群体中做好的个体能够期望复制C倍到新一代群体中。
线性尺度变换F’=aF+b,F为原适应度;F’为变换后的新适26使用线性变换时,群体中有少数几个优良个体的适应度按比例缩小,同时几个较差的个体适应度也按比例扩大。在搜索的后期阶段,随着个体适应度从总体上的不断改进,群体中个体的最大适应度和全部个体的平均适应度较接近,而少数几个较差的个体的适应度却远远小于最大适应度,这时若想维持F’max和Favg的指定倍数关系,将有可能会使较差的个体适应度变换为负值。解决上述问题的方法是:把原最小适应度Fmin映射为F’min=0,并且保持原平均适应度Favg与新的平均适应度F’avg相等。使用线性变换时,群体中有少数几个优良个体的适应度按比例缩小,27乘幂尺度变换F’=Fk新的适应度是原有适应度的某个指定乘幂。幂指数k与所求解的问题有关,并且在算法的执行过程中需要不断对其进行修正才能使尺度变换满足一定的伸缩要求。机器视觉中k的最佳取值为1.005。
乘幂尺度变换F’=Fk新的适应度是原有适应度的某个指定乘幂。28指数尺度变换F’=exp(-F)新的适应度使原有适应度的某个指数。式中系数决定了选择的强制性,越小,原有的是适应度较高的个体的新适应度就越与其它个体的新适应度相差较大,亦即越增加了选择该个体的强制性。指数尺度变换F’=exp(-F)29遗传算法的编码与适应度函数课件30适应度函数的设计
(1)单值、连续、非负、最大化适应度函数F(X)应该是实函数,并且单值、连续,但不要求可导。不过,F(X)的曲线在重要部位,特别在最优解附近一般不宜太陡也不宜过于平缓。适应度函数的设计(1)单值、连续、非负、最大化31(2)计算量小F(X)不应设计得过于繁复,应在上述条件下越简单越好。适应度函数的设计
(2)计算量小适应度函数的设计32(3)通用性一个适应度函数的好坏,还应满足尽可能广泛的通用性,使用户在求解种种问题时,最好无需改变适应度函数中的参数。它能使用户在对所求解函数的全局最优解的性质完全“无知”的情况下,由算法在运行过程中自动修正其中的参数值,从而一步一步接近最优解。从另一种意义上说,这样的适应度函数具有自适应性。适应度函数的设计
(3)通用性适应度函数的设计33理想情况下:b的值是minf(x)=y*,当适应度值为0.5时,α是f(x)到minf(x)的距离。考虑到适应度函数的不同应用场合,将β值取为2,将α值分别取为1,1.5,0.5.即可在b,a取定的情况下得到3种适应度函数。理想情况下:b的值是minf(x)=y*,当适应度值为034当取α=1时,适应度值在[0.5~1]之间是线性的;对于在全局最优解y*附近变化比较缓慢的函数,用α=0.5可以使适应度函数较灵敏地反映出y值的变化情况.在算法的后期,则可以有效地拉开最优解附近点的适应度值,便于做出敏感选择,从而有利于以后的选择;当α=1.5时的适应度函数则有相反的适应情况.本文建议公式里的b和a随遗传算法的下一代进化而不断地修正.当取α=1时,适应度值在[0.5~1]之间是线性的;35b
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 二零二五年钢材生产许可证合同规范文本3篇
- 2025年粤教版必修1生物上册阶段测试试卷含答案
- 二零二五年度航空航天材料样本试验合同3篇
- 二零二五版四合院房产出售与生态旅游开发合同3篇
- 2024版外墙保温劳务合同
- 2025年粤教版七年级化学上册阶段测试试卷含答案
- 2025年度网络营销推广技术服务合同4篇
- 独特2024年度版权许可使用合同
- 2025年上教版必修1物理上册月考试卷含答案
- 校园软件施工方案
- 矩形砖砌渠道施工方案
- 大数据与人工智能ppt
- 中医科特色诊疗规范
- 建筑工程一切险条款版
- PEP小学六年级英语上册选词填空专题训练
- 古建筑修缮项目施工规程(试行)
- GA 844-2018防砸透明材料
- 化学元素周期表记忆与读音 元素周期表口诀顺口溜
- 非人力资源经理的人力资源管理培训(新版)课件
- 钼氧化物还原过程中的物相转变规律及其动力学机理研究
- (完整word)2019注册消防工程师继续教育三科试习题及答案
评论
0/150
提交评论