遺傳算法及對于過早收斂的改進(jìn)

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

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

關(guān)鍵詞 遺傳算法；過早收斂；改進(jìn)

中圖分類號 TP18 文獻(xiàn)標(biāo)識(shí)碼 A 文章編號 2095-6363（2017）15-0023-01

遺傳算法（Genetic Algorithm，GA）是自然科學(xué)與工程科學(xué)互相結(jié)合的產(chǎn)物，是一類借鑒達(dá)爾文自然選擇機(jī)理（適者生存，優(yōu)勝劣汰遺傳機(jī)制）演化而來的隨機(jī)化搜索方法。

遺傳算法求解優(yōu)化問題的性能與交叉概率（Pc）、變異概率（Pm）等參數(shù)的選擇有著很大的聯(lián)系。本文基于傳統(tǒng)思路，對GA的交叉概率和變異概率參數(shù)進(jìn)行自適應(yīng)控制，對過早收斂問題進(jìn)行了適當(dāng)優(yōu)化。

1 遺傳算法綜述

1.1 遺傳算法思想

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

1.2 遺傳算法的思想流程

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

2 過早收斂及其特點(diǎn)

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

過早收斂對于整個(gè)種群來說弊大于利，因?yàn)榻Y(jié)果并非是全局最優(yōu)，僅僅是局部最優(yōu)。特別是到了算法進(jìn)行的后期，進(jìn)過算法的多代進(jìn)化，完美的個(gè)體已經(jīng)在種群中占據(jù)絕大多數(shù)，這時(shí)傳統(tǒng)的交叉操作已經(jīng)不能達(dá)到預(yù)期的作用。變異操作雖然能產(chǎn)生不同于父代的個(gè)體，使整個(gè)過程能跳出局部最優(yōu)而達(dá)到全局最優(yōu)，但是變異概率是小概率事件，同樣無法達(dá)到理想結(jié)果。

3 過早收斂的原因

3.1 種群規(guī)模太小

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

3.2 選擇壓力

選擇過程會(huì)根據(jù)適應(yīng)度值的大小進(jìn)行遺傳或者淘汰。過大的選擇壓力會(huì)導(dǎo)致種群多樣性的流失，以至于遺傳過程趨于收斂。

3.3 變異概率

遺傳算法中，對收斂速度起到?jīng)Q定性作用的是變異概率。當(dāng)Pm太小時(shí)，變異過程不會(huì)產(chǎn)生不同于父本的個(gè)體，整個(gè)過程會(huì)去趨近于收斂。

4 預(yù)防過早收斂的措施

4.1 傳統(tǒng)方式

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

4.2 改進(jìn)方式

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

1994年，Srinivas依據(jù)遺傳算法傳統(tǒng)思想建立了一套隨當(dāng)代種群適應(yīng)度值而動(dòng)態(tài)變化的自適應(yīng)遺傳算法。其中交叉概率和變異概率的值由以下公式確定。

式中：為種群中最大的適應(yīng)度值；為每代種群中平均適應(yīng)度值；為要較差的兩個(gè)個(gè)體中較大的適應(yīng)度值；為要變異個(gè)體的適應(yīng)度值；K1，k2，k3，k4——?。?，1）區(qū)間的值。Pc和Pm隨適應(yīng)度值變化的曲線如圖1、圖2所示。

由以上公式得出在遺傳過程中，當(dāng)種群趨于收斂達(dá)到局部最優(yōu)時(shí)，遺傳過程的Pc和Pm概率會(huì)增加，而處于剛開始階段個(gè)體適應(yīng)度值大小不一時(shí)，交叉變異概率會(huì)很小。這樣保證了當(dāng)出現(xiàn)“完美”個(gè)體時(shí)，不會(huì)被該類個(gè)體迅速占領(lǐng)主要地位而過早收斂。

5 結(jié)論

通過自適應(yīng)遺傳算法，交叉概率和變異概率隨著個(gè)體的適應(yīng)度值在種群平均適應(yīng)度和最大適應(yīng)度值之間進(jìn)行線性調(diào)整，打破了傳統(tǒng)交叉變異概率一成不變的傳統(tǒng)方式，使得遺傳算法得到最終的全局最優(yōu)解。

參考文獻(xiàn)

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

[2]張鈴，張鈸.遺傳算法機(jī)理的研究[J].軟件學(xué)報(bào)，2000（7）：945-951.

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