基于改進遺傳規劃算法的數據擬合

(1.廈門大學 模式識別與智能系統研究所， 福建 廈門 361005；2.重慶通信學院 自動化學院， 重慶 400035)



摘 要：針對傳統數據擬合方法需預先估計基函數、依賴于應用領域等問題，基于遺傳規劃的動態可變特性，提出將遺傳規劃與最小二乘法結合，設計具有一定通用性和自適應能力的數據擬合算法。在分析傳統遺傳規劃算法的基礎上，詳細介紹了算法改進方法，并針對各種類型的擬合數據進行了對比實驗。實驗結果表明，該算法不僅可以應用到多種場合，而且可以提高擬合效率與精度。

關鍵詞：遺傳規劃；改進；數據擬合；最小二乘法

中圖分類號：TP301 文獻標志碼：A

文章編號：10013695(2009)02048104



Data fitting based on improved genetic programming



SHAO Guifang1，ZHOU Qifeng1，CHEN Guiqiang2 (1.Institute of Pattern Recognition Intelligent System， Xiamen University， Xiamen Fujian 361005， China；2.Dept. of Automation， Chongqing Communication Institute Quarterly， Chongqing 400035， China)Abstract:There are many problems in current data fitting methods， such as it needs to estimate the radical function in advance and depends on the application field， and so on. Based on the dynamic alterable property of genetic programming (GP)，combined GP with least square method， and designed a new data fitting method which had universal and selfadaptive capacity. Firstly，analyzed the traditional GP.Secondly，introduced the improved method in details.Finally，fimiched some contrastive experiments based on various fitting data. Experiment results show that this method can be applied in many fields， and it can improve the fitting efficiency and precision.

Key words:genetic programming; improve; data fitting; least square method



在科學實驗中，經常涉及大量數據，通常采用數據擬合方法來探索這些數據隱含的內在規律。數據擬合在很多領域都有應用，如工程數據分析、圖像數據分析等，擬合方法也有很多，如最小二乘法、支持向量機、樣條函數方法等[1]。傳統的曲線擬合，如最小二乘法，先要根據專業知識，從理論上推導，或者根據以往的經驗，確定變量之間的函數關系，從而預先確定方程的結構形式（線性形式、對數形式或多項式等），然后再進行參數估計。但實際中很難準確判定方程的結構形式，尤其是數據無明顯規律或數據量比較大的情況，很難估計數據間的關系，因此傳統的曲線擬合均存在一定的局限性。

近年來，進化計算、自然計算等很多模仿自然生物進化過程的算法應運而生，并在很多領域取得了較好的應用效果。遺傳規劃早在1992年就由Koza教授提出，并應用于很多領域[2]，但國內對遺傳規劃的研究非常少，其應用也僅限于機器人的路徑規劃方面。

遺傳規劃遵從生物進化的優勝劣汰，適者生存原則，具有動態可變性、能夠描述層次化問題等優點。目前，也有人利用遺傳規劃進行數據擬合[3~5]，但都直接利用傳統算法進行計算，很難保證一次搜索到最優結果，而且針對不同的應用，需要依據經驗重新設置算法參數。

針對傳統數據擬合算法的不足，如需要預先設計基函數，不同應用需設計不同的基函數等，基于遺傳規劃在其他領域的成功應用[6]，將遺傳規劃引入到數據擬合領域，并進行算法改進，結合最小二乘法，提出了一種具有一定自適應能力的數據擬合算法。

1 傳統遺傳規劃算法

遺傳規劃是從一組隨機生成的初始可行解開始，通過選擇、交叉和突變等遺傳操作，逐步迭代而逼近問題的最優解。傳統遺傳規劃算法操作步驟如下：

a）個體表示。傳統遺傳規劃算法個體表示有三種方法，即樹狀結構、線狀結構和網狀結構。其中，樹狀結構操作簡單方便，使用最為廣泛。

b）種群生成。遺傳規劃初始個體的生成方法主要有三種，即完全法、生長法和混合法。只用完全法形成的初始群體，個體間在結構上很相似，而只用生長法形成的初始群體，個體間在結構上的差異可能會很大。為了增加群體的多樣性，同時又保證結構的合理性，可將兩種方法結合起來。

c）交叉。遺傳規劃包括三種交叉算子，即子樹交叉、模塊交叉和自身交叉。通常采用子樹交叉方式來產生新個體，即隨機從父代中選擇出一些個體，選擇其中最好的個體進行交叉操作，如果選擇出的兩個個體適應度相同，則選擇含有節點少的個體。

d）變異。遺傳規劃主要有子樹突變和點突變兩種變異算子。點突變只針對節點進行替換操作，如選擇的節點是函數，則隨機從函數集中選擇一個代替；子樹突變是對所選擇節點以下的整個子數用隨機生成的新子樹代替。

e）新一代個體。傳統遺傳規劃算法通常采用誤差絕對值作為適應度函數來評價個體的優劣，并分別從父代和通過交叉變異產生的子代中選擇出一部分個體構成新種群，再重復c）和d）的遺傳操作，直到達到最大進化代數。

由于遺傳規劃是一種隨機性很強的全局搜索優化算法，是否能收斂到全局最優解與初始種群的質量、參數選擇、遺傳操作及適應度值的計算方法等有很大關系。因此，有必要對其進行改進，以提高其收斂性能，使其更適合實際應用。

2 算法改進

2.1 參數設置

1）個體表示樹狀結構在程序中可以采用數組和類等方式靈活存儲，簡單方便，因此采用樹狀結構表示個體。遺傳規劃用終止符集抽象表示問題的輸入，用函數集模擬對輸入的處理，針對數據擬合問題，可以設計終止符集為T={x，α}，函數集F={+，-，×，/，sin，cos，log，…}。函數集越詳盡，產生的個體越復雜，因此，函數集到底應該包含多少運算符要依據實際應用情況進行調整，以提高算法效率。

2）種群產生 為了保證個體結構合理以及種群具有多樣性，采用混合法產生初始種群。同時，為了防止個體在進化過程中無限制地增大，限制了個體的節點數目最大為25，并按式(1) 選擇節點：

node=f random_num＞(flag*flag+3)/(size-i+1)

telse(1)

其中：size為限制個體的最大節點數；flag為條件標志，初始為1，每從函數集中選擇一次，自動加1，從終止符集中選擇一次，則自動減1；i為產生節點數；random_num為產生的隨機數。

3）適應度函數 數據擬合最終的目的就是使擬合出來的函數能最大限度地包含原始數據，能充分展現出原始數據的內在規律。在未知數據內在規律的情況下，利用遺傳規劃可以產生不同結構的基函數。產生基函數后，如何評價這些基函數。遺傳規劃主要通過適應度函數來評價每個個體，鑒于最小二乘法在確定擬合函數結構后，具有較好的效果。因此，本文利用最小二乘法來設計適應度函數：

fi=Mj=0|p(xj)-yj|2 (i=1，2，…，N)(2)

其中：p為遺傳規劃產生的個體，即擬合函數。

4）終止條件 為了提高算法效率，保證每次運行能找出較優的結果，設置了如式(3)所示的終止條件，三個條件只要有一個滿足就結束程序。

p=fi＜0.001

hits≥90%

gen=max_gen(3)

其中：hits表示擬合匹配程度；max_gen為進化代數。

2.2 輪盤賭選擇進行交叉

遺傳規劃的交叉操作主要有子樹交叉、自身交叉和模塊交叉等三種方法。本文選擇了子樹交叉法來實現交叉操作，為了保證種群的多樣性，引入了輪盤賭來選擇進行交叉的個體，具體操作流程如下：

假設，種群中有N個染色體c1，c2，…，cN，其適應度函數值分別為f1，f2，…，fN，優化問題為適應度函數值越小越好。

a）歸一化處理整個種群中染色體的適應度值

P(c0)=0；P(ci)=P(ci-1)+(1/fi)/ξ；i=1，2，…，N(4)

其中ξ=Ni=11/fi，fi≠0。如果fi=0，可以令f′i=fi+ζ，重新計算式(3)。ζ為常數，f′i≠0。

對于適應度函數值越大越好的情況，可以將式(4)改為

P(c1)=0；P(ci)=P(ci-1)+fi/ξ；i=1，2，…，N(5)

其中ξ=Ni=1fi。

b）隨機產生一個數β，β∈[0，1]。如果P(ci-1)＜β＜P(ci)，那么選擇第i個染色體進行交叉操作。

c）重復步驟b）選擇另一個染色體cj，j≠i。

d）如果所選擇的兩個個體相同或適應度值相等，則重復b），直到選擇出兩個不同的個體。

e）在選擇出的兩個染色體中用均勻分布的隨機方法分別選擇交叉點，包括交叉點在內的交叉點以下的子樹稱為交叉段。

f）交叉兩個父代個體的交叉段，完成交叉操作。

2.3 混合變異

為提高算法搜索能力，使結果更接近于全局最優解，避免早熟收斂，本文選擇了兩種方式來實現突變，即大規模突變和子樹突變。

2.3.1 大規模突變

大規模突變是根據整個種群的適應度情況來確定是否進行突變，其目的主要是為了提高較差個體的性能，提高種群多樣性，避免陷入早熟，大規模突變的操作過程如下：

a）利用式fi=1/(fpopulation-i+0.0001)，將最小適應度變為最大適應度問題。

b）計算整個種群適應度：

fitpopulation=(N×foptimal)/(Ni=1fi)

(6)

其中：N為種群大小；foptimal為最優個體適應度。本文對種群個體進行了按適應度排序，所以第0代個體就是最優個體，即foptimal=f0。

c）如果fitpopulation＞α，則轉d）進行大規模突變，否則不進行。α可根據情況確定，本文中α=0.9。

d）對種群中第N/4~N的個體利用隨機產生新個體方式來替代。

2.3.2 子樹突變

子樹突變主要發生在利用輪盤賭選擇了兩個父代個體進行交叉后，依據如下步驟進行：

a）隨機產生一個數β，如果β＜Pmute則轉b）進行子樹突變，否則不進行。

b）隨機產生變異點，隨機生成一棵樹結構個體，用該樹代替變異個體變異點以下的子樹。

c）如果變異后的個體節點數超過最大限制節點，則轉b）重新進行子樹變異。

2.4 新一代個體的選擇

由于遺傳規劃過程存在很大的隨機性，適應度高的個體不一定是最差個體。但傳統方法中，適應度較大的個體很少有機會在下一代中起作用。為了解決該問題，給適應度較大的個體一定的表現機會，本文引入了按適應度排序，具體操作如下： 

a）復制父輩個體。

b）復制通過選擇交叉、變異等產生的子代個體。

c）將父輩與子代個體組合在一起，按適應度從小到大排序，從中選擇出較優的N個個體形成新一代種群。

d）繼續進行其他操作。

通過上述改進操作，提高了種群的多樣性，并大大降低了遺傳規劃早熟收斂的概率。

3 實驗分析

為了使遺傳規劃算法更好地應用在數據擬合領域，前文討論了在參數設置、交叉個體選擇、變異及新一代個體選擇等方面的改進。為了驗證算法的有效性，在VC6下實現了該算法，并針對不同類型的數據進行了大量實驗，分別與最小二乘法和傳統遺傳規劃算法進行比較。下面給出了3組不同性質的實驗分析，這些實驗都是在同一組進化參數下進行的，即Pcross=6，Pmute=0.01，N=20，max_gen=50。區別是函數集和終止符集有所不同。

3.1 實驗1

針對明顯有規律性的數據，在同樣的初始條件下，分別給出3組測試數據，每組數據包含10個數據項，如表1所示。函數集F={+，-，×，/}，終止符集T={x}，將本文算法分別與最小

針對表1的3組測試數據，分別假設基函數是2階多項式和3階多項式形式，用最小二乘法進行擬合，與本文算法擬合結果進行對比，得到如表2所示的計算結果。

表2 實驗結果對比1

表2中的誤差為平均誤差，可以利用式(7)進行計算，主要用來評價擬合結果的優劣。

e=（(nk=1|f(xk)-yk|2）/n)1/2(7)

3.1.2 與傳統遺傳規劃算法比較

利用傳統遺傳規劃算法和本文算法，針對表1的每組數據分別進行51次實驗，記錄每次找到擬合結果時的進化代數，并進行統計，得到如表3所示的進化代數對比數據。圖1為本文算法針對三組測試數據得到的擬合曲線與實際數據的擬合情況對比圖。以表1的第1組數據（即xi，y1i）為例，圖2為傳統遺傳規劃算法和本文算法在51次實驗中，每次實驗成功時的進化代數對比圖；圖3為最優個體適應度變化曲線；圖4為計算過程中種群多樣性的變化曲線。

表3 進化代數

進化代數算法最小值最大值平均值

從表2 可以看出，在數據量比較小、且有一定規律性的情況下，利用最小二乘法和本文算法均能得到較好的擬合結果，最小二乘法在有些情況下反而能得出比本文算法更逼近的擬合結果。

從圖1可以看出，在不改變程序的情況下，本文算法可以適應不同數據的擬合，并且基本能找到最佳的擬合函數。

從表3和圖2可以看出，針對表1給出的3組測試數據所進行的51次實驗，本文算法總體上要比傳統遺傳規劃算法運行效率高，即能在較短的時間內找出最佳擬合結果，某些情況下，甚至在第0代就能找到結果。而傳統遺傳規劃算法需要運行較長時間才能找到擬合結果，有些情況甚至進化完50代都不一定能找到最佳擬合結果。

從圖3和4可以看出，本文算法與傳統遺傳規劃算法相比有兩個優勢，即適應度能快速收斂和種群多樣性比較好，這也證明了本文算法的改進是有效的。

針對表4數據，分別采用最小二乘法、傳統遺傳規劃算法和本文算法進行擬合，通過50次實驗，得到擬合結果如表5所示。其中誤差利用式(7)計算得到。

表5 實驗結果對比2

名稱方程誤差成功率

傳統GP112+111.18327/-0.311128x2-27.55132

0.628 569%

最小二乘法-0.02026x2+0.61161x+106.450.501 1100%

本文算法111.4-9/x-1/x20.205 990%

在50次實驗中，由于最小二乘法是在已經確定基函數結構形式的情況下進行擬合的，每次都逼近相同的函數，成功率為100%，平均誤差也一致；而傳統遺傳規劃算法，50次實驗中有16次沒有找到結果；本文算法有5次沒有找到結果。從表5和圖5可以看出，在數據沒有明顯規律的情況下，本文算法能擬合出最逼近的結果。

3.3 實驗3

前面2組實驗，主要針對小批量數據，用來驗證算法的有效性和可移植性。本次實驗主要通過大量數據，來驗證算法的執行效率。利用MATLAB 6.5隨機生成各種數據點，作為測試數據，如y=x+x2+normrnd(-1，1，1，201)，x∈[-10，10]，x按0.1變化，表示產生201個數據點，并給y添加了滿足正態高斯分布的隨機噪聲，在與前面實驗同樣的條件下，分別用最小二乘法、傳統GP和本文算法進行擬合，得到如表6所示結果。

修改函數集為F={+，-，×，/，sin，cos}，其他條件不變，利用y=sin(2x)+normrnd(-0.1，0.1，1，1，1001)，x∈[1，101]產生1 001個測試數據，分別用三種方法進行擬合，得到如表6所示結果。其他實驗情況這里就不再列出。

表6 實驗結果對比3

名稱方程誤差 耗時/ms

1最小二乘法方程0.99x2+0.97x-0.71.501 92

GPx2+x1.311 640

本文算法x2+x-11.032 715

2最小二乘法方程8.07e(-2.04x2)

1.501 93

GPsin(2x)0.144 876

本文算法sin(cos x+2x-sin(cos x))1.032 725

從表6可以看出，隨著數據點個數的增加，傳統GP和本文算法運算時間也加長，而最小二乘法運算時間變化很小，但最小二乘法的擬合結果卻不如傳統GP和本文算法精確。

4 結束語

傳統數據擬合方法需要依據經驗知識預先確定擬合函數的結構形式，由此設計的程序也只能解決某一領域的某一確定問題，可移植性較差。而遺傳規劃具有動態可變特性，不需要先驗知識，因此，本文將遺傳規劃引入到數據擬合領域。同時，結合實際應用經驗，為了提高運算效率、避免傳統遺傳規劃算法的早熟收斂、種群多樣性差等問題，從適應度函數設計、交叉個體選擇、變異操作等方面對其進行了改進。針對不同類型的數據，將本文算法與最小二乘法和傳統遺傳規劃算法等進行了比較，驗證了本文算法的有效性，證明其具有一定通用性，可直接移植到其他領域進行應用，并且具有較高的計算精度和執行效率。但本文算法也存在一定的問題，即針對比較復雜的應用場合，需要適當調整函數集和終止符集。

參考文獻：

［1］

吳宗敏.散亂數據的擬合——模型、方法與理論[M].北京：科學出版社，2006:620.

[2]KOZA J R，KEANE M A，STREETER M J，et al.Genetic programming IV:routine humancompetitive machine intelligence[M].Norway:Kluwer Academic Publishers，2003:1525.

[3]侯進軍，熊令純.遺傳程序設計在數據擬合中的應用[J].長沙電力學院學報，1999，14（2）:141144.

[4]黃麗劍，李郝林.遺傳規劃在測量數據擬合中的應用[J].自動化儀表，2001，22（10）:1516.

[5]XIA Y，TIAN S P，WEI H Y，et al.Application of genetic programming and least square method on data fitting[J]. Chinese Journal of Electron Devices，2007，30（4）:13871390.

[6]邵桂芳，李祖樞，陳桂強.基于進化計算的控制結構設計方法[J].中南大學學報，2007，38（增刊1）:207212.