改進(jìn)遺傳算法在計(jì)算機(jī)數(shù)學(xué)建模中的應(yīng)用研究

張琳娜

（陜西國防工業(yè)職業(yè)技術(shù)學(xué)院，陜西西安 710302）

遺傳算法的基礎(chǔ)思想就是對(duì)生物界遺傳過程的模仿，整個(gè)過程通過3 個(gè)基本操作構(gòu)成，分別為選擇、交叉和變異，用染色體表示二進(jìn)制，用基因表示參數(shù)，最后得到群體。在層數(shù)較多時(shí)，基本遺傳算法存在編碼冗長(zhǎng)和尋優(yōu)效果差的問題。所以，為了解決基本遺傳算法的問題，通過深入研究與分析，提出改進(jìn)遺傳算法。該算法的遺傳編碼操作簡(jiǎn)便，方便交叉與操作，提高了操作的便捷性與簡(jiǎn)單性，還能夠減小矩陣編碼長(zhǎng)度，在理論與實(shí)踐方面有一定的突破與創(chuàng)新[1-2]。

1 遺傳算法的設(shè)計(jì)

1.1 遺傳算法設(shè)計(jì)步驟

在使用遺傳算法求解問題時(shí)，首先要設(shè)計(jì)并改進(jìn)算法，其步驟為：

1）確定編碼方案。遺傳算法利用編碼的解決方案進(jìn)行求解；

2）確定適應(yīng)度函數(shù)。適應(yīng)度值能夠度量解的好壞，大部分都是基于目標(biāo)函數(shù)來表示；

3）確定選擇函數(shù)。使用優(yōu)勝劣汰選擇機(jī)制，提高高適應(yīng)度值個(gè)體的存活概率；

4）選擇控制參數(shù)。包括算法執(zhí)行最大迭代代數(shù)、種群規(guī)模、不同遺傳操作執(zhí)行概率；

5)設(shè)計(jì)遺傳算子。包括選擇、交叉和變異；

6)確定算法終止規(guī)則；

7）編程上機(jī)運(yùn)行。根據(jù)遺傳算法結(jié)構(gòu)編程，得到問題求解[3]。

1.2 編碼方法

如何使用編碼方案完善具體應(yīng)用問題，是遺傳算法主要研究方向，一般都是利用兩條操作性較強(qiáng)的編碼原則進(jìn)行參考[4]。

1）二進(jìn)制編碼。二進(jìn)制編碼利用符號(hào)集{0,1}，其創(chuàng)建個(gè)體基因型為二進(jìn)制符號(hào)串，長(zhǎng)度和問題解精度具有密切關(guān)系。假如某參數(shù)取值范圍為[Vmin，Vmax]，利用二進(jìn)制編碼符號(hào)串對(duì)此參數(shù)表示，其能夠產(chǎn)生2i種不同基因個(gè)體，關(guān)系為式（1）：

該方案精度表示為式（2）：

假設(shè)某個(gè)體編碼表示為：X:bi,bi-1,…b1，解碼公式表示為式（3）：

二進(jìn)制編碼方案主要優(yōu)勢(shì)為編解碼操作較簡(jiǎn)單，方便實(shí)現(xiàn)交叉等遺傳算法，直觀且易懂[5]。

2）浮點(diǎn)數(shù)編碼。浮點(diǎn)數(shù)編碼方法對(duì)浮點(diǎn)運(yùn)算使用的范圍進(jìn)行定義，表示個(gè)體長(zhǎng)度與決策變量，代表基因個(gè)體價(jià)值。因?yàn)榇司幋a方法為決策變量真正的價(jià)值，所以浮點(diǎn)編碼也是真正價(jià)值編碼方法。比如，某優(yōu)化問題具有4 個(gè)設(shè)計(jì)變量xi，變量都具有與其相對(duì)的上下限，那么得到式（4）：

相應(yīng)的表現(xiàn)形式為式（5）：

與其他編碼相比，此編碼能夠應(yīng)用到高遺傳算法精確度范圍中，使運(yùn)算效率得到提高[6]。

1.3 基本遺傳算子

遺傳算法是將搜索算法與自然選擇算法作為基礎(chǔ)，是一種基于自然選擇與遺傳機(jī)理的隨機(jī)搜索方法，主要包括變異算子、交叉算子、選擇算子。通過交叉算子與選擇算子實(shí)現(xiàn)遺傳算法的搜索功能，接近最優(yōu)解能力。

1）選擇算子。選擇指的是通過群體對(duì)優(yōu)良個(gè)體進(jìn)行選擇，淘汰劣質(zhì)個(gè)體，其能夠使目前群體中的個(gè)體根據(jù)適應(yīng)度值成為新群體中的幅值[7]，具體過程為：

假設(shè)第t代種群A(t)個(gè)體數(shù)指的是m，也就是m(H,t)。在對(duì)操作進(jìn)行選擇的過程中，位串Aj通過概率被選中并且復(fù)制，fi指的是個(gè)體Aj(t)的適應(yīng)度。假設(shè)一代中群體大小為n，而且個(gè)體兩兩不相同，那么模式H在第t+1 代中樣本數(shù)表示為式（6）：

公式中的f(H)指的是t時(shí)刻所對(duì)應(yīng)平均適應(yīng)度值，假設(shè)群體平均適應(yīng)度值表示為式（7）：

假設(shè)模式H平均適應(yīng)度比群體適應(yīng)度要高，高出部分表示為cfˉ，c指的是常數(shù)，那么得到式（8）：

2）隨機(jī)競(jìng)爭(zhēng)選擇。隨機(jī)競(jìng)爭(zhēng)選擇根據(jù)輪盤賭選擇個(gè)體時(shí)，利用個(gè)體競(jìng)爭(zhēng)選中高適應(yīng)度值的個(gè)體，進(jìn)入到下一代個(gè)體中，淘汰低適應(yīng)度值的個(gè)體[8]。

2 遺傳算法的改進(jìn)

2.1 自適應(yīng)改進(jìn)遺傳算法運(yùn)算流程

交叉算子能夠通過基因重組得出優(yōu)良個(gè)體，假如群體所有個(gè)體沒有基因，通過交叉算法無法得出缺失基因，但是可以利用遺傳算法得到。變異算子是指生物界基因突變的模擬，尋找群體個(gè)體缺乏的優(yōu)質(zhì)基因，對(duì)新個(gè)體進(jìn)行計(jì)算。文中提出改進(jìn)的自適應(yīng)遺傳算法[9]，執(zhí)行流程為：

1）實(shí)現(xiàn)初始群體編碼，并且設(shè)置收斂條件、種群大小、染色體長(zhǎng)度；

2）全面計(jì)算個(gè)體的適應(yīng)度值；

3）判斷收斂條件是否滿足需求，如果滿足，就輸入結(jié)果；如果不滿足，就進(jìn)入到下一步；

4）判斷arcsin(fave/fmax)≥π/6 是否成立，成立則說明種群最大適應(yīng)度和適應(yīng)度平均值比π/6 要大，此時(shí)判斷適應(yīng)度值的集中度比較簡(jiǎn)單。這時(shí)對(duì)交叉和變異進(jìn)行判斷，有效執(zhí)行選擇操作；如果不成立，則說明種群適應(yīng)度平均值不接近最大適應(yīng)度，此時(shí)具有較大的種群差異度值。

5）回到第2）步[10]。圖1 為改進(jìn)算法的求解流程。

圖1 改進(jìn)算法的求解流程

2.2 改進(jìn)算法的交叉概率與變異概率

為了能夠充分發(fā)揮交叉概率Pc與變異概率Pm的適應(yīng)度的集中分散程度，提出兩者自適應(yīng)選取計(jì)算公式：

當(dāng)arcsin(fave/fmax)＜π/6 時(shí)，說明種群適應(yīng)度平均值和最大適應(yīng)度值并不接近，小于π/6 時(shí)能夠判斷此時(shí)種群適應(yīng)度值分散，這時(shí)的種群差異較大、種類豐富，具有良好的多樣性。提高交叉概率Pc值，交換染色體基因，進(jìn)化優(yōu)質(zhì)新個(gè)體，降低變異概率Pm值和優(yōu)良個(gè)體破壞的可能性，促進(jìn)收斂的速度[11]。

另外，當(dāng)arcsin(fave/fmax)≥π/6 時(shí)，表示種群適應(yīng)度平均值接近最大適應(yīng)度值，超過π/6 時(shí)要判斷種群適應(yīng)度較集中，縮小了種群差異度，缺乏豐富種群和優(yōu)質(zhì)個(gè)體，還會(huì)占據(jù)大量的算法執(zhí)行時(shí)間。這時(shí)降低交叉概率Pc值和交叉操作，提高變異概率Pm值，避免陷入到局部極值，搜索全局最優(yōu)解[12]。

2.3 最優(yōu)保存策略

在實(shí)際使用的過程中，自適應(yīng)遺傳算法變異概率與交叉概率會(huì)在某個(gè)時(shí)刻變大，使良好優(yōu)質(zhì)體系遭到破壞。所以，文中利用最優(yōu)保存策略對(duì)遺傳每代最優(yōu)個(gè)體進(jìn)行保留[13]。對(duì)遺傳操作后每代產(chǎn)生的全新群體和前一代群體中的最高適應(yīng)值進(jìn)行全面對(duì)比，假如比前一代最高適應(yīng)值要小，就要將新一代個(gè)體淘汰，增加前一代高適應(yīng)值。最優(yōu)保存策略能夠破壞最優(yōu)個(gè)體遺傳操作，這是文中自適應(yīng)算法收斂性改進(jìn)的基礎(chǔ)[14]。

3 案例分析

文中遺傳算法在改進(jìn)之后具有較強(qiáng)的能力，能夠避免傳統(tǒng)遺傳算法在辨識(shí)問題的復(fù)雜計(jì)算方法，辨識(shí)初始模型公式（10）為：

此辨識(shí)初始模型根據(jù)最小二乘法求出上述公式參數(shù)a1、a2b1、b2，為常見辨識(shí)方法。然后基于矩陣編碼改進(jìn)遺傳算法，具體優(yōu)化流程為：

1）根據(jù)待求參數(shù)個(gè)體確定矩陣串的列和行，假如有6 個(gè)待定參數(shù)，那么要確定3×2 或者2×3 個(gè)矩陣，此特定6 個(gè)參數(shù)利用6 個(gè)元素表示[15]；

2）在搜索參數(shù)過程中要確定其范圍，遺傳算法在搜索范圍對(duì)參數(shù)存在相應(yīng)極限，此范圍是以具體問題進(jìn)行確定；

3）合理評(píng)價(jià)個(gè)體適應(yīng)度，文中根據(jù)最小二乘定義實(shí)現(xiàn)選擇和評(píng)價(jià)。選擇平方值平均最小一個(gè)組成為最優(yōu)值輸出，此為矩陣編碼遺傳算法與辨識(shí)度最小二乘兩相結(jié)合的重點(diǎn)，在此過程中，矩陣編碼結(jié)合最小二乘法，然后得到矩陣編碼遺傳算法搜索關(guān)鍵點(diǎn)。最后對(duì)比參數(shù)值與實(shí)際測(cè)量參數(shù)值差額取平方數(shù)，使其成為遺傳算法適應(yīng)度函數(shù)[16]；

4）為了避免優(yōu)秀父串在交叉與變異過程中出現(xiàn)破壞，工作人員會(huì)使兩個(gè)最優(yōu)子代避免變異或者交叉，而是直接選擇其子代。以下公式為Pc、Pm的說明：

4 實(shí)驗(yàn)結(jié)果

在此實(shí)踐過程中，三階線性離散系統(tǒng)輸入輸出數(shù)據(jù)一共40 個(gè)，最后以矩陣編碼遺傳算法最小二乘法實(shí)現(xiàn)參數(shù)估計(jì)工作[17]，在此試驗(yàn)計(jì)算過程中給定初始條件為公式（11）：

通過以上公式表示，y(k)為實(shí)際測(cè)量值，J(k)指的是矩陣編碼遺傳算法的最優(yōu)參數(shù)[1.756 4 0.942 3 0.151 8 0.999 8 0.521 7 0.069 5]，但是在解碼前要確定參數(shù)變化范圍[18]，辨識(shí)結(jié)果表示為V=1.698 7 0.932 1 0.149 9 1.00 2 0.521 5 0.693。

5 結(jié)束語

文中提出的改進(jìn)遺傳算法，全局搜索能力與并行性較強(qiáng)，遺傳操作與編碼技術(shù)較簡(jiǎn)單，降低了優(yōu)化問題限制性。該遺傳算法被廣泛應(yīng)用到模式識(shí)別、圖像處理、機(jī)器學(xué)習(xí)、優(yōu)化控制等方面，遺傳算法推廣與研究對(duì)社會(huì)經(jīng)濟(jì)的發(fā)展具有重要意義。