遺傳算法-交叉變異

第三部分遺傳算法課后任務查找資料，學習了解個體編碼的方法、交叉的方法和變異的方法。一、個體編碼方法1、二進制編碼：（1）定義：二進制編碼方法是使用二值符號集（0,1｝，它所構成的個體基因型是一個二進制編碼符號串。二進制編碼符號串的長度與問題所要求的求解精度有關。（2）舉例：0WxW1023,精度為1,m表示二進制編碼的長度。則有建議性說法：使2m-1W1000（跟精度有關）W2m-1。取m=10則X:0010101111就可以表示一個個體，它所對應的問題空間的值是x=175。（3）優(yōu)缺點優(yōu)點：符合最小字符集原則，便于用模式定理分析；缺點：連續(xù)函數(shù)離散化時的映射誤差。2、格雷碼編碼：（1）定義：格雷碼編碼是其連續(xù)的兩個整數(shù)所對應的編碼之間只有一個碼位是不同的，其余碼位完全相同。它是二進制編碼方法的一種變形。十進制數(shù)0—15之間的二進制碼和相應的格雷碼分別編碼如下。二進制編碼為：0000，0001，0010，0011，0100o0101，0110，0111，1000，1001，1010，1011，1100，1101，1110，1111；格雷碼編碼為：0000，0001，0011，0010，0110，0111，0101，0100，1100,1101,1111,1110,1010,1011,1001,1000。（2）舉例：對于區(qū)間0。1023］中兩個鄰近的整數(shù)X1=175和X2=176,若用長度為10位的二進制編碼，可表示為X11：0010101111和X120010110000，而使用同樣長度的格雷碼，它們可分別表示為X21：0010101111和X22：0010101000O（3）優(yōu)點：增強了遺傳算法的局部搜索能力，便于連續(xù)函數(shù)的局部控件搜索。3、符號編碼法符號編碼法是指個體染色體編碼串中的基因值取自一個無數(shù)值含義、而只有代碼含義的符號集如｛A,B,C…｝。符號編碼的主要優(yōu)點是：1）符合有意義積術塊編碼原則2）便于在遺傳算法中利用所求解問題的專門知識3）便于遺傳算法與相關近似算法之間的混合使用。但對于使用符號編碼方法的遺傳算法，一般需要認真設計交叉、變異等遺傳運算的操作方法，以滿足問題的各種約束村求，這樣才能提高算法的搜索性能。二、交叉的方法1、單點交叉：單點交叉又稱為簡單交叉，它是指在個體編碼串中只隨機設置一個交叉點，然后在該點相互交換兩個配體個體的部分染色體。如圖1父代，01|101單點交叉「.子代L01|000）一父代2：11000JI子代2：11|101JA交叉點圖1單點交叉2、兩點交叉：兩點交叉是指在個體編碼串中隨機設置了兩個交叉點然后再進行部分基因交換，兩點交叉的具體操作過程是在相互配對的兩個個體編碼串中隨機設置兩個交叉點，交換兩個個體在所設定的兩個交叉點之間的部分染色體，圖2為兩點交叉運算示意圖父代1：01|101|00110雙點交叉.子代L011000]00110父代2:11|00010100子代務11|101|10100tt交叉點1交叉點2圖2兩點交叉3、多點交叉：或稱廣義交叉，是指在個體編碼串中隨機設置多個交叉點，然后進行基因交換，其操作過程與單點交叉和兩點交叉相類似3、均勻交叉：也稱一致交叉，是指兩個配對個體的每個基因座上的基因都以相同的交叉概率進行交換，從而形成兩個新的個體，其具體運算是通過設置一屏蔽字來確定新個體的各個基因如何由哪一個父代個體來提供，主要操作過程如下：1）隨機產(chǎn)生一個與個體編碼串長度等長的屏蔽字W=w1w2Lw1Lw1，其中L為個體編碼串長度。2）由上述規(guī)則從AB兩個父代個體中產(chǎn)生出兩個新的子代個體A’、B’，若wi=0則A’在第i個基因座上的基因值繼承A的對應基因值，B’在第i個基因座上的基因值繼承B的對應基因值，若i=1,則A’在第i個基因座上的基因值繼承B的對應基因值，B’在第i個基因座上的基因值繼承A的對應基因值。4、均勻兩點交叉：是指兩個配體A、B中隨機產(chǎn)生兩個交叉點，然后按隨機產(chǎn)生的0、1、2三個整數(shù)進行基因交換，從而形成兩個新的個體。當隨機數(shù)是0時，配體的前面部分交叉;當隨機數(shù)是1時配體的中間部分交叉;當隨機數(shù)是2時，配體的后面部分交叉還有其他的交叉算子，如縮小代理交叉，洗牌交叉等。5、適合浮點數(shù)編碼的交叉算子浮點數(shù)編碼方法是指個體的每個基因值用某一范圍內的一個浮點數(shù)來表示，個體的編碼長度等于其決策變量的個數(shù)除上述所述的適合二進制編碼方法的交叉算子可用于浮點數(shù)編碼方法的交叉操作中還使用以下主要的交叉算子1）離散交叉：是指在個體之間交換變量的值子個體的每個變量可按等概率隨機地挑選父個體2）算術交叉：是指由兩個個體的線性組合而產(chǎn)生出兩個新的個體，算術交叉的操作對象一般是由浮點數(shù)編碼所表示的個體.其定義為兩個向量，染色體的組合:x1=A1x1+人2x2；x2=人1x2+人2x1其中人1、人2稱為乘子，特殊情況有當人1=人2=0.5時，Davis稱其為平均交叉Schwefel稱其為中間交叉intermediatecrossover把乘子作為區(qū)間[-d，1+d]上的隨機數(shù)時，Muhlenbein和Schlierkamp-Voosen稱其為擴展中間交叉。3）啟發(fā)式交叉：如果父個體1和父個體2而父個體1有較好的適應度，則如下函數(shù)產(chǎn)生子個體:子個體=父個體2+Radio3（父個體1-父個體2)其中Radio指定子代離較好適應度的父代有多遠，其缺省值為1.2三、變異的方法均有變異均有變異(UniformMutation)操作是指分別用符合某一范圍內均勻分布的隨即數(shù)，以某一較小的概率來替換個體編碼串中各個基因座上的原有基因值。均勻變異的具體操作過程是：依次指定個體編碼串中的每各個基因座為變異點；對每一個變異點，以概率pm從對應基因的取值范圍內取一隨機數(shù)來來代替原有基因值。邊界變異算子邊界變異算子(BoundaryMutation)是均勻變異操作的一個變形遺傳算法。在進行邊界變異操作時，隨機地取基因座的二個對應邊界基因之一取代替原有基因值。非均勻變異算子非均勻變異的具體操作過程于均勻那變異相似，但它重點搜索原個體附近的微小區(qū)域。在進行由X=X1X2XkXl向X=X1X2Xk'XI的非均勻變異操作時，若變異點Xk處的基因值取值范圍為[Ukmin,Ukmax],則新的基因Xk'由下式確定：|Xk4-A(t?Uma!(-Xk)ifrandom(0,1)=0Xk=|Xk-A(t,孤一政)誓「赤叩(0,1片1，式中，A(t,y),(y表示Ukmax-Xk和Xk-Ukmin)表示［0,y］范圍內符合非均勻分布的一個隨機數(shù),要求隨著進化代數(shù)t的增加,A(t,y)接近于0的概率也逐漸增加。例如，A(t,y)可按下式定義：△(t,y)=y.(1-r(1-t/T)b)式中r為［0,1］范圍內符合均勻分布的一個隨機數(shù),T時最大進化代數(shù),b時一個系統(tǒng)參數(shù)，它決定了隨機數(shù)擾動對進化代數(shù)t的依賴程度。高斯變異算子高斯變異(Ga