遗传算法(模式理论)

遗传算法的理论基础主要内容1.遗传算法的模式理论2.遗传算法实现中的一些基本问题遗传算法的模式理论从前面简单遗传算法的操作中，我们可以看到寻优问题的性能是朝着不断改进的方向发展的。但是我们怎么能知道对某一特定问题使用遗传算法会得到优化或接近优化的解呢？这一章节分析遗传算法中的模式理论：1.模式；2.复制对模式的影响；3.交叉对模式的影响；4.变异对模式的影响；5.遗传算法有效处理的模式数量。模式一个模式(Schemata)就是一个描述种群中在位串的某些确定位置上具有相似性的位串子集的相似性模板(SimilarityTemplate)。例如：(即取位串的十进制数值的平方)位串适配值x=01101f(x)=x2＝132＝16911000576010006410011361在上列种群里的各位串之间，我们能发现具有某种相似性和这种相似性与高适配值之间具有某种因果关系。模式位串适配值0110116911000576010006410011361这种因果关系例如：凡是以“1”开始的位串，其适配值就高；以“0”开始的位串的适配值就低。这种相似性正是遗传算法有效工作的因素。根据对种群中高适配置位串之间的相似性的分析，Holland提出了遗传算法的模式理论.模式为了描述一个模式，在用以表示位串的两个字符的字母{0,1}中加入一个通配符“*”，就构成了一个表示模式用的三个字符的字母表{0，1，*}。因此用三元素字母表{0，1，*}可以构造出任意一种模式。一个模式与一个特定位串相匹配是指：该模式中的1与位串中的1相匹配，模式中的0与位串的0相匹配，模式中的“*”可以匹配位串中的0或1。模式例如：模式00*00匹配了两个位{00100,00000}模式*111*可以和{01110,01111,11110,11111}中的任何一个位串匹配，即与长度为5中间三位为“1”的四个位串匹配；模式0*1**则匹配了长度为5、第一位为0、第三位为1的8个位串{00100,00101,00110,00111,01100,01101,01110,01111}模式模式的思路为我们提供了一种简单而有效的方法，使能够在有限字母表的基础上讨论有限长位串的严谨定义的相似性。应强调的是，“*”只是一个元符号，既是代表其他符号的一个符号。它不能被遗传算法直接处理，只不过是允许来描述特定长度和特定字母表的位串的所有可能相似性的符号件。模式一般地，假定字母表的基数是k，例如{0,1}的基数是2，则定义在该字母表上的长度为l的位串中所有可能包含的最大模式数为（k+1)l，原因是在l个位置中的任何一个位置上都可以取k个字符中的任何一个及通配符“*”，即共有k+1个位置中的任何一个位置的全排列数为（k+1)l。例如，对长度l＝5，k=2则会有3×3×3×3×3＝35＝243＝(k+1)l中不同的相似模板，而位串的数量仅为kl=25=32。可见，模式的数量要大于位串的数量。模式对于任一长度为l的给定位串，其中所含模式数为2l个。因为在l个位置中的任一位置除了取其确定值外，还可以取“*”,即任一位置上都有两种不同表示，故有2l个不同模式，因此，对于大小为n的种群，则包含有2l～n×2l种模式.种群中位串之间的众多的相似性，可引导遗传算法有效地搜索。因为即使是一个规模不大的种群，也包含了丰富的2l～n×2l个有关这种相似性的信息。这些相似性和适配值之间的相关性正是是遗传算法能够进行有效搜索的根本所在。模式为论述方便，首先定义一些名词术语。不失一般性，考虑在二进制字母表V={0，1}上构造位串的表示。用大写字母表示一个位串，如这里的代表一个二值特性ai又可称为基因。相应地，一个模式是定义在V＋＝{0,1,*}之上的，用大写字母H表示，如H=10**11*。在第t代的种群用A(t)表示，种群中的个体位串分别用Aj（j＝1，2，…，n）表示。VaaaaaaAill-1321),,2,1(liai模式为了区分不同类型的模式，对模式H定义两个量：模式位数(Order)和模式的定义长度(DefiningLength)分别表示为O(H)和δ(H)。•O(H)是H中有定义的非“*”为的个数；•模式的定义长度δ(H)是指H中最两端的有定义位置之间的距离如H＝00*1*0，则O(H)=4，(H)=6-1＝5H＝**11***，则O(H)=2，(H)＝4-3＝1H＝*******，则O(H)=0，(H)=0这两个量为分析位串的相似性及分析遗传操作对重要模式(称为建筑块(BuildingBlocks)的模式)的影响提供了基本的手段复制对模式的影响设在给定时间(代)t，种群A(t)包含有m个特定模式H，记为m=m(H,t)•在复制过程中，A(t)中的任何一个位串Ai以概率Pi＝fi/∑fi被选中并进行复制。•假如选择是有放回地抽样，且两代种群之间没有交叠(即若A(t)的规模为n，则在产生A(t+1)时，必须从A(t)选n个位串进匹配池).复制对模式的影响可以期望在复制完成后，在t+1时刻，特定模式H的数量为式中f(H)是在t时刻对应于模式H的位串的平均配值，因为整个种群的平均适配值，则上式又可写为ifHfntHmtHm)(),()1,(nffi()(,1)(,)(21)fHmHtmHtf复制对模式的影响可见，经过复制操作后，下一代中特定模式的数量H正比于所在位串的平均值与种群平均适配值的比值。•f(H)时，H的数量将增加；•f(H)时，H的数量将减少。种群A(t)中的任一模式H在复制中都将按照式(2-1)的规律变化，即•适配值高于种群平均值的模式在下一代中的数量增加；•而适配值低于种群平均值的模式在下一代的数量将减少。这种所有模式的增减在复制中是并行进行的,遗传算法中隐含的并行机制就在于此。ff复制对模式的影响差分方程2-1即是复制操作对模式H数量影响的定量描述。为了进一步分析高于平均适配值的模式数量的增长，假设(c是一个大于零的常数)，则式（2-1）可重写为fcfHf)((,1)(,)(1)(,)(22)fcfmHtmHtfcmHt复制对模式的影响从原始种群开始（t＝0），并假定是一个稳定的值，则有可见，对于高于平均适配值的模式的数量将呈指数形式增长（c0）。从对复制的分析可以看到，虽然复制过程成功地以并行方式控制着模式数量以指数形式增减，但由于复制只是将某些高适配值个体全盘复制，或是淘汰某些低适配值个体，而决不会产生新的模式结构，因而性能的改进是有限的tcHmtHm）＋（1)0,()1,(交叉对模式的影响交叉过程是位串之间的有组织的而又是随机的信息交换。交叉操作对一个模式H的影响和模式的定义长度δ(H)有关。δ(H)越大，模式H被分裂的可能性就越大，因为交叉操作要随机选择出进行匹配的一对位串上的某一随机位置进行交叉。δ(H)越大，δ(H)的跨度就大，随机交叉点落入其中的可能性就越大，从而H的存活率就越低。交叉对模式的影响例如位串长度l＝7，有如下的包含两个型式的位串AA＝0111000H1=*1****0，δ(H1)＝5H2=***10**，δ(H2)＝1•随机地产生的交叉位置在3和4之间：A＝011|1000H1=*1*|***0，Pd＝5/6H2=***|10**，Pd＝1/6交叉对模式的影响•模式H1比模式H2更容易被破坏，即H1将在交叉中被破坏。显然被破坏的可能性正比于δ(H1)模式H1定义长度δ(H1)＝5，如果交叉点始终是随机地从l-1＝7-1=6个可能的位置选取，那么模式H1被破坏的概率为Pd＝δ(H1)/(l-1)＝5/6它的存活概率为Ps＝1-Pd＝1/6交叉对模式的影响•类似的，模式H2的定义长度δ(H2)＝1，它被破坏的概率为Pd＝1/6，存活的概率为Ps＝1-Pd＝5/6。推广到一般情况，可以计算出任何模式的交叉存活概率的下限为•在上面的讨论中，我们均假设交叉的概率为1。若交叉的概率为Pc(即在选出进匹配池的一对位串上发生交叉操作的概率)，则存活率由下式表示：11lHPs）（11lHPPcs）（交叉对模式的影响结合式（2-1），在复制、交叉操作之后，模式H的数量为即因此，在复制和交叉的综合作用之下，模式H的数量变化取决于其平均适配值的高低(f(H)或f(H))和定义长度δ(H)的长短，f(H)越大，δ(H)越小，则H的数量就越多。sPfHftHmtHm)(),()1,(]11[)(),()1,(lHPfHftHmtHmc）（ff变异对模式的影响变异是对位串中的单个位置以概率Pm进行随机替换，因而它可能破坏特定的模式。一个模式H要存活，意味着它所有的确定位置都存活。因此，由于单个位置的基因值存活的概率为1-Pm(保持率)，而且由于每个变异的发生是统计独立的，因此，一个特定模式仅当它的O(H)个确定位置都存活时才存活，即（1-Pm）自乘O(H)次，从而得到经变异后，特定模式的存活率为(1-Pm)O(H)变异对模式的影响由于一般情况自下Pm«1，H的存活率可以表示为综合考虑复制、交叉和变异操作的共同作用，则模式H在经历了复制、交叉、变异操作之后，在下一代中的数量可表示为上式也可近似表示为mHOmPHOP)(1)1()(])(1][1)(1[)(),()1,(mcPHOlHPfHftHmtHm])(1)(1[)(),()1,(mcPHOlHPfHftHmtHm模式定理的结论由上述分析可以得出结论：定义长度短的、确定位数少的、平均适配值高的模式数量将随着代数的增加呈指数增长。这个结论称为模式理论(SchemaTheory)或遗传算法的基本定理(TheFundamentalofGeneticAlgorithms)。根据模式理论，随着遗传算法的一代一代地进行，那些定义长度短的、位数少的、高适配值的模式将越来越多，因而可期望最后得到的位串(即这些模式的组合)的性能越来越得到改善，并最终趋向全局的最优。遗传算法有效处理的模式数根据前面的分析可知，当位串长度为l时，一个包含n个位串的种群中含有的模式个数在2l～n•2l之间。由于定义长度较长，确定位数较多的模式存活率较低，那么如何估计在新的一代的产生过程中经历了复制、交叉和变异之后被有效处理的模式的个数呢？遗传算法有效处理的模式数例：计算在一个长度为l的位串中，模式长度≤ls的模式个数。假设l=10,ls=5,有如下位串:1011100010•先计算确定位处在前5个位置上的模式：00010即形如*****的模式个数，其中％表示该位置要么取原位串的值(0或1),要么是*。显然，共有2ls个该模式。10111％％％％％遗传算法有效处理的模式数•然后将框架向后移一位，计算下5个位置上的模式:10010即形如*****的模式，亦有2ls个如此一共计算l-ls+1次。故总的模式数为，但是这些模式中，有近一半是重复的。01110％％％％％)1(2sllls遗传算法有效处理的模式数对于n个位串的种群，总模式数的上限为，但一般达不到这个数量。确定位数少的模式在一个较大的种群中会有重复。为了能教准确地估计，我们选取一个恰当地种群规模n=2ls/2。之所以这样做，是因为我们期望确定位数≥ls/2的模式不多于一个。在一个长度为ls的模式中，确定位数ls/2的模式数和确定位数ls/2的模式数是一样多的。)1(21slllns遗传算法有效处理的模式数若我们仅计算确定位数≥ls/2的模式数(确定位数少的模式重复的可能性大)，且根据n＝ls/2的假设，可得总模式数的下限值ns为即将代入，且取等号，有即所以在产生新的一代的过程中，遗传算法处理的模式数的数量级为O(n3)，这是遗传算法的一个重要特征。2)1(21slsllnns22sln341nllnss3cnns22)1(slssllnn模式定理的小结在产生新的