遺傳算法中進化停滯問題的思考

1、遺傳算法中進化停滯問題的考慮摘要遺傳算法作為一種功能強大的隨機搜索算法被廣泛地應(yīng)用在許多領(lǐng)域，但是進化效率低下問題始終是困擾用戶的一個主要問題，“進化停滯即是它的表現(xiàn)之一。本文分析了“進化停滯問題產(chǎn)生的機理，并給出了合理的解決方案。關(guān)鍵詞遺傳算法，進化停滯，適應(yīng)函數(shù)一引言通過對遺傳算法的根底理論研究，各種進步進化效率的方法得以廣泛采用，但是針對詳細(xì)的應(yīng)用領(lǐng)域，還有許多細(xì)節(jié)問題影響著軟件的詳細(xì)運作，網(wǎng)絡(luò)優(yōu)化問題中出現(xiàn)的進化停滯問題就是其中一個例子。遺傳算法應(yīng)用在網(wǎng)絡(luò)優(yōu)化中為網(wǎng)絡(luò)設(shè)計者提供了第一手科學(xué)的理論根據(jù)，但是網(wǎng)絡(luò)優(yōu)化問題屬于求解復(fù)雜問題的全局最優(yōu)解，時間復(fù)雜性決定了遺傳算法的執(zhí)行效率，出如

2、今進化過程中的“進化停滯問題無疑又加劇了執(zhí)行效率低下的缺陷，成為遺傳算法應(yīng)用在網(wǎng)絡(luò)優(yōu)化問題中的重要條件。二遺傳算法中“進化停滯問題的分析我們設(shè)計了一款染色體采用自然編碼，以網(wǎng)絡(luò)連接邊為權(quán)值求解網(wǎng)絡(luò)最小連接費用的軟件，固定參數(shù)實驗中發(fā)現(xiàn)如下問題如表1所示：表1進化結(jié)果比照表進化代數(shù)最小費用939.8864550548.94277100460.02706200342.16332300322.83430500322.66646某一次500代程序優(yōu)化運行結(jié)果所示，前300代進化根本理想，但300500代進化卻陷于停滯。分析其原因，以適應(yīng)函數(shù)參考閾值限制穿插或變異的染色體進化，對于優(yōu)化未進展到一定程度的

3、代數(shù)影響不大，因為此時部分優(yōu)化同樣具有很大的開展空間，適應(yīng)函數(shù)的改變是可觀的，但是對于進化到達(dá)一定程度后，積累的部分優(yōu)化會在穿插或變異時帶入下一代，導(dǎo)致適應(yīng)函數(shù)值的改變非常困難，此時就會產(chǎn)生“進化停滯問題?？磥怼斑M化停滯問題的出如今于適應(yīng)函數(shù)對進化過程控制的不合理性，所以我們有必要重新認(rèn)識適應(yīng)函數(shù)。三適應(yīng)函數(shù)分析我們知道，適應(yīng)度是遺傳算法得以進展下去的關(guān)鍵1。由于有了適應(yīng)度，個體之間才存在競爭，競爭的結(jié)果就是：生存下來的個體越來越優(yōu)秀，適應(yīng)度最高的個體那么是最符合求解目的的個體最優(yōu)解。適應(yīng)度是這么重要，對個體適應(yīng)度的評價方法和詳細(xì)操作在遺傳算法中就有相當(dāng)重要的地位。把優(yōu)化的目的函數(shù)解釋為生物種

4、群對環(huán)境的適應(yīng)性，要實現(xiàn)的目的就是個體的適應(yīng)度評判標(biāo)準(zhǔn)，越符合目的的個體，其適應(yīng)度就越大，反之就小，這就是適應(yīng)函數(shù)。適應(yīng)函數(shù)的選取直接關(guān)系到進化結(jié)果的收斂和成熟，對進化效率起著至關(guān)重要要的作用。四遺傳算法中解決進化停滯問題的可行方案“進化停滯問題的出現(xiàn)導(dǎo)致進化方向的盲目性和無效染色體的產(chǎn)生，科學(xué)選擇適應(yīng)函數(shù)、科學(xué)處理必然存在的無效染色體就成為解決問題的關(guān)鍵。因此，我們可以從以下幾個圍繞適應(yīng)函數(shù)控制的方面著手處理“進化停滯問題：1、做好約束的處理優(yōu)化目的函數(shù)的約束一般可分為值域約束、等式約束、不等式約束2。由于初始種群隨機產(chǎn)生，滿足等式約束較費事，所以在算法一開場，就要采取措施使它們和相等數(shù)量的

5、問題變量一起被消去，這樣做就減少了一部分搜索空間，留下的線性不等式的約束就構(gòu)成了搜尋解時必須進展搜索的凸集。搜索空間的凸性確保理解的線性組合無需檢驗約束就產(chǎn)生新的解，從而在全局角度減少了進化中搜索的范圍，防止發(fā)散的搜索域帶來的“進化停滯問題。2、最優(yōu)保存策略的選擇最優(yōu)保存策略是對適應(yīng)函數(shù)控制的有力補充，就是第n代種群通過遺傳算子的操作過后，假如得到的新的種群中的最優(yōu)個體最符適宜應(yīng)函數(shù)的個體沒有前n代種群中的最優(yōu)個體優(yōu)秀的話，就把第n+1代種群的最差個體用上代最優(yōu)個體替代1。最優(yōu)保存策略的施行可保證迄今為止的最優(yōu)個體不會被穿插、變異運算所破壞，否那么在運算過程中總的最優(yōu)個體之后的一切運算都成了沒

6、有必要的浪費，陷于“進化停滯問題。3、合理采用穿插概率和變異概率針對已定的適應(yīng)函數(shù)，進化中積累的部分優(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)值較高的個體,選擇較低的穿插概率和變異概率,使該個體得以保護進入下一代,對于適應(yīng)值較低的個體,選擇較高的穿插概率和變異概率,使該個體被淘汰掉。這樣既保持了群體的多樣性,又保證了遺傳算法的收斂性,有效地進步了遺傳算法的優(yōu)化才能，

7、從而防止了“進化停滯問題的產(chǎn)生。4、無效染色體的處理遺傳算法是一種隨機搜索算法，這就不可防止的導(dǎo)致進化過程中無效染色體的產(chǎn)生。直接丟棄顯然不是一個好的選擇，這會大大增加循環(huán)的次數(shù)，陷于進化停滯問題，解決方法是設(shè)計一個合理的懲罰算子對無效染色體施行懲罰2，使之可以被重新應(yīng)用到進化過程中，防止無效循環(huán)產(chǎn)生的“進化停滯問題。5、動態(tài)域值限制的引入對于穿插或變異染色體適應(yīng)度函數(shù)值差異過小導(dǎo)致的進化停滯問題，采取的解決方法那么在于根據(jù)實際情況確定一個動態(tài)參數(shù)閾值，作為判斷相鄰兩代或幾代染色體進化方向的根據(jù)，假設(shè)相鄰兩代或幾代染色體適應(yīng)度函數(shù)值的差小于此閾值，那么視為進化方向有誤，應(yīng)重新選擇父染色體進展穿

8、插或變異引導(dǎo)進化方向。當(dāng)然，對于進化要求不高的情況，也可以據(jù)此直接完畢進化。實驗中，用動態(tài)閾值作為適應(yīng)函數(shù)參考閾值，即每代均求前n代適應(yīng)函數(shù)值的均值或者群體中所有個體適應(yīng)度的方差小于某一個極小的閾值2，穿插或變異時假設(shè)新一代染色體的適應(yīng)函數(shù)值小于此閾值，那么重新進展穿插或變異，50次閾值判斷仍未能滿足要求那么完畢進化。事實充分證明了上述看法，解決了“進化停滯問題，使程序效率得以大幅度進步。五結(jié)論遺傳算法是一種不受構(gòu)造模型、約束條件、參數(shù)初值等因素限制的新型優(yōu)化算法4，在許多領(lǐng)域得以實現(xiàn)，但是它的進化效率低下問題始終是困擾用戶的主要問題，解決“進化停滯問題只是解決了進化效率低下問題的一個方面，問題的最終解決還需要更為深化的研究與討論。參考文獻(xiàn)1陳國良.遺傳算法及應(yīng)用,北京：人民郵電出版社，19962楊新敏孫靜