基于適應度函數及交叉操作改進的自適應遺傳算法

□文/竇明鑫劉曉霞

（1.中國地質大學長城學院；2.河北金融學院 河北·保定）

基于適應度函數及交叉操作改進的自適應遺傳算法

□文/竇明鑫1劉曉霞2

（1.中國地質大學長城學院；2.河北金融學院 河北·保定）

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

自適應遺傳算法；適應度函數；交叉操作；實數編碼

收錄日期：2012年5月10日

引言

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

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

一、改進的遺傳算法

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

其中，f（xi）是所對應的函數值是群體的平均函數值，fmax為上一代最優解所對應的函數值，t為當前代數，T為預先設置好的最大迭代次數。

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

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

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

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

二、算法步驟

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

Step2 計算每個個體的函數值，之后計算種群函數的平均值，最后按照本文設定的適應度函數，即（1）式計算當前種群中每個個體的適應度。

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

表1 三種算法對測試函數的運行結果

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

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

Step6 最優保存策略，結合文獻本文將最優保存策略算法做如下修改：第一步，計算每個個體的函數值，然后排序，找出最優解，最差解；第二步，若上一代最優解的函數值比當前最優解的函數值大，則用上一代的最優解替換當前最優解；若上一代的最優解函數值小，則用上一代的最優解替換當前中的最差解。這樣基于Markov鏈的數學理論分析表明，保留最優個體策略的遺傳算法能夠以概率1收斂于最優解。

Step7 滿足迭代次數即停止，否則代數加1，轉入Step2。

三、仿真試驗

（一）測試函數。選取參考文獻的測試函數為：

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

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

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

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

四、結束語

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

[1]李敏強等.遺傳算法的基本理論與應用[M].北京：科學出版社，2004.

[2]陳理國，蔡之華.改進的正交遺傳算法及其在函數優化中的應用.計算機工程與設計，2008.29.13.

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

[4]王小平，曹立明.遺傳算法——理論、應用與軟件實現[M].西安：西安交通大學出版社，2002.

TP3

A