梁 迪, 郭啟航, 姜廷霖

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

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

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

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

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

1 CS -SVM模型構建

1.1 布谷鳥搜索算法

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

(1)

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

Si=stepmin+(Smax-Smin)di.

(2)

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

di定義如下:

(3)

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

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

1.2 支持向量機算法

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

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

(4)

式中:ω表示權重向量;b表示偏向量.

為將結構風險降低到最小,可將式(4)優(yōu)化轉換為如下問題:

(5)

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

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

(7)

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

(8)

為防止維數(shù)災難發(fā)生,用核函數(shù)k(xi,x)代替高維空間中的向量內積(φ(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停車位預測模型,首先將樣本數(shù)據(jù)分為訓練樣本和測試樣本,并設置算法所需的參數(shù).在SVM中有C和σ2個參數(shù)需要尋優(yōu),采用CS算法對C和σ進行優(yōu)化,構建CS -SVM停車位預測模型.建立CS -SVM模型的步驟如下.

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

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

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

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

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

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

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

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

CS -SVM停車位預測模型構建過程圖如圖1所示.

圖1 CS -SVM 預測模型構建圖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ù)預處理

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

(14)

2.3 實驗結果分析及對比

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

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

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

表4為CS -SVM實測值、WNN、SVM實測值對比,CS -SVM模型MMSE、RMSE值均最小,與其他模型相比,CS -SVM模型與實際測量值更為接近,預測精度更高.并且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 結 論

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