遺傳算法進(jìn)化停滯

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

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

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

一引言

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

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

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

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

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

進(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)化，對(duì)于優(yōu)化未進(jìn)行到一定程度的代數(shù)影響不大，因?yàn)榇藭r(shí)局部?jī)?yōu)化同樣具有很大的發(fā)展空間，適應(yīng)函數(shù)的改變是可觀的，但是對(duì)于進(jìn)化達(dá)到一定程度后，積累的局部?jī)?yōu)化會(huì)在交叉或變異時(shí)帶入下一代，導(dǎo)致適應(yīng)函數(shù)值的改變非常困難，此時(shí)就會(huì)產(chǎn)生“進(jìn)化停滯”問(wèn)題。

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

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

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

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

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

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

1、做好約束的處理

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

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

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

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

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

4、無(wú)效染色體的處理

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

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

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

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

五結(jié)論

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

參考文獻(xiàn)

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

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

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

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