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

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

盧建中,程浩

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

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

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

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

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

為了克服上述缺點(diǎn),本文采用改進(jìn)的遺傳算法優(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接受準(zhǔn)則對(duì)GA新適應(yīng)度和上次迭代適應(yīng)度進(jìn)行比較,更有效地找出最優(yōu)適應(yīng)度,從而克服了上述遺傳算法的缺點(diǎn)。實(shí)驗(yàn)結(jié)果證明了本文提出的MGABP模型不僅改善了BP神經(jīng)網(wǎng)絡(luò)收斂速度慢等缺點(diǎn),而且對(duì)遺傳算法的過早收斂和局部收斂性差進(jìn)行了優(yōu)化。

1算法基本原理

1.1　遺傳算法

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

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

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

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

(1)

(2)

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

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

(3)

(4)

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

1.3　交通流

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

2理論分析與改進(jìn)

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

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

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

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

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

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

2.2　對(duì) GA缺陷問題的改進(jìn)

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

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

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

圖1　 GA缺陷改進(jìn)流程圖

2.3　 MGABP建模

算法基本步驟如下:

(1) 初始化參數(shù)。包括神經(jīng)網(wǎng)絡(luò)訓(xùn)練數(shù)據(jù)歸一化、各個(gè)網(wǎng)絡(luò)層節(jié)點(diǎn)數(shù);遺傳算法種群規(guī)模、迭代次數(shù)、編碼長度計(jì)算;模擬退火算法初始溫度、溫度降低參數(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)值和閾值作為改進(jìn)遺傳算法的初始種群。假設(shè)生成P個(gè)個(gè)體的初始種群M=(M1,M2,…,MP)T, 為了得到高精度權(quán)值和閾值,采用實(shí)數(shù)編碼方式,編碼長度為:

(5)

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

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

(6)

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

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

(7)

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

(8)

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

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

(9)

(10)

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

(11)

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

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

3仿真實(shí)驗(yàn)及結(jié)果

3.1　仿真條件

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

(12)

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

實(shí)驗(yàn)誤差評(píng)價(jià)采用絕對(duì)誤差E、平均絕對(duì)誤差MAE、均方誤差MSE、平均相對(duì)誤差MRE,計(jì)算公式如下:

(13)

(14)

(15)

(16)

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

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

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

仿真實(shí)驗(yàn)數(shù)據(jù)引用文獻(xiàn)[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í)輸出數(shù)據(jù)。BP、GABP、MGABP神經(jīng)網(wǎng)絡(luò)模型預(yù)測結(jié)果如圖2～圖4所示。

實(shí)驗(yàn)誤差結(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時(shí),從MAE(平均絕對(duì)誤差)、MSE(均方誤差)和MRE(平均相對(duì)誤差)可以看出,MGABP模型的數(shù)值明顯小于GABP模型和BP模型,說明MGABP預(yù)測模型對(duì)實(shí)測交通流的預(yù)測效果較好。

表1　實(shí)驗(yàn)誤差

4結(jié)束語

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

[參考文獻(xiàn)]

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

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

基金項(xiàng)目：國家自然科學(xué)基金重點(diǎn)資助項(xiàng)目(71231004)

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

doi:10.3969/j.issn.1003-5060.2015.01.027

中圖分類號(hào):TP183;U491文獻(xiàn)標(biāo)識(shí)碼：A

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

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

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

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

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

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

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

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

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

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

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

(責(zé)任編輯張镅)