遺傳算法交叉變異

1、第三部分 遺傳算法 課后任務(wù)查找資料，學(xué)習(xí)了解個(gè)體編碼的方法、交叉的方法和變異的方法。一、個(gè)體編碼方法1、二進(jìn)制編碼：（1） 定義：二進(jìn)制編碼方法是使用二值符號(hào)集0,1，它所構(gòu)成的個(gè)體基因型是一個(gè)二進(jìn)制編碼符號(hào)串。二進(jìn)制編碼符號(hào)串的長(zhǎng)度與問(wèn)題所要求的求解精度有關(guān)。（2）舉例：0x1023,精度為1,m表示二進(jìn)制編碼的長(zhǎng)度。則有建議性說(shuō)法：使 2m-11000（跟精度有關(guān)）2m-1。取m=10則X:0010101111就可以表示一個(gè)個(gè)體，它所對(duì)應(yīng)的問(wèn)題空間的值是x=175。（3）優(yōu)缺點(diǎn)優(yōu)點(diǎn)：符合最小字符集原則，便于用模式定理分析；缺點(diǎn)：連續(xù)函數(shù)離散化時(shí)的映射誤差。2、格雷碼編碼：（1） 定義：格

2、雷碼編碼是其連續(xù)的兩個(gè)整數(shù)所對(duì)應(yīng)的編碼之間只有一個(gè)碼位是不同的，其余碼位完全相同。它是二進(jìn)制編碼方法的一種變形。十進(jìn)制數(shù)015之間的二進(jìn)制碼和相應(yīng)的格雷碼分別編碼如下。二進(jìn)制編碼為：0000，0001，0010，001 1，0100。0101，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）舉例：對(duì)于區(qū)間0。1023中兩個(gè)鄰近的整數(shù)X1=175和X2=176，若用長(zhǎng)

3、度為10位的二進(jìn)制編碼，可表示為X11：0010101111和X12 0010110000，而使用同樣長(zhǎng)度的格雷碼，它們可分別表示為X21：0010101111和X22：0010101000。（3）優(yōu)點(diǎn)：增強(qiáng)了遺傳算法的局部搜索能力，便于連續(xù)函數(shù)的局部控件搜索。3、符號(hào)編碼法符號(hào)編碼法是指?jìng)€(gè)體染色體編碼串中的基因值取自一個(gè)無(wú)數(shù)值含義、而只有代碼含義的符號(hào)集如A,B,C。符號(hào)編碼的主要優(yōu)點(diǎn)是：1)符合有意義積術(shù)塊編碼原則2)便于在遺傳算法中利用所求解問(wèn)題的專(zhuān)門(mén)知識(shí)3)便于遺傳算法與相關(guān)近似算法之間的混合使用。但對(duì)于使用符號(hào)編碼方法的遺傳算法，一般需要認(rèn)真設(shè)計(jì)交叉、變異等遺傳運(yùn)算的操作方法，以滿(mǎn)足

4、問(wèn)題的各種約束村求，這樣才能提高算法的搜索性能。2、 交叉的方法1、單點(diǎn)交叉：?jiǎn)吸c(diǎn)交叉又稱(chēng)為簡(jiǎn)單交叉，它是指在個(gè)體編碼串中只隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，然后在該點(diǎn)相互交換兩個(gè)配體個(gè)體的部分染色體。如圖1圖1 單點(diǎn)交叉2、兩點(diǎn)交叉：兩點(diǎn)交叉是指在個(gè)體編碼串中隨機(jī)設(shè)置了兩個(gè)交叉點(diǎn) 然后再進(jìn)行部分基因交換，兩點(diǎn)交叉的具體操作過(guò)程是: 在相互配對(duì)的兩個(gè)個(gè)體編碼串中隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)，交換兩個(gè)個(gè)體在所設(shè)定的兩個(gè)交叉點(diǎn)之間的部分染色體，圖2為兩點(diǎn)交叉運(yùn)算示意圖圖2 兩點(diǎn)交叉3、多點(diǎn)交叉：或稱(chēng)廣義交叉，是指在個(gè)體編碼串中隨機(jī)設(shè)置多個(gè)交叉點(diǎn)，然后進(jìn)行基因交換，其操作過(guò)程與單點(diǎn)交叉和兩點(diǎn)交叉相類(lèi)似3、 均勻交叉：也稱(chēng)一

5、致交叉，是指兩個(gè)配對(duì)個(gè)體的每個(gè)基因座上的基因都以相同的交叉概率進(jìn)行交換，從而形成兩個(gè)新的個(gè)體，其具體運(yùn)算是通過(guò)設(shè)置一屏蔽字來(lái)確定新個(gè)體的各個(gè)基因如何由哪一個(gè)父代個(gè)體來(lái)提供，主要操作過(guò)程如下：1）隨機(jī)產(chǎn)生一個(gè)與個(gè)體編碼串長(zhǎng)度等長(zhǎng)的屏蔽字W=w1w2Lw1Lw1，其中L為個(gè)體編碼串長(zhǎng)度。2）由上述規(guī)則從A B兩個(gè)父代個(gè)體中產(chǎn)生出兩個(gè)新的子代個(gè)體A 、B，若wi = 0則A在第i個(gè)基因座上的基因值繼承A的對(duì)應(yīng)基因值，B在第i個(gè)基因座上的基因值繼承B的對(duì)應(yīng)基因值，若i = 1 ,則A在第i 個(gè)基因座上的基因值繼承B的對(duì)應(yīng)基因值，B在第i 個(gè)基因座上的基因值繼承A的對(duì)應(yīng)基因值。4、均勻兩點(diǎn)交叉：是指兩個(gè)

6、配體A 、B中隨機(jī)產(chǎn)生兩個(gè)交叉點(diǎn)，然后按隨機(jī)產(chǎn)生的0 、1 、2三個(gè)整數(shù)進(jìn)行基因交換，從而形成兩個(gè)新的個(gè)體。當(dāng)隨機(jī)數(shù)是0時(shí)，配體的前面部分交叉;當(dāng)隨機(jī)數(shù)是1時(shí)配體的中間部分交叉;當(dāng)隨機(jī)數(shù)是2時(shí)，配體的后面部分交叉還有其他的交叉算子，如縮小代理交叉，洗牌交叉等。5、適合浮點(diǎn)數(shù)編碼的交叉算子浮點(diǎn)數(shù)編碼方法是指?jìng)€(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來(lái)表示，個(gè)體的編碼長(zhǎng)度等于其決策變量的個(gè)數(shù) 除上述所述的適合二進(jìn)制編碼方法的交叉算子可用于浮點(diǎn)數(shù)編碼方法的交叉操作中 還使用以下主要的交叉算子1）離散交叉：是指在個(gè)體之間交換變量的值子個(gè)體的每個(gè)變量可按等概率隨機(jī)地挑選父?jìng)€(gè)體2）算術(shù)交叉：是指由兩個(gè)個(gè)體的

7、線(xiàn)性組合而產(chǎn)生出兩個(gè)新的個(gè)體，算術(shù)交叉的操作對(duì)象一般是由浮點(diǎn)數(shù)編碼所表示的個(gè)體. 其定義為兩個(gè)向量，染色體的組合: x1= 1x1+ 2x2；x2= 1x2+ 2x1其中 1、 2稱(chēng)為乘子，特殊情況有當(dāng) 1= 2= 0.5時(shí)，Davis稱(chēng) 其 為 平 均 交 叉Schwefel稱(chēng)其為中間交叉 intermediate crossover把乘子作為區(qū)間 - d ，1 + d 上的隨機(jī)數(shù)時(shí)，Muhlenbein 和Schlierkamp - Voosen稱(chēng)其為擴(kuò)展中間交叉。3）啟發(fā)式交叉：如果父?jìng)€(gè)體1和父?jìng)€(gè)體2而父?jìng)€(gè)體1有較好的適應(yīng)度，則如下函數(shù)產(chǎn)生子個(gè)體:子個(gè)體=父?jìng)€(gè)體2 + Radio 3 （

8、父?jìng)€(gè)體1 -父?jìng)€(gè)體2）其中Radio指定子代離較好適應(yīng)度的父代有多遠(yuǎn)，其缺省值為1. 23、 變異的方法1）均有變異均有變異( Uniform Mutation) 操作是指分別用符合某一范圍內(nèi)均勻分布的隨即數(shù), 以某一較小的概率來(lái)替換個(gè)體編碼串中各個(gè)基因座上的原有基因值。均勻變異的具體操作過(guò)程是:( 1) 依次指定個(gè)體編碼串中的每各個(gè)基因座為變異點(diǎn);( 2) 對(duì)每一個(gè)變異點(diǎn), 以概率 pm從對(duì)應(yīng)基因的取值范圍內(nèi)取一隨機(jī)數(shù)來(lái)來(lái)代替原有基因值。2） 邊界變異算子 邊界變異算子( Boundary Mutation) 是均勻變異操作的一個(gè)變形遺傳算法。在進(jìn)行邊界變異操作時(shí), 隨機(jī)地取基因座的二個(gè)對(duì)應(yīng)

9、邊界基因之一取代替原有基因值。3）非均勻變異算子 非均勻變異的具體操作過(guò)程于均勻那變異相似, 但它重點(diǎn)搜索原個(gè)體附近的微小區(qū)域。在進(jìn)行由 X=X1X2XkXl向X=X1X2Xk Xl的非均勻變異操作時(shí), 若變異點(diǎn) Xk處的基因值取值范圍為Ukmin,Ukmax, 則新的基因 Xk 由下式確定:式中, (t, y),( y 表示 Ukmax- Xk和 Xk- Ukmin) 表示0, y范圍內(nèi)符合非均勻分布的一個(gè)隨機(jī)數(shù), 要求隨著進(jìn)化代數(shù) t 的增加,(t, y)接近于 0 的概率也逐漸增加。例如, (t, y)可按下式定義: (t, y)=y.(1-r(1- t/T)b)式中 r 為0,1范圍內(nèi)符合均勻分布的一個(gè)隨機(jī)數(shù), T 時(shí)最大進(jìn)化代數(shù), b 時(shí)一個(gè)系統(tǒng)參數(shù), 它決定了隨機(jī)數(shù)擾動(dòng)對(duì)進(jìn)化代數(shù) t 的依賴(lài)程度。4）高斯變異算子高斯變異( Gaussian Muta