基于啟發(fā)式算法的短時(shí)交通流量預(yù)測(cè)研究

周小敏

摘要：針對(duì)初始參數(shù)的有效性直接影響B(tài)P神經(jīng)網(wǎng)絡(luò)對(duì)短時(shí)交通流量預(yù)測(cè)的準(zhǔn)確性這一問題，該文提出了基于CS（Cuckoo Search）算法與BP（Back Propagation）神經(jīng)網(wǎng)絡(luò)相結(jié)合的啟發(fā)式算法來(lái)進(jìn)行短時(shí)交通流量預(yù)測(cè)。該算法首先用相空間重構(gòu)理論對(duì)訓(xùn)練序列進(jìn)行重構(gòu)，接著把重構(gòu)后的序列作為BP神經(jīng)網(wǎng)絡(luò)的輸入序列，同時(shí)采用CS算法來(lái)進(jìn)行BP神經(jīng)網(wǎng)絡(luò)的最優(yōu)閥值與初始連接權(quán)值的尋找，最后就得到了所需要的預(yù)測(cè)模型。仿真表明，本文所提算法在短時(shí)間內(nèi)能夠準(zhǔn)確地預(yù)測(cè)交通流量的變化趨勢(shì)，從而大大增加了所預(yù)測(cè)流量的可信度。

關(guān)鍵詞：BP神經(jīng)網(wǎng)絡(luò)；短時(shí)交通流量；CS算法

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2014）23-5513-03

1 概述

隨著城市人口不斷增加，我國(guó)城市道路的建設(shè)進(jìn)度難以跟上車輛數(shù)目的增長(zhǎng)速度，從而使得交通擁堵問題日益嚴(yán)重，因此在現(xiàn)有道路條件下，如何對(duì)交通的進(jìn)行高效的管理與調(diào)度以提升道路的通行能力，從而最大限度地緩解交通擁堵問題成為了一個(gè)十分重要的研究課題。而ITS（Intelligent Transport System，智能交通系統(tǒng)）[1]是目前最有效的解決辦法之一。ITS把網(wǎng)絡(luò)技術(shù)、信息技術(shù)、控制技術(shù)等先進(jìn)的現(xiàn)代化技術(shù)運(yùn)用到交通管理中，從而構(gòu)建了一個(gè)覆蓋全城的、全方位的、準(zhǔn)確、實(shí)時(shí)、高效的智能系統(tǒng)。其中的交通流量預(yù)測(cè)是ITS的一項(xiàng)重要功能。這是因?yàn)镮TS是根據(jù)未來(lái)的交通流量來(lái)制定相應(yīng)的交通管理策略。因此，預(yù)測(cè)的準(zhǔn)確性直接關(guān)系到交通管理測(cè)率的有效性。而短時(shí)交通流量預(yù)測(cè)為流量預(yù)測(cè)的重要組成部分。

經(jīng)過(guò)多年的研究，人們?cè)诙虝r(shí)交通流量預(yù)測(cè)方面取得了豐碩的成果，提出許多的預(yù)測(cè)算法[2]。根據(jù)算法的理論依據(jù)，這些預(yù)測(cè)算法可以分成基于確定理論的預(yù)測(cè)算法與基于混沌理論的預(yù)測(cè)算法。常用的基于確定理論的預(yù)測(cè)算法有：Kalman濾波法、時(shí)間序列法、線性回歸法等。這些算法都假設(shè)交通流量的變化是一個(gè)線性過(guò)程，但是在實(shí)際生活中，交通流量的變化是一個(gè)非線性時(shí)變的過(guò)程，因此這些基于確定理論的預(yù)測(cè)算法的預(yù)測(cè)準(zhǔn)確度并不理想，其所得到的預(yù)測(cè)結(jié)果與實(shí)際情況相差會(huì)比較大，從而影響了交通管理策略的制定與調(diào)整。而常用的基于混沌理論的預(yù)測(cè)算法有：基于神經(jīng)網(wǎng)絡(luò)的預(yù)測(cè)法、基于遺傳算法的預(yù)測(cè)法、基于向量機(jī)的預(yù)測(cè)法等。這些算法能夠?qū)Ψ蔷€性環(huán)境進(jìn)行預(yù)測(cè)，從而能取得較高的預(yù)測(cè)精度。而該類算法的工作流程通常分為三個(gè)步驟：相空間的重構(gòu)、預(yù)測(cè)算法的選擇和參數(shù)優(yōu)化、預(yù)測(cè)模型的生成。對(duì)訓(xùn)練序列進(jìn)行相空間重構(gòu)的目的是為了發(fā)掘訓(xùn)練序列背后所隱藏的內(nèi)在規(guī)律。而預(yù)測(cè)算法是用來(lái)對(duì)從訓(xùn)練數(shù)據(jù)中提取預(yù)測(cè)模型，從而用于對(duì)未來(lái)進(jìn)行預(yù)測(cè)。由于基于BP神經(jīng)網(wǎng)絡(luò)的短時(shí)交通流量預(yù)測(cè)算法能夠?qū)崿F(xiàn)自我學(xué)習(xí)并且具備預(yù)測(cè)可行度高等優(yōu)點(diǎn)，因此本文選擇該算法作為預(yù)測(cè)算法。但是，BP神經(jīng)網(wǎng)絡(luò)的閥值與初始連接權(quán)值直接影響該算法的預(yù)測(cè)可信度，如果參數(shù)設(shè)置不合理，該算法的收斂速度不僅會(huì)變慢而且所得到的預(yù)測(cè)模型也可能只是局部最優(yōu)。針對(duì)這個(gè)問題，蟻群算法、遺傳算法、退火算法等分別被用于BP神經(jīng)網(wǎng)路的參數(shù)優(yōu)化。但是，參數(shù)經(jīng)過(guò)優(yōu)化后的BP神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)可行度還有有待提升。

而智能啟發(fā)算法CS算法通過(guò)利用鳥類的飛行搜索原理，使得群體內(nèi)的信息交流增多，從而實(shí)現(xiàn)了較快的收斂速度，這為參數(shù)優(yōu)化問題提供了新的研究思路。在本文中，為了提高預(yù)測(cè)的可行度與精度，提出了基于CS（Cuckoo Search）算法與BP（Back Propagation）神經(jīng)網(wǎng)絡(luò)相結(jié)合的啟發(fā)式算法（簡(jiǎn)稱CS-BP算法）來(lái)進(jìn)行短時(shí)交通流量的預(yù)測(cè)。

2 相關(guān)理論介紹

2.1 相空間重構(gòu)

其中，[γ]與[vj]分別為該層的閥值和從隱層到輸出層的連接權(quán)值。

在基于BP神經(jīng)網(wǎng)絡(luò)[4]的預(yù)測(cè)算法中，連接權(quán)值與閥值是隨機(jī)產(chǎn)生的，從而會(huì)造成收斂速度以及預(yù)測(cè)結(jié)果都不是很理想，因此，采用CS算法對(duì)連接權(quán)值與閥值進(jìn)行優(yōu)化，從而提升BP神經(jīng)網(wǎng)絡(luò)的收斂速度與預(yù)測(cè)可行度。

2.3 CS算法

Yang等人在2009年的時(shí)候根據(jù)布谷鳥在后代繁衍中所使用的寄生策略，提出CS算法[5]。該算法遵守三個(gè)原則：

a）布谷鳥每次隨機(jī)地在一個(gè)其它鳥的鳥巢中產(chǎn)一枚蛋；

b）放有優(yōu)質(zhì)蛋的鳥巢將會(huì)被保留；

c）一旦寄主鳥發(fā)現(xiàn)其巢中有布谷鳥的蛋，其要么放棄鳥巢，要么就把該蛋清出鳥巢。

令第t代中的第i個(gè)鳥巢的位置為[x（t）i]，搜索路徑為[L（λ）]，那么在第t+1代中的第i個(gè)鳥巢的位置為：

[x（t+1）i=x（t）i+α⊕L（λ），（i=1，2，…，n）] （5）

其中，[α]為步長(zhǎng)因子。

為了解決CS算法收斂速度慢等缺點(diǎn)，利用高斯擾動(dòng)來(lái)加快收斂速度，實(shí)現(xiàn)方法為：第t代中的第i個(gè)鳥巢的位置[x（t）i]進(jìn)行繞到擾動(dòng)，從而實(shí)現(xiàn)對(duì)[x（t）i]的更進(jìn)一步的搜索。

令[pt=x（t）1，x（t）2，…，x（t）nT]，則引入高斯擾動(dòng)后的[p`t]：

[p`t=pt+β⊕ε] （6）

其中，[β]與[ε]分別為常量，擾動(dòng)矩陣（矩陣大小與[pt]相同）。

從公式（6）可以看出，通過(guò)[β]與[ε]的使用，使得鳥巢的位置變化更靈活，從而實(shí)現(xiàn)了算法的快速收斂。

3 基于啟發(fā)式算法的短時(shí)交通流量預(yù)測(cè)的實(shí)現(xiàn)

上一節(jié)分別對(duì)本文所提算法用到的相關(guān)理論進(jìn)行了介紹，本節(jié)將綜合利用上述理論來(lái)實(shí)現(xiàn)本文所提算法。算法的實(shí)現(xiàn)步驟為：

1）首先通過(guò)對(duì)交通流量進(jìn)行測(cè)量得到短時(shí)流量訓(xùn)練序列，然后分別用關(guān)聯(lián)維算法與互信息法來(lái)確定維數(shù)[m]與時(shí)延[τ]，最后利用[m]與[τ]對(duì)訓(xùn)練序列進(jìn)行相空間重構(gòu)，那么重構(gòu)后的序列被用作神經(jīng)網(wǎng)絡(luò)的訓(xùn)練序列；

2）首先隨機(jī)地生成[n]個(gè)鳥巢的位置[p（0）i=x（0）1，x（0）2，…，x（0）nT]，而鳥巢的位置是與神經(jīng)網(wǎng)絡(luò)的閥值與連接權(quán)重相對(duì)應(yīng)的。然后神經(jīng)網(wǎng)絡(luò)根據(jù)每一個(gè)鳥巢位置所對(duì)應(yīng)的參數(shù)開始訓(xùn)練，從而得到相應(yīng)的預(yù)測(cè)精度，最后找出當(dāng)前訓(xùn)練周期內(nèi)的最優(yōu)鳥巢[x（0）b]；

3）首先[x（0）b]保持不變，而其它鳥巢的位置利用公式（5）進(jìn)行變化，接著計(jì)算變化了的位置所對(duì)應(yīng)的預(yù)測(cè)精度，然后把本次所得到的預(yù)測(cè)精度與相應(yīng)的上代預(yù)測(cè)精度相比較，最后把精度高的鳥巢位置保留下來(lái)，從而生成了一組新的鳥巢位置[kt=x（t）1，x（t）2，…，x（t）nT]；

4）首先隨機(jī)生成一組[r]，接著把[r]與[Pa]進(jìn)行比較，[kt]中的鳥巢位置被發(fā)現(xiàn)概率小的將被保留，其它的經(jīng)隨機(jī)地改變，從而得到一組新的位置，然后計(jì)算新位置所對(duì)應(yīng)的預(yù)測(cè)精度，最后把精度高的位置保留下來(lái)，從而成了一組新的鳥巢位置[pt=x（t）1，x（t）2，…，x（t）nT]；

5）首先利用公式（6）對(duì)[pt]實(shí)施擾動(dòng)，而擾動(dòng)后的位置為[p't=x（t）'1，x（t）'2，…，x（t）'nT]，接著計(jì)算[p't]每個(gè)位置所對(duì)應(yīng)的預(yù)測(cè)精度，最后把精度高的位置保留下來(lái)，從而成了一組新的鳥巢位置[p''t=x（t）''1，x（t）''2，…，x（t）''nT]，并令把[pt]=[p''t]；

6）首先跳出[pt]中預(yù)測(cè)精度最高的鳥巢[x（t）b]，接著判斷該預(yù)測(cè)精度是否能夠達(dá)到要求，如果達(dá)到，把[x（t）b]作為神經(jīng)網(wǎng)絡(luò)的參數(shù)設(shè)置，調(diào)到（7），否則的話，跳到（3）；

7）首先[x（t）b]所對(duì)應(yīng)閥值與初始權(quán)值送入神經(jīng)網(wǎng)絡(luò)，然后神經(jīng)網(wǎng)絡(luò)開始用訓(xùn)練序列進(jìn)行訓(xùn)練，從而得到預(yù)測(cè)模型，最后用預(yù)測(cè)模型進(jìn)行預(yù)測(cè)。

4 仿真分析

為了驗(yàn)證本文所提算法（簡(jiǎn)稱CS-BP）的性能，將對(duì)基于PSO的BP神經(jīng)網(wǎng)絡(luò)的預(yù)測(cè)算法（簡(jiǎn)稱PSO-BP）和基于GA的BP神經(jīng)網(wǎng)絡(luò)的預(yù)測(cè)算法（簡(jiǎn)稱GA-BP）與CS-BP三者的預(yù)測(cè)誤差進(jìn)行分析。

GA-BP的參數(shù)為：變異與交叉概率分別為0.12，0.73，種群規(guī)則與最大進(jìn)化次數(shù)分別為30和300。PSO-BP的參數(shù)為：[c1=c2=3]，其它參數(shù)與GA-BP相同。而CS-BP的參數(shù)為：鳥巢數(shù)為30，[Pa=0.25]，最大進(jìn)化次數(shù)不超過(guò)300。

三種預(yù)測(cè)算法根據(jù)[X]的前380個(gè)數(shù)據(jù)來(lái)生成預(yù)測(cè)模型，并使用預(yù)測(cè)模型來(lái)預(yù)測(cè)后100個(gè)數(shù)據(jù)，圖2給出了三種算法預(yù)測(cè)的結(jié)果。

5 小結(jié)

本文針對(duì)交通流量預(yù)測(cè)中的短時(shí)交通流量預(yù)測(cè)問題，提出了基于CS Search）算法與BP神經(jīng)網(wǎng)絡(luò)相結(jié)合的啟發(fā)式算法。并且仿真表明，本文所提算法在短時(shí)間內(nèi)能夠準(zhǔn)確地預(yù)測(cè)交通流量的變化趨勢(shì)，從而大大增加了所預(yù)測(cè)流量的可信度，為智能交通管理提供了重要的依據(jù)。

參考文獻(xiàn)：

[1] Liu X， Fang Z. An agent-based intelligent transport system[M]//Computer Supported Cooperative Work in Design IV. Springer Berlin Heidelberg， 2008： 304-315.

[2] 沈國(guó)江， 王嘯虎， 孔祥杰. 短時(shí)交通流量智能組合預(yù)測(cè)模型及應(yīng)用[J]. 系統(tǒng)工程理論與實(shí)踐， 2011， 31（3）： 561-568.