改進GA優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的短時交通流預(yù)測

程浩(1979-),男,安徽桐城人,博士,合肥工業(yè)大學(xué)講師.

改進GA優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的短時交通流預(yù)測

盧建中,程浩

(合肥工業(yè)大學(xué) 管理學(xué)院,安徽 合肥230009)

摘要:為了提高BP 神經(jīng)網(wǎng)絡(luò)預(yù)測模型對短時交通流的預(yù)測準確性,文章提出了一種基于改進遺傳算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的短時交通流預(yù)測方法。由于模擬退火算法具有較強的局部搜索能力,能夠在搜索過程中避免陷入局部最優(yōu)解,因此引入模擬退火算法中的Metropolis接受準則來增加遺傳算法的局部搜索能力,避免了遺傳算法過早收斂和陷入局部最優(yōu)解。通過改進的遺傳算法優(yōu)化BP 神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值,然后訓(xùn)練BP 神經(jīng)網(wǎng)絡(luò)預(yù)測模型以求得最優(yōu)解。仿真結(jié)果表明,該方法對短時交通流預(yù)測具有較好的預(yù)測精確性。

關(guān)鍵詞:交通流預(yù)測;BP神經(jīng)網(wǎng)絡(luò);遺傳算法;模擬退火算法;Metropolis接受準則

Short-termtrafficflowforecastbasedon

modifiedGAoptimizedBPneuralnetwork

LUJian-zhong,CHENGHao

(SchoolofManagement,HefeiUniversityofTechnology,Hefei230009,China)

Abstract:In order to improve the accuracy of short-term traffic flow forecast based on BP neural network prediction model, a forecast method based on modified genetic algorithm(GA) optimized BP neural network is proposed. Because the simulated annealing(SA) algorithm has strong local searching capability and can avoid getting into limited optimum solution in the searching process, the Metropolis acceptance criteria in the SA algorithm is introduced to GA, which effectively overcomes premature convergence and getting into limited optimum solution. The modified genetic algorithm is used to optimize BP neural network’s weights and thresholds, then the BP neural network model is trained to obtain the optimal solution. The simulation results show that this method is accurate in short-term traffic flow forecast.

Keywords:trafficflowforecast;BPneuralnetwork;geneticalgorithm(GA);simulatedannealing(SA)algorithm;Metropolisacceptancecriteria

物聯(lián)網(wǎng)被認為是繼計算機、互聯(lián)網(wǎng)與移動通信之后的世界信息產(chǎn)業(yè)的又一次浪潮,而車聯(lián)網(wǎng)是物聯(lián)網(wǎng)應(yīng)用于智能交通領(lǐng)域的集中體現(xiàn),也是物聯(lián)網(wǎng)的一個重點領(lǐng)域。車聯(lián)網(wǎng)可以實現(xiàn)車與人之間、車與車之間、車與基礎(chǔ)設(shè)施之間信息通訊的交換,但是組建車聯(lián)網(wǎng)過程中還有一些關(guān)鍵的技術(shù)問題需要研究,如RFID技術(shù)、車聯(lián)網(wǎng)新協(xié)議研發(fā)、智能交通等。其中智能交通是國內(nèi)外學(xué)者研究的熱點,而實時準確的交通流預(yù)測是智能交通的前提和關(guān)鍵。

根據(jù)交通流預(yù)測的時間可以將交通流劃分為短時交通流、中期和長期交通流,而短時交通流預(yù)測的實時性最強、反映最為快捷,因此實際應(yīng)用也最為廣泛。國內(nèi)外學(xué)者針對短時交通流預(yù)測建立了各種模型,如BP神經(jīng)網(wǎng)絡(luò)模型[1]、小波理論模型[2]以及混沌理論模型[3-4]等。其中BP神經(jīng)網(wǎng)絡(luò)模型是目前廣泛應(yīng)用的預(yù)測模型,但是該模型存在易陷入局部極小值、收斂速度慢等缺點,文獻[5]利用遺傳算法(GA)優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)克服了這些缺點,但是遺傳算法存在過早收斂和局部收斂性差的問題。

為了克服上述缺點,本文采用改進的遺傳算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)預(yù)測模型——MGABP模型,該算法利用GA優(yōu)化BP神經(jīng)網(wǎng)絡(luò)中的初始權(quán)值和閾值,利用模擬退火算法(SA)[6-7]中Metropolis接受準則對GA新適應(yīng)度和上次迭代適應(yīng)度進行比較,更有效地找出最優(yōu)適應(yīng)度,從而克服了上述遺傳算法的缺點。實驗結(jié)果證明了本文提出的MGABP模型不僅改善了BP神經(jīng)網(wǎng)絡(luò)收斂速度慢等缺點,而且對遺傳算法的過早收斂和局部收斂性差進行了優(yōu)化。

1算法基本原理

1.1　遺傳算法

遺傳算法(geneticalgorithm,GA)[8]是一種借鑒自然界中適者生存、優(yōu)勝劣汰的進化機制演化而來的高度并行、隨機、自適應(yīng)搜索算法,它目前已被人們廣泛地應(yīng)用于組合優(yōu)化、機器學(xué)習(xí)、信號處理、自適應(yīng)控制和人工生命等領(lǐng)域,它是現(xiàn)代智能計算中的關(guān)鍵技術(shù)。在遺傳算法計算中,首先對所優(yōu)化參數(shù)進行編碼,隨機產(chǎn)生n個初始種群,然后根據(jù)種群擇優(yōu)目標方向確定種群的適應(yīng)度函數(shù)。通過對種群的選擇運算、交叉運算、變異運算后,最終得到遺傳算法的解。

1.2　 BP神經(jīng)網(wǎng)絡(luò)算法

BP神經(jīng)網(wǎng)絡(luò)算法[9]由信號的正向傳播和誤差的反向傳播2個部分組成。正向傳播是樣本從輸入層傳入,到達隱含層處理再傳向輸出層;如果輸出與期望的輸出有偏差,則將偏差沿著網(wǎng)絡(luò)反向傳播,逐層修改權(quán)值和閾值,來達到預(yù)測目標。

設(shè)Xi=(x1,x2,…,xn)(i=1,2,…,n)為系統(tǒng)輸入,輸出為Yi=xi+1,選擇典型的BP神經(jīng)網(wǎng)絡(luò)3層設(shè)計,取BP神經(jīng)網(wǎng)絡(luò)輸入層個數(shù)為n、隱含層個數(shù)為p、輸出層個數(shù)為1,轉(zhuǎn)移函數(shù)采用Sigmoid函數(shù),則隱含層各個節(jié)點的輸入與輸出為：

(1)

(2)

其中,ωij為連接輸入層與隱含層的權(quán)值;θj為隱含層節(jié)點的閾值。

同理,輸出層的節(jié)點輸入和輸出分別為:

(3)

(4)

其中,vj為連接隱含層與輸出層的權(quán)值;γ為輸出層的閾值;bj為隱含層節(jié)點的輸出。因此輸出yi是可以預(yù)測的。

1.3　交通流

交通流[10]是指在單位時間內(nèi)通過道路某一地點、某一斷面或者某一車道的實際車輛數(shù),而交通流預(yù)測是指利用已有的交通流的歷史數(shù)據(jù),通過某種方法對將來某時間內(nèi)的交通流進行預(yù)測的技術(shù)。其中短時交通流預(yù)測是在時間跨度不超過15min,在此時刻t對下一決策時刻t+1乃至以后若干時刻t+n的交通流做出實時精準的預(yù)測。

2理論分析與改進

2.1　傳統(tǒng) GA缺陷原因分析

過早收斂和局部收斂性差的原因可以歸結(jié)如下[11]:

(1) 選擇壓力。采用排序選擇或者競賽選擇模式,當前群體的最優(yōu)個體期望抽樣比較大時,個體選擇壓力太大,導(dǎo)致群體的多樣性迅速減低;反之,則個體選擇壓力太小,模式競賽減弱,遺傳算子重組生成高階模式的能力降低,也會出現(xiàn)進化停滯現(xiàn)象。

(2) 變異概率。當變異概率比較小時,群體多樣性下降太快,容易導(dǎo)致有效基因迅速丟失且難以恢復(fù);反之,盡管群體多樣性可以保持在較高水平,但是高階模式被破壞的概率也隨之增大。

(3) 適應(yīng)函數(shù)性質(zhì)。當適應(yīng)度函數(shù)高度非線性,染色體基因位之間高度相關(guān),有效模板更容易被破壞;或者最優(yōu)解附近為非常平緩的超平面,高階競爭模式適應(yīng)值的差異非常小,在適應(yīng)值比例選擇方式下的模式競爭激烈,導(dǎo)致當前最佳個體適應(yīng)值的改進出現(xiàn)停滯。

(4) 群體初始化。初始群體分布在編碼空間的局部區(qū)域,導(dǎo)致GA的搜索范圍受到限制。

2.2　對 GA缺陷問題的改進

針對上述分析可以看出，遺傳算法是把握搜索過程的總體能力,但是在遺傳的迭代過程中容易錯過最優(yōu)解,導(dǎo)致局部空間搜索能力較弱,從而收斂到全局最優(yōu)解能力較弱,在優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的過程中存在著過早收斂和局部收斂性差的問題,而模擬退火算法正好克服了這些缺點。

本文借鑒了模擬退火算法(simulatedannealing,SA)思想。SA是在金屬加工工藝中,金屬材料加熱到某一高溫狀態(tài),然后慢慢冷卻下來的金屬熱處理過程?；谶@一機理建立起來了一種局部最優(yōu)化方法,能夠以隨機搜索技術(shù)從概率意義上找出目標函數(shù)的全局最優(yōu)解。它開始從某個初始解出發(fā),經(jīng)過大量解的變換后,可以求得給定控制參數(shù)值時組合優(yōu)化問題的相對最優(yōu)解;然后減小控制參數(shù)t的值,重復(fù)執(zhí)行Metropolis算法,就可以在控制參數(shù)t趨于0時,最終求得組合優(yōu)化問題的整體最優(yōu)解。

由此可以看出模擬退火算法具有較強的局部搜索能力,能夠在搜索過程中避免陷入局部最優(yōu)解。利用SA的這一特性來優(yōu)化GA,在GA的選擇、交叉、變異產(chǎn)生新的適應(yīng)度后,利用SA中的Metropolis接受準則對GA新適應(yīng)度和上次迭代適應(yīng)度進行判斷,從而選擇最優(yōu)的適應(yīng)度,因此有效地抑制遺傳算法過早收斂,提高算法局部尋優(yōu)的精確性。GA缺陷改進流程圖如圖1所示。

圖1　 GA缺陷改進流程圖

2.3　 MGABP建模

算法基本步驟如下:

(1) 初始化參數(shù)。包括神經(jīng)網(wǎng)絡(luò)訓(xùn)練數(shù)據(jù)歸一化、各個網(wǎng)絡(luò)層節(jié)點數(shù);遺傳算法種群規(guī)模、迭代次數(shù)、編碼長度計算;模擬退火算法初始溫度、溫度降低參數(shù)以及模擬退火次數(shù)初始化。

(2) 創(chuàng)建BP神經(jīng)網(wǎng)絡(luò),將歸一化后的訓(xùn)練數(shù)據(jù)給神經(jīng)網(wǎng)絡(luò)的輸入層,然后得到神經(jīng)網(wǎng)絡(luò)初始網(wǎng)絡(luò)的權(quán)值和閾值作為改進遺傳算法的初始種群。假設(shè)生成P個個體的初始種群M=(M1,M2,…,MP)T, 為了得到高精度權(quán)值和閾值,采用實數(shù)編碼方式,編碼長度為:

(5)

其中,R、S1、S2分別為BP神經(jīng)網(wǎng)絡(luò)輸入層節(jié)點數(shù)、隱含層節(jié)點數(shù)、輸出層節(jié)點數(shù)。

(3) 確定個體的適應(yīng)度函數(shù)。適應(yīng)度函數(shù)的選擇是通過BP神經(jīng)網(wǎng)絡(luò)對數(shù)據(jù)進行訓(xùn)練,以其預(yù)測值與實際值差的倒數(shù),即預(yù)測值的誤差倒數(shù)作為改進遺傳算法的適應(yīng)度。

(6)

其中,yi為BP神經(jīng)網(wǎng)絡(luò)第i節(jié)點實際輸出;oi為BP神經(jīng)網(wǎng)絡(luò)第i節(jié)點預(yù)測輸出;a為(0,1)之間的任意值。

(4) 采用輪盤賭法選擇算子,即基于適應(yīng)度比例的選擇策略對每一代種群中的染色體進行選擇。選擇概率為:

(7)

(5) 由于個體采用實數(shù)編碼,交叉操作方法采用實數(shù)交叉法。第k個染色體ak和第l個染色體al在第j位的交叉操作方法如下:

(8)

其中,b為[0,1]間的隨機數(shù)。

(6) 變異操作。選取第i個個體的第j個基因aij進行變異操作,即

(9)

(10)

其中,amax、amin分別為基因aij的最大值和最小值;r為[0,1]之間的隨機數(shù);r1為隨機數(shù);g為當前迭代次數(shù);Gmax為最大進化代數(shù)。

(11)

其中,Δf為新的適應(yīng)度減去上一次迭代適應(yīng)度的差;T為模擬退火初始溫度參數(shù)。

(8) 將改進GA得到的最優(yōu)個體,即BP神經(jīng)網(wǎng)絡(luò)輸入層到隱含層的權(quán)值和閾值, 通過BP神經(jīng)網(wǎng)絡(luò)進行訓(xùn)練,訓(xùn)練過的網(wǎng)絡(luò)再輸入一組預(yù)測輸入數(shù)據(jù),通過網(wǎng)絡(luò)得到最終預(yù)測輸出值,即短時交通流量的預(yù)測值。

3仿真實驗及結(jié)果

3.1　仿真條件

為了驗證本文算法的有效性,在Matlab2012a環(huán)境下,采用Matlab語言編寫算法程序,并且利用Matlab神經(jīng)網(wǎng)絡(luò)工具箱建立如下3種預(yù)測模型:BP神經(jīng)網(wǎng)絡(luò)短時交通流預(yù)測(BP)、遺傳算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)短時交通流預(yù)測(GABP)、改進遺傳算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)短時交通流預(yù)測(MGABP)。實驗分別采用這3種模型對同一路段的交通流量數(shù)據(jù)進行預(yù)測對比。首先在實驗中對交通流預(yù)測數(shù)據(jù)進行歸一化處理,且處理到[0,1]之間,即

(12)

其中,xmin、xmax為歸一化前數(shù)據(jù)的最小值和最大值;xi為歸一化前訓(xùn)練數(shù)據(jù);yi為歸一化后數(shù)據(jù)。

實驗誤差評價采用絕對誤差E、平均絕對誤差MAE、均方誤差MSE、平均相對誤差MRE,計算公式如下:

(13)

(14)

(15)

(16)

其中,n為交通流數(shù)據(jù)個數(shù);xk為交通流量真實值;xk′為交通流量預(yù)測值。

實驗采用3層BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu),BP神經(jīng)網(wǎng)絡(luò)參數(shù)設(shè)定如下:訓(xùn)練次數(shù)為100,訓(xùn)練目標為0.000 1,學(xué)習(xí)率為0.1。遺傳算法參數(shù)設(shè)定為:迭代次數(shù)100,種群規(guī)模30。模擬退火算法參數(shù)設(shè)定:初始溫度為100,溫度降低參數(shù)為0.98,模擬退火次數(shù)初始為1。

3.2　實測交通流量數(shù)據(jù)的實證分析

仿真實驗數(shù)據(jù)引用文獻[12],在這些數(shù)據(jù)中,前10組數(shù)據(jù)的前15行數(shù)據(jù)為訓(xùn)練輸入數(shù)據(jù),前10組數(shù)據(jù)中最后1行數(shù)據(jù)為訓(xùn)練輸出數(shù)據(jù)。預(yù)測輸入數(shù)據(jù)為后8組數(shù)據(jù)中的前15行數(shù)據(jù),后8組數(shù)據(jù)最后1行數(shù)據(jù)為真實輸出數(shù)據(jù)。BP、GABP、MGABP神經(jīng)網(wǎng)絡(luò)模型預(yù)測結(jié)果如圖2～圖4所示。

實驗誤差結(jié)果見表1所列。

圖2　 BP神經(jīng)網(wǎng)絡(luò)模型預(yù)測

圖3　 GABP神經(jīng)網(wǎng)絡(luò)模型預(yù)測

圖4　 MGABP神經(jīng)網(wǎng)絡(luò)模型預(yù)測

從表1中可以看出,在訓(xùn)練樣本是150和預(yù)測樣本為8時,從MAE(平均絕對誤差)、MSE(均方誤差)和MRE(平均相對誤差)可以看出,MGABP模型的數(shù)值明顯小于GABP模型和BP模型,說明MGABP預(yù)測模型對實測交通流的預(yù)測效果較好。

表1　實驗誤差

4結(jié)束語

本文針對BP神經(jīng)網(wǎng)絡(luò)預(yù)測易陷入局部極小值和收斂速度慢的缺點,在GA算法中引入了模擬退火算法中Metropolis接受準則進行判斷,提出了改進GA的優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的短時交通流預(yù)測方法,可用于車聯(lián)網(wǎng)交通數(shù)據(jù)的預(yù)測。通過該方法和BP神經(jīng)網(wǎng)絡(luò)、GABP神經(jīng)網(wǎng)絡(luò)的誤差對比分析發(fā)現(xiàn),MGABP模型提高了收斂速度,克服了陷入局部極小值,達到了很好的預(yù)測精度。

[參考文獻]

關(guān)鍵詞[1]白曉雷，黃廣君，段建輝.一種基于BP神經(jīng)網(wǎng)絡(luò)的抽取方法[J].合肥工業(yè)大學(xué)學(xué)報：自然科學(xué)版，2014，37(7)：808-811,896.

收稿日期：2014-01-03；修回日期：2014-08-10

基金項目：國家自然科學(xué)基金重點資助項目(71231004)

作者簡介：盧建中(1986-),男,安徽廬江人,合肥工業(yè)大學(xué)碩士生;

doi:10.3969/j.issn.1003-5060.2015.01.027

中圖分類號:TP183;U491文獻標識碼：A

[2]賀國光,李宇,馬壽峰.基于小波分解與重構(gòu)的交通流短時預(yù)測法[J].系統(tǒng)工程理論與實踐,2002(9):101-106.

[3]董春嬌,邵春福,李娟,等. 基于混沌分析的道路網(wǎng)交通流短時預(yù)測[J].系統(tǒng)工程學(xué)報,2001,26(3):340-345.

[4]盧宇,賀國光.一種新的交通流混沌實時判定方法[J].系統(tǒng)工程理論方法應(yīng)用,2006,15(5):445-450.

[5]李松,劉力軍,解永樂.遺傳算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的短時交通流混沌預(yù)測[J].控制與決策,2011,26(10):1581-1585.

[6]康立山,謝云,尤矢勇,等.非數(shù)值并行算法(第一冊):模擬退火算法[M].北京: 科學(xué)出版社, 2003:1-38.

[7]任傳祥,張海,范躍祖.混合遺傳-模擬退火算法在公交智能調(diào)度中的應(yīng)用[J].系統(tǒng)仿真學(xué)報,2005,17(9):2075-2081.

[8]席裕庚,柴天佑,惲為民.遺傳算法綜述[J].控制理論與應(yīng)用,1996,13(6):697-708.

[9]李松,劉力軍, 翟曼.改進粒子群算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的短時交通流預(yù)測[J].系統(tǒng)工程理論與實踐,2012,32(9):2045-2049.

[10]SmithBL,DemetskyMJ.Trafficflowforecasting:comparisonofmodelingapproaches[J].JournalofTransportationEngineering,1997,123(4),261-266.

[11]李敏強,寇紀淞,林丹,等.遺傳算法的基本理論與應(yīng)用[M].北京:科學(xué)出版社,2002:163-208.

[12]李波.基于小波和遺傳神經(jīng)網(wǎng)絡(luò)的短時城市交通流量預(yù)測研究[D].北京:北京交通大學(xué),2012.

(責任編輯張镅)