一種改進(jìn)的自適應(yīng)遺傳算法

文/劉曉霞 竇明鑫

（1.河北金融學(xué)院；2.中國(guó)地質(zhì)大學(xué)長(zhǎng)城學(xué)院 河北·保定）

引言

遺傳算法（GA）由美國(guó)Michigan大學(xué)的Holland教授于1975年首先提出，后經(jīng)De Jong、GoldBerg等人改進(jìn)推廣，廣泛應(yīng)用于各類問題。它是一種模擬自然界生物進(jìn)化過程與機(jī)制的全局概率優(yōu)化搜索方法。

早期遺傳算法在進(jìn)化過程中易出現(xiàn)早熟收斂和局部收斂性差等問題，為了克服上述問題，人們提出了多種改進(jìn)算法。本文對(duì)自適應(yīng)算法進(jìn)行改進(jìn)，算法中不僅交叉和變異概率是自適應(yīng)的，而且構(gòu)造了一種自適應(yīng)的適應(yīng)度函數(shù)，以便更好地進(jìn)行復(fù)制、交叉、變異操作，同時(shí)結(jié)合實(shí)數(shù)編碼精度高、搜索范圍大和二進(jìn)制編碼的收斂速度快、變異操作易實(shí)現(xiàn)的特點(diǎn)，算法還采用了實(shí)數(shù)與二進(jìn)制編碼相結(jié)合的方式，在防止早熟的同時(shí)還能提高全局搜索能力，最后利用改進(jìn)算法進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明本算法具有收斂概率高和平均收斂代數(shù)少的優(yōu)點(diǎn)。

一、改進(jìn)的遺傳算法

其中，fmax為上一代最優(yōu)解所對(duì)應(yīng)的函數(shù)值，t為當(dāng)前代數(shù)，T為預(yù)先設(shè)置好的最大迭代次數(shù)。

2、格雷碼周期變異。由于二進(jìn)制變異容易控制，可以避免考慮實(shí)數(shù)變異涉及的變異方向，所以本文在變異操作中采用二進(jìn)制格雷編碼，格雷編碼的定義見（2）式，

其中，p為原二進(jìn)制編碼，l為編碼長(zhǎng)度。格雷編碼不僅具有良好的局部搜索能力，還能克服二進(jìn)制編碼Hamming懸崖，之后將變異概率設(shè)定成一個(gè)周期性變化的函數(shù)，見（3）式：

其中，a，b是待定值，此函數(shù)在一個(gè)周期內(nèi)是單調(diào)遞減的，在進(jìn)化后期種群趨于穩(wěn)定時(shí)，降低選擇壓的同時(shí)應(yīng)該采取大概率變異，保持種群的多樣性，防止陷入局部解。經(jīng)測(cè)試，當(dāng)a=3，b=19時(shí)算法性能較好。

二、算法步驟

Step1 采用實(shí)數(shù)編碼產(chǎn)生初始種群，在函數(shù)定義域內(nèi)按照均勻分布隨機(jī)產(chǎn)生n個(gè)個(gè)體，｛xi｝（1，2，…n）設(shè)定最大進(jìn)化代數(shù)設(shè)為T。

Step3 根據(jù)每個(gè)個(gè)體的適應(yīng)度，采用比例選擇法。通過這種適應(yīng)度轉(zhuǎn)換，使得在進(jìn)化前期原本函數(shù)值小的個(gè)體將有更大的概率被選擇，保持了種群的多樣性。

Step4 按照概率pc在種群中隨機(jī)選擇父代個(gè)體進(jìn)行交叉操作。

Step5 首先依據(jù)變異概率pm選定變異個(gè)體，然后利用格雷碼周期變異操作進(jìn)行編碼、變異、最后解碼。

Step6 最優(yōu)保存策略。本文將最優(yōu)保存策略算法做如下修改：第一步，計(jì)算每個(gè)個(gè)體的函數(shù)值，然后排序，找出最優(yōu)解，最差解；第二步，若上一代最優(yōu)解的函數(shù)值比當(dāng)前最優(yōu)解的函數(shù)值大，則用上一代的最優(yōu)解替換當(dāng)前最優(yōu)解；若上一代的最優(yōu)解函數(shù)值小，則用上一代的最優(yōu)解替換當(dāng)前中的最差解。這樣，基于Markov鏈的數(shù)學(xué)理論分析表明，保留最優(yōu)個(gè)體策略的遺傳算法就能夠以概率1收斂于最優(yōu)解。

Step7 滿足迭代次數(shù)即停止，否則代數(shù)加1，轉(zhuǎn)入Step2。

三、仿真試驗(yàn)

1、測(cè)試函數(shù)。選取文獻(xiàn)[3、6、7]的測(cè)試函數(shù)為：

其中，f1為單峰二次函數(shù)，當(dāng)（x1+x2+x3）＝（0，0，0）時(shí)有全局最小值 0；f2有無數(shù)個(gè)局部最大值，只有一個(gè)全局最大點(diǎn)（0，0），最大值為1；f3是一維連續(xù)且含三角函數(shù)的多峰函數(shù)，當(dāng)x=1.8505時(shí)，全局最大值為 3.8503；f4是 Schaffer函數(shù)，當(dāng)（x1，x2）=（0，0）時(shí)有全局最小值 0。

2、測(cè)試結(jié)果對(duì)比分析。用本文算法同基本遺傳算法和自適應(yīng)遺傳算法進(jìn)行比較，其中取種群規(guī)模m=200，基本遺傳算法的交叉概率pc=0.85和變異概率pm=0.1，自適應(yīng)遺傳算法的交叉概率和變異概率分別為：

表1 三種算法對(duì)測(cè)試函數(shù)的運(yùn)行結(jié)果

其中，pc1=0.85，pc2=0.65，pm1=0.15，pm2=0.05，f'為兩個(gè)要交叉?zhèn)€體適應(yīng)度大的個(gè)體適應(yīng)度值，最大迭代次數(shù)設(shè)為T＝150，對(duì)各測(cè)試函數(shù)分別獨(dú)立運(yùn)行100次得到表 1。（表 1）

通過實(shí)驗(yàn)表明，本文的算法在對(duì)函數(shù)f1、f3、f4的測(cè)試中，達(dá)到最優(yōu)值的收斂代數(shù)明顯減少，得到了令人滿意的效果，對(duì)函數(shù)f2的測(cè)試中雖然本文算法提高了算法的收斂概率，同時(shí)收斂的代數(shù)也明顯減少，所以本文的算法在減少收斂代數(shù)方面和提高收斂概率方面是具有優(yōu)越性的。

四、結(jié)束語

本文提出改進(jìn)的適應(yīng)度函數(shù)，使得在進(jìn)化初期一些函數(shù)值差的個(gè)體也能有更高的概率參與到選擇、交叉、變異操作中，保存了種群的多樣性，同時(shí)在自適應(yīng)交叉的過程也采用了新的方法，使得在避免“近親繁殖”的基礎(chǔ)上擴(kuò)大了搜索范圍，整個(gè)算法結(jié)合實(shí)數(shù)編碼的全局能力強(qiáng)和格雷碼局部收斂能力強(qiáng)的兩個(gè)特點(diǎn)，在算法中使用了實(shí)數(shù)編碼與格雷編碼相結(jié)合的方法，使得收斂的迭代次數(shù)明顯減小。雖然采用格雷編碼會(huì)導(dǎo)致算法收斂速度慢，但是明顯降低了不收斂的次數(shù)，大大提高了算法收斂速度和收斂概率，使本文算法具有較高的計(jì)算效率。

[1]王力，侯燕玲.基于遺傳算法通用試題庫(kù)系統(tǒng)研究[J].微計(jì)算機(jī)信息，2008.5.

[2]李敏強(qiáng)，寇紀(jì)淞，林丹等.遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社，2004.

[3]楊曉華，陸桂華，酈建強(qiáng).解非線性極大極小問題的格雷碼加速遺傳算法[J].河海大學(xué)學(xué)報(bào)，2003.31.1.

[4]魏平，熊偉清.一種改進(jìn)的實(shí)數(shù)編碼遺傳算法[J].計(jì)算機(jī)應(yīng)用研究，2004.21.9.

[5]王小平，曹立明.遺傳算法——理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社，2002.