改進(jìn)麻雀搜索算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的短時(shí)交通流預(yù)測(cè)

王 珅,李昕光,詹 郡,呂 桐

(青島理工大學(xué) 機(jī)械與汽車工程學(xué)院,青島 266525)

在城市不可能無(wú)限增加車道的情況下,交通控制和交通誘導(dǎo)成為緩解交通擁堵的最好方法。良好的交通控制和交通誘導(dǎo)需要精準(zhǔn)的短時(shí)交通流預(yù)測(cè)作為支撐[1]。由于交通流的不確定性和突發(fā)性,傳統(tǒng)的線性模型不能對(duì)交通流進(jìn)行很好地預(yù)測(cè)。BP神經(jīng)網(wǎng)絡(luò)通過(guò)其較強(qiáng)的輸入到輸出的映射功能、自學(xué)習(xí)和自適應(yīng)能力,可以對(duì)具有非線性變化的交通流進(jìn)行很好地預(yù)測(cè)。但傳統(tǒng)BP神經(jīng)網(wǎng)絡(luò)的預(yù)測(cè)結(jié)果對(duì)初始參數(shù)的選取具有極高的依賴性,不當(dāng)?shù)某跏紖?shù)選取會(huì)導(dǎo)致程序陷入局部最優(yōu)或收斂過(guò)慢[2-4]。

近年來(lái),各種群智能優(yōu)化算法憑借搜索能力強(qiáng)、收斂速度快、結(jié)果不依賴初始參數(shù)選取等特點(diǎn),在神經(jīng)網(wǎng)絡(luò)的優(yōu)化上得到廣泛應(yīng)用。例如通過(guò)粒子群算法來(lái)優(yōu)化BP神經(jīng)網(wǎng)絡(luò)模型,從而提高BP神經(jīng)網(wǎng)絡(luò)短時(shí)交通流預(yù)測(cè)模型的預(yù)測(cè)精度[5-7]。但粒子群算法收斂速度慢,尋優(yōu)能力較弱。2020年提出的麻雀搜索算法(Sparrow Search Algorithm,SSA)相較于粒子群算法,具有參數(shù)少,結(jié)構(gòu)簡(jiǎn)單,收斂快等特點(diǎn),獲得了較廣泛應(yīng)用。李雅麗等[8]針對(duì)最近幾年來(lái)較為典型的幾個(gè)群智能算法,利用22個(gè)測(cè)試函數(shù),從算法的精度、收斂速度和預(yù)測(cè)結(jié)果的穩(wěn)定性等方面對(duì)算法進(jìn)行了對(duì)比,對(duì)比結(jié)果顯示麻雀搜索算法的性能遠(yuǎn)超其他算法;劉麗娜等[9]用改進(jìn)麻雀搜索算法來(lái)求解作業(yè)車間調(diào)度問題,獲得了更好的最小值、平均值和尋優(yōu)成功率;ZHANG等[10]用改進(jìn)麻雀搜索算法設(shè)計(jì)了移動(dòng)機(jī)器人的仿生路徑規(guī)劃;JIANG等[11]利用改進(jìn)麻雀搜索算法來(lái)解決現(xiàn)有算法求解飛行器軌跡優(yōu)化問題時(shí)收斂精度低、易陷入局部?jī)?yōu)化的問題。

本文提出一種基于改進(jìn)麻雀搜索算法(Improving Sparrow Search Algorithm,ISSA)優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的短時(shí)交通流預(yù)測(cè)模型(ISSA-BP),針對(duì)標(biāo)準(zhǔn)麻雀搜索算法易收斂于原點(diǎn)的問題,對(duì)標(biāo)準(zhǔn)麻雀搜索算法中發(fā)現(xiàn)者和加入者的位置更新公式進(jìn)行部分改進(jìn),改善標(biāo)準(zhǔn)麻雀搜索算法的全局探索能力,降低計(jì)算復(fù)雜度。利用改進(jìn)麻雀搜索算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的權(quán)值,使BP神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)模型的收斂速度更快,精度更高。

1 改進(jìn)麻雀搜索算法

麻雀搜索算法和粒子群算法都是根據(jù)鳥類的種群覓食行為提出的。2020年提出的新型的麻雀搜索算法不僅考慮到了鳥類的覓食行為,還考慮到了針對(duì)捕食者的反捕食和種群中鳥類之間的奪食行為[12],同其他智能群體優(yōu)化算法相比較,麻雀搜索算法的初始參數(shù)更少,收斂速度更快[13]。

1.1 標(biāo)準(zhǔn)麻雀搜索算法

在SSA中,假設(shè)有N只麻雀在D維搜索空間中覓食,則將第i只麻雀在搜索空間中的位置坐標(biāo)設(shè)置為Xi=[xi1,xi2,…,xid],xid表示第i只麻雀在d維度中位置的。D維空間中每一只麻雀的位置都是目標(biāo)函數(shù)的一個(gè)解,將麻雀在空間中的位置代入目標(biāo)函數(shù)會(huì)得到解的值,按照解的大小對(duì)麻雀種群進(jìn)行排序,排序靠前的麻雀作為發(fā)現(xiàn)者,將優(yōu)先獲取食物,并為加入者提供覓食方向。發(fā)現(xiàn)者的位置更新公式為

(1)

在式(1)中,當(dāng)R2

(2)

在麻雀種群中約有10%～20%的麻雀負(fù)責(zé)警戒,這些麻雀會(huì)根據(jù)自己的判斷來(lái)確定是否有危險(xiǎn),這部分警戒麻雀的位置更新公式為

(3)

在式(3)中,當(dāng)fi>fg時(shí),表示該麻雀不在種群中心,需要往中心靠攏;當(dāng)fi=fg時(shí),表示種群中心的麻雀需要向其他麻雀靠攏。

1.2 麻雀搜索算法的缺陷

圖1 迭代散點(diǎn)分布

利用3個(gè)測(cè)試函數(shù)對(duì)原算法的缺陷進(jìn)行驗(yàn)證。對(duì)帶入3個(gè)測(cè)試函數(shù)的原算法選擇相同的參數(shù):維度為2、麻雀數(shù)為10、循環(huán)次數(shù)為100、測(cè)試次數(shù)為50。具體測(cè)試函數(shù)和測(cè)試結(jié)果的平均值如表1所示。

表1 測(cè)試函數(shù)參數(shù)和測(cè)試結(jié)果

由表1可知,隨著最優(yōu)值的位置距離原點(diǎn)越遠(yuǎn),測(cè)試結(jié)果的平均值越大,因此標(biāo)準(zhǔn)的SSA算法對(duì)于最優(yōu)解越靠近原點(diǎn)的函數(shù),尋優(yōu)的效果越好。但BP神經(jīng)網(wǎng)絡(luò)的最優(yōu)值所對(duì)應(yīng)的權(quán)值和閾值未必靠近原點(diǎn),所以需要對(duì)標(biāo)準(zhǔn)SSA算法進(jìn)行改進(jìn)。

1.3 麻雀搜索算法的改進(jìn)

保留標(biāo)準(zhǔn)麻雀搜索算法的收斂和反捕食公式不變,對(duì)易收斂于原點(diǎn)的位置更新公式進(jìn)行部分改進(jìn)。受粒子群算法[14-15]中粒子會(huì)根據(jù)最優(yōu)粒子的位置和自身最優(yōu)位置進(jìn)行搜索這一行為的啟發(fā),將位置更新公式分別改為以自身為中心的搜索模式和以全局最優(yōu)位置為中心的搜索模式,在增加搜索多樣性的同時(shí)避免麻雀在探索過(guò)程中向原點(diǎn)收斂,同時(shí)也降低了計(jì)算的復(fù)雜度,提高程序的運(yùn)行效率。因此,改進(jìn)式(1)中當(dāng)R2v/2時(shí)的位置更新公式,改進(jìn)后的2個(gè)位置更新公式為

(4)

(5)

式中:L為搜索空間的長(zhǎng)度;r為隨機(jī)數(shù),取值范圍為[-1,1];Pm為常數(shù),表示發(fā)現(xiàn)者的數(shù)量;a為搜索因子。

a的值從0.2非線性縮減至約0.03,其計(jì)算公式為

a=0.2-0.1×[exp(t/Tm)-1]

(6)

式(6)中利用以自然數(shù)為底數(shù)的指數(shù)函數(shù)在[0,1]的取值范圍內(nèi)的函數(shù)值先緩慢增加后快速增加的特點(diǎn),令搜索因子a在迭代初期能以較大的值緩慢縮小,提高發(fā)現(xiàn)者在自身附近的搜索范圍;迭代后期搜索因子a的值以較快的速度縮小為較小值,提高自身的收斂速度。

以式(4)中的粒子搜索范圍構(gòu)建f(x)=a×L×r×(x/Pm)函數(shù)并將結(jié)果制作為散點(diǎn)圖,其中,a=0.2,L=200,Pm=30。表示為迭代初期按適應(yīng)度值排序的麻雀?jìng)€(gè)體的搜索范圍。將所構(gòu)建函數(shù)的計(jì)算結(jié)果制作為散點(diǎn)圖,散點(diǎn)分布圖如圖2所示。

圖2 麻雀散點(diǎn)分布

從圖2中可以看出種群中的麻雀?jìng)€(gè)體隨著適應(yīng)度的逐漸降低搜索范圍會(huì)逐漸變大。迭代后期的散點(diǎn)由于a的縮小更加收斂,變化幅度將會(huì)更小。使得麻雀種群前期有較大的搜索空間,后期有較快的收斂速度。

為了使算法在迭代前期具有較高的全局搜索范圍,迭代后期具有較快的局部收斂速度,令跟隨發(fā)現(xiàn)者覓食與不跟隨發(fā)現(xiàn)者覓食的加入者的比例系數(shù)隨迭代次數(shù)指數(shù)衰減,計(jì)算公式為

H=b+b·ct

(7)

式中:H為加入者中不隨發(fā)現(xiàn)者覓食的比例系數(shù);b為常數(shù),取值為0.35;ct為衰減因子,根據(jù)最大迭代次數(shù)和所需衰減到的大小進(jìn)行設(shè)置,取值為0.999。

2 改進(jìn)算法的測(cè)試

2.1 測(cè)試函數(shù)

為測(cè)試改進(jìn)麻雀搜索算法的性能,選取4個(gè)國(guó)際通用的基準(zhǔn)測(cè)試函數(shù)(f1～f4)[16]對(duì)ISSA進(jìn)行仿真測(cè)試,同時(shí)對(duì)這4個(gè)測(cè)試函數(shù)的最優(yōu)值位置進(jìn)行偏移從而衍生出(f5～f8)4個(gè)偏移函數(shù),其中f1,f5僅有1個(gè)極值,其余函數(shù)均有多個(gè)極值。8個(gè)測(cè)試函數(shù)的參數(shù)值如表2所示。

表2 8個(gè)測(cè)試函數(shù)的參數(shù)值

2.2 算法測(cè)試

利用上述8個(gè)測(cè)試函數(shù)對(duì)ISSA,SSA和PSO進(jìn)行測(cè)試,為保證算法的公平性及準(zhǔn)確性,給3種算法設(shè)置相同的參數(shù)。種群中的個(gè)體數(shù)均為30,搜索空間的維度均為30,最大迭代次數(shù)均為1000,每個(gè)函數(shù)獨(dú)立運(yùn)行50次,分別記錄每次測(cè)試的最優(yōu)值位置與實(shí)際最優(yōu)值位置之間距離的標(biāo)準(zhǔn)差,計(jì)算公式為

(8)

計(jì)算3種算法在8種測(cè)試函數(shù)中的最優(yōu)值位置與實(shí)際最優(yōu)值之間距離的平均值和標(biāo)準(zhǔn)差,用以比較算法的搜索精度和穩(wěn)定性。PSO,SSA,ISSA算法對(duì)8個(gè)測(cè)試函數(shù)的測(cè)試結(jié)果(小數(shù)點(diǎn)后保留2位有效數(shù)字)如表3所示。

表3 不同模型對(duì)于8個(gè)測(cè)試函數(shù)的誤差

由表3可知,SSA和ISSA在8個(gè)函數(shù)上的尋優(yōu)效果均好于PSO算法;SSA算法在f1～f4函數(shù)(函數(shù)最優(yōu)解在每個(gè)維度上均為0)尋優(yōu)好于ISSA,這是由于SSA算法會(huì)收斂于原點(diǎn);在f5～f8函數(shù)(函數(shù)最優(yōu)解在每個(gè)維度上的值均為50)上ISSA尋優(yōu)效果好于SSA,并且ISSA在(f1,f5)、(f2,f6)、(f3,f7)、(f4,f8)這4組對(duì)比函數(shù)上尋優(yōu)效果接近,而SSA在這4組對(duì)比函數(shù)上的尋優(yōu)效果相差很大,所以ISSA相比較于SSA算法有著更好的普遍適應(yīng)性,更適合用于解決實(shí)際問題。

3 短時(shí)交通流模型構(gòu)建與實(shí)驗(yàn)測(cè)試

3.1 構(gòu)建模型

針對(duì)BP神經(jīng)網(wǎng)絡(luò)在非線性預(yù)測(cè)中的優(yōu)缺點(diǎn),用改進(jìn)麻雀搜索算法的最優(yōu)解作為BP神經(jīng)網(wǎng)絡(luò)的初始權(quán)值,結(jié)合交通流特性構(gòu)建基于改進(jìn)麻雀搜索算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)(ISSA-BP)的短時(shí)交通流預(yù)測(cè)模型。

1) 利用python語(yǔ)言和Tensorflow深度學(xué)習(xí)框架設(shè)計(jì)神經(jīng)網(wǎng)絡(luò)層數(shù),確定輸入層、隱藏層以及輸出層的節(jié)點(diǎn)個(gè)數(shù)和每層的激活函數(shù),搭建BP神經(jīng)網(wǎng)絡(luò)模型。

2) 搭建改進(jìn)麻雀搜索算法模型,確定麻雀種群的適度值函數(shù)。用第1)步中構(gòu)建的BP神經(jīng)網(wǎng)絡(luò)期望值與預(yù)測(cè)值之差的絕對(duì)值之和作為麻雀的適度值函數(shù)來(lái)構(gòu)建ISSA算法模型。

3) 通過(guò)迭代來(lái)尋找到最優(yōu)適度值。輸出其所對(duì)應(yīng)的位置作為最優(yōu)解,將輸出的最優(yōu)解作為BP神經(jīng)網(wǎng)絡(luò)的權(quán)值和閾值。將BP神經(jīng)網(wǎng)絡(luò)代入訓(xùn)練集進(jìn)行訓(xùn)練,當(dāng)訓(xùn)練精度達(dá)到要求或達(dá)到最大迭代次數(shù)后,輸入測(cè)試集,并輸出最終測(cè)試結(jié)果與真實(shí)值之間的誤差。

3.2 模型評(píng)價(jià)

為了對(duì)短時(shí)交通流預(yù)測(cè)模型的精度進(jìn)行判定,采用平均絕對(duì)百分誤差(MAPE)、平均絕對(duì)值誤差(MAE)和均方誤差(MSE)進(jìn)行誤差分析[17-19],公式如下:

(9)

(10)

(11)

式中:EMAPE,EMAE,EMSE分別為平均絕對(duì)百分誤差值、平均絕對(duì)值誤差值、均方誤差值。

3.3 實(shí)驗(yàn)測(cè)試

模型的輸入為3,輸出為1。BP神經(jīng)網(wǎng)絡(luò)以及PSO-BP,SSA-BP,ISSA-BP模型的BP神經(jīng)網(wǎng)絡(luò)部分采用相同的網(wǎng)絡(luò)結(jié)構(gòu),模型的輸入層輸入節(jié)點(diǎn)個(gè)數(shù)為3;隱藏層為2層,每層的節(jié)點(diǎn)個(gè)數(shù)均為10;輸出層的節(jié)點(diǎn)個(gè)數(shù)為1;激活函數(shù)采用Sigmoid函數(shù)。

為了評(píng)價(jià)ISSA-BP模型的性能,采用西安市區(qū)某道路斷面18 d交通流量數(shù)據(jù)[20]進(jìn)行實(shí)驗(yàn)測(cè)試。該道路斷面的交通流量數(shù)據(jù)以15 min為間隔,從7:30開始到11:30截止,每天16組數(shù)據(jù),共288組數(shù)據(jù)。首先對(duì)數(shù)據(jù)進(jìn)行預(yù)處理,刪除數(shù)據(jù)集中的異常值并利用牛頓插值公式進(jìn)行填充。數(shù)據(jù)集中的交通流數(shù)據(jù)只有每天的16個(gè)數(shù)據(jù)為連續(xù)數(shù)據(jù),每天16個(gè)交通流數(shù)據(jù)除去作為特征輸入的3個(gè)數(shù)據(jù),每天可制作13組訓(xùn)練數(shù)據(jù)。為了使模型達(dá)到充分訓(xùn)練,將前17 d的數(shù)據(jù)制作為訓(xùn)練集,共221組訓(xùn)練數(shù)據(jù);最后一天的數(shù)據(jù)制作為測(cè)試集,共13組測(cè)試數(shù)據(jù)。將訓(xùn)練集和測(cè)試集數(shù)據(jù)分別輸入BP,PSO-BP,SSA-BP,ISSA-BP神經(jīng)網(wǎng)絡(luò)模型進(jìn)行短時(shí)交通流的預(yù)測(cè),比較各個(gè)模型的預(yù)測(cè)輸出。4種短時(shí)交通流預(yù)測(cè)模型的真實(shí)值曲線和預(yù)測(cè)值曲線如圖3-圖6所示。

從圖3-圖6中可以看出,ISSA-BP模型相較于其他3個(gè)模型的預(yù)測(cè)值曲線更貼合真實(shí)值曲線?；贐P和SSA-BP的短時(shí)交通流預(yù)測(cè)結(jié)果前半部分小于真實(shí)值,后半部分大于真實(shí)值,二者的預(yù)測(cè)結(jié)果均不能很好地表現(xiàn)出交通流的變化趨勢(shì);基于PSO-BP和ISSA-BP的短時(shí)交通流預(yù)測(cè)結(jié)果在真實(shí)值上下波動(dòng),二者的預(yù)測(cè)結(jié)果均能較好地表現(xiàn)出交通流的變化趨勢(shì),但基于PSO-BP的預(yù)測(cè)值曲線與真實(shí)值曲線之間的差值波動(dòng)較大,預(yù)測(cè)的交通流量與真實(shí)值之間的誤差較大;基于ISSA-BP模型的預(yù)測(cè)值曲線相較于PSO-BP的預(yù)測(cè)值曲線更貼合真實(shí)值曲線,能夠更好地滿足交通流變化的預(yù)測(cè)。

為更科學(xué)直觀地判斷4種交通流預(yù)測(cè)模型的預(yù)測(cè)效果,利用3.2部分所選擇的3種誤差評(píng)價(jià)指標(biāo)對(duì)4種模型的交通流量預(yù)測(cè)結(jié)果進(jìn)行對(duì)比分析,對(duì)比結(jié)果如表4所示。由表4可知,基于ISSA-BP的短時(shí)交通流預(yù)測(cè)模型相較于其他3個(gè)預(yù)測(cè)模型,其預(yù)測(cè)結(jié)果在3種誤差分析中均表現(xiàn)最好。從MAPE評(píng)價(jià)指標(biāo)的對(duì)比結(jié)果來(lái)看,ISSA-BP模型的預(yù)測(cè)精度比BP模型高49.17%,比PSO-BP模型高38.47%,比SSA-BP神經(jīng)網(wǎng)絡(luò)模型高40.64%;從MAE評(píng)價(jià)指標(biāo)的對(duì)比結(jié)果來(lái)看,ISSA-BP模型的預(yù)測(cè)精度比BP模型高48.85%,比PSO-BP模型高38.71%,比SSA-BP神經(jīng)網(wǎng)絡(luò)模型高40.99%;從MSE評(píng)價(jià)指標(biāo)的對(duì)比結(jié)果來(lái)看,ISSA-BP模型的預(yù)測(cè)精度比BP模型高68.34%,比PSO-BP模型高61.84%,比SSA-BP神經(jīng)網(wǎng)絡(luò)模型高63.36%。說(shuō)明ISSA-BP在短時(shí)交通流預(yù)測(cè)方面具有更好的預(yù)測(cè)精度。

表4 4種預(yù)測(cè)模型的誤差

4 結(jié)論

針對(duì)標(biāo)準(zhǔn)麻雀搜索算法易收斂于原點(diǎn)和局部最優(yōu)值的缺陷,對(duì)麻雀群體中的發(fā)現(xiàn)者和部分加入者的位置更新公式進(jìn)行改進(jìn),使其不再輕易收斂于原點(diǎn),并增強(qiáng)麻雀種群前期的全局搜索能力使其不易陷入局部最優(yōu)。應(yīng)用4個(gè)國(guó)際通用的基準(zhǔn)測(cè)試函數(shù)和4個(gè)偏移測(cè)試函數(shù)對(duì)ISSA的性能進(jìn)行了驗(yàn)證,結(jié)果顯示ISSA在8個(gè)測(cè)試函數(shù)上的表現(xiàn)均優(yōu)于PSO,在最優(yōu)值不在原點(diǎn)的偏移測(cè)試函數(shù)上的表現(xiàn)優(yōu)于SSA。ISSA比PSO的測(cè)試表現(xiàn)更好,比SSA擁有更好的普遍適應(yīng)性。用改進(jìn)的麻雀搜索算法得到的最優(yōu)解作為BP神經(jīng)網(wǎng)絡(luò)的初始權(quán)值,構(gòu)建了ISSA-BP短時(shí)交通流預(yù)測(cè)模型。通過(guò)實(shí)驗(yàn)測(cè)試對(duì)SSA模型、PSO模型和BP神經(jīng)網(wǎng)絡(luò)模型進(jìn)行了對(duì)比分析,結(jié)果顯示ISSA-BP模型的誤差最小,預(yù)測(cè)精度最高。下一步考慮應(yīng)用該算法對(duì)多種因素以及特殊因素影響下的短時(shí)交通流量進(jìn)行預(yù)測(cè)。