遺傳算法模式定理推導

8.3遺傳算法基本定理1、模式的概念所謂模式就是一個相同的構形，它描述的是一個數(shù)字串的子集合，在這個集合中的所有數(shù)字串之間、在某些確定位置上是相同的。模式一般用大寫字母H表示。用3個字符的字母表V=[0,1,*]組成的三元組來描述模式，其中，符號*代表不確定數(shù)字，即在特定位置上可以與數(shù)字0或1相匹配。例如，字符串長為5的模式H=*11*0，并稱數(shù)字串A=01110是模式H的一個代表串，這是因為數(shù)字串A與模式H在確定位置2、3和5上相匹配。遺傳算法的操作過程非常簡單，從一個含有N個染色體的初始群體出發(fā)，不斷循環(huán)地執(zhí)行選擇、交叉和變異運算?？雌饋磉z傳算法是按這種簡單的模式直接作用在一個個數(shù)字串組成的群體上，實際上，在每一代的計算過程中，這種數(shù)字串的顯式操作過程蘊含了大量模式的隱含操作。這里，首先討論選擇、交叉和變異算子對模式作用的影響。對于由N個二進制數(shù)字串組成的群體中，至多包含有N2乙個模式(所有符號*都為確定數(shù)字時)，式中L為數(shù)字串長。在遺傳算法的執(zhí)行過程中，所有的模式并不是以同等的機會發(fā)生的。有些模式比起其他的模式更明確，例如，模式011*1和模式0****相比，在相似性方面，模式011*1就比較明確。有些模式的跨度要比另一些模式的長，例如，模式1***1和模式1*1**相比，在長度方面，模式1***1要跨越整個串長。為了定量地描述模式，下面介紹兩個基本概念:模式的定義長度和模式的階。模式H的定義長度是指模式H中第1個常數(shù)位置與最后1個常數(shù)位置之間的距離，用8(H)表示。例如，模式H廣011*1**的定義長度為6(H1)=4，這是因為模式H1中第1個常數(shù)的位置為1，最后回個常數(shù)的位置為5，它們之間的距離為5-1=4；另一個模式^=0******中僅有1個常數(shù)位置，即第1個和最后1個常數(shù)位置是同一個位置，2因此其定義長度6(H)=0。模式H的階是指出現(xiàn)在模式H中常數(shù)的個數(shù)，用O(H)表示。在二進制數(shù)字串中，一個模式H的階就是模式中所有1和0的個數(shù)。例如，模式H廣011*1**的階為4，可記為O(H1)=4，同樣地，模式H2=0******階為1，可記為0(H)=1。模式、模式的定義長度以及模式的階對于討論和區(qū)分數(shù)字串的相似性是有用的標志，并且它們提供了一個基本的方法來分析遺傳算子對包含在群體中的基因的作用效果。下面分別考慮選擇、交叉和變異操作對包含在群體中的模式作用的單獨效果和聯(lián)合效果，并最終導出模式定理。2、選擇操作的效果假設在給定時間t代，一個特定的模式H有m個代表數(shù)字串包含在群體A(r)中，記為m=m(H,t)，在不同的時間t代，不同的模式H可能有不同數(shù)量的代表數(shù)字串。在選擇操作階段，每個數(shù)字串根據(jù)它的適應度函數(shù)值進行選擇，一個數(shù)字串A.(t)的選擇率P為

式中，f.為數(shù)字串A。)的適應度函數(shù)值。當采用沒有重疊的N個數(shù)字串的群體替代群體A⑺后，人們期望在時間(11)代，模式H在群體A(l1)中有m=m(H,t+1)個代表數(shù)字串，則模式H的數(shù)量為m（H,m（H,，十1）=,）N?式中，f(H)表示在時間t代模式H包含的所有代表數(shù)字串的平均適應度函數(shù)值。由于群體的平均適應度函數(shù)值可記為:故模式H的選擇生長方程可表示為—(‘I)由此式看出，一個特定的模式H按照其適應度函數(shù)值與群體的平均適應度函數(shù)值之間的比例生長，換句話說，當f(H)>f時，模式H的代表數(shù)字串在下一代中將會增多；當f(H)<f時，模式H的代表數(shù)字串在下一代中將會減少。群體A(t)中的任一模式H在選擇操作下都將按上述規(guī)律變化，這種對所有模式數(shù)量的增減在選擇操作中是并行發(fā)生的，遺傳算法中隱含的并行機制就在于此。上面定量分析了選擇對不同模式的影響，可以看出，在平均適應度函數(shù)值以上的模式數(shù)量將逐漸增加，平均適應度函數(shù)值以下的模式數(shù)量將逐漸消失。在此基礎上，下面導出一個定量表達式。假設某一特定模式H的適應度函數(shù)值保持在高出群體平均適應度函數(shù)值以上一個Cf，即f(H)-f=Cf，C為一常數(shù)，則模式H的選擇生長方程可變?yōu)?MH,1)=E)?(/十二(1十C).用(H,F)從時間t=0代開始，模式H的選擇生長方程為：He)=MH,O)?(1十CV至此選擇的作用已清楚了。當常數(shù)C>0時，在群體平均適應度函數(shù)值以上的模式數(shù)量將會按指數(shù)規(guī)律增長，而當常數(shù)CV0時，在群體平均適應度函數(shù)值以下的模式數(shù)量將會按指數(shù)規(guī)律減少。在一定程度上，選擇可以把按指數(shù)規(guī)律增長或減少的模式并行地遺傳到下一代。一方面，許許多多不同的模式根據(jù)相同的規(guī)則，通過利用簡單的選擇算子被并行地處理；另一方面，僅僅只有選擇操作并無助于搜索空間中新的區(qū)域，這是因為選擇操作并沒有搜索新的點。3、交叉操作的效果雖然選擇對模式H的數(shù)量的影響令人驚奇，但若無交叉操作，它就失去了意義，因為選擇不會在數(shù)字串空間中產生新的點，它只是一種選擇而已。因而，為了檢測模式空間中新的區(qū)域，需要執(zhí)行交叉操作。這里，僅考慮簡單的一點交

叉的作用效果。一點交叉過程首先是隨機選擇一對交配數(shù)字串，然后隨機選擇一個交叉位置，將其中一個數(shù)字串從交叉位置到右端的子串與另一個交配數(shù)字串對應的子串相交換。為了討論方便，不妨考慮一個長度為6的串以及隱含其中的兩個模式。>1=010110耳=許*畀11胃假定A被選中進行交叉，而交叉點以等概率產生，即交叉點落在1、2、3、4、5的概率相同。這里不妨假設交叉點為3,即交叉發(fā)生在位置3和位置4之間，并以分隔符“I”表示交叉泣置，即有TOC\o"1-5"\h\z■T=01。|I1。*1*I**0=***iJL#在這種情況下，除了與A進行交叉的串（稱作配偶）在確定位（比如位置2、6）相同（這種可能性我們暫且不考慮）外，模式丑］將遭到破壞，因為位置2的“1”和位置6的“0”在交叉產生的子代個體中將被替代為不同的值。比如A的配偶為#=101001，則產生的后代為A=010001，A=101001，都不是H的樣本，即發(fā)生交叉后，模式氣丟失了。而相同情況下，2h卻依然存在，因為不論A的配偶為任何串，H中確定位4的“1”和確定位5的“1”都將一塊傳入子代?？赡苡械淖x者會問，2假若交叉點在位置4，H2不也會遭到破壞嗎？不錯!但有一點可以看出，由于交叉點等概率產生，模式，遭破壞的概率（在位置2、3、4、5交叉都遭破壞）大大超過模式H（只在位置41交叉遭破壞），即H的“生命力”要強于H「22現(xiàn)在定量地討論一下。我們注意到模式氣的定義長度為4，那么交叉點在6-1=5個位置隨機產生時，H遭破壞的概率為P=5（H）/（/-1）=4/5，換句話說，其生存概率為1/5；而模式H2的定義長建為1「則H2遭破壞的概率為P=5（H）/（1-1）=1/5，即生存概率為4/5。2d更一般地講，模式H只有當交叉點落在定義長度之外才能生存。在簡單交叉（單點交叉）下的H的生存概率P=1-5（H）/（1-1）。而交叉本身也是以一定S的概率P發(fā)生的，所以模式H的生存概率為：CP,eP,e1—R一1)（8.2）現(xiàn)在我們考慮先前暫且忽略的可能性，即交叉發(fā)生在定義長度內，模式H不被破壞的可能性。在前面的例子中，若A的配偶在位置2、6上有一位與A相同，則氣將被保留。考慮到這一點，式（8.2）給出的生存概率只是一個下界，即有：p,>p,>1-P,--1)（8.3）式（8.3）描述了模式在交叉算子作用下的生存概率?，F(xiàn)在考慮模式H在選擇和交叉算子的共同作用下的變化。參照式（8.1）和式（8.3），則有：-"勇…「.w，-"?「.?I」"4)由(8.4)式可以看出，在選擇和交叉算子的共同作用下，模式的增長(減少)取決于兩個因素：(1)模式的平均適應度是否高于群體平均適應度；(2)模式是否具有較短的定義長度。顯然，那些平均適應度高于群體平均適應度、具有短定義長度的模式將呈指數(shù)級增長?，F(xiàn)在考慮選擇和交叉結合在一起時對模式的作用效果。當僅考慮選擇時，人們感興趣的是計算一個特定的模式在下一代中期望出現(xiàn)的數(shù)目。假設選擇和交叉操作是不相關的，可用下式來估算：也〈H、￡十I)aH,l)-——1-rfLL-1J(8.5)比較式(8.1)和式(8.3)可以看出，選擇和交叉一起對模式的作用效果是，通過把僅有選擇作用的模式數(shù)量與在交叉作用下的生存概率相乘得到的。模式H的數(shù)量增多或減少與一個乘積因子有關。在選擇和交叉作用下，這個乘積因子與兩個因素有關：模式的適應度函數(shù)值f(H)是在群體平均適應度函數(shù)值f之上還是之下；模式具有相對短的定義長度還是長的定義長度5(H)。當f(H)越大，8(H)越短，則在下一代中，模式H的數(shù)量就越多，且按指數(shù)增長率進化發(fā)展。4、變異算子的作用效果最后討論變異算子的作用效果。由變異引起模式H被破壞的概率表示為PO(H)，其中P為變異概率。變異算子是以概率P隨機地改變數(shù)字串中一個位置上的值，為亍使模式H可以生存下來，所有特定的位置上的值必須存活。因為單個等位基因存活的概率為1-P，并且由于每次變異都是統(tǒng)計獨立的，因此，當模式H中個O(H)確定位都存活時，這個模式才存活，因而在變異算子作用下，則模式H的存活概率為(1-P)o(h)。一般情況下P□1，模式H的存活概率可以近似地等于1-PO(H)。""m5、模式定理因此，在考慮選擇、交叉和變異作用下，一個特定模式H在下一代中期望產生的數(shù)目可近似表示為用(He+1)法用(何，)?^^?[1—Fcyry-(XH)]1-PO(H)乘以(8.5)式：[1-P5^H)][1-PO(H)]=1-P5^