基于改進遺傳算法的交通流量小波網(wǎng)絡預測

柴良勇,　殷禮勝,　甘　敏,　魯照權,　談　堃,　張　艷

(合肥工業(yè)大學 電氣與自動化工程學院,安徽 合肥　230009)

?

基于改進遺傳算法的交通流量小波網(wǎng)絡預測

柴良勇,殷禮勝,甘敏,魯照權,談堃,張艷

(合肥工業(yè)大學 電氣與自動化工程學院,安徽 合肥230009)

針對小波網(wǎng)絡結構不易確定和網(wǎng)絡參數(shù)隨機選擇易造成較大預測誤差的問題,文章通過對采集的交通流數(shù)據(jù)進行分析和多次試驗判斷誤差,來確定小波神經(jīng)網(wǎng)絡的結構;提出了一種改良的遺傳算法來初始化神經(jīng)網(wǎng)絡的權值參數(shù),并對種群的進化進行分析;最后將遺傳算法選擇出的最優(yōu)個體解碼成小波網(wǎng)絡的權值和因子,用構建的小波神經(jīng)網(wǎng)絡來預測短時交通流量,得出預測結果。研究結果表明改進遺傳算法優(yōu)化的小波網(wǎng)絡能夠較好地預測輸出,并能夠降低輸出誤差均值。

遺傳算法;小波網(wǎng)絡;交通流量;預測

隨著交通基礎設施建設和智能運輸系統(tǒng)的發(fā)展,交通規(guī)劃和交通誘導成為交通領域研究的熱點。對于交通規(guī)則和交通誘導來說,準確的交通流量是其實現(xiàn)的前提和關鍵。交通流量預測根據(jù)時間跨度可分為長期交通流量預測和短時交通流量預測,其中短時交通流量預測[1-2]是智能運輸系統(tǒng)的核心內(nèi)容,智能運輸系統(tǒng)中多個子系統(tǒng)的功能實現(xiàn)都是以其為基礎的。神經(jīng)網(wǎng)絡[3]是一個具有高度非線性的動力學系統(tǒng),具有非線性擬合能力,因此可以利用神經(jīng)網(wǎng)絡模型對交通流量進行短時預測。本文采用基于小波分析的一種前饋神經(jīng)網(wǎng)絡,即小波網(wǎng)絡[4]。小波網(wǎng)絡具有學習能力強、精度高的特點，也具有較強的逼近能力和容錯能力。然而小波網(wǎng)絡的連接權值、平移因子、伸縮因子一般只通過隨機選取。并且小波神經(jīng)網(wǎng)絡的結構不易確定,特別是中間隱含層數(shù)量的選取。本文通過仿真實驗選定隱含層的輸入,并利用改進的遺傳算法對網(wǎng)絡的權值和因子進行訓練,找到最優(yōu)解。

1　小波網(wǎng)絡結構的確定

1.1小波網(wǎng)絡

小波網(wǎng)絡是一種以BP神經(jīng)網(wǎng)絡為基礎,小波基函數(shù)作為隱含層節(jié)點傳遞函數(shù),信號前向傳播、誤差反向傳播的神經(jīng)網(wǎng)絡,拓撲結構[5]如圖1所示。

圖1　小波網(wǎng)絡拓撲結構

圖1中,X1,X2,…,Xk為小波神經(jīng)網(wǎng)絡的輸入?yún)?shù);Y1,Y2,…,Yk為小波神經(jīng)網(wǎng)絡的預測輸出;ωij和ωjk為小波神經(jīng)網(wǎng)絡權值。在輸入序列信號為xi(i=1,2,…,k)時,隱含層輸出為：

其中,S(j)為隱含層第j個節(jié)點輸出值;ωij為輸入層到隱含層的連接權值;bj為小波基函數(shù)f(j)的平移因子;aj為小波基函數(shù)f(j)的伸縮因子;f(j)為小波基函數(shù)。

本文選擇的小波基函數(shù)統(tǒng)一為Morlet母小波基函數(shù),數(shù)學式為:

網(wǎng)絡輸出層計算公式為:

其中,ωjk為隱含層到輸出層的連接權值;S(j)為隱含層第j個節(jié)點輸出值;l為隱含層節(jié)點數(shù);m為輸出層節(jié)點數(shù)。

1.2小波網(wǎng)絡結構的確定

短時交通流量某時刻的值與本路段前幾個時刻的交通流量相關。可將交通流量的前幾個時刻作為網(wǎng)絡的輸入,將要預測的時刻流量作為網(wǎng)絡的輸出。本文利用文獻[2]中某路段的一周數(shù)據(jù)集合,采集間隔為20 min記錄1次,共記錄了376個時間點數(shù)據(jù)。將前280個交通數(shù)據(jù)用于訓練,剩余96個數(shù)據(jù)用于預測輸出。將280個數(shù)據(jù)依次每4個數(shù)據(jù)為1組,每組的下一時刻數(shù)據(jù)為要預測的流量值。這樣就將這280個數(shù)據(jù)分成了276組輸入和276組輸出。輸入的數(shù)據(jù)為4維的,輸出的為1維的。同理可將剩余96組數(shù)據(jù)分成92組用于測試網(wǎng)絡預測的擬合效果。當然在這里也可選擇輸入的維數(shù)為5或6甚至更高維數(shù)。一般研究表明，在無擁堵的情況下某時刻流量與之前時刻相距越遠關聯(lián)越小，所以在這里選擇維數(shù)為4,即120 min內(nèi)的流量較好。通過數(shù)據(jù)分析可將小波網(wǎng)絡的輸入節(jié)點定為4,輸出節(jié)點定為1。下面討論隱含節(jié)點的確定。

一般情況下,小波網(wǎng)絡的隱含節(jié)點沒有固定的選取辦法,只通過經(jīng)驗確定,不過隱含節(jié)點數(shù)越多,函數(shù)的樣本內(nèi)數(shù)據(jù)擬合效果越好,但是會增加網(wǎng)絡的學習時間,而且在樣本外的預測會變得很差。本文通過多次仿真實驗，根據(jù)預測誤差確定出隱含節(jié)點數(shù),這里的誤差為平均絕對誤差,即

圖2　不同隱含層數(shù)的預測誤差統(tǒng)計結果

通過圖2可以得出,當隱含層數(shù)過少時,預測輸出的誤差可能會產(chǎn)生較大的誤差,當隱含層數(shù)為7時,誤差就達到了較小的程度,考慮到訓練時間以及避免“過度吻合”的現(xiàn)象,這里選擇隱含層節(jié)點數(shù)為7。即小波網(wǎng)絡結構為4-7-1結構。

2　改進的遺傳算法優(yōu)化小波網(wǎng)絡

2.1改進的遺傳算法優(yōu)化小波網(wǎng)絡權值和因子

遺傳算法是一種基于全局選擇的優(yōu)化算法。它通過模擬自然界的優(yōu)勝劣汰的原理,一代代優(yōu)化種群個體,并逐步逼近最優(yōu)解。采用遺傳算法對神經(jīng)網(wǎng)絡進行優(yōu)化,其要素主要包括種群的初始化、設計適應度函數(shù)、選擇、交叉及變異操作等。下面按步驟先后對改進的遺傳算法優(yōu)化網(wǎng)絡進行說明。

2.1.1種群初始化

對于小波神經(jīng)網(wǎng)絡,將網(wǎng)絡的輸入層到隱含層權值ωij、隱含層到輸出層權值ωjk以及伸縮平移因子aj、bj編碼成一組染色體,本文采用實數(shù)編碼,所以該染色體串形式如下:

其中,ω1為輸入層到隱含層各權值;ω2為隱含層到輸出層的各權值。因此染色體的編碼長度為24+6+6+6=42。注意到隱含層的輸出公式中伸縮因子aj為分母,因此不能為零,故在后面的種群進化變異中需要加一個測試函數(shù)來判斷aj是否為0。

2.1.2數(shù)據(jù)預處理

為了加快網(wǎng)絡的訓練速度,對采集到的數(shù)據(jù)進行預處理,由于交通流量原序列變化范圍較大,直接對原始數(shù)據(jù)處理會引起較大的波動,所以對數(shù)據(jù)進行歸一化處理,歸一化的公式如下:

在Matlab中用[inputn,inputs]=mapmin max(input-train)即可實現(xiàn)數(shù)據(jù)歸一化,input-train為訓練樣本數(shù)據(jù)。

2.1.3適應度函數(shù)的選取

用個體作為網(wǎng)絡的初始權值和因子,用訓練樣本訓練小波網(wǎng)絡,然后預測輸出。個體的適應度值即為預測輸出與期望輸出的誤差之和,計算公式如下:

其中,n為網(wǎng)絡輸出節(jié)點數(shù),這里為1;yi為網(wǎng)絡第i個節(jié)點輸出;oi為第i個節(jié)點期望輸出;M為用來預測的樣本組數(shù)。

2.1.4選擇操作

遺傳算法的選擇操作有錦標賽法、輪盤賭法等,輪盤賭法易造成繁殖機會少,提前收斂于局部最優(yōu)解的情況,選擇誤差比較大,有時甚至不能選中適應度高的個體,適應度低的個體反而可能被選中。

最優(yōu)保留法把適應度高的個體直接復制到下一代,不參與交叉和變異,但是這樣會加速進化使其停滯在最優(yōu)解,從而影響全局搜索能力。

對此,有人提出了期望值法[6],本文提出一種變系數(shù)的期望值法,首先計算出個體被選中的期望值,然后根據(jù)個體的期望值大小安排被選擇的次數(shù)。計算公式如下:

按期望值M的整數(shù)部分來安排選中的個數(shù),當所有個體選中完之后,為了保證種群的數(shù)量保持不變,則對M的小數(shù)部分進行排序,按適應度從高到底選擇個體填充種群,使其達到種群要求的數(shù)量。為了保證進化開始時不能將較優(yōu)個體選擇過多,漏掉一些將來可能會成為最優(yōu)解的個體，加入了變量β,進化開始時取β=0.9,隨著進化的進行,同時為了加快收斂速度,β值變大。這里采用3段式,在種群終止代數(shù)的前1/3取β=0.9,中間1/3取β=1.4,后1/3取β=1.8,這樣既能夠加快進化的收斂速度,也能夠避免網(wǎng)絡開始就選擇局部最優(yōu)解并大肆繁殖的弊端。

2.1.5交叉操作

交叉是遺傳算法的核心操作,是產(chǎn)生新的優(yōu)秀個體最主要的手段。交叉能將2個個體中優(yōu)良的性能傳遞給下一代串中,若交叉后性能不良,可通過選擇進行摒棄。

(1) 交叉方式的選擇。多點交叉容易破壞原有基因塊,但可以產(chǎn)生較多的新基因。因此在迭代前期選取多點交叉比較合適。

進化后期優(yōu)良個體較多,宜采用一點交叉,避免破壞優(yōu)良個體。所以在這里采用了3段式的交叉方式:

其中,X、Y為隨機選擇的染色體;posn為隨機選擇的染色體交叉點位置,當進化代數(shù)i≤(1/3)maxgen(i為進化代數(shù),maxgen為進化終止的代數(shù))時,n=1,2,3;當i>(1/3)maxgen且i≤(2/3)maxgen時,n=1,2；當i>(2/3)maxgen時,n=1;其中β為隨機數(shù)。

(2) 交叉概率的選擇。交叉概率決定一次循環(huán)中是否進行交叉操作。交叉概率越大,交叉越頻繁;交叉概率越小,則不能產(chǎn)生新的個體,種群進化嚴重遲緩。一般交叉概率取0.4～0.99之間。

本文采用變交叉概率[7]來決定交叉的操作，公式如下:

其中,Pc0為交叉初始概率;Pstep為交叉概率減少的步長;i為遺傳進化的代數(shù);Pc min為預先設定的最小交叉率。本文取Pc min=0.4,Pc0=0.99,Pstep=0.008。

2.1.6變異操作

變異是對遺傳算法的改進,既能防止遺傳算法收斂到局部最優(yōu)解,也能對交叉中丟失的某種基因進行修復和補充。變異的概率一般取0.000 1～0.1。隨著進化代數(shù)的增加,希望變異的概率越大,這樣能夠加大局部搜索而取得更優(yōu)的個體。與前面的交叉分段操作保持一致,在總進化代數(shù)的前1/3,取變異率Pm=0.001,中間1/3取Pm=0.01,最后部分取Pm=0.1。變異操作如下:

X(pos)=X(pos)+Mu,

2.1.7解碼、計算適應度及跳轉(zhuǎn)

將上述經(jīng)過選擇、交叉、變異之后的種群個體依次解碼成小波網(wǎng)絡的權值和因子,利用解碼后的權值和因子訓練小波網(wǎng)絡,訓練條件滿足之后,運用測試數(shù)據(jù)預測輸出,進而計算出誤差,即計算出個體的適應度大小。挑選出這一代種群中的最佳適應度和平均適應度,記錄在進化軌跡矩陣中。然后判斷是否滿足進化條件,進化條件可以是適應度達到規(guī)定的要求或者進化代數(shù)達到規(guī)定的數(shù)值。條件不滿足時,跳轉(zhuǎn)到2.1.4節(jié),進行新一輪的選擇、交叉、變異。

2.2改進算法優(yōu)化小波網(wǎng)絡分析

通過上述分析，利用改進的遺傳算法優(yōu)化小波網(wǎng)絡的初始權值和因子,在這里將種群的進化代數(shù)設置成100,種群的最佳適應度和平均適應度曲線如圖3所示。

圖3中并不能很直觀地看出改進的效果,于是將改進前后種群進化的平均適應度曲線和最佳適應度曲線放在一起,如圖4所示。

圖3　改進前后種群的進化曲線

圖4　改進前、后平均適應度與最佳適應度的對比

由圖3、圖4可以看出,改進的遺傳算法在種群進化過程中平均適應度比較平緩地降低,相對于未改進前的平均適應度有著更快的收斂速度,在30代時即可達到未改進算法結束時(即100代)的平均適應度，而且進化結束時有著更低的適應度。通過最佳適應度的對比,可發(fā)現(xiàn)種群進化尋優(yōu)的能力大大提高,不到20代即可尋得比未改進算法終止時還優(yōu)的個體。

針對小波網(wǎng)絡參數(shù)的改良[8]和用遺傳算法優(yōu)化神經(jīng)網(wǎng)絡[9],以及用遺傳算法與小波網(wǎng)絡結合[10-11]進行建模擬合非線性系統(tǒng)都有相應的研究,然而相關研究中考慮到遺傳算法收斂速度問題的卻不多,本文將改進后的遺傳算法用來優(yōu)化小波網(wǎng)絡,進化過程、收斂速度均較好。

3　優(yōu)化后的小波網(wǎng)絡預測交通流量

3.1優(yōu)化后的小波網(wǎng)絡用于流量預測

將上面經(jīng)過改進遺傳算法選擇后的最優(yōu)個體解碼成小波神經(jīng)網(wǎng)絡權值ωij、ωjk以及伸縮因子aj和平移因子bj。然后采用梯度下降法修正網(wǎng)絡的權值和小波基函數(shù)的參數(shù)。修正過程如下:

(1) 計算網(wǎng)絡預測誤差。

其中,yo(k)為期望輸出;y(k)為網(wǎng)絡預測輸出。

(2) 根據(jù)誤差修正小波基因子和網(wǎng)絡權值。

其中，調(diào)整變量由誤差決定,公式如下:

取η=0.01。

(3) 判斷算法是否結束,若沒有結束,則繼續(xù)計算誤差調(diào)整權值。

(4) 當權值調(diào)整結束后,利用前面所述的92組測試數(shù)據(jù)的輸入組作為網(wǎng)絡的輸入,進而可在網(wǎng)絡的輸出節(jié)點得到預測的流量輸出。

3.2優(yōu)化后的小波網(wǎng)絡預測流量仿真

經(jīng)過上述分析,可以得到改進后的交通流量預測圖,同時與未改進的交通流量預測圖作對比,結果如圖5所示。

由圖5可以看出，改進和未改進的小波網(wǎng)絡都可跟蹤實際交通流量的趨勢,但是改進后的預測更加貼近實際流量值。在未改進的流量預測中,由于初始權值的隨機性,會造成網(wǎng)絡收斂到局部最優(yōu)解,由圖5a可見，在時間點的后期預測值明顯與真實值相差較大，而且預測在某些點存在較大的誤差,這些都是隨機選擇初始權值和因子而產(chǎn)生的一些不理想的小波預測結果。由圖5b可見,改進后的小波神經(jīng)網(wǎng)絡能夠?qū)⒄`差控制在合理的范圍內(nèi),更好地預測網(wǎng)絡的輸出。

圖5　未改進和遺傳算法改進后小波流量預測

為了說明改進前、后的交通流量誤差情況,再進行一組實驗,將實際流量與預測流量的誤差刻畫在一張圖中,分別為改進前和改進后的誤差。在這里誤差取為預測值與真實值之差。誤差圖如圖6所示。

圖6　改進前、后誤差對比

從圖6可以看出,改進后的預測誤差可以控制在一個較小的范圍內(nèi)波動,而未改進的誤差均值明顯大于改進后網(wǎng)絡預測輸出的誤差。由此可見改進后的小波網(wǎng)絡能夠較好地預測交通流量。此外,進行了50組的仿真實驗預測,將每個時間點的預測絕對誤差求和再平均,得到下面2個數(shù)據(jù)：未改進的總平均絕對誤差為24.54,且在這50組中出現(xiàn)了6次平均誤差大于40的情況；而改進后的預測平均誤差為18.72,且沒有1組誤差大于25。由此可以得出結論,基于改進遺傳算法的小波網(wǎng)絡能更好地預測交通流量。

4　結　論

與傳統(tǒng)預測交通流量相比,神經(jīng)網(wǎng)絡具有更優(yōu)的預測能力,這得益于它自身的特點,它擅長于描述非線性系統(tǒng)以及數(shù)學模型難以表達的復雜系統(tǒng)。關于小波網(wǎng)絡結構的選取,目前還沒有很好的定論,在這里只是經(jīng)過簡單的試湊找出相對合適的隱含層節(jié)點數(shù)。小波網(wǎng)絡連接權值和伸縮平移因子的初始值選擇不當,會導致整個網(wǎng)絡學習不收斂,預測誤差加大。因此本文加入了遺傳算法去初始化網(wǎng)絡的權值和因子,同時對遺傳算法進行了改進,可以加快它收斂到最優(yōu)解的速度,仿真結果表明改進的遺傳算法能夠更快地收斂到最優(yōu)解。采用優(yōu)化的權值因子來構建小波網(wǎng)絡用來預測輸出,能夠更好地跟蹤預測真實值。

[1]高慧，趙建玉,賈磊.短時交通流預測方法綜述[J].濟南大學學報(自然科學版)，2008,22(1):88-94.

[2]YANG L C，JIA L,WANG H.Wavelet network with genetic algorithm and its applications for traffic flow forecasting[C]//Fifth World Congress on Intelligent Control and Automation,Vol 6.IEEE,2004:5330-5333.

[3]劉金錕.智能控制[M].3版.北京:電子工業(yè)出版社,2014:198-224.

[4]DING Y，SHOUSHENG L I U，SHOUSONG H U.Extended wavelet neural network structure and its optimal method[J].Control Theory & Applications,2003:564-570.

[5]史峰,王小川,郁磊,等.MATLAB神經(jīng)網(wǎng)絡30個案例分析[M].北京: 北京航天航空大學出版社，2009:208-217.

[6]許奎.基于改進自適應遺傳算法的配電網(wǎng)重構的研究[D].南寧: 廣西大學，2008.

[7]蒲永紅.改進遺傳算法在無功優(yōu)化中的應用研究[D].濟南:山東大學，2007.

[8]張清華.小波神經(jīng)網(wǎng)絡參數(shù)優(yōu)化及其應用[D].沈陽:東北農(nóng)業(yè)大學，2009.

[9]孫麗娟.基于遺傳算法的小波神經(jīng)網(wǎng)絡短時交通流預測[D].濟南:山東科技大學，2009.

[10]鄒巍,陸百川,鄧捷,等.基于遺傳算法與小波神經(jīng)網(wǎng)絡的客流預測研究[J].武漢理工大學學報:交通科學與工程版，2014,38(5):1148-1151.

[11]李婧瑜,李歧強,侯海燕,等.基于遺傳算法的小波神經(jīng)網(wǎng)絡交通流預測[J].山東大學學報(工學版)，2007,37(2):109-112.

(責任編輯張镅)

Prediction of traffic flow with wavelet network based on improved genetic algorithm

CHAI Liangyong,YIN Lisheng,GAN Min,LU Zhaoquan,TAN Kun,ZHANG Yan

(School of Electric Engineering and Automation, Hefei University of Technology, Hefei 230009, China)

For the problems that hidden layers of the wavelet network are not easy to determine and random selection of network parameters easily causes greater prediction errors, the structure of wavelet neural network is determined through the analysis of traffic data collected and the error determination using the simulation of several tests. Then an improved genetic algorithm is proposed to initialize the neural network weights and thresholds, and to analyze the evolution of the population. Finally, the best individual selected by the genetic algorithm is decoded into the wavelet network connection weights and factor. The short-term traffic flow is predicted by using the wavelet neural network constructed, and the predicted results are gotten. The results show that the wavelet network optimized by the improved genetic algorithm can predict output and reduce the average output error.

genetic algorithm; wavelet network; traffic flow; prediction

2015-03-05

柴良勇(1991-),男,安徽宣城人,合肥工業(yè)大學碩士生;

魯照權(1962-),男,安徽廬江人,博士, 合肥工業(yè)大學教授,碩士生導師.

10.3969/j.issn.1003-5060.2016.07.008

TP202

A

1003-5060(2016)07-0900-06