進化數據分組處理算法研究進展

摘 要:先對進化人工神經網絡的理論研究和運用現狀進行了分析，在此基礎上，分別分析了各種進化數據分組處理算法研究的現狀，最后結合進化數據分組處理算法研究現狀提出了一些新的進化算法。

關鍵詞:人工神經網絡; 遺傳算法; 數據分組處理算法

中圖分類號:TP181; TP183

文獻標志碼:A

文章編號:1001-3695(2010)02-0405-03

doi:10.3969/j.issn.1001-3695.2010.02.002

Reviews of evolutional group method of data handling

MIN Song-qiang， HE Chang-zheng

(School of Business Administration， Sichuan University， Chengdu 610064， China)

Abstract:This paper first analyzed the theoretical research and application of the status of evolutional artificial neural network(ANN)， then analyzed the various status of evolutional group method of data handling (GMDH). At last， basing on this researched，it put forward some new algorithms.

Key words:artificial neural network(ANN); genetic algorithm(GA); group method of data handling(GMDH)

人工神經網絡(ANN)具有適應性和魯棒性等優點，但它具有收斂速度慢、全局搜索能力差等缺點[1]。霍蘭借助達爾文的進化論以及門德爾的遺傳學說的思想，把最優問題的求解過程擬合成物種進化發展的過程，創建了遺傳算法(GA)[2]。該算法不依賴于問題模型的特性，具有全局最優性、隱含并行性等優點，已經在各個領域得到廣泛的應用。將GA應用于ANN實現了多種進化算法，這種算法具有ANN的廣泛映射能力和遺傳算法的全局、隱含并行尋優及高效率學習能力。Ivakhnenko [3]提出的數據分組處理算法(GMDH)具有與ANN類似的結構，在與GA結合研究中也取得了一些重要的研究成果。這些進化后的算法結合了GA的優點，在一定程度上降低了模型的復雜性、增強了模型的全局搜索能力并加快了模型的收斂速度，在實際問題的應用中得到了較好的效果[4]。

1 進化ANN研究的現狀

ANN中權值的調整主要利用的是梯度搜索算法，如果誤差是多峰或是不可微的，該算法往往限于局部最優。利用GA可解決這個問題，首先對連接權值進行染色體編碼[5]，再利用GA優化。對于傳統的ANN結構的設計主要是利用反復的實驗得到最優的權重，進化算法利用GA優化網絡結果與優化權重時類同，通常都是采用直接編碼和間接編碼兩種方式。這里直接編碼方式有對連接權值分離的進化方式及將結構和權值同時進化兩種方式[6];間接編碼方式是對主要的參數編碼，可減少染色體的長度[7]，文獻[8]中認為這種編碼方式比直接編碼得到的結果更合理。在網絡結構進化上還有對連接函數的優化，這里主要是對每層中考慮多種傳遞函數。再有，實際應用中可能存在大量輸入變量時，利用GA選擇較為有效的輸入變量特征，可以減少計算量，更為有效地快速得到最優解[9]。既然對ANN的每個部分利用GA進化可以得到較優的結果，文獻[10]就把ANN中所涉及到的所有參數同時利用GA進化。各種進化的ANN方法在一定程度上都解決了ANN存在的收斂于局部最優、計算量大和收斂速度慢等問題，進化算法已在諸如經濟管理等許多領域得到了實際的應用[6~10]。

2 數據分組處理算法

數據分組處理方法是由烏克蘭科學院Ivakhnenko 院士在1967年首先提出的，是用于復雜系統建模和識別的多變量分析方法[11]。它采用多層迭代， 借助自組織原理， 利用數據和計算機相對客觀地選擇變量之間的關系， 通過啟發式學習實現輸入、輸出間的非線性映射， 用外準則選取最優模型， 實現對所研究系統內部結構的模擬。利用這種方法對于系統建立模型可以不需要先驗知識，并且近幾年成功地將這種方法運用到了工程、科學和經濟等領域。其基本運算步驟如下[12]:

a)劃分訓練集和檢測集。給出系統輸入—輸出數據觀察樣本集合ω， 將其分為訓練集A(training set)和檢測集B(testing set)，數據樣本個數Nω=NA+NB。

b)建立輸入變量和輸出變量間的一般關系，作為參考函數一般取Volterra函數級數或Kolmogorov-Gabor多項式的離散形式作為參考函數:

y=a0+∑mi=1aixi+∑mi=1∑mj=1aijxixj+∑mi=1∑mj=1∑mk=1aijkxixjxk+…

c)從具有外補充性質的選擇準則中選出一個或幾個作為外準則。

d)產生算法的初始輸入變量，據所選取的參考函數， 將函數中每一項都作為一個算法的初始輸入變量。若選定二次K-G多項式，以x1，x2為輸入數據的變量，那么相應的K-G多項式為f(x1，x2)=a0+a1x1+a2x2+a3x21+a4x22+a5x1x2，所以網絡的輸入變量為(v1=a0，v2=a1x1，v3=a2x2，v4=a3x21，v5=a4x22，v6=a5x1x2)。

e)產生第一層局部模型。參考函數yk=fk(vi，vj)為第一層中間模型，它由自組織過程自適應產生，且所含變量個數、函數結構彼此相同，同時在訓練集A上估計yk的參數。

f)利用準則對第一層生產的模型篩選。選擇外準則值小的Fk個模型作為第二層的輸入變量。

g)形成最優復雜度模型網絡結構。重復e)f)，會生成一個復雜度不斷增加的模型網絡結構，并選擇外準則值最低的模型作為最優復雜度模型。

利用以上七步生成的最優模型結構如圖1所示。由于GMDH與其他的數據挖掘方法相比，具有對噪聲的小數據樣本較強的預測能力，并且結果是顯式的模型，具有解釋經濟對象構成因素的功能，因此在理論和實際兩個方面都得到了很多的發展[12]。

3 進化GMDH研究現狀

雖然GMDH相對于ANN而言有自己的優點[13]，但是也存在以下主要不足之處[14]:a)對于相對簡單的系統可能產生過度復雜的系統多項式;b)當處理高維的非線性系統時，由于參考函數的限制可能會產生過度復雜的網絡。針對GMDH的不足，利用GA優化GMDH體現在以下幾個方面。

1)GMDH的分層參數進化

利用GA選擇每一層的輸入參數，這里的參數指的是每個節點的輸入變量個數、參考函數類型、具體的輸入變量。這方面研究的典型代表是Dong-Won Kim，他率先把Sung-Kwun Oh在數據分組處理方法的基礎上提出的多項式神經網絡(PNN)與遺傳算法結合[15，16]，對每個節點所包含的參數用二進制的方式編碼，利用遺傳算子中的選擇、交叉、變異算子生成不同的個體，再利用適應度函數選擇較優的節點作為下一層的輸入，利用這種方法可以自動地優化前面提到的三個參數，而不需要再由建模者提前確定這三個參數。利用這種方法的主要優點在于:依靠客觀環境的變換選擇下一代種群的思想，減少了人為作用從而減少了模型的誤差;利用隨機的思想產生節點的輸入，而不用像傳統的數據分組處理方法那樣窮舉所有的可能輸入組合，很好地解決了計算量大的問題;不提前確定特定的一種參考函數，特定的輸入變量組合方式保證了節點的多樣性，較好地解決了傳統數據分組處理方式中難以避免的收斂到局部最優的問題。但是，這種方法也并不是完全由自組織產生，每一層的節點個數并沒有擺脫人為的參與，且節點個數較少，這意味著不能完全地避免局部最優問題;而且這種方法所選擇的參考函數類型是K-G多項式中的某一部分，這樣的選擇方式過濾掉了很多有用的輸入變量。

2)GMDH層次結構參數進化

GMDH層次結構參數進化主要是由Nariman-Zadeh等人提出，主要思想是神經元的輸入變量不只是與其相鄰的前層節點的輸出，還考慮了更前層的較優節點的輸出。在進化時，利用的是符號編碼的方式對每個輸入變量編碼，選擇和交叉算子在多層間進行的，相應地也利用了變異算子，形成了新的網絡結構[17]。這種算法在層次結構上的優化方式保證了多樣性，能較快地達到收斂的目的，減少網絡的層數，增加了有效的輸入變量的個數，保證了群體的多樣性，加快了逼近最優解的速度，可在較少層的情況下達到收斂的目標。Sakaguchi等人[18]在系統識別時也提出利用GA進化GMDH網絡，首先是利用GA選擇神經元的單項式，再利用 GA 所選擇得到的單項式的權值進化，這里采用了兩種GA的算子分別對結構和層數實現了進化。在權值進化時采用的是與進化ANN類似的方式，在一定程度上改變了傳統的GMDH估計參數的方法。

這種方法的不足就是只優化相關參數的選擇，并沒有實現參考函數的多樣化，就很難避免算法限于局部最優和計算量大的問題，且在軟件操作上難以實現。

3)利用其他改進的GA進化GMDH算法

由于GA本身也存在不足之處，在進化GMDH算法時，對GA的改進是一個重要的方面。a)由于傳統GA的隨機搜索可能帶來過大的計算量，利用有平行直接搜索能力的差分遺傳算法對傳統的遺傳算子進行改進，差分遺傳算法對傳統的選擇、交叉、變異遺傳算子進行了改進，經實驗證明在改進后更能保證個體的多樣性，值能較快地收斂到最優值[19]。b)針對GA中交叉和變異算子進行調整參數時，染色體互相共享信息，整個種群是比較均勻地向最優區域移動，而粒子群算法是單向的信息流動[20]，整個搜索更新過程是跟隨當前最優解單向移動過程，能更快地收斂于最優解。c)針對進化算法的第一個方面提到的GMDH只是用了K-G多項式，并不能很好地保持模型的精確度，用遺傳規劃(EP)的思想首先選擇輸入變量與輸出變量間最優的參考函數，再代入網絡計算，這種方法在進行時間序列預測天氣和財政方面能較為精確地逼近函數最優值[21]。當然，針對遺傳算法本身的不足和方法應用到的具體領域的不同，可以嘗試利用新的算法來改進遺傳算法，如利用模擬退火算法、小生境技術和共享函數及交互式遺傳算法等思想解決問題。

4)GA與其他優化算法結合進化GMDH算法

不同的應用領域對結合算法的要求是不同的，如果算法需要解決的問題是一個模糊集合，可將結合的算法與模糊數學結合產生基于GA的模糊多項式神經網絡[22，23]。這種組合算法首先對數據進行模糊化，再在模糊化方式和模糊規則的選擇中融入遺傳算法。但這種組合算法是機械地把模糊集合融入到GMDH和遺傳算法的結合中，并沒有針對算法本身的特點進行考慮。與模糊數學結合的另一種方式就是針對實際問題中輸入變量較少的情況。由于缺乏輸入數據不能較好地逼近函數，利用這種方法保證數據的多樣性，再利用遺傳算法保證群體的多樣性[16]。還有一個方式就是利用信息粒的思想解決和處理大量復雜信息問題，這種思想是把大量復雜信息按其各自的特征和性能劃分成若干較簡單的塊，而每個如此劃分出來的塊被看成一個粒，并將得到的信息粒作為網絡的輸入[14，24]。

4 進化GMDH研究展望

4.1 基于進化ANN對進化GMDH研究的展望

對比進化ANN研究現狀和進化GMDH現狀，進化GMDH的研究可結合三種算法的各自特點和各個算法之間的差異，進化GMDH的研究可借鑒進化ANN先利用GA選擇ANN的各項參數，再把選擇好的參數代入網絡中的方式;對于進化GMDH，也可用先選擇參數再代入GMDH網絡中。但是本文選擇的參數卻與進化ANN不同，在參數選擇上考慮利用GA對分式函數、K-G多項式、調和函數三種參考函數選擇，及對正則化準則、抗干擾準則和組合準則三種準則進行選擇。將選擇好的參數代入GMDH網絡中，得到的新的算法流程如圖2所示。新的進化GMDH算法考慮到了數據集的構成特性，并且利用多種選擇準則更有利于剔除模型存在的誤差，并且在理論和實驗上GMDH網絡在一定程度上優于人工神經網絡[13]，所以這種算法也可以運用到經濟管理以及工程方面。在實際利用這種算法的過程中可以先分析數據和適用行業的特點，再選擇參考函數、選擇準則、運算的層數以及每層中的節點個數等參數。

4.2 基于GMDH的特點對進化GMDH研究的展望

GMDH與ANN有著類似的網絡結構，而GMDH中的模型分為參數模型和非參數模型[25]。筆者認為可以借鑒進化ANN的思想從以下這兩個方面進化GMDH。

a)進化GMDH參數模型。GMDH的參數模型一般有組合算法、分層算法和調和算法，目前在GMDH參數模型上的研究相對還是比較少。根據這三種算法的特點，結合GA的全局搜索特點，在這方面是能作進一步的研究的，如調和算法可以與傅里葉函數結合應用于經濟管理中的時間序列數據的處理。

b)進化GMDH非參數模型。GMDH的三種基本非參數模型(客觀聚類分析、相似體合成算法、自組織模糊準則歸納算法)中的相似體合成算法由于要隨機地產生待選模式，可以基于GA選擇不同的待選模式和不同的待選模式變換，結合外準則和GMDH網絡，可以實現基于GA的多層GMDH相似體合成算法的網絡。再有，調和算法主要用于波動的過程，比較適合于時間序列數據，結合相似體合成算法需要時間序列數據的特點，可以在GMDH網絡上實現更優化的算法。當然這兩種算法與其他算法結合也是可以進一步研究的。

參考文獻:

[1]韓力群 .人工神經網絡理論、設計及應用[M].北京:化學工業出版社，2002.

[2]王小平，曹立明.遺傳算法[M].西安:西安交通大學出版社，2002.

[3]IVAKHNENKO A G. Heristic self-organizing in problems of enginee-ring cybernetics[J]. Automatica， 1967，6(2):207-219.

[4]AMANIFARD N， NARIMAN-ZADEH N， BORJI M， et al. Modelling and Pareto optimization of heat transfer and flow coeffcients in microchannels using GMDH type neural networks and genetic algorithms[J]. Energy Conversion and Management， 2008，49(2):311-325.

[5]WHITLEY D， STARKWEATHER T. Genetic algorithms and neural networks:optimizing connections and connectivity[J]. Parallel Computing， 1990，14(3):347-361.

[6]LIU Yong， YAO Xin. A population-based learning algorithm which learns both architectures and weights of neural networks [J]. Journal of Advanced Software Res， 1996，3(1):54-65.

[7]PEREZ C A， HOLZMANNA C A. Improvements on hand written digit recognition by genetic selection of neural network topology and by augmented training[C]//Proc of IEEE International Conference on Systems， Man， and Cybernetics. 1997:1487-1491.

[8]MERRILL J W L， PORT R F. Fractally configured neural networks[J]. Neural Networks，1991，4(1):53-60.

[9]STORK D G， WALKER S， BURN M， et al. Preadaptation in neural circuits[C]//Proc of International Joint Conference on Neural Networks. 1990:202-205.

[10]WANG Hsing-Wen. Identification of characteristics after soft breakdown with GA-based neural networks[C]//Proc of the 19th International Conference on Industrial， Engineering and other Application. 2006:564-572.

[11]賀昌政，呂建平. 自組織數據挖掘理論與經濟系統的復雜性研究 [J].系統工程理論與實踐， 2001， 21(12):1-5.

[12]賀昌政.自組織數據挖掘與經濟預測[M].北京:科學出版社，2005.

[13]賀昌政，張賓，俞海. 自組織數據挖掘與人工神經網絡方法比較研究[J]. 系統工程理論與實踐，2002，22(11):11-14，50.

[14]MAHMOOD A， SHARMIN S， BARUA D， et al. Graph matching recombination for evolving neural networks[C]//Proc of the 4th International Conference on Neural Networks. 2007:562-568.

[15]OH S K，PEDRYCZ W. The design of self-organizing polynomial neural networks[J]. Information Sciences， 2002，141(3):237-258.

[16]KIM D W， PARK G T. Advanced self-organizing polynomial neural network[J]. Neural Computing Applications，2007，16(4-5):443-452.

[17]NARIMAN-ZADEH N， DARVIZEH A， AHMAD-ZADEH G R. Hybrid genetic design of GMDH-type neural networks using singular va-lue decomposition for modelling and prediction of the explosive cutting process[J]. Journal of Engineering Manufacture， 2003，217(6):779-790.

[18]SAKAGUCHI A， YAMAOTO T. A study on system identification using GA and GMDH network[C]//Proc of the 29th Annual Confe-rence on IEEE Industrial Electronics Society. 2003:2387-2392.

[19]ONWUBOLU G C. Design of hybrid differential evolution and group method of data handling networks for modeling and prediction[J]. Information Sciences， 2008，178(18):3616-3634.

[20]ABBOD M， DESHPANDE K. Using intelligent optimization methods to improve the group method of data handling in time series prediction[C]//Proc of the 8th International Conference on Computional Science. 2008:16-25.

[21]HIASSAT V， ABBOD M， MORT N. Using genetic programming to improve the GMDH in time series prediction[M]//Statistical Data Mining and Knowledge Discovery. [S.l.]:Chapman and Hall， 2003:265-284.

[22]NARIMA-ZADEH N， DARVIZEH A， DADFARMAI M H. Design of ANFIS networks using hybrid genetic and SVD methods for the modelling of explosive cutting process[J]. Journal of Materials Proces-sing Technology， 2004， 155-156:1415-1421.

[23]OH S K， PEDRYCZ W. A new approach to self-organizing multilayer fuzzy polynomial neural networks based on genetic optimization[J]. Advanced Engineering Informatics，2004，18(1):29-39.

[24]PARK H， PARK D， OH S K. Genetically optimized self-organizing fuzzy polynomial neural networks based on informationgranulation[C]//Proc of the 2nd International Conference on Neural Networks. Berlin:Springer， 2005:410-415.

[25]張賓，賀昌政. 自組織數據挖掘方法研究綜述[J]. 哈爾濱工業大學學報， 2006，38(10):1719-1723，1727.