遗传算法的数学基础

第3章遗传算法的数学基础遗传算法在机理方面具有搜索过程和优化机制等属性，数学方面的性质可通过模式定理和构造块假设等分析加以讨论，Markov链也是分析遗传算法的一个有效工具。遗传算法的选择操作是在个体适应度基础上以概率方式进行的，在概率选择方式上与模拟退火法有些类似。本章将较全局地介绍遗传算法的基础数学理论和分析工具，包括验证基础遗传算法（SGA）的有效性的模式定理，分析遗传算法过程的Walsh模式变换方法，遗传算法的欺骗问题以及遗传算法的动态分析工具—Markov链分析。3.1模式定理1.模式我们将种群中的个体即基因串中的相似样板称为“模式”，模式表示基因串中某些特征位相同的结构，因此模式也可能解释为相同的构形，是一个串的子集。在二进制编码中，模式是基于三个字符集{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的种群模式种类总数的期望值为：12(1(1(1/2)))LiiinliC种群最多可以同时处理2lng个模式，见下例例一个个体（种群中只有一个），父个体011要通过变异变为子个体001，其可能影响的模式为：被处理的模式总数为8个，8=1*23如果独立的考虑种群中的各个串，则仅能得到n条信息，然而当把适应值与各个串结合考虑，发掘串群体的相似点，就可得到大量的信息来帮助指导搜索，相似点的大量信息包含在规模不大的种群中。2.模式阶和定义距定义1：模式阶模式H中确定位置的个数成为模式H的模式阶，记作O(H)例O(011**1**0)=5定义2定义阶模式中第一个确定位置和最后一个确定位置之间的距离，记作()H例(011**1**0)8(001**1***)53.模式定理假定在给定时间步t(即第t代)，种群A(t)中有m个个体属于模式H，记为m=m(H,t),即第t代时，有m个个体属于H模式。在再生阶段（即种群个体的选择阶段），每个串根据它的适应值进行复制（选择），一个串Ai被复制（选中）的概率为：1iinjjfpfn表示种群中个体总数当采用非重叠的n个串的种群替代种群A(t),可以得到下式：1()(,1)(,)njjfHmHtmHtnfgg其中：()iiHffHm，表示在t时模式H的平均适应度若用1njjffn表示种群平均适应度，则前式可表示为：()(,1)(,)fHmHtmHtf上式表明：一个特定的模式按照其平均适应度值与种群的平均适应度值之间的比率生长，换句话说就是：那些适应度值高于种群平均适应度值的模式，在下一代中将会有更多的代表串处于A(t+1)中，因为在()fHf时有m(H,t+1)m(H,t)假设从t=0开始，某一特定模式适应度值保持在种群平均适应度值以上cf，c为常数c0,则模式选择生长方程为：(,1)(,)(1)(,)(1)(,0)tfcfmHtmHtcmHtcmHf上式表明，在种群平均值以上（以下）的模式将按指数增长（衰减）的方式被复制。下面讨论交叉对模式H的影响：例：对串A分别在下面指定点上与H1模式和H2模式进行交叉A0111000H1*1****0(被破坏概率：()551716Hl；生存率：1/6)H2***10**(被破坏概率：()111716Hl；生存率：5/6)显然A与H1交叉后，H1被破坏，而与H2交叉时，H2不被破坏。一般地有：模式H被破坏的概率为()1Hl，故交叉后模式H生存的概率为()11Hl（:l串长；（H）:模式H的定义阶）考虑到交叉本身是以随机方式进行的，即以概率Pc进行交叉，故对于模式H的生存概率Pc可用下式表示：()11schppl同时考虑选择交叉操作对模式的影响，（选择交叉互相独立不影响）则子代模式的估计：()()(,1)(,)[1]1cfHHmHtmHtplfg上式表明模式增长和衰减依赖于两个因素：一是模式的适应度值f(H)与平均适应度值的相对大小；另一个是模式定义阶()H的大小（当Pc一定，L一定时）。下面再考察变异操作对模式的影响：变异操作是以概率Pm随机地改变一个位上的值，为了使得模式H可以生存下来，所有特定的位必须存活。因为单个等位基因存活的概率为（1—Pm）,并且由于每次变异都是统计独立的，因此，当模式H中O(H)个确定位都存活时，这时模式H才能被保留下来，存活概率为：()(1)1()()1OHmmmpOHppg（为0.01以下）上式表明O(H)个定位值没有被变异的概率。由此我们可得到下式()()(,1)(,)[1()]1cmfHHmHtmHtpOHplfg(,1)mHt—在t+1代种群中存在模式H的个体数目(,)mHt—在t代种群中存在模式H的个体数目()fH——在t代种群中包含模式H的个体平均适应度f——t代种群中所有个体的平均适应度l——个体长度cp——交叉概率mp——变异概率对于k点交叉时，上式可表示为：1()1()(,1)(,)[1()]kKllHcmklccfHmHtmHtpOHpcfg模式定理：在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。4.积木块假设（buildingblockhypochesis）遗传算法通过短定义距、低阶以及高适应度的模式（积木块），在遗传操作作用下相互结合，最终接近全局最优解。满足这个假设的条件有两个：（1）表现型相近的个体基因型类似（2）遗传因子间相关性较低积木块假设指出，遗传算法具备寻找全局最优解的能力，即积木块在遗传算子作用下，能生成低阶、短距、高平均适应度的模式，最终生成全局最优解。模式定理还存在以下缺点：（1）模式定理只对二进制编码适用（2）模式定理只是指出具备什么条件的木块会在遗传过程中按指数增长或衰减，无法据此推断算法的收敛性（3）没有解决算法设计中控制参数选取问题3.2Walsh模式变换1980年，密歇根大学的A.D.Bethke博士论文“作为函数优化器的遗传算法”，首次应用Walsh函数进行遗传算法的模式处理，采用Walsh函数的离散形式有效地计算模式的平均适应度，从而对遗传算法的优化过程的特征进行分析。3.3非均匀Walsh模式变换3.4欺骗问题在遗传算法中，将所有妨碍评价值高的个体生成，从而影响遗传算法正常工作的问题统称为欺骗问题（deceptiveproblem）,根据模式定理，如果低阶、高适应度模式中包含了最优解的话，遗传算法就可能找出它来，但是如果低阶、高适应度模式中未包含最优串的具体取值，则遗传算法只能找出次优解。定义竞争模式若模式H和H’中，*位置是完全一致的，但任一确定位的编码均不同，则称H和H’互为竞争模式。例10***与01***是竞争模式10***与11***不是竞争模式定义欺骗性假定f(x)的最大值对应的x集合为x*，H为包含x*的m阶模式，H的竞争模式为H’，而且f(H)f(H’),则f为m阶欺骗。例对于一个三位二进制编码的模式，如果f(111)为最大值，下列12个不等式中任意一个不等式成立，则存在欺骗问题。模式阶数为1时：f(**1)f(**0),f(*1*)f(*0*),f(1**)f(0**)模式阶数为2时：f(*11)f(*00),f(1*1)f(0*0),f(11*)f(00*)f(*11)f(*01),f(1*1)f(0*1),f(11*)f(01*)f(*11)f(*10),f(1*1)f(1*0),f(11*)f(10*)造成上述欺骗问题的主要原因有两个：编码不当或适应度函数选择不当。如果它们均是单调关系，则不会存在欺骗性问题，但是对于一个非线性问题，难于实现其单调性。1.欺骗函数的类型Goldberg曾研究用适应度函数的非单调性来研究欺骗性问题。考虑一个2位二进制最大化问题，假定“11”对应最优解，若H(0*)H(1*)，则欺骗性存在。该条件可化为：(00)(01)(10)(11)(00)(10)(01)(11)2222ffffffff或下面以前一种为例进行讨论，设(11)/(00),(01)/(00),'(10)/(00)rffcffcff则有：r1+c-c’c1：称为Ⅰ类欺骗问题，见图1，求最优化时较难c=1:称为Ⅱ类欺骗问题，见图2，此问题求最优化更难图1图2这两类欺骗性问题应该称为非单调问题，在非单调问题中同时存在欺骗性和非欺骗性问题。过去，将适应度函数的非单调问题与欺骗问题同等看待，认为遗传算法只有在单调问题里有效。但是，如果单调问题不使用遗传算法或者不使用概率搜索，一般的搜索法可能是适用的，没有遗传算法存在的必要。即使是单调的，只有存在需要高机能交叉操作（非单调且非欺骗问题），才能使遗传算法存在有意义，这不外乎使交叉操作成为遗传算法本质作用的一个证明。2.欺骗性化解可以采用Grey编码或纠正适应度函数3.遗传算法的困难问题容易问题：采用基本的遗传算法，易于得到最优解的场合或问题困难问题;与上相反遗传算法的欺骗性与遗传算法的困难性不存在对等或等价关系，这是由于遗传算法的欺骗性是从静态超平面分析给出的，并且假设个体数无偏差，而遗传算法的困难性来源于不适当的问题表示、交叉和变异的扰动作用、有限的种群大小、复杂的多模型状态图等。3.5遗传算法动态分析从随机过程和数理统计角度讨论遗传算法较为一般的规律，有助于较好地把握遗传算法的特性，以提高求解效率和改善求解效果。铃木（1995年）从Markov链的角度分析了基本遗传算法（SGA）的统计规律，并得到了一些有意义的结论。SGA的当前种群只与前一代种群有关，因此SGA可以用一个Markov链来描述。第四章遗传算法的改进自从1975年J.H.Holland系统地提出遗传算法的完整结构和理论以来，总多学者一直致力于推动遗传算法的发展，对编码方式、控制参数的确定、选择方式和交叉机理等进行了深入的探究，引入了动态策略和自适应策略以改善遗传算法的性能，提出了各种变形的遗传算法（VariantsofCanonicalGeneticAlgorithm,简称VCGA）.其基本途径概括起来有以下几个方面：（1）改变遗传算法的组成成分或使用技术，如选用优化控制参数、适合问题特性的编码技术等。（2）采用混合遗传算法（3）采用动态自适应技术，在进化过程中调整算法控制参数和编码力度（4）采用非标准的遗传操作算子（5）采用并行遗传算法本章将介绍这些方面的典型思路和集中改进的遗传算法。4.1分层遗传算法对于一个问题，首先随机生成N*n各样本(n=2,N=2),然后将它们分成N个子种群，每个子种群包括n各样本，对每个子种群独立的运行各自的遗传算法，记它们为GAi(i=1,2,….N)。这N个遗传算法最好在设置特性上有较大差异，这样就可以为将来的高层遗传算法产生更多种类的优良模式。在每个子种群的遗传算法运行到一定代数后，将N个遗传算法的结果种群记录到二维数组R[1….N,1…n]中，则R[i,j]（i=1…N,j=1…n）表示GAi的结果种群的第j个个体。同时将N各结果种群的平均适应度值记录到数组A[1….N]中，A[i]表示GAi的结果种群平均适应度。高层遗传算法与普通遗传算法的操作相类似，也可以分为以下三个步骤：1.选择（种群之内选择）基于数组A[1….N]，即N个遗传算法的平均适应度值，对数组R代表结果种群进行选择操作，一些结果种群由于它们的平均适应度值高而被复制，甚至复制多次；另一些结果种群由于它们的种群平均适应度值低而被淘汰。2.交叉（种