遗传算法的编码与适应度函数课件.ppt

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的二进制编码，取

8、各参数编码串中的最高位联在一起，作为个体编码的前n位编码、再取次高位联在一起作为个体第二组n位编码，.,再取最后一位联在一起作为编码的最后n位。n这种编码方式中，各个参数的局部编码结构就不易被遗传算子破坏掉，它适合于各参数之间的相互关系较弱，特别是某一各或少数几个参数其主要作用时的优化问题。 适应度函数n传算法中使用适应度这个概念来度量群体中各个个体在优化计算中有可能达到或接近于或有助于找到最有解的优良程度。n适应度高的个体遗传到下一代的可能性比较大，而适应度比较低的个体遗传到下一代的概率相对小一些。n度量个体适应度的函数称为适应度函数。目标函数与适应度函数n遗传算法的一个特点就是它仅使用所求

9、问题的目标函数值就可得到下一步的有关搜索信息。而对目标函数值的使用是通过评价个体的适应度来体现的。n评价个体适应度的过程一般是： （1）对个体编码串进行解码处理后，可得到个体的表现型； （2）有个体表现型可计算出对应个体的目标函数值； （3）根据最优化问题的类型，有目标函数值按一定转换规则求出个体的适应度。最优化问题n最优化问题可以分为两大类，一类为求目标函数的全局最大值，另一类为求目标函数的全局最小值。n对于目标函数最小值的优化问题可转化为： min f(X)=max (-f(X) n当优化目标是函数的最大值，并且目标函数总取正时，可以直接设定个体适应度F（x）为：F（x）=f（x）注：Cm

10、ax和Cmin最好与种群无关 n我们希望在遗传算法运行的初期，算法能对一些适应度较高的个体进行控制，降低其适应度与其他个体适应度之间的差异程度，从而限制复制数量，以维护群体的多样性。 n在遗传运算后期，算法能对个体适应度进行适当放大，扩大最佳个体适应度与其它适应度之间的差异程度，以提高个体之间的竞争性。n目前常用的个体适应度尺度变换方法主要有三种：线性尺度变换、乘幂尺度变换、指数尺度变换。线性尺度变换nF=aF+b，F为原适应度；F为变换后的新适应度，a和b位系数。n系数a和b直接影响到这个尺度变换的大小，所以对其选择有一定的要求，一般要满足以下条件：nFavg= Favg，这条要求是为了保证

11、群体中适应度接近于平均适应度的个体能够有期待的数量被遗传到下一代种群中。nFmax=C Favg，C为最佳个体的期望复制数量。这条要求是为了保证群体中做好的个体能够期望复制C倍到新一代群体中。 n使用线性变换时，群体中有少数几个优良个体的适应度按比例缩小，同时几个较差的个体适应度也按比例扩大。n在搜索的后期阶段，随着个体适应度从总体上的不断改进，群体中个体的最大适应度和全部个体的平均适应度较接近，而少数几个较差的个体的适应度却远远小于最大适应度，这时若想维持Fmax和Favg的指定倍数关系，将有可能会使较差的个体适应度变换为负值。n解决上述问题的方法是：把原最小适应度Fmin映射为Fmin=0

12、，并且保持原平均适应度Favg与新的平均适应度Favg相等。乘幂尺度变换F=Fk新的适应度是原有适应度的某个指定乘幂。幂指数k与所求解的问题有关，并且在算法的执行过程中需要不断对其进行修正才能使尺度变换满足一定的伸缩要求。机器视觉中k的最佳取值为1.005。 指数尺度变换nF=exp（- F）n新的适应度使原有适应度的某个指数。式中系数 决定了选择的强制性， 越小，原有的是适应度较高的个体的新适应度就越与其它个体的新适应度相差较大，亦即越增加了选择该个体的强制性。适应度函数的设计 n(1)单值、连续、非负、最大化 适应度函数F(X)应该是实函数,并且单值、连续,但不要求可导。不过,F(X)的曲

13、线在重要部位,特别在最优解附近一般不宜太陡也不宜过于平缓。n(2)计算量小 F(X)不应设计得过于繁复,应在上述条件下越简单越好。适应度函数的设计 n(3)通用性 一个适应度函数的好坏,还应满足尽可能广泛的通用性,使用户在求解种种问题时,最好无需改变适应度函数中的参数。它能使用户在对所求解函数的全局最优解的性质完全“无知”的情况下,由算法在运行过程中自动修正其中的参数值,从而一步一步接近最优解。从另一种意义上说,这样的适应度函数具有自适应性。适应度函数的设计 n理想情况下 :b的值是minf(x)= y*,当适应度值为0.5时,是f(x)到minf(x)的距离。考虑到适应度函数的不同应用场合,

14、 将值取为2,将值分别取为1,1.5,0.5.即可在b,a取定的情况下得到3种适应度函数。abxfabxfabxfabxfXF)( ,)(11)( ,)(5 . 01)(abxfabxfabxfabxfXF)( ,)(11)( ,)(5 . 01)(n当取=1时,适应度值在0.51之间是线性的;n对于在全局最优解y*附近变化比较缓慢的函数,用=0.5可以使适应度函数较灵敏地反映出y值的变化情况.在算法的后期,则可以有效地拉开最优解附近点的适应度值,便于做出敏感选择,从而有利于以后的选择;n当=1.5时的适应度函数则有相反的适应情况.本文建议公式里的b和a随遗传算法的下一代进化而不断地修正. nb的值可取当前第i代中的最小值,即而则建议用下列公式求取 ： 若要求适应度函数曲线变化得“陡”一些,只需把公式中的相关系数调节得再小一些即可(例如将分母变大);同样,若要求适应度函数曲线“缓”一点,可以把系数适当调大一些(例如将分母变小). 30*max, 5 . 0maxfifia遗传算法的终止条件 遗传算法的终止条件常用的判定准则有下面两种n连续几代个体平均适应度的差异小于某一个极小的阈值。n群体中所有个体适应度方差小于某一个极小的阈值。