【正文】 newpop]=selection(pop,fitvalue)。 %運(yùn)行初始化函數(shù)，隨機(jī)產(chǎn)生初始群體 for i=1:20%20 為迭代次數(shù) [objvalue]=calobjvalue(pop)。 %設(shè)置交叉概率，本例中交叉概率是定值，若想設(shè)置變化的交叉概率可用表達(dá)式表示，或從寫(xiě)一個(gè) %交叉概率函數(shù)，例如用神經(jīng)網(wǎng)絡(luò)訓(xùn)練得到的值作為交叉概率 pm=。 %設(shè)置初始參數(shù)，群體大小 chromlength=8。 參考文獻(xiàn) [1]《遺傳算法原理及應(yīng)用》 /周明，孫樹(shù)棟編著 北京國(guó)防工業(yè)出版社， 1999。取值太小產(chǎn)生新個(gè)體速度又較慢，一般建議范圍 (~) (3) 變異概率 Pm 較大時(shí)雖能產(chǎn)生比較多的新個(gè)體，但有可能破壞掉較好的模型使得遺傳算法的性能近似于隨機(jī)搜索算法性能， Pm 太小變異操作產(chǎn)生新個(gè)體和抑制早熟的能力較差，最佳 范圍 (~) 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 28 第五章 結(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ì)比分析。 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 27 程序調(diào)試總結(jié)： (1) 群體大小 M 較小時(shí)可以提高遺傳算法的運(yùn)行速度 ,但是降低了群體的多樣性有可能引起算法的早熟現(xiàn)象，當(dāng) M 較大時(shí)使得運(yùn)行效率降低，一般建議范圍為 (20~100)最佳。 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 25 【 分析】選擇二進(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)解明顯。也就是說(shuō)，變異增加了全局優(yōu)化的特質(zhì)。但是，它能保證算法過(guò)程不會(huì)產(chǎn)生無(wú)法進(jìn)化的單一群體。 經(jīng)交叉運(yùn)算得到的新個(gè)體基因串種群以變異概率 Pm= 隨機(jī)指定有一位或幾位基因座上的基因值進(jìn)行變異操作 . 1101111111101011 (生成的新個(gè)體 ) 以變異概率分別對(duì)每個(gè)或者幾個(gè)基因位做變異操作就可以生成新的種群個(gè)體。在變異時(shí)，對(duì)執(zhí)行變異的串的對(duì)應(yīng)位求反，即把 1 變?yōu)?0，把 0 變?yōu)?1。 本例選用單點(diǎn)交叉法： 從選擇運(yùn)算求出適應(yīng)度較高的種群，從該種群種隨機(jī)抽出 2 個(gè)個(gè)體基因型編碼進(jìn)行配對(duì)交叉 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 23 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è)體種群。這個(gè)過(guò)程反映了隨機(jī)信息交換；目的在于產(chǎn)生新的基因組合也即產(chǎn)生新的個(gè)體。 交叉運(yùn)算 使用第三章的單點(diǎn)交叉算子 對(duì)于選中用于繁殖下一代的個(gè)體，隨機(jī)地選擇兩個(gè)個(gè)體的相同位置，按交叉概率 P。 （ 4） 設(shè)計(jì)遺傳算子 選擇運(yùn)算 a. 使用第三章的賭輪選擇算法 ,求解最佳適應(yīng)度種群： b. 分別求出 20 個(gè)初始種群中每個(gè)種群個(gè)體的適應(yīng)度函數(shù)，并計(jì)算所有種群的和S。 這樣，就產(chǎn)生了對(duì)環(huán)境適應(yīng)能力較強(qiáng)的后代。 顯然．從式 (3— 86)可知： a、適應(yīng)度較高的個(gè)體，繁殖下一代的數(shù)目較多。 給出目標(biāo)函數(shù) f，則 f(bi)稱(chēng)為個(gè)體 bi 的適應(yīng)度。在選擇時(shí)，以適應(yīng)度為選擇原則。 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 22 （二）進(jìn)化到當(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)選取。 （二）進(jìn)化到當(dāng)前代為止的最小目標(biāo)函數(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)選取。根據(jù)前述個(gè)體編碼方法和定義域的離散化方法可知，將代碼 Yi 轉(zhuǎn)換為變量 Xi 的解碼公式為： （ 3） 確定個(gè)體評(píng)價(jià)方法 在遺傳算法中，以個(gè)體適應(yīng)度的大小來(lái)確定該個(gè)體被遺傳到下一代群體 中的概率。使用這種編碼方法，解空間和遺傳算法的搜索空間具有一一對(duì)應(yīng)的關(guān)系。從離散點(diǎn) Umin 到 Umax，依次讓它們分別對(duì)應(yīng)從 0000000000（ 0）到 1111111111（ 1023）之間的二進(jìn)制編碼。 本算例的求解步驟 （ 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)。 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 20 第四章：用遺傳算法求 解復(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ì)比分析。一般建議范圍是 ~，隨著遺傳算法在線(xiàn)性能的下降，可以減蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 19 小變異概率的取值 （ 5） 終止帶寬 T它表示遺傳算法運(yùn)行到指定的進(jìn)化代數(shù)之后就停止運(yùn)行并將最佳個(gè)體作為所求問(wèn)題的最優(yōu)解輸出。隨著遺傳算法在線(xiàn)性能的提高可以增大交叉概率的取值。 （ 3） 交叉概率 Pc。容易引起遺傳算法的早熟現(xiàn)象，而當(dāng) M 取值較大時(shí)降低了遺傳算法的運(yùn)行效率。 （ 2） 群體大小 M：表示群體中所含個(gè)體的數(shù)量。 d、非均勻變異：對(duì)每個(gè)基因座都以相同的概率進(jìn)行變異運(yùn)算之后相當(dāng)于整個(gè)解向量在解空間中，作了一個(gè)輕微的變動(dòng)。 c、 邊界變異：邊界變異是上述均勻變異操作的一個(gè)變形遺傳算法。 均勻交叉示意圖 11001011 + 11011101 = 11011111 圖（ 33） 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 18 變異算子 遺傳算法中所謂變異運(yùn)算是指?jìng)€(gè)體染色體編碼串中某些基因座上的基因值用該基因座的其他等位基因替換，從而形成新個(gè)體。 具體操作過(guò)程： 1 在相互配對(duì)的兩個(gè)個(gè)體編碼串中隨 機(jī)設(shè)置 2 個(gè)交叉點(diǎn) 2 交換 2 個(gè)個(gè)體在所設(shè)定的兩個(gè)交叉點(diǎn)之間的部分染色體。 特點(diǎn)：假如鄰接基因座之間的關(guān)系能夠提供比較好的個(gè)體性狀和較高的個(gè)體適應(yīng)度的話(huà)則這個(gè)單點(diǎn)交叉操作破壞這種個(gè)體性狀和降低個(gè)體適應(yīng)度的可能性最小。 交叉算子的設(shè)計(jì)過(guò)程： 1 如何確定交 叉點(diǎn)的位置 2 如何進(jìn)行部分基因交換 最常用的交叉算子是單點(diǎn)交叉算子。 這個(gè)過(guò)程可以被下面的這個(gè)算法來(lái)模擬： 1． ［求和］ 計(jì)算所 有種群的適應(yīng)度的和 S； 2． ［選擇］ 在區(qū)間（ 0， S）上隨機(jī)的產(chǎn)生一個(gè)數(shù) r； 3． ［循環(huán)］ 從某個(gè)基因開(kāi)始，逐一取出基因來(lái)，把它的適應(yīng)度加到 s 上去（ s 開(kāi)始為 0），如果 s 大于 r，則停止循環(huán)并返回當(dāng)前基因； 當(dāng)然，第一步在計(jì)算中只需要執(zhí)行一次。如下圖所示： 蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 16 圖 31 賭輪算法示意圖 然后開(kāi)始扔彈子，扔到那個(gè)地方就把對(duì)應(yīng)的基因拿出來(lái)。想像一個(gè)輪盤(pán)賭的機(jī)器上放置了種群中所有的基因。 （ 4） 輪盤(pán)賭選擇方法 （ Roulette Wheel Selection） 父代的選擇是根據(jù)他們的適應(yīng)度做出的。 b. 根據(jù)具體問(wèn)題，設(shè)計(jì)一個(gè)概率分配表將各個(gè)概率值按上述排列次序分配給各個(gè)個(gè)體。 作用： 該策略的實(shí)施可保證迄今為止所得到的最優(yōu)個(gè)體不會(huì)被交叉，變異等遺傳運(yùn)算所破壞，它遺傳算法收斂性的一個(gè)重要保證條件。 b. 若當(dāng)前群體中最佳個(gè)體的適應(yīng)度比總的迄今為止的最好個(gè)體適應(yīng)度還要高，則以當(dāng)前群體中的最佳個(gè)體做為新的迄今為止的最好個(gè)體。我們希望適應(yīng)度最好的個(gè)體要盡可能保留到下一代群體中。 設(shè)群體大小為 M,個(gè)體 I 的適應(yīng)度為 Fi 則個(gè)體被選種的概率 Pis 為： pis=Fi/∑ Fi (I=1,2….M) （ 35） 由此可見(jiàn)，適應(yīng)度越高的個(gè)體被選種的概率也越大，反之適應(yīng)度越低的個(gè)體被選種的概率也越小。 選擇運(yùn)算 （ 1） 比例選擇方法：是一種回放式隨機(jī)采樣方法。 算子選擇 遺傳算法中的選擇操作就是用來(lái)確定如何從父代群體中按某種方法選取哪些個(gè)體遺傳到下一代群體中一種遺傳運(yùn)算。 （ 2） 乘冪尺度變換 公式為： F’=FK （ 33） 冪指數(shù) K 與所求解的問(wèn)題有關(guān)，并且在算法的執(zhí)行中需要不斷對(duì)其進(jìn)行修正才能使尺度 變換滿(mǎn)足一定的伸縮要求。 線(xiàn)性尺度變換的選取條件： F’avg要等于原適應(yīng)度平均值 Favg。我們希望在遺傳算法運(yùn)行的后期階段，算法能夠?qū)€(gè)體的適應(yīng)度進(jìn)行適當(dāng)?shù)姆糯?，擴(kuò)大最佳個(gè)體適應(yīng)度與其他個(gè)體適應(yīng)度之間的差異程度，以提高個(gè)體之間的競(jìng)爭(zhēng)性。如何確定適應(yīng)度對(duì)遺傳算法的性能有很大的影響。 （ 3） 根據(jù)最優(yōu)化問(wèn)題的類(lèi)型，由目標(biāo)函數(shù)值按一定的轉(zhuǎn)換規(guī)則求出個(gè)體的適應(yīng)度。 評(píng)價(jià)個(gè)體適應(yīng)度的一般過(guò)程： （ 1） 對(duì)個(gè)體編碼串進(jìn)行解碼處理后，可得到個(gè)體表現(xiàn)型 。適應(yīng)度較高的個(gè)體遺傳到下一代的概率教大，反之遺傳到下一代的概率相對(duì)小一些。 （ 2） 應(yīng)使用能使問(wèn)題得到自然表示和描述的具有最小字符的編碼方案。這些取值可以是與問(wèn)題有關(guān)任何值：整 數(shù)，實(shí)數(shù)，字符或者其他一些更復(fù)雜的東西。因?yàn)槎M(jìn)制編碼在這類(lèi)問(wèn)題中不好用。其對(duì)應(yīng)的表現(xiàn)型是： X =[ , , , , ]T 浮點(diǎn)數(shù)編碼方 法有下面幾個(gè)優(yōu)點(diǎn)： （ 1） 適合于在遺傳算法中表示范圍較大的數(shù)。 由二進(jìn)制編碼到格雷碼換算公式為： ??? ????? ? 1,....,2,1,1 mmIbigi bmgm 公式 (31) 由格雷碼到二進(jìn)制轉(zhuǎn)換公式為： ??? ?????? ? 1.... ..,2,1,1 mmIgigibi bmgm 公式 (32) 格雷碼優(yōu)點(diǎn)： （ 1） 便于提高遺傳算法的局部搜索能力 （ 2） 交叉，變異等遺傳操作便于實(shí) 現(xiàn) （ 3） 符合最小字符串編碼原則 （ 4） 便于利用模式定理對(duì)算法進(jìn)行理論分析 浮點(diǎn)數(shù)編碼方法 定義：所謂浮點(diǎn)數(shù)編碼方法是指?jìng)€(gè)體的每個(gè)基因值用某一范圍內(nèi)的一個(gè)浮點(diǎn)數(shù)來(lái)表示，個(gè)體的編碼長(zhǎng)度等于其決策變量的個(gè)數(shù)。 格雷碼編碼方法 定義：格雷碼是這樣的一種編碼方法，其連續(xù) 2 個(gè)整數(shù)所對(duì)應(yīng)的編碼值之間僅僅只有蘇州大學(xué) 自學(xué) 考試 畢業(yè)論文（設(shè)計(jì)） 12 一個(gè)碼位是不相同的，其余碼位都相同。 表 31 二進(jìn)制編碼的基因 基因 A 101100101100101011100101 基因 B 111111100000110000011111 使用二進(jìn)制編碼時(shí)，即使等位基因的數(shù)量不大，我們也可以得到很多種可能的基因。 二進(jìn)制編碼方法