遺傳算法進化停滯

前言：本站為你精心整理了遺傳算法進化停滯范文，希望能為你的創(chuàng)作提供參考價值，我們的客服老師可以幫助你提供個性化的參考范文，歡迎咨詢。

摘要遺傳算法作為一種功能強大的隨機搜索算法被廣泛地應用在許多領域，但是進化效率低下問題始終是困擾用戶的一個主要問題，“進化停滯”即是它的表現(xiàn)之一。本文分析了“進化停滯”問題產生的機理，并給出了合理的解決方案。

關鍵詞遺傳算法，進化停滯，適應函數(shù)

一引言

通過對遺傳算法的基礎理論研究，各種提高進化效率的方法得以廣泛采用，但是針對具體的應用領域，還有許多細節(jié)問題影響著軟件的具體運作，網絡優(yōu)化問題中出現(xiàn)的進化停滯問題就是其中一個例子。

遺傳算法應用在網絡優(yōu)化中為網絡設計者提供了第一手科學的理論依據(jù)，但是網絡優(yōu)化問題屬于求解復雜問題的全局最優(yōu)解，時間復雜性決定了遺傳算法的執(zhí)行效率，出現(xiàn)在進化過程中的“進化停滯”問題無疑又加劇了執(zhí)行效率低下的缺陷，成為遺傳算法應用在網絡優(yōu)化問題中的重要條件。

二遺傳算法中“進化停滯”問題的分析

我們設計了一款染色體采用自然編碼，以網絡連接邊為權值求解網絡最小連接費用的軟件，固定參數(shù)實驗中發(fā)現(xiàn)如下問題（如表1所示）：

表1進化結果對比表

進化代數(shù)最小費用

0939.88645cm

50548.94277cm

100460.02706cm

200342.16332cm

300322.83430cm

500322.66646cm

某一次500代程序優(yōu)化運行結果所示，前300代進化基本理想，但300­­——500代進化卻陷于停滯。

分析其原因，以適應函數(shù)參考閾值限制交叉或變異的染色體進化，對于優(yōu)化未進行到一定程度的代數(shù)影響不大，因為此時局部優(yōu)化同樣具有很大的發(fā)展空間，適應函數(shù)的改變是可觀的，但是對于進化達到一定程度后，積累的局部優(yōu)化會在交叉或變異時帶入下一代，導致適應函數(shù)值的改變非常困難，此時就會產生“進化停滯”問題。

看來“進化停滯”問題的出現(xiàn)在于適應函數(shù)對進化過程控制的不合理性，所以我們有必要重新認識適應函數(shù)。

三適應函數(shù)分析

我們知道，適應度是遺傳算法得以進行下去的關鍵[1]。由于有了適應度，個體之間才存在競爭，競爭的結果就是：生存下來的個體越來越優(yōu)秀，適應度最高的個體則是最符合求解目標的個體（最優(yōu)解）。適應度是這么重要，對個體適應度的評價方法和具體操作在遺傳算法中就有相當重要的地位。

把優(yōu)化的目標函數(shù)解釋為生物種群對環(huán)境的適應性，要實現(xiàn)的目標就是個體的適應度評判標準，越符合目標的個體，其適應度就越大，反之就小，這就是適應函數(shù)。適應函數(shù)的選取直接關系到進化結果的收斂和成熟，對進化效率起著至關重要要的作用。

四遺傳算法中解決進化停滯問題的可行方案

“進化停滯”問題的出現(xiàn)導致進化方向的盲目性和無效染色體的產生，科學選擇適應函數(shù)、科學處理必然存在的無效染色體就成為解決問題的關鍵。因此，我們可以從以下幾個圍繞適應函數(shù)控制的方面著手處理“進化停滯”問題：

1、做好約束的處理

優(yōu)化目標函數(shù)的約束一般可分為值域約束、等式約束、不等式約束[2]。由于初始種群隨機產生，滿足等式約束較麻煩，所以在算法一開始，就要采取措施使它們和相等數(shù)量的問題變量一起被消去，這樣做就減少了一部分搜索空間，留下的線性不等式的約束就構成了搜尋解時必須進行搜索的凸集。搜索空間的凸性確保了解的線性組合無需檢驗約束就產生新的解，從而在全局角度減少了進化中搜索的范圍，避免發(fā)散的搜索域帶來的“進化停滯”問題。

2、最優(yōu)保存策略的選擇

最優(yōu)保存策略是對適應函數(shù)控制的有力補充，就是第n代種群通過遺傳算子的操作過后，如果得到的新的種群中的最優(yōu)個體（最符合適應函數(shù)的個體）沒有前n代種群中的最優(yōu)個體優(yōu)秀的話，就把第n+1代種群的最差個體用上代最優(yōu)個體替代[1]。最優(yōu)保存策略的實施可保證迄今為止的最優(yōu)個體不會被交叉、變異運算所破壞，否則在運算過程中總的最優(yōu)個體之后的一切運算都成了沒有必要的浪費，陷于“進化停滯”問題。

3、合理采用交叉概率和變異概率

針對已定的適應函數(shù)，進化中積累的局部優(yōu)化會在交叉或變異時帶入下一代，導致適應函數(shù)值的改變非常困難。為了提高效率和快速獲得最優(yōu)解,我們可以根據(jù)個體的適應度值,自適應地調節(jié)交叉概率和變異概率,當群體有陷入局部最優(yōu)解的趨勢時,就相應地提高交叉概率和變異概率,當群體在解空間發(fā)散時,就降低交叉概率和變異概率[3]。對于適應值較高的個體,選擇較低的交叉概率和變異概率,使該個體得以保護進入下一代,對于適應值較低的個體,選擇較高的交叉概率和變異概率,使該個體被淘汰掉。這樣既保持了群體的多樣性,又保證了遺傳算法的收斂性,有效地提高了遺傳算法的優(yōu)化能力，從而避免了“進化停滯”問題的產生。

4、無效染色體的處理

遺傳算法是一種隨機搜索算法，這就不可避免的導致進化過程中無效染色體的產生。直接丟棄顯然不是一個好的選擇，這會大大增加循環(huán)的次數(shù)，陷于進化停滯問題，解決辦法是設計一個合理的懲罰算子對無效染色體實施懲罰[2]，使之能夠被重新應用到進化過程中，避免無效循環(huán)產生的“進化停滯”問題。

5、動態(tài)域值限制的引入

對于交叉或變異染色體適應度函數(shù)值差異過小導致的進化停滯問題，采取的解決辦法則在于根據(jù)實際情況確定一個動態(tài)參數(shù)閾值，作為判斷相鄰兩代或幾代染色體進化方向的依據(jù)，若相鄰兩代或幾代染色體適應度函數(shù)值的差小于此閾值，則視為進化方向有誤，應重新選擇父染色體進行交叉或變異引導進化方向。當然，對于進化要求不高的情況，也可以據(jù)此直接結束進化。

實驗中，用動態(tài)閾值作為適應函數(shù)參考閾值，即每代均求前n代適應函數(shù)值的均值（或者群體中所有個體適應度的方差小于某一個極小的閾值）[2]，交叉或變異時若新一代染色體的適應函數(shù)值小于此閾值，則重新進行交叉或變異，50次閾值判斷仍未能滿足要求則結束進化。事實充分證明了上述看法，解決了“進化停滯”問題，使程序效率得以大幅度提高。

五結論

遺傳算法是一種不受結構模型、約束條件、參數(shù)初值等因素限制的新型優(yōu)化算法[4]，在許多領域得以實現(xiàn)，但是它的進化效率低下問題始終是困擾用戶的主要問題，解決“進化停滯”問題只是解決了進化效率低下問題的一個方面，問題的最終解決還需要更為深入的研究與探討。

參考文獻

1陳國良.遺傳算法及應用［M］,北京：人民郵電出版社，1996

2楊新敏孫靜怡錢育渝.城市交通流配流問題的遺傳算法求解[J],城市交通，2002年第二期

3南海鵬，王濤，余向陽.基于改進遺傳算法的水輪機調速器參數(shù)優(yōu)化[M],北京：中國水利水電出版社，2002

4孫艷豐戴春榮.幾種隨機搜索算法的比較研究[J],北京：系統(tǒng)工程與電子技術第二期，1998年