布谷鳥搜索算法優(yōu)化支持向量機的停車位預(yù)測

梁 迪, 郭啟航, 姜廷霖

(沈陽大學(xué) 機械工程學(xué)院, 遼寧 沈陽 110044)

隨著我國汽車保有量的增加,停車位的預(yù)測及查詢成為研究熱點的問題.調(diào)查數(shù)據(jù)顯示,造成交通擁堵的原因中有30%是因為駕駛者無法找到停車位所導(dǎo)致[1].可用停車位的預(yù)測,可以幫助駕駛者在出發(fā)或者距目標地點一段路程時,知道到達該停車場時可用停車位的數(shù)量,使其能夠快速停放車輛.精確和快速地提供可用停車位的預(yù)測信息,不但可以使得駕駛者節(jié)省停車時間,同時也緩解了城市交通的停車難和擁堵等問題[2].

對一些停車管理系統(tǒng)的研究表明,引導(dǎo)式停車管理系統(tǒng)和基于云平臺的停車誘導(dǎo)系統(tǒng)可以引導(dǎo)駕駛者將車停在就近停車位,幫助駕駛者找到空閑停車位[3-4].通過平均行駛距離、平均步行距離、停車占有率等指標對引導(dǎo)式停車管理系統(tǒng)的有效性進行評估,但這兩種系統(tǒng)都缺少對停車位空余趨勢變化的預(yù)判,容易導(dǎo)致駕駛者到達停車場時沒有停車位可用,增加駕駛者不必要的行駛距離.Ajay等[5]通過分析收集的數(shù)據(jù),采用Delphi技術(shù)篩選出重要參數(shù),并建立停車位需求預(yù)測模型對校園停車位進行預(yù)測,有助于校園規(guī)劃人員提供適當?shù)耐＼囋O(shè)施,但這種非線性時間序列的數(shù)據(jù)擬合存在較大預(yù)測誤差缺陷.為降低預(yù)測誤差,孫涌等[6]采用多層前饋神經(jīng)網(wǎng)絡(luò)模型來預(yù)測空閑停車位,Doucoure等[7]將神經(jīng)網(wǎng)絡(luò)、支持向量機和回歸樹相結(jié)合進行停車位連續(xù)變化情況下的預(yù)測,這些預(yù)測方法在精度上得到了提高,但穩(wěn)定性和容錯性較差.

支持向量機(support vector machine,SVM)在1964年被提出,并在20世紀90年代由Vapnik等通過學(xué)習(xí)理論衍生出一系列改進和擴展算法.SVM處理高維度的非線性問題時具有很好的效果,而且SVM 模型有著優(yōu)良的推廣性[8].但SVM模型中參數(shù)的選擇會直接影響模型的預(yù)測精度,懲罰系數(shù)C選擇過高,模型容易過擬合.懲罰系數(shù)C選擇過低,模型容易欠擬合.核函數(shù)寬度參數(shù)σ如果太小,容易出現(xiàn)訓(xùn)練集擬合精度高而測試集擬合精度低的情況.而布谷鳥搜索(cuckoo search,CS)算法具有很強的尋優(yōu)能力以及參數(shù)少的特點,CS可以在SVM設(shè)置的參數(shù)解空間中進行尋優(yōu),找到最優(yōu)的參數(shù)解,從而提高模型的預(yù)測精度.CS與SVM相結(jié)合的模型在諸多領(lǐng)域中都有應(yīng)用,并都取得了不錯的效果.在熱點話題預(yù)測的應(yīng)用中,布谷鳥搜索算法優(yōu)化支持向量機模型可以準確描述熱點話題的變化趨勢[9].洑佳紅[10]提出一種基于改進支持向量機的預(yù)測方法對尾礦庫風(fēng)險安全進行預(yù)測,并通過與粒子群算法、遺傳算法進行對比得出其改進算法擬合準確率更好.劉超湖[11]提出一種基于改進布谷鳥搜索算法的支持向量機組合預(yù)測模型(ICS -SVM)應(yīng)用于實際邊坡變形預(yù)測,并選取7個基準函數(shù)測試ICS算法的尋優(yōu)性能,驗證了改進后的算法具有更高的預(yù)測精度以及良好地穩(wěn)定性,可以較好地反映邊坡實際變形情況.為了提高風(fēng)電場輸出功率的預(yù)測精度,劉家敏[12]等將小波分析(WD)與布谷鳥優(yōu)化支持向量機(CS -SVM)相結(jié)合對風(fēng)功率進行超短期預(yù)測,通過對預(yù)測結(jié)果的對比,WD -CS -SVM模型預(yù)測結(jié)果更加精準,具有較強的優(yōu)越性和實用性.

針對停車預(yù)測中存在的問題,本文擬采用布谷鳥搜索算法與支持向量機(cuckoo search-support vector machine,CS -SVM)組合預(yù)測方法對空閑停車位進行預(yù)測.通過布谷鳥搜索算法優(yōu)化SVM中的2個參數(shù),懲罰系數(shù)C和核函數(shù)寬度σ,并在布谷鳥搜索算法中加入自適應(yīng)動態(tài)調(diào)整公式,使步長因子根據(jù)每個階段不同情況進行自適應(yīng)動態(tài)調(diào)整,從而提高SVM模型的預(yù)測精度以及穩(wěn)定性.通過構(gòu)建CS -SVM模型對停車位做出準確預(yù)測,將所收集的空閑停車位數(shù)據(jù)分為訓(xùn)練集和測試集,訓(xùn)練集用于CS -SVM模型的訓(xùn)練,測試集用于對CS -SVM模型預(yù)測效果的驗證.選擇平均相對誤差MMSE、均方根誤差RMSE、確定性系數(shù)R2這3種評價指標對CS -SVM模型進行評價,并基于實際算例比較了CS -SVM、小波神經(jīng)網(wǎng)絡(luò)(WNN)以及支持向量機這3種方法的預(yù)測精度.

1 CS -SVM模型構(gòu)建

1.1 布谷鳥搜索算法

布谷鳥搜索算法是2009年Yang和S.Deb提出的一種新興啟發(fā)算法[13],它不僅結(jié)合了鳥類及果蠅特殊的萊維飛行模式進行搜索,增加了種群之間的信息交流,加速收斂速度,而且參數(shù)少、操作簡單、尋優(yōu)能力強.布谷鳥尋窩的路徑和位置更新公式如下:

(1)

在CS算法中,利用萊維飛行產(chǎn)生的步長不能確保快速收斂,具有一定的隨機性且缺乏自適應(yīng)性,所以步長因子要根據(jù)每個階段不同情況來進行自適應(yīng)的動態(tài)調(diào)整.離最佳鳥窩位置步長自適應(yīng)動態(tài)調(diào)整公式如下:

Si=stepmin+(Smax-Smin)di.

(2)

式中,Smax和Smin分別表示最大步長和最小步長.

di定義如下:

(3)

式中:ni為第i個鳥窩的位置;nbest表示此時鳥窩的位置為最優(yōu)位置;dmax為其他鳥窩位置與最佳鳥窩位置間的最大距離.

按照式(2),步長可以根據(jù)第i個鳥窩位置離最佳鳥窩位置的距離進行自適應(yīng)調(diào)整.距離越近,步長越小;距離越遠,步長越大.

1.2 支持向量機算法

SVM建模是利用非線性函數(shù)φ(x)將輸入的數(shù)據(jù)樣本映射到更高維的希爾伯特空間F中,轉(zhuǎn)換為線性回歸函數(shù)f(x)[14].SVM在高維的希爾伯特特征空間F中的線性回歸函數(shù)為

f(x)=ω·φ(x)+b.

(4)

式中:ω表示權(quán)重向量;b表示偏向量.

為將結(jié)構(gòu)風(fēng)險降低到最小,可將式(4)優(yōu)化轉(zhuǎn)換為如下問題:

(5)

將式(5)優(yōu)化問題轉(zhuǎn)變?yōu)橥苟蝺?yōu)化問題,引入拉格朗日乘數(shù)法,

將式(5)轉(zhuǎn)換為對偶形式來提高收斂速度,轉(zhuǎn)換如下:

(7)

對于線性回歸問題,SVM回歸函數(shù)為

(8)

為防止維數(shù)災(zāi)難發(fā)生,用核函數(shù)k(xi,x)代替高維空間中的向量內(nèi)積(φ(xi),φ(x)),則SVM的回歸函數(shù)為:

(9)

由于徑向基核函數(shù)相較于其他核函數(shù)在沒有先驗知識的情況下具有參數(shù)少、性能穩(wěn)定的特點,所以本文將徑向基核函數(shù)作為SVM的核函數(shù),其定義如下:

(10)

式中,σ為徑向基核函數(shù)的寬度參數(shù).

通過對SVM建?？梢钥闯?懲罰因子C,核函數(shù)寬度參數(shù)σ的選擇對SVM的性能有較大影響,因此本文采用布谷鳥搜索算法來優(yōu)化SVM參數(shù).

1.3 CS -SVM模型

建立CS -SVM停車位預(yù)測模型,首先將樣本數(shù)據(jù)分為訓(xùn)練樣本和測試樣本,并設(shè)置算法所需的參數(shù).在SVM中有C和σ2個參數(shù)需要尋優(yōu),采用CS算法對C和σ進行優(yōu)化,構(gòu)建CS -SVM停車位預(yù)測模型.建立CS -SVM模型的步驟如下.

Step 1 確定CS算法相應(yīng)參數(shù),即鳥巢的個數(shù)N,鳥巢被發(fā)現(xiàn)的概率Pa,最大迭代次數(shù)imax,拋棄鳥巢個數(shù)s,淘汰因數(shù)θ,C和σ的上限以及下限.

Step 2 將所選停車場實測數(shù)據(jù)分為訓(xùn)練樣本和測試樣本,然后把訓(xùn)練集歸一化到[0,1]之間進行歸一化處理.

Step 3 設(shè)定評價指標.選用平均相對誤差MMSE、均方根誤差RMSE作為評價CS -SVM模型精度的指標,選取確定性系數(shù)R2來評價模型的穩(wěn)定性.各評價指標計算公式為

Step 4 初始化鳥巢位置(C,σ),設(shè)置初始概率參數(shù)Pa=0.8,將初始化的鳥巢位置(C,σ)代入SVM模型中,通過式(11)求出MMSE值,并保留最佳的鳥巢位置.

Step 5 更新布谷鳥鳥巢的位置,并將更新之后鳥巢位置的解代入到SVM模型中,得到更新后的MMSE值.將更新后所求MMSE值與上一代鳥巢位置所求解的MMSE值進行比較,若更新后解的MMSE值更小,則原來鳥巢位置將被更好的鳥巢位置所取代;反之,鳥巢位置不變.

Step 6 全局更新結(jié)束之后,進行局部搜索.每個鳥巢隨機產(chǎn)生一個[0,1]之間的數(shù)r,若r>Pa,表示這個鳥巢會暴露,需要淘汰這個鳥巢,然后隨機產(chǎn)生一個新的鳥巢;反之,鳥巢位置不變.

Step 7 局部搜索結(jié)束后,將所有鳥巢位置解的MMSE值按照大小排序,淘汰3個位置較差的鳥巢,并重新生成3個相應(yīng)的鳥巢,計算其MMSE值.

Step 8 判斷迭代是否終止,也就是迭代次數(shù)有沒有超過最大迭代次數(shù)imax或者超過所設(shè)置的最小誤差ε,若2個條件都沒達到,則從第5個步驟繼續(xù)迭代;若達到其中任一條件,則迭代終止,求得此時C和σ的最優(yōu)解.并將此時鳥巢的最優(yōu)解(C,σ)代入SVM進行訓(xùn)練,輸出最終的預(yù)測值.

CS -SVM停車位預(yù)測模型構(gòu)建過程圖如圖1所示.

圖1 CS -SVM 預(yù)測模型構(gòu)建圖Fig.1 CS -SVM prediction model construction diagram

2 仿真實驗

2.1 數(shù)據(jù)來源

本文選擇遼寧省沈陽市新瑪特中街店地下停車場的停車數(shù)據(jù)作為實驗數(shù)據(jù),統(tǒng)計時間為2019年12月10日—2019年12月12日16∶00—20∶00停車場4 h剩余停車位數(shù)據(jù),以每5 min作為數(shù)據(jù)時間間隔,數(shù)據(jù)如表1～表3所示.

表1 12月10日16∶00—20∶00空閑停車位個數(shù)(間隔5 min)Table 1 Number of free parking spaces on December 10th from 16∶00—20∶00(every 5 minutes)

表2 12月11日16∶00—20∶00空閑停車位個數(shù)(間隔5 min)Table 2 Number of free parking spaces on December 11st from 16∶00—20∶00(every 5 minutes)

表3 12月12日16∶00—20∶00空閑停車位個數(shù)(間隔5 min)Table 3 Number of free parking spaces on December 12an from 16∶00—20∶00(every 5 minutes)

2.2 停車位數(shù)據(jù)預(yù)處理

為加快模型的SVM學(xué)習(xí)速度,對停車位數(shù)據(jù)進行預(yù)處理,歸一化[0,1]之間,即:

(14)

2.3 實驗結(jié)果分析及對比

將數(shù)據(jù)分成2部分,前50個數(shù)據(jù)作為訓(xùn)練樣本用于預(yù)測模型的訓(xùn)練,其余數(shù)據(jù)作為驗證集來檢測預(yù)測模型的效果.將訓(xùn)練樣本代入SVM進行訓(xùn)練,然后采用CS對SVM參數(shù)進行優(yōu)化,得到最優(yōu)參數(shù)為:C=80、σ=1.296.采用C=80,σ=1.296對訓(xùn)練集進行重新學(xué)習(xí),建立CS -SVM停車位預(yù)測模型,將訓(xùn)練樣本代入CS -SVM模型中,得到的擬合結(jié)果如圖2所示.

圖2 預(yù)測擬合曲線對比Fig.2 Comparison of prediction fitting curve

從圖2可以看出,CS -SVM模型所預(yù)測的停車位變化趨勢與實際值擬合程度非常高,擬合精度達到97.25%,比一般的擬合精度88%要高很多.與WNN(小波神經(jīng)網(wǎng)絡(luò))、SVM(向量機)擬合結(jié)果相比,CS -SVM預(yù)測更加精確.從擬合結(jié)果來看, CS -SVM可以對停車位變化趨勢進行預(yù)測,是一種擬合效果很好的停車位預(yù)測模型.

表4為CS -SVM實測值、WNN、SVM實測值對比,CS -SVM模型MMSE、RMSE值均最小,與其他模型相比,CS -SVM模型與實際測量值更為接近,預(yù)測精度更高.并且CS -SVM模型確定性系數(shù)R2也最小,因此穩(wěn)定性相比WNN、SVM更佳

表4 CS -SVM、WNN、SVM實測值對比Table 4 Comparison of measured values of CS -SVM, WNN and SVM

3 結(jié) 論

為對空閑停車位進行準確預(yù)測,減少駕駛者尋找停車位所用時間,提出了一種布谷鳥搜索算法優(yōu)化支持向量機的組合預(yù)測方法.通過CS算法對SVM的參數(shù)C和σ進行尋優(yōu),并在布谷鳥搜索算法中加入自適應(yīng)動態(tài)調(diào)整公式,提高了模型的預(yù)測精度,增強了模型的穩(wěn)定性.在預(yù)測時間步長相同的情況下,該方法與傳統(tǒng)預(yù)測方法相比具有更高的預(yù)測精度,在停車位的預(yù)測中具有良好的效果,對于緩解城市交通擁堵也具有很強的現(xiàn)實意義.SVM模型實際上是通過不斷優(yōu)化的方法來解決二次線性規(guī)劃問題的算法,改進后的CS -SVM仍然不適用于處理長時間序列問題,只適合處理小于30 min條件下短時間跨度的高精度預(yù)測.