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