【文章內(nèi)容簡(jiǎn)介】 幾位基因座上的基因值做變異運(yùn)算 b、均勻變異：指分別用符合某一范圍內(nèi)隨機(jī)數(shù)，以某一較小概率來(lái)替換個(gè)體編碼串中各個(gè)基因座上的原有基因值。 c、 邊界變異：邊界變異是上述均勻變異操作的一個(gè)變形遺傳算法。在進(jìn)行邊界變異操作時(shí)，隨機(jī)的取基因座的 2 個(gè)對(duì)應(yīng)邊界基因值之一去 替換原來(lái)的基因值。 d、非均勻變異：對(duì)每個(gè)基因座都以相同的概率進(jìn)行變異運(yùn)算之后相當(dāng)于整個(gè)解向量在解空間中，作了一個(gè)輕微的變動(dòng)。 遺傳算法的其他運(yùn)行參數(shù) （ 1） 編碼串長(zhǎng)度 L：使用二進(jìn)制來(lái)表示個(gè)體時(shí)，編碼串長(zhǎng)度 L 的選取與問(wèn)題所要求的求 解精度有關(guān)。 （ 2） 群體大小 M：表示群體中所含個(gè)體的數(shù)量。 M 取值越小可提運(yùn)算速度但降低群體多樣性。容易引起遺傳算法的早熟現(xiàn)象，而當(dāng) M 取值較大時(shí)降低了遺傳算法的運(yùn)行效率。一般建議范圍 20100。 （ 3） 交叉概率 Pc。交叉操作是遺傳算法中產(chǎn)生新個(gè)體的主要方法，一般建議范圍 是 。隨著遺傳算法在線(xiàn)性能的提高可以增大交叉概率的取值。 （ 4） 變異概率 Pm。一般建議范圍是 ~，隨著遺傳算法在線(xiàn)性能的下降，可以減蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 18 小變異概率的取值 （ 5） 終止帶寬 T它表示遺傳算法運(yùn)行到指定的進(jìn)化代數(shù)之后就停止運(yùn)行并將最佳個(gè)體作為所求問(wèn)題的最優(yōu)解輸出。建議范圍是 100~1000 （ 6） 代溝 G：表示每一代群體中被替換掉的個(gè)體在全部個(gè)體中所占的百分比。 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 19 第四章：用遺 傳算法求解復(fù)雜函數(shù)極值問(wèn)題 本課題采用遺傳算法求解函數(shù)最大值問(wèn)題，應(yīng)用常規(guī)的二進(jìn)度編碼，利用賭輪算法選擇最憂(yōu)群體，進(jìn)行交叉變異等遺傳操作，最終求出所求函數(shù)最大值即最憂(yōu)解，最后在 MATLAB語(yǔ)言環(huán)境下進(jìn)行調(diào)試，更改相關(guān)參數(shù)，得出幾組最憂(yōu)解圖象并進(jìn)行對(duì)比分析。 所求問(wèn)題為 f(x)=x+9*sin(4x)+8*cos(3x)的最大值 ， 其中 定義域?yàn)?5=x=12，采用二進(jìn)制編碼，選取種群個(gè)體數(shù)目為 20， 設(shè)定 二進(jìn)制編碼長(zhǎng)度為 10，交叉概率為 ，變異概率是 。 本算例的求解步驟 （ 1） 確定決策變量 和約束條件 【問(wèn)題】求 f(x)= 11*sin(6*x)+7*cos(5*x)的最大值，其中 0=x=2*pi 【分析】選擇二進(jìn)制編碼，種群中的個(gè)體數(shù)目為 20，二進(jìn)制編碼長(zhǎng)度為 10，交叉概率為 ,變異概率為 （ 2） 確定編碼方法 用長(zhǎng)度為十的二進(jìn)制編碼串來(lái)分別表示兩個(gè)決策變量 Umax(2π) Umin(0)。 10位二進(jìn)制 編碼串可以表示為 0 到 1023 之間的 1024 個(gè)不同的數(shù)，故將 Umax Umin的定義域離散為 1023個(gè)均等的區(qū)域，包括兩個(gè)端點(diǎn)在內(nèi)共有 1024個(gè)不同的離散點(diǎn)。從離散點(diǎn) Umin 到 Umax，依次讓它們分別對(duì)應(yīng)從 0000000000（ 0）到 1111111111（ 1023）之間的二進(jìn)制編碼。再將分別表示 Umax Umin 的二進(jìn)制編碼串聯(lián)在一起，組成一個(gè) 20 位長(zhǎng)的二進(jìn)制編碼串，它構(gòu)成了這個(gè)函數(shù)優(yōu)化問(wèn)題的染色體編碼方法。使用這種編碼方法，解空間和遺傳算法的搜索空間具有一一對(duì)應(yīng)的關(guān)系。 例如：就表示為一個(gè)個(gè)體的基因型，其中前十位表示 Umax 后十位表示 Umin X: 11111111 00000000 2π 0 00000000…00000000=0 ? Umin 00000000…00000001=1 ? Umin+￡ … … … 11111111…11111111=2^l1 ? Umax 則二進(jìn)制編碼精度為： ￡ =UmaxUmin/2^l1 公式（ 41） 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 20 假設(shè)某一個(gè)個(gè)體編碼是 X: blbl1bl2…b2b1 確定解碼方法 Xi=Umin+ L ∑ bi* 2^( i1) * UmaxUmin/2^l 1 i=1 公式（ 42） 解碼時(shí)需先將 20 位長(zhǎng)的二進(jìn)制編碼串切斷為兩個(gè) 10 位長(zhǎng)的二進(jìn)制編碼串，然后分別將他們轉(zhuǎn)化為對(duì)應(yīng)的十進(jìn)制整數(shù)代碼，分別記為 Y1 Y2。根據(jù)前述個(gè)體編碼方法和定義域的離散化方法可知，將代碼 Yi 轉(zhuǎn)換為變量 Xi 的解碼公式為： （ 3） 確定個(gè)體評(píng)價(jià)方法 在遺傳算法中，以個(gè)體適應(yīng)度的大小來(lái)確定該個(gè)體被遺傳到下 一代群體中的概率。基本遺傳算法使用比例選擇算子來(lái)確定群體中各個(gè)個(gè)體遺傳到下一代群體中的數(shù)量。為正確計(jì)算不同情況下各個(gè)個(gè)體的遺傳概率，要求所有個(gè)體的適應(yīng)度必須為整數(shù)或者是零，不能是負(fù)數(shù) 為滿(mǎn)足適應(yīng)度取非負(fù)值的要求，基本遺傳算法一般采用下面兩種方法之一將目標(biāo)函數(shù) f(x)變換為個(gè)體適應(yīng)度 F(X) 方法一：對(duì)于求目標(biāo)函數(shù)最大值的優(yōu)化問(wèn)題，變換方法為： F(X)={ F(X) + Cmin, if f(x)+ Cmin0 0, if f(x)+Cmin≤ 0 公式（ 43） 式中， Cmin 為一個(gè)適當(dāng)?shù)叵鄬?duì)比較小的數(shù)，它可用下面幾種方法之一來(lái)選取。 （一）預(yù)先指定一個(gè)較小的數(shù)。 （二）進(jìn)化到當(dāng)前代為止的最小目標(biāo)函數(shù)值。 （三）當(dāng)前代或最近幾代群體中的最小目標(biāo)函數(shù)值。 方法二：對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問(wèn)題，變換方法為： F(X)={ Cmaxf (X) , if f (X)Cmax 0, if f(x)≥ Cmax 公式（ 44） 式中， Cmax 位為一個(gè)適當(dāng)?shù)叵鄬?duì)比較 大的數(shù)，它可用下面幾種方法之一來(lái)選取。 （一）預(yù)先指定一個(gè)較大的數(shù)。 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 21 （二）進(jìn)化到當(dāng)前代為止的最大目標(biāo)函數(shù)值。 （三）當(dāng)前代或最近幾代群體中的最大目標(biāo)函數(shù)值 根據(jù)適者生存原則選擇下一代的個(gè)體。在選擇時(shí)，以適應(yīng)度為選擇原則。適應(yīng)度準(zhǔn)則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則。 給出目標(biāo)函數(shù) f，則 f(bi)稱(chēng)為個(gè)體 bi 的適應(yīng)度。以 (386) 為選中 bi 為下一代個(gè)體的次數(shù)。 顯然．從式 (3— 86)可知： a、適應(yīng)度較高的個(gè)體，繁殖下一代的數(shù)目較多。 b、適應(yīng)度較小的個(gè)體，繁殖下一代的數(shù)目較少；甚至被淘汰。 這樣，就產(chǎn)生了對(duì)環(huán)境適應(yīng)能力較強(qiáng)的后代。對(duì)于問(wèn)題求解角度來(lái)講，就是選擇出和最優(yōu)解較接近的中間解。 （ 4） 設(shè)計(jì)遺傳算子 選擇運(yùn)算 a. 使用第三章的賭輪選擇算法 ,求解最佳適應(yīng)度種群： b. 分別求出 20 個(gè)初始種群中每個(gè)種群個(gè)體的適應(yīng)度函數(shù)，并計(jì)算所有種群的和S。 c. 在區(qū)間（ 0， S）上隨機(jī)的產(chǎn)生一個(gè)數(shù) r 從某個(gè)基因開(kāi)始，逐一取出 基因來(lái)，把它的適應(yīng)度加到 s 上去（ s 開(kāi)始為 0），如果 s 大于 r，則停止循環(huán)并返回當(dāng)前基因； 當(dāng)然，第一步在計(jì)算中只需要執(zhí)行一次 因此基因越是適應(yīng)環(huán)境那么它被選擇到的機(jī)會(huì)就越大。 交叉運(yùn)算 使用第三章的單點(diǎn)交叉算子 對(duì)于選中用于繁殖下一代的個(gè)體，隨機(jī)地選擇兩個(gè)個(gè)體的相同位置，按交叉概率 P。在選中的位置實(shí)行交換。這個(gè)過(guò)程反映了隨機(jī)信息交換；目的在于產(chǎn)生新的基因組合也即產(chǎn)生新的個(gè)體。交叉時(shí)，可實(shí)行單點(diǎn)交叉或多點(diǎn)交叉。 本例選用單點(diǎn)交叉法： 從選擇運(yùn)算求出適應(yīng)度較高的種群，從該種群種隨機(jī)抽出 2 個(gè)個(gè)體基因型 編碼進(jìn)行配對(duì)交叉 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 22 111111111 (個(gè)體基因型 ) 2π (個(gè)體表現(xiàn)型 ) 00000000 (個(gè)體基因型 ) 0 (個(gè)體表現(xiàn)型 ) 111111111+00000000=11011111 (產(chǎn)生的新個(gè)體 ) 種群的各個(gè)個(gè)體兩兩配對(duì)后以交叉概率 Pc= 隨機(jī)指定各個(gè)基因位進(jìn)行交叉運(yùn)算即生成新個(gè)體種群。 假如鄰接基因座之間的關(guān)系能夠提供比較好的個(gè)體性狀和較高的個(gè)體適應(yīng)的話(huà)則這個(gè)單點(diǎn)交叉操作破壞這種個(gè)體性狀和降低個(gè)體適應(yīng)度的可能性最小 變異運(yùn)算 使用第三章的 基本位變異算子確定遺 根據(jù)生物遺傳中基因變異的原理，以變異概率 Pm 對(duì)某些個(gè)體的某些位執(zhí)行變異。在變異時(shí)，對(duì)執(zhí)行變異的串的對(duì)應(yīng)位求反，即把 1 變?yōu)?0，把 0 變?yōu)?1。變異概率 Pm 與生物變異極小的情況一致，所以， Pm的取值較小，一般取 。 經(jīng)交叉運(yùn)算得到的新個(gè)體基因串種群以變異概率 Pm= 隨機(jī)指定有一位或幾位基因座上的基因值進(jìn)行變異操作 . 1101111111101011 (生成的新個(gè)體 ) 以變異概率分別對(duì)每個(gè)或者幾個(gè)基因位做變異操作就可以生成新的種群個(gè)體。 單靠變異不能在求解中得到好處。但是，它能保證算法過(guò)程不會(huì)產(chǎn)生無(wú)法進(jìn)化的單一群體。因?yàn)樵谒械膫€(gè)體一樣時(shí)，交叉是無(wú)法產(chǎn)生新的個(gè)體的，這時(shí)只能靠變異產(chǎn)生新的個(gè)體。也就是說(shuō)，變異增加了全局優(yōu)化的特質(zhì)。 遺傳算法的運(yùn)行參數(shù) 群體大小： M （ 20100） 終止代數(shù)： T （ 100500） 交叉概率： Pc （ ） 變異概率： Pm () 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 23 算例驗(yàn)證 【問(wèn)題】求 f(x)= 11*sin(6*x)+7*cos(5*x)的最大值，其中 0=x=2*pi 【分析 】選擇二進(jìn)制編碼，種群中的個(gè)體數(shù)目為 20，二進(jìn)制編碼長(zhǎng)度為 10，交叉概率為,變異概率為 X（個(gè)體表現(xiàn)型值） : Y（目標(biāo)函數(shù)值） : FINAL(最優(yōu)解 )= 由圖 可見(jiàn)，遺傳代數(shù)較小時(shí)， 交叉概率較大時(shí)圖象局部最優(yōu)解分散， 全局最優(yōu)解緩慢收斂。 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 24 【分析】選擇二進(jìn)制編碼，種群中的個(gè)體數(shù)目為 20，二進(jìn)制編碼長(zhǎng)度為 10，交叉概率為,變異概率為 X（個(gè)體表現(xiàn)型值） : Y（目標(biāo)函數(shù)值） : FINAL(最優(yōu)解 )= 由圖可見(jiàn)，當(dāng)交叉概率變小變異概 率變大 ，局部最憂(yōu)解減少，全局最優(yōu)解明顯。 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 25 【分析】選擇二進(jìn)制編碼，種群中的個(gè)體數(shù)目為 50，二進(jìn)制編碼長(zhǎng)度為 10，交叉概率為,變異概率為 X（個(gè)體表現(xiàn)型值） : Y（目標(biāo)函數(shù)值） : FINAL(最優(yōu)解 )= 由圖可見(jiàn)，遺傳代數(shù)增加，變異概率增加，全局最憂(yōu)解收斂性 最優(yōu) 。 程序調(diào)試總結(jié)： 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 26 (1) 群體大小 M 較小時(shí)可以提高遺傳算法的運(yùn)行速度 ,但是降低了群體的多樣性有可能引起算法的早熟現(xiàn)象，當(dāng) M 較大時(shí)使得運(yùn)行效率降低，一般建議范圍為 (20~100)最佳。 (2) 交叉操作是產(chǎn)生新個(gè)體的主要方法一般應(yīng)取值較大，但太大會(huì)破壞群體的優(yōu)良模型，對(duì)進(jìn)化產(chǎn)生不利影響。取值太小產(chǎn)生新個(gè)體速度又較慢，一般建議范圍 (~) (3) 變異概率 Pm 較大時(shí)雖能產(chǎn)生比較多的新個(gè)體，但有可能破壞掉較好的模型使得遺傳算法的性能近似于隨機(jī)搜索算法性能， Pm 太小變異操作產(chǎn)生新個(gè)體和抑制早熟的能力 較差，最佳范圍 (~) 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 27 第五章 結(jié)論 本文首先介紹遺傳算法歷史發(fā)展基本原理方法對(duì)遺傳算法的編碼，解碼方法進(jìn)行深入分析，從而確定了用二進(jìn)制編碼方法來(lái)求解復(fù)雜函數(shù)優(yōu)化問(wèn)題，通過(guò)選澤，交叉，變異等遺傳操作，最后用 MATLAB 語(yǔ)言進(jìn)行調(diào)試，改變遺傳算法相關(guān)參數(shù)求出函數(shù)最優(yōu)解并進(jìn)行對(duì)比分析。得出遺傳算法不僅可求解簡(jiǎn)單函數(shù)最值問(wèn)題，而且可以?xún)?yōu)化許多復(fù)雜系統(tǒng)函數(shù)問(wèn)題，它提供了一種系統(tǒng)優(yōu)化函數(shù)的通用框架，它不依賴(lài)于問(wèn)題的具 體領(lǐng)域，對(duì)問(wèn)題的種類(lèi)具有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多科學(xué)領(lǐng)域。 參考文獻(xiàn) [1]《遺傳算法原理及應(yīng)用》 /周明，孫樹(shù)棟編著 北京國(guó)防工業(yè)出版