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

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

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

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

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

1 改進麻雀搜索算法

麻雀搜索算法和粒子群算法都是根據(jù)鳥類的種群覓食行為提出的。2020年提出的新型的麻雀搜索算法不僅考慮到了鳥類的覓食行為,還考慮到了針對捕食者的反捕食和種群中鳥類之間的奪食行為[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ù)的一個解,將麻雀在空間中的位置代入目標(biāo)函數(shù)會得到解的值,按照解的大小對麻雀種群進行排序,排序靠前的麻雀作為發(fā)現(xiàn)者,將優(yōu)先獲取食物,并為加入者提供覓食方向。發(fā)現(xiàn)者的位置更新公式為

(1)

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

(2)

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

(3)

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

1.2 麻雀搜索算法的缺陷

圖1 迭代散點分布

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

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

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

1.3 麻雀搜索算法的改進

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

(4)

(5)

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

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

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

(6)

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

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

圖2 麻雀散點分布

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

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

H=b+b·ct

(7)

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

2 改進算法的測試

2.1 測試函數(shù)

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

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

2.2 算法測試

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

(8)

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

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

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

3 短時交通流模型構(gòu)建與實驗測試

3.1 構(gòu)建模型

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

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

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

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

3.2 模型評價

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

(9)

(10)

(11)

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

3.3 實驗測試

模型的輸入為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é)點個數(shù)為3;隱藏層為2層,每層的節(jié)點個數(shù)均為10;輸出層的節(jié)點個數(shù)為1;激活函數(shù)采用Sigmoid函數(shù)。

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

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

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

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

4 結(jié)論

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