遺傳算法編碼

1、遺傳算法編碼讀萬卷書不如行萬里路，今天下決心寫一個(gè)SGA(Simple Genetic Alogrithms)程序，是求解非約束優(yōu)化問題。max f(x1,x2) = 21.5 + x1*sin(4 * PI *x1) + x2*sin(20 * PI * x2)-3.0 = x1 = 12.14.1 = x2 = 5.8這可是遺傳算法中最容易的，可是結(jié)果卻令人失望，在整個(gè)求解過程中都收斂在局部最優(yōu)，只有通過加大變異率才能求得全局最優(yōu)，但問題可想而知：全局最優(yōu)解不穩(wěn)定，就好像是曇花一現(xiàn)。 查了一下資料才發(fā)現(xiàn)是編碼設(shè)計(jì)的問題。我用的是二進(jìn)制編碼。 編碼是應(yīng)用遺傳算法時(shí)要解決的首要問題，也是設(shè)計(jì)遺

2、傳算法時(shí)的一個(gè)關(guān)鍵步驟。編碼方法影響到交叉算子、變異算子等遺傳算子的運(yùn)算方法，大很大程度上決定了遺傳進(jìn)化的效率。 迄今為止人們已經(jīng)提出了許多種不同的編碼方法?？偟膩碚f，這些編碼方法可以分為三大類：二進(jìn)制編碼法、浮點(diǎn)編碼法、符號(hào)編碼法。下面我們從具體實(shí)現(xiàn)角度出發(fā)介紹其中的幾種主要編碼方法。 1.二進(jìn)制編碼方法： 它由二進(jìn)制符號(hào)0和1所組成的二值符號(hào)集。它有以下一些優(yōu)點(diǎn)：1) 編碼、解碼操作簡單易行2) 交叉、變異等遺傳操作便于實(shí)現(xiàn)3) 符合最小字符集編碼原則4) 利用模式定理對(duì)算法進(jìn)行理論分析。 二進(jìn)制編碼的缺點(diǎn)是：對(duì)于一些連續(xù)函數(shù)的優(yōu)化問題，由于其隨機(jī)性使得其局部搜索能力較差，如對(duì)于一些高精度

3、的問題（如上題），當(dāng)解迫近于最優(yōu)解后，由于其變異后表現(xiàn)型變化很大，不連續(xù)，所以會(huì)遠(yuǎn)離最優(yōu)解，達(dá)不到穩(wěn)定。而格雷碼能有效地防止這類現(xiàn)象 2.格雷碼方法： 格雷碼方法是這樣的一種編碼方法，其連續(xù)兩個(gè)整數(shù)所對(duì)應(yīng)的編碼值之間僅僅只有一個(gè)碼位是不同的。如下表十進(jìn)制二進(jìn)制格雷碼000000000100010001200100011300110010401000110501010111601100101701110100810001100910011101101010111111101111101211001010131101101114111010011511111000 增加遺傳距離假設(shè)有一個(gè)二進(jìn)制編碼

4、B=bmbm-1b2b1，其對(duì)應(yīng)的格雷碼為G=gmgm-1g2g1由二進(jìn)制編碼轉(zhuǎn)格雷碼的轉(zhuǎn)換公式為： gm = bm gi = bi+1bi ，i=m-1,m-2,2,1（真異或假的結(jié)果是真，假異或真的結(jié)果也是真，真異或真的結(jié)果是假，假異或假的結(jié)果是假）由格雷碼轉(zhuǎn)二進(jìn)制的轉(zhuǎn)換公式為： bm = gm bi = bi+1gi, i=m-1,m-2,2,1從以上表格可以看出，當(dāng)一個(gè)染色體變異后，它原來的表現(xiàn)現(xiàn)和現(xiàn)在的表現(xiàn)型是連續(xù)的。 格雷碼編碼的主要優(yōu)點(diǎn)是：1) 便于提高遺傳算法的局部搜索能力2) 交叉、變異等遺傳操作便于實(shí)現(xiàn)3) 符合最小字符集編碼原則4) 便于利用模式定理對(duì)算法進(jìn)行理論分析3.

5、浮點(diǎn)編碼法 對(duì)于一些多維、高精度要求的連續(xù)函數(shù)優(yōu)化問題，使用二進(jìn)制編碼來表示個(gè)體時(shí)將會(huì)有一些不利之處。 二進(jìn)制編碼存在著連續(xù)函數(shù)離散化時(shí)的映射誤差。個(gè)體長度較知時(shí)，可能達(dá)不到精度要求，而個(gè)體編碼長度較長時(shí)，雖然能提高精度，但卻使遺傳算法的搜索空間急劇擴(kuò)大。 所謂浮點(diǎn)法，是指個(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來表示。在浮點(diǎn)數(shù)編碼方法中，必須保證基因值在給定的區(qū)間限制范圍內(nèi)，遺傳算法中所使用的交叉、變異等遺傳算子也必須保證其運(yùn)算結(jié)果所產(chǎn)生的新個(gè)體的基因值也在這個(gè)區(qū)間限制范圍內(nèi)。 浮點(diǎn)數(shù)編碼方法有下面幾個(gè)優(yōu)點(diǎn)：1) 適用于在遺傳算法中表示范圍較大的數(shù)2) 適用于精度要求較高的遺傳算法3) 便于較大空間的遺傳搜索4) 改善了遺傳算法的計(jì)算復(fù)雜性，提高了運(yùn)算交率5) 便于遺傳算法與經(jīng)典優(yōu)化方法的混合使用6) 便于設(shè)計(jì)針對(duì)問題的專門知識(shí)的知識(shí)型遺傳算子7) 便于處理復(fù)雜的決策變量約束條件4.符號(hào)編碼法 符號(hào)編碼法是指個(gè)體染色體編碼串中的基因值取自一個(gè)無數(shù)值含義、而只有代碼含義的符號(hào)集如A,B,C。 符號(hào)編碼的主要優(yōu)點(diǎn)是：1) 符合有意義積術(shù)塊編碼原則2) 便于在遺傳算法中利用所求解問題的專門知識(shí)3) 便