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

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

關(guān)鍵詞遺傳算法，進(jìn)化停滯，適應(yīng)函數(shù)

一引言

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

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

二遺傳算法中“進(jìn)化停滯”問題的分析

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

表1進(jìn)化結(jié)果對比表

進(jìn)化代數(shù)最小費(fèi)用

0939.88645cm

50548.94277cm

100460.02706cm

200342.16332cm

300322.83430cm

500322.66646cm

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

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

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

三適應(yīng)函數(shù)分析

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

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

四遺傳算法中解決進(jìn)化停滯問題的可行方案

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

1、做好約束的處理

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

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

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

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

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

4、無效染色體的處理

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

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

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

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

五結(jié)論

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

參考文獻(xiàn)

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

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

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

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