遺傳算法及對于過早收斂的改進

尚一猛　周桂紅　閆安　郭曉穎　張國磊

摘 要 遺傳算法是模擬達爾文生物進化論中的自然選擇與遺傳學機理的生物過程的一種計算模型。該模型通過模擬自然進化過程來搜索最優解，其應用非常廣泛。但是在運用遺傳算法的過程之中經常遇到過早收斂的問題，為了改進該問題，在文中對遺傳算法進行了介紹，并在此基礎上就如何改進過早收斂進行探討。

關鍵詞 遺傳算法；過早收斂；改進

中圖分類號 TP18 文獻標識碼 A 文章編號 2095-6363（2017）15-0023-01

遺傳算法（Genetic Algorithm，GA）是自然科學與工程科學互相結合的產物，是一類借鑒達爾文自然選擇機理（適者生存，優勝劣汰遺傳機制）演化而來的隨機化搜索方法。

遺傳算法求解優化問題的性能與交叉概率（Pc）、變異概率（Pm）等參數的選擇有著很大的聯系。本文基于傳統思路，對GA的交叉概率和變異概率參數進行自適應控制，對過早收斂問題進行了適當優化。

1 遺傳算法綜述

1.1 遺傳算法思想

通常來說，遺傳算法包括三個算子，即選擇、交叉和變異。選擇算子的作用是為了提升整個群體的平均適度值，在整個群體中選擇那些評價值高的個體組成交配池的主要群體： 交叉算子的主要作用是選擇交配池中的優良基因遺傳給下一代，先將交配池中個體進行兩兩配對，再有目的的交換部分基因，生成基因性狀更加復雜的個體；變異算子是對個體某一個或是幾個按照某一較小的概率進行反轉二進制字符。從而實現對自然界中基因突變現象的模擬。

1.2 遺傳算法的思想流程

1）初始化群體；2）計算群體上每個個體的適應度值；3）針對于個體適應度值，依據某個規則選擇將進入下一代的個體；4）通過概率Pc進行交叉操作；5）通過概率Pm進行突變操作；6）未達到終止條件，則返回2）步，否則進入下一步；7）輸出群體中適應度值最大的個體作為問題的滿意解或最優解。

2 過早收斂及其特點

過早收斂在早期的選擇過程，種群中就出現了“完美”個體，該類個體的適應度值特別大，然而選擇壓力很大，后期變異概率比較小。繼而在后期的繁殖中占主體地位，種群的多樣性會很快的降低進而導致種群多樣化的喪失。

過早收斂對于整個種群來說弊大于利，因為結果并非是全局最優，僅僅是局部最優。特別是到了算法進行的后期，進過算法的多代進化，完美的個體已經在種群中占據絕大多數，這時傳統的交叉操作已經不能達到預期的作用。變異操作雖然能產生不同于父代的個體，使整個過程能跳出局部最優而達到全局最優，但是變異概率是小概率事件，同樣無法達到理想結果。

3 過早收斂的原因

3.1 種群規模太小

種群數量太小，種群基因庫不能被多重選擇，只靠后期變異帶來新的基因，效率是遠遠不夠的。

3.2 選擇壓力

選擇過程會根據適應度值的大小進行遺傳或者淘汰。過大的選擇壓力會導致種群多樣性的流失，以至于遺傳過程趨于收斂。

3.3 變異概率

遺傳算法中，對收斂速度起到決定性作用的是變異概率。當Pm太小時，變異過程不會產生不同于父本的個體，整個過程會去趨近于收斂。

4 預防過早收斂的措施

4.1 傳統方式

選擇合適的種群規模。在計算量允許的情況下，盡可能選擇較大的群體規模；適中的選擇壓力，避免選擇過程將大多數個體淘汰，保持種群的多樣性。

4.2 改進方式

遺傳算法中的算子主要是選擇、交叉、變異。作為遺傳算法中最主要的部分，交叉和變異對于避免過早收斂起到決定性的最用。如今比較流行的交叉變異過程選擇對應的概率都是一個固定的常數，根據問題的實際情況來確定。

1994年，Srinivas依據遺傳算法傳統思想建立了一套隨當代種群適應度值而動態變化的自適應遺傳算法。其中交叉概率和變異概率的值由以下公式確定。

式中：為種群中最大的適應度值；為每代種群中平均適應度值；為要較差的兩個個體中較大的適應度值；為要變異個體的適應度值；K1，k2，k3，k4——取（0，1）區間的值。Pc和Pm隨適應度值變化的曲線如圖1、圖2所示。

由以上公式得出在遺傳過程中，當種群趨于收斂達到局部最優時，遺傳過程的Pc和Pm概率會增加，而處于剛開始階段個體適應度值大小不一時，交叉變異概率會很小。這樣保證了當出現“完美”個體時，不會被該類個體迅速占領主要地位而過早收斂。

5 結論

通過自適應遺傳算法，交叉概率和變異概率隨著個體的適應度值在種群平均適應度和最大適應度值之間進行線性調整，打破了傳統交叉變異概率一成不變的傳統方式，使得遺傳算法得到最終的全局最優解。

參考文獻

[1]何大闊，王福利.一種提高遺傳算法全局收斂型的方法[J].東北大學學報（自然科學版），2003，24（6）：511-514.

[2]張鈴，張鈸.遺傳算法機理的研究[J].軟件學報，2000（7）：945-951.

[3]蔣騰旭，謝楓.遺傳算法中防止早熟收斂的幾種措施[J].計算機與現代化，2006（12）：54-57.endprint