基本遺傳算法及的應用舉例

1、實用標準文案基本遺傳算法及應用舉例遺傳算法(Genetic Algorithms)是一種借鑒生物界自然選擇和自然遺傳機制的隨機、高度并行、自適應搜索算法。遺傳算法是多學科相互結(jié)合與滲透的產(chǎn)物。目前它已發(fā)展成一種自組織、自適應的多學科技術(shù)。針對各種不同類型的問題，借鑒自然界中生物遺傳與進化的機理，學者們設(shè)計了不同的編碼方法來表示問題的可行解，開發(fā)出了許多不同環(huán)境下的生物遺傳特征。這樣由不同的編碼方法和不同的遺傳操作方法就構(gòu)成了各種不同的遺傳算法。但這些遺傳算法有共同的特 點，即通過對生物的遺傳和進化過程中的選擇、交叉、變異機理的模仿來完成對最優(yōu)解的自適應搜索過程。基于此共同點，人們總結(jié)出了最基本

2、的遺傳算法一一基本遺傳算法?；?遺傳算法只使用選擇、交叉、變異三種基本遺傳操作。遺傳操作的過程也比較簡單、容易理 解。同時，基本遺傳算法也是其他一些遺傳算法的基礎(chǔ)與雛形。1.1.1編碼方法用遺傳算法求解問題時，不是對所求解問題的實際決策變量直接進行操作，而是對表示可行解的個體編碼的操作，不斷搜索出適應度較高的個體，并在群體中增加其數(shù)量，最終尋找到問題的最優(yōu)解或近似最優(yōu)解。因此，必須建立問題的可行解的實際表示和遺傳算法的染色體位串結(jié)構(gòu)之間的聯(lián)系。在遺傳算法中，把一個問題的可行解從其解空間轉(zhuǎn)換到遺傳算法 所能處理的搜索空間的轉(zhuǎn)換方法稱之為編碼。反之，個體從搜索空間的基因型變換到解空間的表現(xiàn)型的方

3、法稱之為解碼方法。編碼是應用遺傳算法是需要解決的首要問題，也是一個關(guān)鍵步驟。迄今為止人們已經(jīng)設(shè)計出了許多種不同的編碼方法。基本遺傳算法使用的是二進制符號0和1所組成的二進制符號集 0, 1,也就是說，把問題空間的參數(shù)表示為基于字符集0, 1構(gòu)成的染色體位串。每個個體的染色體中所包含的數(shù)字的個數(shù)L稱為染色體的長度或稱為符號串的長度。一般染色體的長度L為一固定的數(shù)，如X=10011100100011010100表示一個個體，該個體的染色體長度L=20。二進制編碼符號串的長度與問題所要求的求解精度有關(guān)。假設(shè)某一參數(shù)的取值范圍是a, b,我們用長度為L的二進制編碼符號串來表示該參數(shù)，總共能產(chǎn)生21種不

4、同的編碼,若參數(shù)與編碼的對應關(guān)系為00000000000 00000000=0一 a00000000000 00000001=1 a+ 811111111111111111111= 2L-1 一 b則二進制編碼的編碼精度b a2l 1假設(shè)某一個個體的編碼是Xkakak2aki ,則對應的解碼公式為、，cba /C ° L j xk aL7( akj2)21 j 1例如，對于x 0,1023,若用長度為10的二進制編碼來表示該參數(shù)的話，則下述符號串:X=0010101111就表示一個個體，它對應的參數(shù)值是X=175.此時的編碼精度為1.二進制編碼方法相對于其它編碼方法的優(yōu)點，首先是編碼

5、、解碼操作簡單易行；其次是交叉遺傳操作便于實現(xiàn)；另外便于對算法進行理論分析。2.個體適應度函數(shù)在遺傳算法中，根據(jù)個體適應度的大小來確定該個體在選擇操作中被選定的概率。個體的適應度越大，該個體被遺傳到下一代的概率也越大；反之，個體的適應度越小，該個體被遺傳到下一代的概率也越小?；具z傳算法使用比例選擇操作方法來確定群體中各個個體 是否有可能遺傳到下一代群體中。為了正確計算不同情況下各個個體的選擇概率，要求所有個體的適應度必須為正數(shù)或為零，不能是負數(shù)。這樣，根據(jù)不同種類的問題，必須預先確定 好由目標函數(shù)值到個體適應度之間的轉(zhuǎn)換規(guī)則，特別是要預先確定好目標函數(shù)值為負數(shù)時的處理方法。設(shè)所求解的問題為：

6、maxf(x), x D.對于求目標函數(shù)最小值的優(yōu)化問題，理論上只需簡單地對其增加一個負號就可將其轉(zhuǎn) 化為求目標函數(shù)最大值的問題，即min f(x) max( f(x).當優(yōu)化問題是求函數(shù)最大值，并且目標函數(shù)總?cè)≌禃r，可以直接設(shè)定個體的適應度函數(shù)值F(x)就等于相應的目標函數(shù)值 f (x),即 F(x) f (x).但實際目標優(yōu)化問題中的目標函數(shù)有正也有負，優(yōu)化目標有求函數(shù)最大值，也有求函 數(shù)最小值，顯然上面兩式保證不了所有情況下個體的適應度都是非負數(shù)這個要求，必須尋求出一種通用且有效的由目標函數(shù)值到適應度之間的轉(zhuǎn)換關(guān)系，有它來保證個體適應度總?cè)》秦撝?。為滿足適應度取負值的要求，基本遺傳算法

7、一般采用下面方法將目標函數(shù)值f(x)變換為個體的適應度F(x).對于求目標函數(shù)最大值的優(yōu)化方法問題，變換方法為f f(x) Cmin ,f(x) Cmin 0時，F(xiàn)(x) <00f(x) Cmin 0時，式中，Cm.為一個適當?shù)南鄬Ρ容^小的數(shù)，它可以是預先指定的一個較小的數(shù)，或進化到當前代為止的最小目標函數(shù)值，又或當前代或最近幾代群體中的最小目標函數(shù)值。3 .基本遺傳操作方法(1)比例選擇：選擇或稱復制，建立在對個體適應度進行評價的基礎(chǔ)之上。其作用是從當前群體中選擇出一些比較優(yōu)良的個體，并將其復制到下一代群體中。 基本遺傳算法采用比例選擇的方法，所謂比例選擇，是指個體在選擇操作中被選中的

8、概率與該個體的適應度大 小成正比。(2)單點交叉。單點交叉又稱簡單交叉，是遺傳算法所使用的交叉操作方法。(3)基本位變異。基本位變異石最簡單和最基本的變異操作，也是基本遺傳算法中所使用的變異操作方法。 對于基本遺傳算法中用二進制編碼符號串所表示的個體，對需要進行變異操作的某一基因，若原有基因值為 0,則變異操作將該基因值變?yōu)?1 ;反之，若原有基 因值為1 ,則變異操作將其變?yōu)?0.4 .基本遺傳算法的運行參數(shù)執(zhí)行基本遺傳算法時，有4個參數(shù)需要事先指定。它們是群體的大小 M、交叉概率Pc、 變異概率Pm及終止的代數(shù)T.(1) 群體大小M.群體的大小M表示群體中所含個體的數(shù)量。當M取值較小時，可

9、提高遺傳算法的運算速度，但卻降低了群體的多樣性，有可能會引起遺傳算法 的早熟現(xiàn)象；而當M取值較大時，又會使得遺傳算法的運行效率偏低。一般建議范圍是20100.(2) 交叉概率Pc。交叉操作室遺傳算法產(chǎn)生新個體的主要方法，所以交叉概率一般應取較大值。但若取值過大的話，它又會破壞群體活動的優(yōu)良模式，對進化運 算反而產(chǎn)生不利影響；若取值過小的話，產(chǎn)生新個體的速度有太慢。一般建議 的取值范圍是 0.41.00.(3) 變異概率Pm。若變異概率Pm取值較大的話，雖能夠產(chǎn)生出較多的新個體，但也有可能破壞掉很多較好的模式，使得遺傳算法的性能近似于隨機搜索算法的 性能；若變異概率 pmW值太小的話，則變異操作

10、產(chǎn)生新個體的能力和抑制早 熟現(xiàn)象的能力就會較差。一般建議的取值范圍是0.0010.1.(4) 終止彳弋數(shù)T.終止彳弋數(shù)T式表示遺傳算法運行結(jié)束條件的一個參數(shù)，它表示遺傳算法運行到指定的進化代數(shù)之后就停止運行，并將當前群體中的最佳個體作為 所求問題的最優(yōu)解輸出。一般建議的取值范圍是1001000.至于遺傳算法的終止條件，還可以利用某種判定準則，當判定出群體已經(jīng)進化成熟且不 再有進化趨勢時就可終止算法的運行過程。如連續(xù)幾代個體平均適應度的差異小于某一個極小的值；或者群體中所有個體適應度的方差小于某一個極小的值。這 4個參數(shù)對遺傳算法 的搜索結(jié)果及搜索效率都有一定的影響，目前尚無合理選擇它們的理論根

11、據(jù)在遺傳算法的實際應用中，往往需要經(jīng)過多次的試算后才能確定出這些參數(shù)合理的取值范圍或取值大小?；具z傳算法是一個迭代過程，它模仿生物在自然環(huán)境中的遺傳和進化機理，反復將選 擇操作、交叉操作、 變異操作作用與群體，最終可得到問題的最優(yōu)解或近似最優(yōu)解。雖然算 法的思想比較簡單，但它卻具有一定的實用價值，能夠解決一些復雜系統(tǒng)的優(yōu)化計算問題。遺傳算法的應用步驟如下；遺傳算法提供了一種求解復雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的領(lǐng)域和種 類。對一個需要進行優(yōu)化計算的實際應用問題，一般可按下述步驟來構(gòu)造求解該問題的遺傳算法。第一步：建立優(yōu)化模型，即確定出目標函數(shù)、決策變量及各種約束條件以及數(shù)學描述形

12、式或量化方法。第二步：確定表示可行解的染色體編碼方法，也即確定出個體的基因型 x及遺傳算法的 搜索空間。第三步：確定解碼方法，即確定出個體基因型 x到個體表現(xiàn)型x的對應關(guān)系或轉(zhuǎn)換方法。第四步：確定個體適應度的量化評價方法，即確定出由目標函數(shù)值f x到個體適應度F x的轉(zhuǎn)換規(guī)則。第五步：設(shè)計遺傳操作方法，即確定出選擇運算、 交叉運算、變異運算等具體操作方法。第六步：確定遺傳算法的有關(guān)運行參數(shù)，即確定出遺傳算法的 M、T、Pc、Pm等參數(shù)。由上述構(gòu)造步驟可以看出，可行解的編碼方法、遺傳操作的設(shè)計是構(gòu)造遺傳算法時需要 考慮的兩個主要問題，也是設(shè)計遺傳算法時的兩個關(guān)鍵步驟。對不同的優(yōu)化問題需要使用不同

13、的編碼方法和不同的遺傳操作，它們與所求解的具體問題密切相關(guān)，因而對所求解問題的理解程度是遺傳算法應用成功與否的關(guān)鍵。例1 . 1 . 1求解規(guī)劃問題22max f xi, x2xix2,s.t. xi0,1,2, ,7 ,x20,1,2,7.解主要運算過程如表 7-3所示。(1)個體編碼.遺傳算法的運算對象是表示個體的符號串，所以必須把變量1 . 1基本遺傳算法的構(gòu)成要素 為，x2編碼為一種符號串。該例題中， 為和x2取07之間 的整數(shù)，可分別用 3位無符號二進制整數(shù)來表示，將它們連接在一起所組成的6位無符號二進制整數(shù)就形成了個體的基因型，表示一個可行解。例如，基因型 x=101110 所對應

14、的 表現(xiàn)型是x= (5, 6) T。個體的表現(xiàn)型 x和基因型x之間可以通過編碼和解碼相互轉(zhuǎn)換。(2)初始群體的產(chǎn)生。遺傳算法是對群體進行遺傳操作，需要準備一些表示起始搜索點的初始群體數(shù)據(jù)。本例中群體規(guī)模的大小M取為4,即群體由4個個體組成，每個個體可通過隨機方法產(chǎn)生。一個隨機產(chǎn)生的初始群體如表7-3中第2欄所示。(3)適應度計算。本例中，目標函數(shù)總?cè)》秦撝担?并且是以求函數(shù)最大值為優(yōu)化目標， 故可直接利用目標函數(shù)值作為個體的適應度，即F x f X。為計算函數(shù)的目標值，需先對個體基因型X進行解碼。表7-3中第3、第4欄所示為初始群體各個個體的解碼結(jié)果，第5欄所示為各個個體所對應的目標函數(shù)彳1,

15、它也是個體的適應度，第 5欄中還給出了群 體中適應度的最大值和平均值。表7-31個體編號i2初始群體P(0)3X14X25fi X,X26fi/fi10111013534fi 14334fmaX 5025 f 35.75500.242101011530.243011100340.174111001710.357選擇次數(shù)8選擇結(jié)果9配對情況10交叉點位直11父義結(jié)果12變異點13變異結(jié)果10111011-23-41-2 : 23-4 : 4011001501100111110011111011111110101011101001101001211100111101111101114子代群體P (

16、1)15X116X217fi X,X20110013110fi1921111117798fmax981010015126f481110117358(4)選擇操作.其具體操作過程是先計算出群體中所有個體的適應度的總和fi及每個個體的相對適應度的大小fi/fi ,如表7-3中5、6欄所示。表7-3中第7、8欄表示隨機產(chǎn)生的選擇結(jié)果。(5)交叉操作。本例中采用單點交叉的方法，并取交叉概率 Pc=1.00 。表7-3中第 11欄所示為交叉運算的結(jié)果。(6)變異操作。為了能顯示變異操作，取變異概率Pm=0.25,并采用基本位變異的方法進行變異運算。表 7-3第13欄所示為變異運算的結(jié)果。對群體P (t)