基于適應(yīng)度函數(shù)及交叉操作改進(jìn)的自適應(yīng)遺傳算法

□文/竇明鑫劉曉霞

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

基于適應(yīng)度函數(shù)及交叉操作改進(jìn)的自適應(yīng)遺傳算法

□文/竇明鑫1劉曉霞2

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

為了提高遺傳算法的搜索效率，給出了一種改進(jìn)的遺傳算法。該算法改進(jìn)了適應(yīng)度函數(shù)和交叉操作，擴(kuò)大了搜索范圍。通過三個經(jīng)典函數(shù)的測試表明，改進(jìn)算法與基本遺傳算法相比較，在函數(shù)最優(yōu)值、平均收斂代數(shù)、收斂概率等方面都取得了令人滿意的效果。

自適應(yīng)遺傳算法；適應(yīng)度函數(shù)；交叉操作；實數(shù)編碼

收錄日期：2012年5月10日

引言

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

本文對自適應(yīng)算法進(jìn)行了改進(jìn)，構(gòu)造了一種自適應(yīng)的適應(yīng)度函數(shù)，以便更好地進(jìn)行復(fù)制、交叉、變異操作，之后對實數(shù)的交叉操作進(jìn)行了改進(jìn)，擴(kuò)大了搜索范圍，提高了算法全局搜索能力，最后利用改進(jìn)算法進(jìn)行仿真實驗，結(jié)果表明本算法具有收斂概率高和平均收斂代數(shù)少的優(yōu)點。

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

（一）改進(jìn)的適應(yīng)度函數(shù)。為了使進(jìn)化前期原本函數(shù)值低的個體有更大的概率被選擇，保持種群多樣性防止“早熟”，而在后期可以轉(zhuǎn)成正常選擇操作，開始局部求精的搜索。本文參考文獻(xiàn)將適應(yīng)度函數(shù)改進(jìn)為：

其中，f（xi）是所對應(yīng)的函數(shù)值是群體的平均函數(shù)值，fmax為上一代最優(yōu)解所對應(yīng)的函數(shù)值，t為當(dāng)前代數(shù)，T為預(yù)先設(shè)置好的最大迭代次數(shù)。

這種調(diào)整使得原本函數(shù)值遠(yuǎn)離群體均值的個體適應(yīng)度變大，使其被選擇的概率增大，而對種群貢獻(xiàn)較小的函數(shù)值處于中間位置的個體被選擇的概率變小，使得在進(jìn)化前期可以保證種群的多樣性，避免產(chǎn)生模式欺騙問題或過早陷入局部收斂。

（二）改進(jìn)的交叉操作。由于本文對適應(yīng)度函數(shù)的調(diào)整在前期較好地保持種群的多樣性，在進(jìn)化前期為了提高算法的搜索效率，交叉概率設(shè)定的較小，在進(jìn)化后期為了保證種群的多樣性加大了交叉概率，所以本文設(shè)定Pc=0.25+0.45·，其中t和T的含義同上。

本文改進(jìn)的交叉操作是先在交叉前產(chǎn)生三個服從均勻分布的隨機(jī)數(shù)a∈（0，1）、b∈（-1，1）、c∈（-1，1），然后假設(shè)x1、x2是要交叉的兩個父代，個體變量為m維，則 x1、x2可以表示成 x1=（x11，x12，…，x1m），x2=（x21，x22，…，x2m），其中 xij∈［α，β］，設(shè)定△1＝（△11，△12，…，△1m），△2＝（△21，△22，…，△2m）為位移變量，其中△ij=min｛（xij-α），（β-xij）｝（i=1，2；j＝1，2…m），最后進(jìn)行兩次操作得：

x1'、x2'、x1''、x2''分別為兩次操作所產(chǎn)生的子代，從這4個子代中選取適應(yīng)度大的兩個保留到下一代。通過這種操作可以有效地避免兩個數(shù)值相近的個體進(jìn)行“近親繁殖”（數(shù)值相近的個體若只進(jìn)行（3）式的操作會導(dǎo)致種群多樣性快速下降），同時由于 b、c 的選取，生成的 x1'、x2'是兩個不相干的個體，彼此之間獨立，由（3）式?jīng)Q定的后代還可以使子代遺傳父代的某些有用因素，同時由于（2）式的位移調(diào)整，使得（3）式生成的后代比一般的算數(shù)交叉產(chǎn)生后代的范圍得到擴(kuò)大，提高算法的搜索范圍，避免搜索陷入一個局部區(qū)域而出現(xiàn)“早熟”，最后再引入競爭機(jī)制在這四個后代中選出兩個最好后代個體，這樣在保證多樣性的同時可以加快收斂的速度。

二、算法步驟

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

Step2 計算每個個體的函數(shù)值，之后計算種群函數(shù)的平均值，最后按照本文設(shè)定的適應(yīng)度函數(shù)，即（1）式計算當(dāng)前種群中每個個體的適應(yīng)度。

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

表1 三種算法對測試函數(shù)的運行結(jié)果

Step4 按照概率Pc在種群中隨機(jī)選擇父代個體，然后應(yīng)用本文改進(jìn)的交叉方式進(jìn)行交叉，最后通過競爭選取兩個最好的個體作為子代個體。

Step5 按照概率Pm變異操作如下：假設(shè)個體xi中第k個分量xki是待變異個體，通過高斯變異可以得到新的個體分量xiknew，其中：

Step6 最優(yōu)保存策略，結(jié)合文獻(xiàn)本文將最優(yōu)保存策略算法做如下修改：第一步，計算每個個體的函數(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)個體策略的遺傳算法能夠以概率1收斂于最優(yōu)解。

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

三、仿真試驗

（一）測試函數(shù)。選取參考文獻(xiàn)的測試函數(shù)為：

其中，f1為單峰二次函數(shù)，當(dāng)（x1，x2，x3）＝（0，0，0） 時有全局最小值 0；f2是一維連續(xù)且含三角函數(shù)的多峰函數(shù)，當(dāng)x=1.8505時，全局最大值為 3.8503；f3是一個典型的大海撈針類函數(shù)，該函數(shù)將形成不同嚴(yán)重程度的GA 欺騙問題，當(dāng)（x1，x2）＝（0，0）時函數(shù)有最大值3600，并且函數(shù)有4個局部極值點：（5.12，5.12），（-5.12，5.12），（-5.12，－5.12），（5.12，－5.12），函數(shù)值為 2748.78。

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

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

通過實驗表明：本文的算法在對函數(shù)的測試中，達(dá)到最優(yōu)值的收斂代數(shù)明顯減少，得到了令人滿意的效果，特別在對函數(shù)f3的測試中，本文算法不僅減少了收斂的代數(shù)，而且提高了明顯算法的收斂概率。所以，本文的算法在減少收斂代數(shù)方面和提高收斂概率方面是具有優(yōu)越性的。

四、結(jié)束語

本文提出改進(jìn)的適應(yīng)度函數(shù)，使得在進(jìn)化初期一些函數(shù)值差的個體也能有更高的概率參與到選擇、交叉、變異操作中，保存了種群的多樣性，同時在自適應(yīng)交叉的過程也采用了新的方法使得在避免“近親繁殖”的基礎(chǔ)上擴(kuò)大了搜索范圍，大大提高了算法收斂速度和收斂概率，使本文算法具有較高的計算效率。

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

[2]陳理國，蔡之華.改進(jìn)的正交遺傳算法及其在函數(shù)優(yōu)化中的應(yīng)用.計算機(jī)工程與設(shè)計，2008.29.13.

[3]楊春松，程文明.一種進(jìn)化類混合算法的研究[J].計算機(jī)仿真，2007.10.10.

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

TP3

A