基于混沌高效遺傳算法優化SV M的交通量預測＊

康海貴 李明偉 周鵬飛 趙澤輝

（大連理工大學工程建設學部 大連 116024）

支持向量機（SV M）在經驗風險最小化的基礎上同時采用了結構風險最小化準則［1］，很好地解決了小樣本、非線性、高維數、局部極小等實際問題［2］，避免了神經網絡的參數難以選擇、易陷入局部極值和過擬合等缺陷.但是，支持向量機本身并沒有給出選擇合適參數的方法，目前主要依靠經驗法和試算法，很大程度上影響了模型的推廣使用.考慮到基于混沌理論改進的混沌高效遺傳算法（CHEGA）在參數優選中表現出的快速、高效的特點，本文建立了基于CHEGA進行參數優選的CHEGA－SVM交通量預測模型，并進行了仿真驗證.對比結果表明該模型在交通量預測過程中具有一定的實用性.

1 支持向量回歸的基本原理

在解決函數回歸問題時，SV M方法的基本思想是：通過事先定義的非線性映射φ：Rn→Rm（m≥n），把輸入空間的數據x映射到一個高維特征空間，然后在該空間中做線性回歸φ：Rn→Rm（m≥n）.給定數據點集為｛（xi，yi），i＝1，2，…，N｝，式中：xi∈Rn為輸入變量；yi∈Rn為與xi相對應的輸出向量；N為數據點總數.SV M通過下式進行函數回歸估計

式中：ω，φ為m 向量；“·”表示特征空間中的點積；b∈R為閾值.SV M采用最小化結構Rstr來確定參數w和b，即

同時引入松弛變量ξi和ξ＊i（i＝1，2，…，l），式（2）可改寫為

上式便是SVM的原始問題，可以看出原始問題是一個有線性約束的二次規劃問題.根據強對偶定理，引入 Lagrange乘子αi和αi（i＝1，2，…，l），建立Lagrange函數，并對w，b，ξi和ξ＊i求偏導并令其為0，于是得到上述SV M原始問題的對偶問題為

式中：K（xi，yi）＝［φ（xi）·φ（xj）］為核函數，其作用是不必知道從低維輸入空間到高維特征空間非線性映射φ（x）的具體形式，通過引入核函數就可得到決策回歸方程.常用的核函數主要有

多項式函數 K［x，xi］＝［x·xi＋1］q

本文選用的核函數是RBF函數［3］，其中δ為RBF函數的寬度函數.設對偶問題的解為ˉα＝根據SV M的稀疏性一對αi和最多只有一個不為零，即2，…，l）且只有少數可不為零，這些不為零的參數所對應的輸入向量xi稱為支持向量，則決策方程只由支持向量決定，與非支持向量無關.決策回歸方程式（1）可改寫為

式中：xi為訓練年份影響因子向量；x為預測年份的影響因子向量；f（x）為指標集合向量.式（7）即為SVM的交通量預測模型.

由上述可知，SV M的參數主要為懲罰系數C、損失函數參數ε和RBF核函數參數δ2，它們的選擇在很大程度上影響著SV M的預測精度和泛化性能，只有正確選擇參數，才可以使SV M回歸估計得到較好的擬合效果［4］，因此為了提高SV M預測模型的預測精度和泛化性能，本文利用CHEGA進行參數С，ε和δ2的優選.

2 混沌映射

式中：x（i）為變量x在第i次的迭代值，其中u是控制參量.

理論上已經證明當u≥4時系統完全處于混沌狀態，所以x（0）可任意設為［0，1］區間內的初值，但不能為0.25，0.5和0.75，然后根據式（9）得到混沌變量［6］.

圖1給出了n＝500，u＝4，x（0）＝0.45時混沌變量的分布情況.圖2給出了n＝500一般隨機均勻分布系統產生的均勻隨機變量分布情況.

圖1 Logistic映射混沌變量圖

圖2 均勻分布隨機變量圖

從圖1和圖2可以看出，Logistic混沌映射軌道點能夠布滿整個區域的內部和邊界，并且區域的內部和邊界的軌道點的數量分布比較均勻，而均勻分布點雖然能夠布滿整個區域，但多分布在區域的內部，在區域的邊界上的數量分布很少.在大量的非線性優化問題中，最優點的分布可能在區域的內部，也可能在邊界上，因此采用Logistic混沌映射來生成初始群體，并利用混沌變異改進的混沌高效遺傳算法，能夠更好地搜索整個區域，保持種群的多樣性，進行精細搜索.

3 CHEGA－SV M交通量預測模型算法

式中：n為輸入樣本個數；Y1（t）為SV M 擬合序列；Y（t）為實際序列值.基于CHEGA優化CHEGA－SV M交通量預測模型的計算步驟如下.

步驟1 樣本數據和參數初始區間歸一化.對輸入的樣本數據和參數的初始化區間進行歸一化處理，歸一化方法如下.

式中：b（j）和a（j）分別為第j類數據取值范圍的最大值和最小值.

步驟2 混沌隨機父代群體初始化.由Logistic混沌映射在參數初始區間內生成初始父代群體，m 個初始父代群體記為y（j，i），（j＝1，2，3；i＝1，2，…，m），其中y（j，i）為第i個父代個體上的第j個基因，本文取m＝50，u＝4.0，y（j，0）＝0.7.

步驟3 父代個體的適應度評價.將第i個父代個體的基因作為SV M參數，以訓練集樣本為輸入輸出，對SV M模型進行訓練，將SV M訓練結束后返回的輸出序列方差Q的倒數作為第i個父代個體的適應度值F（i）＝1／Q.

步驟4 選擇操作.產生第1個子代群體｛y1（j，i），j＝1，2，3；i＝1，2，…，m｝，取比例選擇方式，則父代個體y（j，i）的選擇概率為ps（i）＝

CHEGA優化SV M參數問題可以轉化為如下最小化問題則 序 列｛p（i），i＝1，2，…，m｝把［0，1］區間分成m 個子區間，生成m－5個隨機數｛u（k），k＝1，2，…，n－5｝，若u（k）在［p（i－1），p（i）］中，則第i個個體y（j，i）被 選 中，即 y1（j，k）＝ y（j，i），為 增 強CHEGA進行全局優化搜索能力，這里把最優秀的5個父代個體直接加入子代群體中，即進行移民操作

步驟5 雜交操作.產生第2個子代群體｛y2（j，i），j＝1，2，3；i＝1，2，…，m｝，根據選擇概率隨機選擇一對父代個體y（j，i1）＝y（j，i2）作為雙親，并進行如下隨機線性組合，產生一個子代個體y2（j，i）

式中：u1，u2，u3都為隨機數，通過雜交操作，共產生m個子代個體.

步驟6 混沌變異操作.產生第3個子代群體｛y3（j，i），j＝1，2，3；i＝1，2，…，m｝，CHEGA的混沌變異操作采用自適應變異概率pm（i）＝1－p（i）來代替個體y（j，i），從而得到子代個體y3（j，i），即

式中：u（j）為混沌變量；um為［0，1］區間上的均勻隨機數.

步驟7 演化迭代.由步驟4到6得到的3m個子代個體，按照其適應度值F＊（i）從大到小進行排序，判斷當前種群中最優個體是否滿足終止準則，若滿足轉入步驟9，否則取排在最前面的m個子代個體作為新的父代群體.然后轉入步驟3進入下一輪演化過程.停止準則采用最大進化代數Gmax與相鄰進化代數最優個體適應值相對誤差E相結合.

步驟8 引進加速遺傳算子.每演化迭代兩次，取進化得到的6m個子代個體中的m個優秀個體的變化區間作為新的初始變化區間，轉入步驟2，重新開始迭代過程.

步驟9 訓練模型輸出預測結果.以當前種群中具有最大適應值的個體的染色體基因С，ε和δ2作為SV M參數訓練模型，輸入待測樣本，輸出預測值.

計算流程見圖3.

4 模型仿真驗證

4.1 CHEGA－SVM交通量預測模型的訓練與預測

結合某市客運量統計數據進行仿真驗證，指標集為1978～2008年全市客運量，經相關性分析得出影響因子集為1978～2008年全市消費品總額、人均收入、能源總量、生產總值、汽車擁有量和總人口.在總體樣本中抽取1982、1986、1990、1995、2001、2007年的影響因子和指標作為測試集，其余為訓練集，應用CHEGA－SV M交通量預測模型分別進行訓練和預測.

利用Matlab 7.1編制模型程序，運行環境為：Core（T M）2CPU，1.81 MHz，2 GB內存的微機.操作系統：Windows XP.仿真中，С的取值范圍為［0.01，200］；ε的取值范圍為［0.01，0.8］；δ2取值范圍為［0.01，50］，最大進化代數Gmax＝100，鄰代最優個體適應值相對誤差E＝0.000 01.為了驗證模型的使用性能，同時選用基于GA優化的GA－SV M模型和基于梯度下降法的傳統BP神經網絡模型進行對比仿真預測，并采用以下三個評價指標進行預測性能對比分析.

圖3 算法流程圖

式中：Y1（t）為 SV M 擬合序列；Y（t）為實際序列值；n為檢驗數據個數.

結合實測數據，進行模型訓練和客運量仿真預測，圖4為CHEGA－SV M交通量預測模型訓練曲線，由圖4可以看出訓練輸出和實際值擬和的較好，擬合平均絕對相對誤差為2.42%，擬合均方根誤差為3.21%，說明CHEGA－SV M交通量預測模型對客運量的歷史序列擬合較穩定.

圖4 CHEGA－SV M模型訓練圖

利用得到的CHEGA－SV M交通量預測模型對1982、1986、1991、1996、2002、2007年的客運量進行預測.圖5為CHEGA－SV M交通量預測值與實際值對比圖，仿真預測平均絕對相對誤差為2.92%，仿真預測均方根誤差為3.89%.

圖5 CHEGA－SV M模型預測圖

4.2 CHEGA－SVM交通量預測模型性能對比分析

將預測得到的客運總量與傳統BP神經網絡模型和GA－SV M模型仿真預測結果進行比較分析，其中BP神經網絡模型選擇的是單隱層BP神經網絡，BP神經網絡參數：最大迭代次數為100次，隱層節點數為7，學習率為0.25，允許的平方根誤差為0.000 1；GA參數：種群大小為50，進化最大代數為100，交叉概率Pc為0.55，變異概率Pm為0.005.仿真預測值如表1所列.

表1 CAGA－υ－SVR與其他3個模型的預測比較

將表1中數據按式（15）、（16）和（17）分別進行誤差指標處理，處理結果如表2所列.

表2 仿真預測誤差指標比較 %

從表2中可以看出，在對基于不同結構預測模型的仿真預測結果對比方面，SV M模型的仿真預測結果要優于傳統的BP神經網絡模型；對采用不同的算法進行參數優選的SV M模型對比方面，基于混沌高效遺傳算法優化的SV M模型的預測精度優于采用傳統遺傳算法優化的SV M模型.

5 結束語

本文提出了基于CHEGA進行參數優選的CHEGA－SV M交通量預測模型，并結合實際數據進行了仿真驗證，對比結果表明：（1）改進的混沌高效遺傳算法可以遍歷到整個區域的內部和邊界，較好的保持了種群的多樣性，提高了參數的優選精度，同時利用優秀個體群逐步縮小搜索空間，加快了尋優速度.利用混沌高效遺傳算法優選SV M模型的參數，克服了SV M模型參數確定難度大、精度低的問題，增強了SV M模型的泛化能力；（2）應用CHEGA－SV M交通量預測模型進行交通量仿真預測，模型的仿真預測精度優于GASV M模型和傳統BP神經網絡模型，平均絕對相對誤差控制在3.0%以內，提高了城市交通量的預測精度，說明采用該模型對城市交通量的預測是可行的；（3）本文提出的CHEGA－SV M交通量預測模型，應用于城市交通量的預測，可以為公路建設項目的設計、施工和管理及相關政策、法規的出臺提供科學的參考依據.

［1］Ki m Kyoung－jae.Financial time series forecasting using support vector machines［J］.Neuron co mputing（S0925－2312），2003，55：307－319.

［2］Vapnik V N.An overview of statistical learning Theory［J］.IEEE Transactions on Neural Networ ks（S1045－9227），1999，10（5）：988－999.

［3］Keerthi K，Lin C J.Asy mptotic Behaviors of Support Vector Machines with Gaussian Kernel ［J］.Neural Computation，2003，153 （3）：1 667－1 689.

［4］Cher kessk V，Yunqian M A.Practical selection of SV M parameters and noise estimation for SV M regression［J］.Neural Networ ks，2004，17（1）：113－126.

［5］Rettemeir K，Falkenhagen B，Kongeter J.Risk assessment new trends in Ger many［C］／／ICOLD.The Proceedings of 21t h Int Congress on Lar ge Dams.Beijing：the Inter national Co mmission on Lar ge Dams，2000：625－641.

［6］Liu B，Wang L，Jin Y H，et al.Impr oved particle swar m optimization combined with chaos［J］.Chaos Solutions and Fractals，2005，25（5）：1 261.