改進遺傳算法在計算機數學建模中的應用研究

張琳娜

（陜西國防工業職業技術學院，陜西西安 710302）

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

1 遺傳算法的設計

1.1 遺傳算法設計步驟

在使用遺傳算法求解問題時，首先要設計并改進算法，其步驟為：

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

2）確定適應度函數。適應度值能夠度量解的好壞，大部分都是基于目標函數來表示；

3）確定選擇函數。使用優勝劣汰選擇機制，提高高適應度值個體的存活概率；

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

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

6)確定算法終止規則；

7）編程上機運行。根據遺傳算法結構編程，得到問題求解[3]。

1.2 編碼方法

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

1）二進制編碼。二進制編碼利用符號集{0,1}，其創建個體基因型為二進制符號串，長度和問題解精度具有密切關系。假如某參數取值范圍為[Vmin，Vmax]，利用二進制編碼符號串對此參數表示，其能夠產生2i種不同基因個體，關系為式（1）：

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

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

二進制編碼方案主要優勢為編解碼操作較簡單，方便實現交叉等遺傳算法，直觀且易懂[5]。

2）浮點數編碼。浮點數編碼方法對浮點運算使用的范圍進行定義，表示個體長度與決策變量，代表基因個體價值。因為此編碼方法為決策變量真正的價值，所以浮點編碼也是真正價值編碼方法。比如，某優化問題具有4 個設計變量xi，變量都具有與其相對的上下限，那么得到式（4）：

相應的表現形式為式（5）：

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

1.3 基本遺傳算子

遺傳算法是將搜索算法與自然選擇算法作為基礎，是一種基于自然選擇與遺傳機理的隨機搜索方法，主要包括變異算子、交叉算子、選擇算子。通過交叉算子與選擇算子實現遺傳算法的搜索功能，接近最優解能力。

1）選擇算子。選擇指的是通過群體對優良個體進行選擇，淘汰劣質個體，其能夠使目前群體中的個體根據適應度值成為新群體中的幅值[7]，具體過程為：

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

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

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

2）隨機競爭選擇。隨機競爭選擇根據輪盤賭選擇個體時，利用個體競爭選中高適應度值的個體，進入到下一代個體中，淘汰低適應度值的個體[8]。

2 遺傳算法的改進

2.1 自適應改進遺傳算法運算流程

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

1）實現初始群體編碼，并且設置收斂條件、種群大小、染色體長度；

2）全面計算個體的適應度值；

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

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

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

圖1 改進算法的求解流程

2.2 改進算法的交叉概率與變異概率

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

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

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

2.3 最優保存策略

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

3 案例分析

文中遺傳算法在改進之后具有較強的能力，能夠避免傳統遺傳算法在辨識問題的復雜計算方法，辨識初始模型公式（10）為：

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

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

2）在搜索參數過程中要確定其范圍，遺傳算法在搜索范圍對參數存在相應極限，此范圍是以具體問題進行確定；

3）合理評價個體適應度，文中根據最小二乘定義實現選擇和評價。選擇平方值平均最小一個組成為最優值輸出，此為矩陣編碼遺傳算法與辨識度最小二乘兩相結合的重點，在此過程中，矩陣編碼結合最小二乘法，然后得到矩陣編碼遺傳算法搜索關鍵點。最后對比參數值與實際測量參數值差額取平方數，使其成為遺傳算法適應度函數[16]；

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

4 實驗結果

在此實踐過程中，三階線性離散系統輸入輸出數據一共40 個，最后以矩陣編碼遺傳算法最小二乘法實現參數估計工作[17]，在此試驗計算過程中給定初始條件為公式（11）：

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

5 結束語

文中提出的改進遺傳算法，全局搜索能力與并行性較強，遺傳操作與編碼技術較簡單，降低了優化問題限制性。該遺傳算法被廣泛應用到模式識別、圖像處理、機器學習、優化控制等方面，遺傳算法推廣與研究對社會經濟的發展具有重要意義。