遗传算法的数学基础

《遗传算法的数学基础》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第3章遗传算法的数学基础遗传算法在机理方面具有搜索过程和优化机制等属性，数学方面的性质可通过模式定理和构造块假设等分析加以讨论，Markov链也是分析遗传算法的一个有效工具。遗传算法的选择操作是在个体适应度基础上以概率方式进行的，在概率选择方式上与模拟退火法有些类似。本章将较全局地介绍遗传算法的基础数学理论和分析工具，包括验证基础遗传算法（SGA）的有效性的模式定理，分析遗传算法过程的Walsh模式变换方法，遗传算法的欺骗问题以及遗传算法的动态分析工具—Markov链分析。3.1模式定理1.模式我们将种群中的个体即基因串中的相似样板称为“模式”，模式表示基因串中某些特征位相同

2、的结构，因此模式也可能解释为相同的构形，是一个串的子集。在二进制编码中，模式是基于三个字符集{0，1，*}的字符串，符号*代表0或1。例1．*1*表示四个元的子集{010011110111}对于二进制编码串，当串长为L时，共有3L个不同的模式。例2．串长L=3，则其模式共有{****1**0***1**01**0***10*00*011*11*00*10*011*10*01*00*111110101011001010100000}共27个1+2*3+22*3+23=33遗传算法中串的运算实际上是模式的运算。如果各个串的每一位按等概率生成0或1，则模式为n的种群模式种类总数的期

3、望值为：种群最多可以同时处理个模式，见下例例一个个体（种群中只有一个），父个体011要通过变异变为子个体001，其可能影响的模式为：被处理的模式总数为8个，8=1*23如果独立的考虑种群中的各个串，则仅能得到n条信息，然而当把适应值与各个串结合考虑，发掘串群体的相似点，就可得到大量的信息来帮助指导搜索，相似点的大量信息包含在规模不大的种群中。2.模式阶和定义距定义1：模式阶模式H中确定位置的个数成为模式H的模式阶，记作O(H)例O(011**1**0)=5定义2定义阶模式中第一个确定位置和最后一个确定位置之间的距离，记作例3.模式定理假定在给定时间步t(即第t代)，种群A(t

4、)中有m个个体属于模式H，记为m=m(H,t),即第t代时，有m个个体属于H模式。在再生阶段（即种群个体的选择阶段），每个串根据它的适应值进行复制（选择），一个串Ai被复制（选中）的概率为：n表示种群中个体总数当采用非重叠的n个串的种群替代种群A(t),可以得到下式：其中：，表示在t时模式H的平均适应度若用表示种群平均适应度，则前式可表示为：上式表明：一个特定的模式按照其平均适应度值与种群的平均适应度值之间的比率生长，换句话说就是：那些适应度值高于种群平均适应度值的模式，在下一代中将会有更多的代表串处于A(t+1)中，因为在时有m(H,t+1)>m(H,t)假设从t=0开始，

5、某一特定模式适应度值保持在种群平均适应度值以上，c为常数c>0,则模式选择生长方程为：上式表明，在种群平均值以上（以下）的模式将按指数增长（衰减）的方式被复制。下面讨论交叉对模式H的影响：例：对串A分别在下面指定点上与H1模式和H2模式进行交叉A0111000H1*1****0(被破坏概率：；生存率：1/6)H2***10**(被破坏概率：；生存率：5/6)显然A与H1交叉后，H1被破坏，而与H2交叉时，H2不被破坏。一般地有：模式H被破坏的概率为，故交叉后模式H生存的概率为（）考虑到交叉本身是以随机方式进行的，即以概率Pc进行交叉，故对于模式H的生存概率Pc可用下式表示：同

6、时考虑选择交叉操作对模式的影响，（选择交叉互相独立不影响）则子代模式的估计：上式表明模式增长和衰减依赖于两个因素：一是模式的适应度值f(H)与平均适应度值的相对大小；另一个是模式定义阶的大小（当Pc一定，L一定时）。下面再考察变异操作对模式的影响：变异操作是以概率Pm随机地改变一个位上的值，为了使得模式H可以生存下来，所有特定的位必须存活。因为单个等位基因存活的概率为（1—Pm）,并且由于每次变异都是统计独立的，因此，当模式H中O(H)个确定位都存活时，这时模式H才能被保留下来，存活概率为：（为0.01以下）上式表明O(H)个定位值没有被变异的概率。由此我们可得到下式—在t+

7、1代种群中存在模式H的个体数目—在t代种群中存在模式H的个体数目——在t代种群中包含模式H的个体平均适应度——t代种群中所有个体的平均适应度——个体长度——交叉概率——变异概率对于k点交叉时，上式可表示为：模式定理：在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。4.积木块假设（buildingblockhypochesis）遗传算法通过短定义距、低阶以及高适应度的模式（积木块），在遗传操作作用下相互结合，最终接近全局最优解。满足这个假设的