三種遺傳算法的改進(jìn)方法與研究

摘 要：遺傳算法是一種基于自然選擇和生物進(jìn)化機(jī)制的智能優(yōu)化算法，由于它具有非常多的優(yōu)點(diǎn)，所以被廣泛應(yīng)用于各個(gè)領(lǐng)域。但是基本的遺傳算法（簡(jiǎn)稱GA）也存在著許多的缺點(diǎn)和不足：適用范圍沒(méi)有非常廣；遺傳算法很容易出現(xiàn)“早熟”收斂，搜索性能不高；遺傳算法的時(shí)間復(fù)雜度往往比較高，而搜索的效率卻比較低。本文針對(duì)基本遺傳算法的陷入局部最優(yōu)和早熟收斂的缺點(diǎn)，對(duì)基本遺傳算法提出了三種改進(jìn)方法：既順序選擇遺傳算法、大變異遺傳算法和雙切點(diǎn)交叉遺傳算法，并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了這些改進(jìn)。

關(guān)鍵詞：遺傳算法；局部最優(yōu)；早熟收斂

中圖分類號(hào)：TP18

遺傳算法（Genetic Algorithm，GA）起源于對(duì)生物系統(tǒng)所進(jìn)行的計(jì)算機(jī)模擬研究，是模擬生物界“物竟天擇、適者生存”的進(jìn)化規(guī)律而開(kāi)發(fā)出來(lái)的一種隨機(jī)化搜索方法。它是由美國(guó)的J.Holland教授在1975年首先提出的，其特點(diǎn)是幾乎不需要所求問(wèn)題的任何信息，僅需目標(biāo)函數(shù)的信息，而且不受搜索空間是否連續(xù)或可微的限制就可找到最優(yōu)解，且具有良好的隱并行性和全局搜索能力[1-2]。遺傳算法通過(guò)模擬自然選擇的繁殖、交叉和變異操作來(lái)尋找更具優(yōu)良品質(zhì)的個(gè)體，用適應(yīng)度函數(shù)來(lái)評(píng)價(jià)個(gè)體的優(yōu)劣性，遵循優(yōu)勝劣汰的原則，找到適應(yīng)度最高的個(gè)體，并且在搜索中不斷增加優(yōu)良個(gè)體的數(shù)目，使種群的數(shù)目不斷增加，相應(yīng)的種群的整體適應(yīng)度也在不斷提高，循環(huán)往復(fù)，直到我們找到具有最高適應(yīng)值的那個(gè)個(gè)體。由于遺傳算法的優(yōu)良性質(zhì)而被廣泛應(yīng)用于函數(shù)優(yōu)化、組合優(yōu)化、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、圖像處理和人工智能等很多領(lǐng)域。但是在處理一些非線性、多模型和多目標(biāo)的函數(shù)優(yōu)化問(wèn)題時(shí)，基本的遺傳算法局部搜索能力弱且容易出現(xiàn)早熟的現(xiàn)象，最后求出的解往往是局部最優(yōu)解而不是全局最優(yōu)解[3-5]。

本文針對(duì)基本遺傳算法陷入局部最優(yōu)和早熟收斂的缺點(diǎn)，提出了三種遺傳算法的改進(jìn)，并具體分析了改進(jìn)的遺傳算法，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了這些改進(jìn)。

1 三種改進(jìn)的遺傳算法

1.1 順序選擇遺傳算法（SBOGA）

基本遺傳算法中個(gè)體的選擇概率與個(gè)體的適應(yīng)值直接相關(guān)，其計(jì)算公式為 （1）

一旦某個(gè)個(gè)體的適應(yīng)值為0，則其選擇概率為0，這個(gè)個(gè)體就不能產(chǎn)生后代，這是基本遺傳算法的一個(gè)很大的缺點(diǎn)。順序選擇策略將選擇概率固定化，其具體步驟為：

（1）按適應(yīng)值大小對(duì)個(gè)體進(jìn)行排序；

（2）定義最好的個(gè)體的選擇概率q，則排序后的第j個(gè)個(gè)體的選擇概率為：

（2）

這樣每個(gè)個(gè)體都有可能被選中從而產(chǎn)生后代。

算法步驟如圖1所示：

圖1 順序選擇遺傳算法流程圖

1.2 大變異遺傳算法（GMGA）

理論上，遺傳算法中的變異操作可以使算法避免“早熟”。但是，為了保證算法的穩(wěn)定性，變異操作的變異概率通常取值很小，所以算法一旦出現(xiàn)“早熟”，單靠傳統(tǒng)的變異操作需要很多代才能變異出一個(gè)不同于其他個(gè)體的新個(gè)體。大變異操作的思路是：當(dāng)某代中所有個(gè)體集中在一起時(shí)，我們以一個(gè)遠(yuǎn)大于通常的變異概率執(zhí)行一次變異操作，具有大變異概率的變異操作（即“大變異操作”）能夠隨機(jī)、獨(dú)立地產(chǎn)生許多新個(gè)體，從而使整個(gè)種群脫離“早熟”。

算法步驟如圖2所示：

圖2 大變異遺傳算法流程圖

1.3 雙切點(diǎn)交叉遺傳算法（DblGEGA）

單點(diǎn)交叉遺傳使得父代雙方交換基因量較大，有時(shí)候很容易破壞優(yōu)秀個(gè)體，而雙切點(diǎn)交叉相對(duì)單點(diǎn)交叉來(lái)說(shuō)，父代雙方交換的基因量較小，有利于個(gè)體的保留。

例如對(duì)于下面的兩個(gè)個(gè)體，如果雙切點(diǎn)交叉的方法，切點(diǎn)1在第2位，切點(diǎn)2在第5位。

切點(diǎn)1 切點(diǎn)2

10 110 011

01 011 101

則通過(guò)交叉后，兩個(gè)個(gè)體分別變?yōu)椋?/p>

10 011 011

01 110 101

即只有兩個(gè)切點(diǎn)之間的部分進(jìn)行了交換。

算法步驟如圖3所示：

圖3 雙切點(diǎn)交叉遺傳算法流程圖

2 計(jì)算機(jī)仿真和結(jié)果分析

為了考察上述三種改進(jìn)遺傳算法的性能，選取一個(gè)測(cè)試函數(shù)——Rastrigrim函數(shù)進(jìn)行測(cè)試。

Rastrigrim函數(shù)：

其函數(shù)圖形如圖4所示：

圖4 Rastrigrim函數(shù)圖形

我們把基本遺傳算法（GA）與三種改進(jìn)的遺傳算法（SBOGA、GMGA和DblGEGA）對(duì)Rastrigrim函數(shù)進(jìn)行測(cè)試，得到的進(jìn)化曲線如圖5所示。

圖5 Rastrigrim函數(shù)的進(jìn)化曲線

由圖5我們可知，雖然基本遺傳算法GA也能得到比較優(yōu)良的解，但是改進(jìn)后的三種遺傳算法得到的解無(wú)疑更近似于理論最優(yōu)解。

利用四種遺傳算法分別進(jìn)行仿真實(shí)驗(yàn)，運(yùn)行20次，結(jié)果如表1所示：

表1 仿真實(shí)驗(yàn)結(jié)果（運(yùn)行20次）

平均值最好值最差值標(biāo)準(zhǔn)偏差

GA39.955840.341539.27180.4442

SBOGA40.352540.352540.35250

GMGA39.999040.352539.63440.3290

DblGEGA40.237540.352539.84720.2195

由進(jìn)化曲線和運(yùn)行結(jié)果可知，在進(jìn)行的20次運(yùn)行中，這三種不同的改進(jìn)算法都能尋到最優(yōu)解，但各種算法的標(biāo)準(zhǔn)偏差有區(qū)別。其中SBOGA的性能最優(yōu)，雖然GMGA在最初的幾代變化波動(dòng)比較大，但是一旦其代數(shù)增加到某一代開(kāi)始，其收斂效果也是非常好的，DblGEGA的性能比較中規(guī)中矩。

3 結(jié)束語(yǔ)

本文針對(duì)基本遺傳算法的陷入局部最優(yōu)和早熟收斂的缺點(diǎn)，提出了三種改進(jìn)的遺傳算法，并通過(guò)仿真實(shí)驗(yàn)證明了三種改進(jìn)的遺傳算法都比基本的遺傳算法性能都有所提高，都更近似于理論最優(yōu)解。

參考文獻(xiàn)：

[1]金晶，蘇勇.一種改進(jìn)的自適應(yīng)遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2005（01）：64-69.

[2]周明，孫樹(shù)棟.遺傳算法原理及其應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2002.

[3]馬永杰，云文霞.遺傳算法研究進(jìn)展[J].計(jì)算機(jī)應(yīng)用研究，2012（04）：1201-1206.

[4]吉根林.遺傳算法研究綜述[J].計(jì)算機(jī)應(yīng)用與軟件，2004（02）：69-73.

[5]葛繼科，玉輝，春明.遺傳算法研究綜述[J].計(jì)算機(jī)應(yīng)用研究.2008（10）：2911-2916.

[6]趙越，茹婷婷.遺傳算法理論與應(yīng)用新探[J].計(jì)算機(jī)與信息技術(shù)，2014（01）：77-78.

[7]齊暢，王東霞，韓穎.多種遺傳算法在函數(shù)優(yōu)化方面的性能比較分析[J].遼寧工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2013（05）：290-293.

作者簡(jiǎn)介：陳郁（1981-），女，山東泰安人，助教，碩士研究生，研究方向：人工智能。

作者單位：濟(jì)寧醫(yī)學(xué)院醫(yī)學(xué)信息工程學(xué)院，山東日照 276826