吳 凡, 孫建紅, 葛鶴銀, 劉景夏
(1. 南京理工大學 電子工程與光電技術學院, 南京 210094;2. 中國人民解放軍理工大學 通信工程學院, 南京 210007)
?
基于GA優(yōu)化IWNN的短時交通流量預測方法
吳 凡1, 孫建紅1, 葛鶴銀1, 劉景夏2
(1. 南京理工大學 電子工程與光電技術學院, 南京 210094;2. 中國人民解放軍理工大學 通信工程學院, 南京 210007)
由于交通流量的非線性、復雜性和不確定性,確定數(shù)學模型的預測方法難以滿足交通管理控制中對預測精度和收斂速度的要求。為了對交通流進行準確、實時、高效的預測,提出將小波理論與神經(jīng)網(wǎng)絡相結合,并改進網(wǎng)絡的訓練過程從而構建改進型小波神經(jīng)網(wǎng)絡;同時運用遺傳算法優(yōu)化網(wǎng)絡的初始權值,最終提高了預測精度,加快了收斂速度,避免陷入局部極小。通過仿真和分析,提出的方法具有較好的預測結果。
交通擁堵; 短時交通流量預測; 改進型小波神經(jīng)網(wǎng)絡; 遺傳算法
近年來,隨著智能交通系統(tǒng)的蓬勃發(fā)展,針對交通擁堵問題的智能交通系統(tǒng)兩大核心子系統(tǒng)交通誘導和交通控制逐漸成為研究的熱門課題。但無論是對于交通誘導還是交通控制系統(tǒng)來說,準確、實時、高效的交通流預測是這些系統(tǒng)實現(xiàn)的前提和關鍵[1-2]。
現(xiàn)階段的短時交通流預測模型一般可分成兩類:一類是以傳統(tǒng)數(shù)學和物理方法為基礎的預測模型(如時間序列模型和卡爾曼濾波模型等);另一類是以現(xiàn)代科學技術和方法(如模擬技術、神經(jīng)網(wǎng)絡、模糊控制等)為主要研究手段而形成的預測模型[3]。第一類方法已經(jīng)難以滿足人們對預測精度越來越高的要求,而第二類方法在一定程度上擺脫了建立精確數(shù)學模型的困擾,開辟了新的思路。
人工神經(jīng)網(wǎng)絡作為一種通用的非線性函數(shù)逼近工具,以其良好的非線性品質、靈活而有效的自組織學習方法在預測領域顯示了極大的優(yōu)勢[4]。傳統(tǒng)的BP神經(jīng)網(wǎng)絡模型存在著收斂速度慢和易陷入局部極小等缺陷。目前不少文獻采用粒子群算法[5]、布谷鳥算法[6]等對BP神經(jīng)網(wǎng)絡參數(shù)進行優(yōu)化,但這些算法沒有改變隱含層的傳遞函數(shù)即神經(jīng)網(wǎng)絡對非線性函數(shù)擬合的基函數(shù)并沒有改變,故預測精度有待進一步提高。目前關于小波理論與神經(jīng)網(wǎng)絡相結合的研究逐漸增多,小波神經(jīng)網(wǎng)絡(Wavelet Neural Network, WNN)作為兩者的結合,繼承了小波變換的優(yōu)點,即對非平穩(wěn)信號具有良好的時頻局部特性和變焦能力,使網(wǎng)絡對非平穩(wěn)信號的逼近能力有了明顯的提高[7-8]。由于小波神經(jīng)網(wǎng)絡的網(wǎng)絡結構和訓練方法沒有改變,所以仍然存在收斂速度慢和易陷入局部極小等缺點。
本文針對收斂速度慢和預測精度較低以及易陷入局部極小等問題,提出改進型小波神經(jīng)網(wǎng)絡(Improved Wavelet Neural Network, IWNN)即在傳統(tǒng)的小波神經(jīng)網(wǎng)絡訓練過程中增加了動量項和自適應學習率,使預測精度得到進一步提高;同時運用遺傳算法(Genetic Algorithm, GA)去優(yōu)化小波神經(jīng)網(wǎng)絡的初始參數(shù),通過遺傳算法的全局搜索能力讓網(wǎng)絡避免陷入局部極小,加快了收斂速度,也為網(wǎng)絡初始參數(shù)的選擇提供了依據(jù),增加了網(wǎng)絡的穩(wěn)定性。
1.1 輸入輸出模型的建立
小波神經(jīng)網(wǎng)絡是以人工神經(jīng)網(wǎng)絡拓撲結構為基礎,將小波基函數(shù)作為神經(jīng)網(wǎng)絡中隱含層節(jié)點的傳遞函數(shù),信號前向傳播的同時、誤差反向傳播的神經(jīng)網(wǎng)絡。小波神經(jīng)網(wǎng)絡的拓補結構如圖1所示。
圖1中,X1,X2,…,Xk是小波神經(jīng)網(wǎng)絡的輸入?yún)?shù);Y1,Y2,…,Ym是小波神經(jīng)網(wǎng)絡的預測輸出;ωij和ωjk為小波神經(jīng)網(wǎng)絡的權值。
當輸入信號序列為xi(i=1,2,…,k)時,隱含層的輸出計算公式如下式所示:
(1)
式中:h(j)為第j個隱含層節(jié)點輸出值;ωij為輸入層和隱含層的連接權值;hj為小波基函數(shù);bj為小波基函數(shù)hj的平移因子;aj為小波基函數(shù)hj的伸縮因子。
本文采用的小波基函數(shù)為Morlet小波函數(shù),如下式所示:
(2)
根據(jù)小波神經(jīng)網(wǎng)絡的拓撲結構可以得出輸出層的計算公式,如下式所示:
(3)
式中:ωjk為隱含層到輸出層的權值;h(j)為第j個隱含層節(jié)點的輸出;l為隱含層節(jié)點數(shù);m為輸出層節(jié)點數(shù)。
綜合式(1)~(3)可以建立從輸入到輸出的映射關系,從而構建了小波神經(jīng)網(wǎng)絡的輸入輸出模型。
1.2 預測的參數(shù)修正
小波神經(jīng)網(wǎng)絡的輸入輸出模型是預測模型的基礎框架,依據(jù)算法和數(shù)據(jù)對模型進行訓練才能使模型具有預測功能。小波神經(jīng)網(wǎng)絡預測模型訓練的關鍵就在于網(wǎng)絡參數(shù)的修正。傳統(tǒng)小波神經(jīng)網(wǎng)絡權值參數(shù)修正算法與BP神經(jīng)網(wǎng)絡的修正算法[9-10]類似,采用的是梯度下降算法,具體步驟如下:
(1) 計算網(wǎng)絡預測誤差:
(4)
式中:yn(k)為實際輸出;y(k)為小波神經(jīng)網(wǎng)絡的預測輸出。
(2) 根據(jù)網(wǎng)絡預測誤差對相應參數(shù)求偏導,從而計算得到小波神經(jīng)網(wǎng)絡參數(shù)的修正值。由于無論是傳統(tǒng)還是改進的算法,對每個參數(shù)修正的方式是相同的,所以本文以ωij的修正方式來代表ωij、ωjk、ak、bk這四個參數(shù)的修正方式:
(5)
式中,η為學習速率。
(3) 依據(jù)計算的修正值修正小波神經(jīng)的網(wǎng)絡權值和小波基函數(shù)的系數(shù):
(6)
式中,i為訓練的次數(shù)。
根據(jù)誤差修正小波神經(jīng)網(wǎng)絡權值和小波基函數(shù)的參數(shù),使網(wǎng)絡預測值逼近期望值,從而實現(xiàn)交通流的短時預測。
2.1 IWNN的參數(shù)修正
由于傳統(tǒng)小波神經(jīng)網(wǎng)絡參數(shù)修正算法采用的是梯度下降算法,而梯度下降法有著收斂速度慢、易陷入振蕩效應和局部極小的缺點[11]。本文針對這些缺點提出引入動量項和自適應學習率來改進小波神經(jīng)網(wǎng)絡的參數(shù)修正方法。修正的公式如下:
(7)
小波神經(jīng)網(wǎng)絡對動量項的學習速率η的取值往往是根據(jù)經(jīng)驗給出的固定值。但在網(wǎng)絡訓練的過程中,訓練開始時效果較好的學習速率不一定適合后面訓練過程。故提出用自適應學習率來替代傳統(tǒng)的固定值學習速率,使學習率能夠依據(jù)訓練誤差的變化來對自己進行動態(tài)調整。常見的自適應學習率算法[13-14]有很多,本文提出的自適應學習率如下式所示:
(8)
式中,e(k)表示第k次訓練時網(wǎng)絡的訓練誤差。
2.2 預測模型
改進型小波神經(jīng)網(wǎng)絡的初始結構仍采用隨機初始化的方式。隨機的初始化方式使網(wǎng)絡的收斂速度、預測精度以及穩(wěn)定性都沒有保證,同時易陷入局部極小值。為了克服這些不足,需要一種全局搜索方式來避免搜索過程收斂于局部最優(yōu)解。
遺傳算法是一種并行隨機搜索最優(yōu)化方法。該算法從許多點開始并行操作,而非局限于一點,因此可以有效地防止搜索過程收斂于局部最優(yōu)解。故本文采用遺傳算法來對網(wǎng)絡的初始結構參數(shù)進行優(yōu)化?;谶z傳算法優(yōu)化改進型小波神經(jīng)網(wǎng)絡的短時交通流預測模型流程圖如圖2所示。
圖2中關于遺傳算法對網(wǎng)絡初始結構優(yōu)化的具體步驟如下:
圖2 基于遺傳算法優(yōu)化改進型小波神經(jīng)網(wǎng)絡的短時交通流預測模型流程圖
(1) 隨機產(chǎn)生n個結構(即產(chǎn)生n個個體),對每個結構進行編碼,每個結構的編碼長度為k×l+l+l+l×m。其中:k為輸入節(jié)點數(shù);l為隱含層節(jié)點數(shù);m為輸出節(jié)點數(shù)。
(2) 將小波神經(jīng)網(wǎng)絡的權值和小波基函數(shù)的參數(shù)按次序編成一個字符串作為問題的解。然后對編碼后的初始群體(即n個個體)進行訓練。
(3) 根據(jù)訓練結果確定每個個體的適應度值。適應度的計算公式如下:
Fitness=1/(1+e)
(9)
式中,e為訓練誤差。
(4) 若遺傳代數(shù)或適應度滿足終止條件,跳至步驟7。
(5) 選擇若干適應度大的個體,直接繼承給下一代。同時用父代適應度最大的個體替代遺傳操作后產(chǎn)生的最差個體。
(6) 對當前一代群體進行交叉和變異等遺傳操作,產(chǎn)生下一代群體,跳至步驟(3)。
(7) 終止循環(huán),得到最佳個體,解碼還原相應值并將此值作為網(wǎng)絡的初始參數(shù)。
3.1 實驗數(shù)據(jù)和網(wǎng)絡結構
城市交通路網(wǎng)中交通路段某時刻的交通流量與本路段前幾個時段的交通流量有關。所以可以根據(jù)實測路段交通流量的歷史數(shù)據(jù)(交通流量的數(shù)據(jù)采集是每15 min一次,24 h不間斷),對該路段的交通流量進行短時交通流預測。由于一共采集了4 d的交通流量數(shù)據(jù)即384個時間點的數(shù)據(jù),所以提出用前3 d共288個交通流量的數(shù)據(jù)來訓練網(wǎng)絡,最后用訓練好的網(wǎng)絡來預測第4 d 96個交通流量數(shù)據(jù)。
為預測路段t+1時刻的交通流量Qt+1,提出將該路段t時刻,t-1時刻,t-2時刻,t-3時刻,t-4時刻,t-5時刻的交通流量作為網(wǎng)絡的輸入節(jié)點,構建6維輸入,1維輸出的網(wǎng)絡。根據(jù)文獻[15]中的公式計算和分析,將隱含層節(jié)點數(shù)定為9。故本文采用的網(wǎng)絡拓撲結構為6-9-1。
3.2 實例仿真結果分析
實驗平臺為CPU2.5GHz,windows8.1,Matlab 2014a的平臺。為方便比較,實驗中BP神經(jīng)網(wǎng)絡,WNN,IWNN,GA 優(yōu)化IWNN均采用6-9-1網(wǎng)絡拓撲結構,并且均進行多次訓練和預測。網(wǎng)絡最大訓練次數(shù)均設為1 000,訓練目標誤差均設為0.05。在遺傳算法中,設定初始種群規(guī)模為40,遺傳代數(shù)為60,交叉概率為0.7,變異概率為0.1。
表1為四種預測模型預測效果對比。本文采用平均相對誤差(MAPE)和迭代次數(shù)(epochs)作為模型預測性能的評價指標,并且每個預測模型均進行多次訓練和預測,取記錄數(shù)據(jù)的平均值作為表中參數(shù)。MAPE的定義如下式所示:
(10)
表1 四種預測模型預測結果的對比
BP神經(jīng)網(wǎng)絡,小波神經(jīng)網(wǎng)絡短時交通流量預測模型的預測值與交通流量實際值的對比曲線圖如圖3所示。
圖3 BP神經(jīng)網(wǎng)絡和小波神經(jīng)網(wǎng)絡預測值與實際值的比較
觀察圖3和表1可以發(fā)現(xiàn),BP神經(jīng)網(wǎng)絡已經(jīng)具有了一定的預測能力。WNN模型的預測值曲線相比較BP神經(jīng)網(wǎng)絡模型而言更加貼合實際值曲線,表1中的數(shù)據(jù)也表明WNN模型的預測精度有著一定的增加。但是圖3中仍然有個別時間點的預測值偏離實際值比較多,這表明預測模型的穩(wěn)定性不高。
IWNN和GA優(yōu)化IWNN預測模型的預測值與實際值的對比曲線圖如圖4所示。
圖4 IWNN和GA優(yōu)化IWNN預測值與實際值的比較
由圖4和表1可知IWNN模型的預測精度相比較BP神經(jīng)網(wǎng)絡和WNN模型有著顯著的提高。同時根據(jù)表1的迭代步數(shù)可知,IWNN預測模型的收斂速度與BP神經(jīng)網(wǎng)絡和WNN模型相比并沒有提升。根據(jù)所記錄的Epochs數(shù)據(jù)可以觀察出IWNN預測模型的收斂過程存在缺陷,為進一步探究IWNN預測模型的缺點,本文將IWNN預測模型訓練過程的隨機10次迭代次數(shù)在圖5中展示并且與GA優(yōu)化IWNN預測模型的隨機10次迭代次數(shù)進行比較。
IWNN和GA優(yōu)化IWNN模型10次訓練的迭代次數(shù)如圖5所示。
圖5 IWNN和GA優(yōu)化IWNN模型訓練迭代次數(shù)的比較
通過圖5可以發(fā)現(xiàn),未經(jīng)GA優(yōu)化的IWNN預測模型的迭代次數(shù)不穩(wěn)定且波動范圍較大,分析該預測模型,發(fā)現(xiàn)造成上述問題的原因是IWNN預測模型的網(wǎng)絡初始結構仍采用隨機初始化的方式。反觀GA優(yōu)化的IWNN預測模型,迭代次數(shù)比較穩(wěn)定且大部分的迭代次數(shù)低于IWNN預測模型。由于預測精度的增加會趨于飽和,根據(jù)表1可以發(fā)現(xiàn)GA優(yōu)化并沒有顯著提高模型的預測精度。但結合圖5和表1的數(shù)據(jù)可以發(fā)現(xiàn)通過GA優(yōu)化可以有效減少訓練的迭代次數(shù)即加快了收斂速度,同時也減小了迭代次數(shù)的波動范圍即提高了預測模型的穩(wěn)定性。
為解決短時交通流預測的難題,本文提出運用小波神經(jīng)網(wǎng)絡作為基礎框架來構建預測模型。針對預測精度不高和收斂速度較慢等缺點提出引入動量項和自適應學習率來改進傳統(tǒng)的小波神經(jīng)網(wǎng)絡,同時運用遺傳算法優(yōu)化改進后的小波神經(jīng)網(wǎng)絡。仿真實驗表明:通過引入動量項和自適應學習率來改進的小波神經(jīng)網(wǎng)絡預測模型在預測精度上有著顯著的提高。遺傳算法的優(yōu)化為網(wǎng)絡初始參數(shù)的選擇提供了可靠的依據(jù),使預測模型在有著良好預測精度的同時也具備穩(wěn)定性高和收斂速度快的優(yōu)點。該預測模型稍加修改還可以應用于其他領域,值得進一步研究與實踐應用。
[1] 賀國光,李 宇,馬壽峰. 基于數(shù)學模型的短時交通流預測方法探討[J]. 系統(tǒng)工程理論與實踐,2000(12):51-56.
[2] 宋 馳,沈國江. 短時交通流預測模型綜述[J]. 自動化博覽,2012(6):84-87.
[3] 劉 靜,關 偉. 交通流預測方法綜述[J]. 公路交通科技,2004(3):82-85.
[4] 董景榮. 基于小波網(wǎng)絡的非線性組合預測方法研究[J]. 系統(tǒng)工程學報,2000(4):383-388.
[5] 李 松,劉力軍,翟 曼. 改進粒子群算法優(yōu)化BP神經(jīng)網(wǎng)絡的短時交通流預測[J]. 系統(tǒng)工程理論與實踐,2012(9):2045-2049.
[6] 賴錦輝,梁 松. 基于ACS優(yōu)化BP神經(jīng)網(wǎng)絡的交通流量短時預測方法[J]. 計算機工程與應用,2014(10):244-248.
[7] Bashir Z, El-Hawary M E. “Short term load forecasting by using wavelet neural networks”[C]∥Proc The IEEE Conference on Electrical and Computer Engineering, Canadian: 2000, 163 - 166.
[8] Sheng-Tun Li, Shu-Ching Chen. Function approximation using robust wavelet neural networks[C]∥Proc The 14fh IEEE International Conference on Tools with Artificial Intelligence, Taiwan, 2002: 483-488.
[9] 胡金濱,唐旭清. 人工神經(jīng)網(wǎng)絡的BP算法及其應用[J]. 信息技術,2004(4):1-4.
[10] 余國強. 基于小波神經(jīng)網(wǎng)絡的短時交通流預測算法的研究[D].廣州:華南理工大學,2012.
[11] 張國彬. 小波神經(jīng)網(wǎng)絡算法的改進與應用[D].福州:福州大學,2006.
[12] 孟維偉. 基于神經(jīng)網(wǎng)絡的交通量預測技術研究[D].南京:南京理工大學,2006.
[13] 于 濤. BP網(wǎng)絡自適應學習率算法分析[D].大連:大連理工大學,2011.
[14] 李浩磊. 基于遺傳算法優(yōu)化小波神經(jīng)網(wǎng)絡的網(wǎng)絡流量預測模型研究[D].西安:西安電子科技大學,2013.
[15] 許 東,吳 錚. 基于MATLAB6.x的系統(tǒng)分析與設計——神經(jīng)網(wǎng)絡.[M]. 2版. 西安:西安電子科技大學出版社,2002.
Short-time Traffic Flow Forecasting Method Based on Improved Wavelet Neural Network Optimized by GA
WUFan1,SUNJian-hong1,GEHe-yin1,LIUJing-xia2
(1. School of Electronic and Optical Engineering, Nanjing University of Science and Technology, Nanjing 210094, China; 2. Institute of Communication Engineering, PLA University of Science and Technology, Nanjing 210007, China)
Traffic flow prediction is a very important research area of intelligent transportation system, and has a very important academic value and practical significance to improve the traffic congestion problems. Traditional prediction methods which used determined mathematical model would not meet the needs of prediction accuracy and convergence speed during the traffic management control because of nonlinear, complexity and uncertainty of traffic flow. In order to forecast traffic flow accurately, real-timely and efficiently, a new algorithm is proposed by combining wavelet theory and neural network, and constructing an IWNN(improved wavelet neural network) with improved network training methods. At the same time, the initial weights are optimized by GA(genetic algorithm). It can improve prediction accuracy, speed up the convergence speed and avoid entering local minima. The simulation results show that it can get better prediction results.
traffic congestion; short-time traffic flow forecasting; IWNN; GA
2015-05-06
江蘇省產(chǎn)學研聯(lián)合創(chuàng)新基金(BY2014004)
吳 凡(1992-),男,江西九江人,碩士生,主要研究方向為嵌入式系統(tǒng)。Tel.:15250980510; E-mail: njustwufan@163.com
孫建紅(1966-),女,江蘇張家港人,副教授,主要從事電路與系統(tǒng)的研究與教學。
Tel.:025-84303086; E-mail: sunjh@njust.edu.cn
TP 391.9
A
1006-7167(2016)05-0134-04