基于模擬退火遺傳算法的GMDH網(wǎng)絡(luò)模型

張 慧，劉湘南，黃 剛

（1.天津城市建設(shè)學(xué)院計(jì)算機(jī)與信息工程學(xué)院，天津300384；2.中國(guó)地質(zhì)大學(xué)（北京）信息工程學(xué)院，北京100083；3.91917部隊(duì)信息中心，北京100841）

GMDH網(wǎng)絡(luò)源于GMDH方法［1］，它是通過(guò)遞階自由分層動(dòng)態(tài)構(gòu)造的多項(xiàng)式神經(jīng)網(wǎng)絡(luò).GMDH網(wǎng)絡(luò)建模時(shí)網(wǎng)絡(luò)結(jié)構(gòu)是在訓(xùn)練中動(dòng)態(tài)確定，而不需要知道輸入輸出變量之間的先驗(yàn)知識(shí).這種方法可以依據(jù)提供的較少的系統(tǒng)信息，通過(guò)自組織的模型結(jié)構(gòu)，建立不同建模目的模型，適應(yīng)不同的復(fù)雜系統(tǒng).文獻(xiàn)表明，GMDH網(wǎng)絡(luò)在復(fù)雜系統(tǒng)建模、多目標(biāo)優(yōu)化、預(yù)測(cè)等方面有廣泛的應(yīng)用［2－5］.但是GMDH網(wǎng)絡(luò)在建模過(guò)程中，一般采用最小二乘法來(lái)辨識(shí)多項(xiàng)式系數(shù)，由于使用最小二乘法來(lái)辨識(shí)參數(shù)存在局限性，傳統(tǒng)的GMDH網(wǎng)絡(luò)在應(yīng)用時(shí)往往需要改進(jìn)，許多學(xué)者在致力于改進(jìn)傳統(tǒng)GMDH網(wǎng)絡(luò)辨識(shí)方法的研究［6－8］.

遺傳算法作為一種全局優(yōu)化算法，成功運(yùn)用于系統(tǒng)辨識(shí)與參數(shù)優(yōu)化［9］.但同時(shí)遺傳算法在全局搜索中存在早熟問(wèn)題，不能保證收斂于全局最優(yōu)點(diǎn)［7］.為避免落入局部最優(yōu)，模擬退火算法采用Metropolis接受準(zhǔn)則，最終漸近收斂于全局最優(yōu)解［10］.本文在GMDH網(wǎng)絡(luò)中，將模擬退火算法與遺傳算法結(jié)合起來(lái)用于對(duì)二元二次多項(xiàng)式系數(shù)的辨識(shí)和優(yōu)化，建立了基于模擬退火遺傳算法的GMDH網(wǎng)絡(luò)模型，并將模型應(yīng)用于泥石流的預(yù)測(cè).計(jì)算機(jī)仿真結(jié)果表明，本文建立的模型是有效的.

1 GMDH網(wǎng)絡(luò)

1.1 GMDH基本原理

假定系統(tǒng)S有m個(gè)輸入變量xi（i＝1，2，…，m），有一個(gè)（一般情況下可能多個(gè)）輸出變量y.現(xiàn)在的問(wèn)題是如何確定下面非線性函數(shù)f（·）的顯明式子：

其中，函數(shù)f可以一般的展成離散型Volterra多項(xiàng)式級(jí)數(shù)（K－G多項(xiàng)式）［6］：

其中，a0，ai，aij，aijk，…，（i，j，k＝1，2，…，m）為多項(xiàng)式系數(shù).

（2）式被廣泛用來(lái)作為非線性模型的完全描述.但要完全確定a0，ai，aij，…等參數(shù)的值是不現(xiàn)實(shí)的，因?yàn)檩斎胱兞吭龆?，?）式的項(xiàng)數(shù)就會(huì)急劇加大.GMDH網(wǎng)絡(luò)模型是通過(guò)多層篩選的方法，用局部簡(jiǎn)單的模型不斷組合逼近（2）式，以得到整體上比較復(fù)雜的模型.

1.2 GMDH網(wǎng)絡(luò)的結(jié)構(gòu)

典型的GMDH網(wǎng)絡(luò)結(jié)構(gòu)圖如圖1所示.

圖1 GMDH的網(wǎng)絡(luò)結(jié)構(gòu)圖Fig.1 The structure of GMDH network

GMDH網(wǎng)絡(luò)的層數(shù)和單元連接并不固定，圖1為示意圖，實(shí)際的GMDH網(wǎng)絡(luò)通過(guò)自組織的形式建立.GMDH的處理單元是一種雙輸入單輸出的結(jié)構(gòu).輸入和輸出之間的關(guān)系以完全二元二次多項(xiàng)式來(lái)表示：

其中，a，b，c，d，e，f為完全二元二次多項(xiàng)式系數(shù).

在GMDH網(wǎng)絡(luò)結(jié)構(gòu)中，處理單元由相鄰兩層的神經(jīng)元組成.處理單元的輸入來(lái)自上層的兩個(gè)神經(jīng)元，兩個(gè)神經(jīng)元形成的完全二元二次多項(xiàng)式作為處理單元的輸出，也就是下層的神經(jīng)元.網(wǎng)絡(luò)每遞進(jìn)一層，多項(xiàng)式的次數(shù)遞增2階，最終整個(gè)網(wǎng)絡(luò)可以形成2k階多項(xiàng)式（k為GMDH的層數(shù)）.由此可見(jiàn)，GMDH網(wǎng)絡(luò)是能夠表達(dá)離散型Volterra多項(xiàng)式級(jí)數(shù)（K－G多項(xiàng)式）的結(jié)構(gòu)模型.

1.3 模擬退火遺傳算法用于辨識(shí)多項(xiàng)式的系數(shù)

（3）式中系數(shù)a，b，c，d，e，f的辨識(shí)通常是用最小二乘法.由于最小二乘法在參數(shù)辨識(shí)時(shí)具有容易陷入局部最小、辯識(shí)非線性系統(tǒng)能力差以及不適用于嚴(yán)重干擾的情況等不足［9］，因而傳統(tǒng)的GMDH網(wǎng)絡(luò)在應(yīng)用中效果不理想.遺傳算法作為一種全局優(yōu)化算法，成功運(yùn)用于系統(tǒng)辨識(shí)與參數(shù)優(yōu)化.但是遺傳算法在全局搜索中也存在早熟問(wèn)題，不能保證收斂于全局最優(yōu)點(diǎn)［10］.為避免落入局部最優(yōu)，模擬退火算法采用Metropolis接受準(zhǔn)則，最終漸近收斂于全局最優(yōu)解［11］.將模擬退火算法與遺傳算法結(jié)合起來(lái)用于對(duì)參數(shù)的辨識(shí)和優(yōu)化，既保證了全局尋優(yōu)又防止了過(guò)早收斂，進(jìn)一步提高了全局與局部尋優(yōu)能力.

2 基于模擬退火遺傳算法的GMDH網(wǎng)絡(luò)模型

2.1 模擬退火遺傳算法的流程

遺傳算法是先將優(yōu)化問(wèn)題的一組基本可行解（xi，yi，zi）編碼為一組二進(jìn)制的字符串即染色體，再對(duì)這些染色體進(jìn)行復(fù)制、交換和變異等操作，從而實(shí)現(xiàn)參數(shù)的優(yōu)化.

運(yùn)用模擬退火遺傳算法辨識(shí)多項(xiàng)式（3）的系數(shù)a，b，c，d，e，f，流程如下圖2所示：

對(duì)遺傳交叉操作的結(jié)果進(jìn)行模擬退火操作，根據(jù)Metropolis準(zhǔn)則判斷是否接受交叉操作所得到的新染色體；對(duì)變異操作所得結(jié)果進(jìn)行模擬退火操作，根據(jù)Metropolis準(zhǔn)則判斷是否接受變異操作所得到的新染色體；并利用Tl＋1＝αTl對(duì)算法進(jìn)行降溫操作.從而實(shí)現(xiàn)遺傳算法與模擬退火算法的結(jié)合，以達(dá)到尋優(yōu)目的.

2.2 基于模擬退火遺傳算法的GMDH網(wǎng)絡(luò)的建模

GMDH網(wǎng)絡(luò)進(jìn)行預(yù)測(cè)，要根據(jù)樣本，通過(guò)自組織的方法建立網(wǎng)絡(luò)模型.建立GMDH模型需要以下幾個(gè)步驟：

步驟1：數(shù)據(jù)收集并把數(shù)據(jù)分成兩個(gè)子集：訓(xùn)練集和測(cè)試集.在總數(shù)為n的數(shù)據(jù)樣本中取出n1個(gè)樣本作為建摸樣本（n1＜n），GMDH網(wǎng)絡(luò)的輸入數(shù)據(jù)形如［x1，x2，…，xm，Y］，是多輸入變量單輸出變量的結(jié)構(gòu)；

步驟2：構(gòu)建基本單元.將樣本的m個(gè)變量中任取兩個(gè)xi，xj（i，j＝1，2，3，…，m，i≠j），以Y為輸出，用模擬退火遺傳算法辨識(shí)部分描述式（3）中的參數(shù)a，b，c，d，e，f，這樣可以得到m·（m－1）／2個(gè)基本單元，從而產(chǎn)生第1層，構(gòu)成初始的網(wǎng)絡(luò)；

圖2 模擬退火遺傳算法流程圖Fig.2 The flow chart of the SA－GA algorithm

步驟3：建立輸入層.先設(shè)定一個(gè)閾值Eg（Eg的設(shè)置需要一定的先驗(yàn)知識(shí)，在本文中將Eg設(shè)為當(dāng)前所有單元輸出方差的均值，這樣在第一步的處理中就可以將誤差較大的單元剔除），將余下的n2個(gè)樣本（n2＝n－n1）中的相應(yīng)變量分別代入上述處理單元，算出處理單元的輸出與實(shí)際輸出的方差E，將各單元的方差與Eg比較，保留那些方差低于閾值的單元（設(shè)共有u1個(gè)單元），記錄這些單元中的最小方差E1m.這樣就得到了第一層的單元；

步驟4：構(gòu)筑中間層.將全部數(shù)據(jù)中的相應(yīng)變量代入第一層單元進(jìn)行計(jì)算，得到第一層的輸出Y1（u），（u＝1，2，…，u1），將Y1（u）作為第二層的輸入，重復(fù)上述兩步，可以得到第二層的處理單元u2個(gè)，第二層的輸出Y2（u），（u＝1，2，…，u2），以及第二層的最小方差E2m，），如果E2m〈E1m，則第二層構(gòu)筑成功，繼續(xù)進(jìn)行下一層的構(gòu)造；

步驟5：建立輸出層.假設(shè)進(jìn)行到第k＋1層，發(fā)現(xiàn)該層的最小方差Ek＋1m＞Ekm，則終止建模，并將第k層中方差最小的那個(gè)單元作為輸出單元.

最后，將與輸出單元相關(guān)的上層單元逐層連接，這樣，其余的無(wú)關(guān)單元不包含在網(wǎng)絡(luò)結(jié)構(gòu)中，至此，得到了以樣本為基礎(chǔ)的GMDH網(wǎng)絡(luò).將相應(yīng)的測(cè)試樣本輸入網(wǎng)絡(luò)模型，就可以進(jìn)行預(yù)測(cè)了.

3 基于模擬退火遺傳算法的GMDH網(wǎng)絡(luò)模型預(yù)測(cè)泥石流建模實(shí)例

泥石流是復(fù)雜的非線性系統(tǒng)，利用非線性理論對(duì)泥石流預(yù)測(cè)預(yù)報(bào)是可行的［12］.用人工神經(jīng)網(wǎng)絡(luò)的非線性結(jié)構(gòu)來(lái)進(jìn)行建模和預(yù)測(cè)，是解決復(fù)雜的非線性映射問(wèn)題的有效方法.本文將基于模擬退火遺傳算法的GMDH網(wǎng)絡(luò)模型（SAGA－GMDH）用于泥石流的預(yù)測(cè).以泥石流一次最大沖出量（Y）為輸出神經(jīng)元，以流域面積（x1）、流域相對(duì)高差（x2）、補(bǔ)給段長(zhǎng)度比（x3）、河溝縱坡（x4）、植被覆蓋率（x5）、溝岸山坡坡度（x6）、24 h最大降雨量（x7）和人口密度（x8）8個(gè)因子為輸入神經(jīng)元，建立泥石流一次最大沖出量預(yù)測(cè)模型.變量及原始數(shù)據(jù)來(lái)源于文獻(xiàn)［13］.采用文獻(xiàn)［13］中前30組泥石流溝的數(shù)據(jù)作為建模樣本數(shù)據(jù)，用已訓(xùn)練好的模型對(duì)后9組泥石流溝的一次最大沖出量進(jìn)行預(yù)測(cè).

現(xiàn)將GMDH網(wǎng)絡(luò)結(jié)構(gòu)、SAGA－GMDH網(wǎng)絡(luò)結(jié)構(gòu)對(duì)泥石流溝的一次最大沖出量進(jìn)行計(jì)算機(jī)仿真.

測(cè)節(jié)點(diǎn)數(shù)）.通過(guò)計(jì)算機(jī)仿真得到預(yù)測(cè)結(jié)果如圖3、圖4所示.

圖3 SAGA－GMDH預(yù)測(cè)的相對(duì)誤差及泥石流一次最大沖出量Fig.3 The relative error（RE）and results of the SAGA－GMDH model for predicting the BQDR（biggest quantity debris flow rushing out once a time）

圖4 GMDH預(yù)測(cè)泥石流一次最大沖出量Fig.4 Results of the GMDH model for predicting the BQDR

利用SAGA－GMDH網(wǎng)絡(luò)進(jìn)行預(yù)測(cè)，平均相對(duì)誤差為3.54%，相關(guān)系數(shù)為0.912 5.優(yōu)于GMDH網(wǎng)絡(luò)模型的預(yù)測(cè)結(jié)果，其平均相對(duì)誤差為5.61%，相關(guān)系數(shù)為0.820 4.

4 結(jié)束語(yǔ)

針對(duì)遺傳算法全局搜索能力強(qiáng)，但局部搜索能力較差，而模擬退火算法局部搜索能力較強(qiáng)的特點(diǎn)，將模擬退火算法與遺傳算法相結(jié)合應(yīng)用于辨識(shí)GMDH網(wǎng)絡(luò)部分描述式系數(shù)，從而克服了傳統(tǒng)GMDH網(wǎng)絡(luò)建模用最小二乘法辨識(shí)參數(shù)時(shí)常常陷入局部極小導(dǎo)致模型預(yù)測(cè)效果不理想的問(wèn)題.通過(guò)泥石流數(shù)據(jù)仿真試驗(yàn)，證明了本文提出的基于模擬退火遺傳算法的GMDH模型對(duì)泥石流預(yù)測(cè)分析是可行的，而且可以得到較好的預(yù)測(cè)模型.由于GMDH方法具有較大的靈活性，適用于解決復(fù)雜系統(tǒng)的實(shí)際問(wèn)題.

［1］ Ivakhnenko A G，Ivakhnenko G A.The review of problems solvable by algorithms of the group method of data handling［J］.Pattern Recognition and Image Analysis，1995，5（4）：527－535.

［2］ Safikhania H，Hajiloo A，Ranjbar M A.Modeling and multiobjective optimization of cyclone separators using CFD and genetic algorithms［J］.Computers and Chemical Engineering，2011，35：1064－1071.

［3］ 吳耿峰，彭 虎.具有混沌特征的GMDH網(wǎng)絡(luò)在降雨量預(yù)測(cè)中的應(yīng)用［J］.小型微型計(jì)算機(jī)系統(tǒng)，2000，21（2）：135－137.

［4］ Xiao J，He C，Jiang X.Structure identification of Bayesian classifiers based on GMDH［J］.Knowledge－Based Systems，2009，22（6）：461－470.

［5］ Madandoust R，Bungey J H，Ghayidel R.Prediction of the concrete compressive strength by means of core testing using GMDH－type neural network and ANFIS models［J］.Computational Materials Science，2011，51（1）：261－272.

［6］ Heung S H.Fuzzy GMDH－type neural network model and its application to forecasting of mobile communication［J］.Computers ＆Industrial Engineering，2006，50：450－457.

［7］ Hernandez F，Herrera F.Intelligent identification of a fermentative process using modified GMDH algorithm［J］.Revista Iberoamericana De Automatica E Informatica Industrial，2012，9（1）：3－13.

［8］ 陳 洪，陳森發(fā).基于遺傳算法的GMDH網(wǎng)絡(luò)模型及其應(yīng)用［J］.數(shù)據(jù)采集與處理，2009，24（6）：820－824.

［9］ 陳森發(fā).復(fù)雜系統(tǒng)建模理論與方法［M］.南京：東南大學(xué)出版社，2005.

［10］ 劉 勇，康立山，陳毓屏.非數(shù)值并行算法（第二冊(cè)）遺傳算法［M］.北京：科學(xué)出版社，2003.

［11］ 王雪梅，王義和.模擬退火算法與遺傳算法的結(jié)合［J］.計(jì)算機(jī)學(xué)報(bào)，1997，20（4）：381－384.

［12］ 孟凡奇.基于GIS的泥石流預(yù)測(cè)預(yù)報(bào)［D］.長(zhǎng)春：吉林大學(xué)，2011：97－98.

［13］ 金 鑫.鞍山市岫巖縣泥石流危險(xiǎn)性評(píng)價(jià)研究［D］.長(zhǎng)春：吉林大學(xué)，2011：44－46.