基于IGA-IBP算法的高速公路逃費預測

李松江，周 舟，李巖芳，王艷春，宋小龍，王 鵬

(長春理工大學 計算機科學技術學院，吉林 長春 130022)

0 引 言

當前，對于高速公路惡意逃費問題，研究學者都有著不同深入的研究。薛[1]將數據挖掘技術引入收費稽查中并建立系統模型；趙等[2]采用聚類分析、判別分析和邏輯回歸分析融合的方法；吳等[3]利用數據挖掘k-means技術研究高速公路的逃費問題。

高速公路收費數據量大且復雜度高，收費管理方式缺乏完善[4]，傳統的算法難以處理。對于高速公路逃費的預測問題，在結合高速公路的收費數據特征下，本文提出一種基于改進的遺傳算法和優化的神經網絡的IGA-IBP算法模型，首先選取6個黃金分割變異算子，迭代出適應度函數的最優解，得到最優初始權重值；然后分步動態調整神經網絡模型的學習率，考慮隱含層和輸出層學習率時加入上一次學習率的變化影響，這使得模型可以加快收斂速度和減小誤差，對高速公路收費數據，利用ReliefF算法[5]提取出車輛逃費行為的主要特征作為該算法的輸入，建立神經網絡模型實現對車輛逃費預測。

1 IGA-IBP神經網絡模型

遺傳算法通過模擬自然進化過程的生存方式，是一種隨機性的全局優化算法[6]，經過選擇、交叉和變異后可以得到最優解。經典的遺傳算法容易陷入“早熟”[7]，不能及時跟蹤網絡的反饋信息，搜索速度慢，處理高速逃費預測這種非線性問題穩定性較差。傳統的BP算法滿足不了高速公路收費數據的復雜性，全局搜索能力差，輸入層、隱含層和輸出層在權值和閾值修正過程中學習率β總是一成不變。當β過小時，模型調整較小，逃費預測速度過慢；當β過大時，預測誤差函數值較高，容易在最優解處發生振蕩，導致出現局部最優解以致模型難以收斂[8]。針對此問題，本文提出IGA-IBP算法，通過改進遺傳算法的變異算子、分步調整BP神經網絡各層間的學習率并考慮前一次學習率影響因子，以及動態調整車輛行駛時間來提高算法對高速公路逃費的預測準確率和穩定性。

1.1 算法設計

遺傳算法中的變異算子對種群優化起重要作用，種群如果失去多樣性，則過早收斂[9]，優化質量低。因此遺傳算法優化時，如何維持種群的多樣性是關鍵問題。本文為了保持種群多樣性，在基本的兩個黃金分割點基礎上提出多個黃金分割變異算子優化傳統遺傳算法，可以獲得進化中的優良新個體，保持群體多樣性。對于多元優化自變向量分量xk,k=1,2,…,n，這2n-1條邊界按照式(1)的黃金分割法的思路尋求新的迭代空間會大大縮小計算量，考慮到種群的迭代過程變化趨勢，本文選取6個黃金分割變異算子，種群中的個體迭代可以如下表示

(1)

遺傳算法進化過程中群體向著更優的目標函數進化，第m代個體進化可以按照以上6種原則進化。對種群個體進行迭代，將待求解的目標函數轉化為適應度函數，適應度函數根據平均值和方差比構建，適應度函數越大個體越好，適應度函數越小個體越差，選擇出6個黃金分割點的適應度函數的最大值，即

(2)

依次迭代個體的適應度函數與上一代的最優解比較，若當前解優于上一代最優解則替換原來的最優解，否則繼續迭代個體并判斷找出最優解。替換原來最優解后，繼續迭代多次比較，最終找出目標最優解。

傳統的BP神經網絡學習率與誤差函數關系較大[10]，其學習率在運算過程中不變會影響模型的性能。針對這種現象，本文采用一種分步動態調整不同層間學習率的方法，即分別對隱含層學習率β1和輸出層學習率β2調整，并考慮前一次學習率的變化影響。在此方法中，隱含層學習率β1(m)和輸出層學習率β2(m)修改公式如下

(3)

(4)

式中：β1(m+1)表示在第m+1次迭代時訓練樣本的隱含層學習率，β2(m+1)表示在第m+1次迭代訓練時訓練樣本的輸出層學習率，ΔE(m)/E(m)表示訓練樣本在第m次迭代訓練時的均方誤差變化率，μ是常數，取值范圍為[0,1]，本文實驗調優后取值為0.6，Δβ1(m-1)表示m前一次的隱含層學習率，Δβ2(m-1)表示m前一次輸出層的學習率。

當ΔE(m)>0時，表明誤差函數增大，輸出預測值與期望值相差過大，權值調整偏大，需要減小輸入層到隱含層的權重以及隱含層到輸出層的權重。同時可以看出，β1(m+1)<β1(m),β2(m+1)<β2(m),β1(m)和β2(m)減小，可以加快收斂速度；當ΔE(m)<0時，表明學習誤差減小，輸出預測值與期望值相差不大。因此可以適當提高輸入層到隱含層和隱含層到輸出層的權重。由于此時誤差很小，ΔE/E比ΔE要大很多，因此當β1(m+1)>β1(m),β2(m+1)>β2(m),β1(m)和β2(m)增大，收斂速度同樣也加快。在學習率變化的同時考慮前一次學習率的影響，使得學習率連續變化，增強算法的可靠性。

1.2 IGA-IBP算法操作過程

通過1.1節分析，IGA-IBP算法如下，其具體實現步驟如下：

(1)編碼方式和種群初始化

考慮權重值的精度要求高，因此采用浮點數編碼方式。隨機產生一組具有N個個體的種群M=(M1,M2,…,Mn)T，種群中每個個體代表一個神經網絡的初始權值分布，個體的長度為神經網絡權值的個數，即

L=m×n+n×h+n+h

(5)

其中，m表示輸入層隱含層神經元個數，n表示隱含層神經元個數，h表示輸出層神經元個數。

(2)確定適應度函數

計算初始種群中每個染色體的適應度值，并定義適應度函數fit(x)。待求解的目標函數f(x)轉化為適應度函數fit(x)，目標函數求最大化問題時，fit(x)=f(x)，解最小化問題時，fit(x)=-f(x)。

(3)個體選擇

個體的選擇即是個體的概率值計算，采用輪盤賭選擇，每次為新種群挑選出新的個體，公式如下

(6)

其中，k為種群個體數目。

(4)交叉操作

使用交叉概率pc對兩個個體進行交叉操作，產生兩個新的個體。交叉概率計算公式如下

(7)

式中：f表示個體的適應度，favg表示種群中所有個體的平均適應度，fmax表示種群中個體適應度的最大值。通常pc1取0.8，pc2取0.6。

(5)變異操作

分別計算式(2)變異點的適應度值，找出最大點。用變異概率pm計算式(1)優化產生新的個體。根據經驗本文初始化變異概率pm=0.08。

(6)循環終止操作

在遺傳算法優化神經網絡權值中，達到最小目標函數或者完成迭代次數后訓練停止，否則重復步驟(2)～步驟(5)。

(7)將改進后的遺傳算法操作完成后得到的最優個體作為神經網絡的初始權重值，然后按1.1節中的改進的BP算法對神經網絡進行訓練，得到預測結果。

算法流程如圖1所示。

圖1 算法模型流程

2 IGA-IBP逃費預測模型數據分析

2.1 特征選取

高速公路收費數據包含許多特征屬性，見表1，算法輸入相關性不大的特征會降低模型的準確率，因此需清洗臟數據，選出合理的特征屬性[11]。

表1 特征屬性標號及對應的名稱

本文采用ReliefF算法處理逃費問題的IGA-IBP算法的特征選擇問題，得到的32個屬性特征權重值如圖2所示。

圖2 不同特征屬性權重值

由圖2可以看出，收費數據特征屬性值的權重不同，標號3,4,7,9,10,12,13,14,18,23,24,30的權重值比較高，均在0.08以上，這些特征屬性對于逃費預測判斷至關重要。而其它特征屬性的權重值較小，屬于臟數據，可以刪除。因此，本文選擇車輛入口牌照號、車輛出口牌照號、出站車型、出口日期、出口時間、入口日期、入口時間、IC卡編號、入口車型、軸數、軸總重、收費額作為IGA-IBP模型的特征向量。

2.2 車輛動態行駛時間計算

司機在高速公路上駕駛速度不一，因此車輛到達收費站的時間不同。有司機因為“跑長買短”出現超時情況，但是實際中一些超時的異常情況跟逃費行為無關，例如在服務區停留休息、道路發生車禍和天氣原因等。因此選定一個合適的時間閾值對于模型的預測準確率有很大影響。高速公路的行駛時間主要由兩方面決定：在非擁擠道路上的行駛時間和堵車排隊等候時間。將路段S分成AB和BC兩段，AB為非擁擠路段長度，BC為擁擠排隊路段長度，若無擁擠現象，則S=AB；若發生擁堵情況，則BC=S-AB，其具體表達式如下

(8)

其中，mi表示排隊的第i種車的數目，di表示第i種車所占的空間長度，n表示排隊的車的類型數。非擁擠道路中，假設第i種類型的車輛行駛速度為vi，則車輛在路段AB上的行駛時間為

(9)

車輛在堵車排隊向前移動直到排隊結束的時間是動態變化的，排隊時間可以認為車輛C前面排隊的每輛車與其相鄰的前一車向前移動的時間間隔λi之和，可以表達為

(10)

式中:L代表車輛C到達排隊隊尾時車輛的排隊隊長。因此，路段S的行駛時間為

(11)

2.3 數據歸一化處理

從原始高速公路數據庫中通過結構化查詢語句獲取的數據，具有不同的量綱和量綱單位，這往往會影響數據分析的結果，因此需要對數據預處理。本文只需對軸總重數據歸一化，采用min-max標準化，對原始數據線性變換，使結果值映射到(0,1)之間。其公式如下

(12)

其中，X′為數據歸一化結果，X為原始數據樣本，Xmax為樣本數據中的最大值，Xmin為樣本數據中的最小值。根據式(12)計算得出軸總重的歸一化數據，見表2。

2.4 模型參數選擇

根據高速公路收費數據中已有的車輛通行時間，通過式(11)得出動態車輛行駛時間，并與車輛在兩站之間行駛的平均時間比較，如果未超時用0表示，否則用1表示；進站車牌和出站車牌相同用0表示，否則用1表示；進站車型和出站車型相同用0表示，否則用1表示；車輛根據軸數和載重量判斷是否超重，如果未超重用0表示，否則用1表示；車輛進站和出站的通行卡相同用0表示，否則用1表示；收費額比正常通行費低用1表示，正常用0表示。高速公路收費數據處理后的神經網絡模型所需特征向量見表3。

表2 軸總重歸一化前后數據

表3 神經網絡特征向量

依據上述描述，輸入層特征個數為7個，輸出層特征個數為1個。根據多次調試后，三層結構對于兩層結構預測結果相差不明顯，但是訓練時間和復雜度明顯提升。因此，隱層最終選擇兩層。隱藏層神經元個數參考式(13)，利用試湊法最終確定第一層神經元個數為26，第二層神經元個數為14

(13)

式中：n為隱層神經元個數，m為輸入層神經元個數，s為輸出層神經元個數，a為一個0～10之間的常數。本文經過多次調優后，n確定為11。學習率大小調整依據1.1節方法調節輸入層到隱含層和隱含層到輸出層的學習率。對于二分類預測和輸出在[0,1]的特點，激活函數選擇非線性函數sigmoid，損失函數使用交叉熵函數。

3 實驗與分析

3.1 實驗數據

實驗數據采用吉林省2014年的數據，根據“留出法”和實例完整度將總共篩選出的846 533條數據劃分成兩部分，80%作為訓練集，20%作為測試集。

3.2 評價指標

實驗通過算法模型的準確率這個量化的指標對神經網絡模型進行評價，計算公式如式(14)所示，對于分類問題，召回率也是重要的評價指標，即所找出的逃費數量占樣本總數的比例，對于召回率其計算公式如式(15)所示

(14)

(15)

其中，TP(true positive)表示將正類預測為正類數，FN(false negative)表示正類預測為負類數，FP(false positive)表示負類預測為正類數。

綜合考慮準確率和召回率，計算公式如下

(16)

在不同問題中的準確率和召回率重視程度不同，本文希望盡可能的少遺漏逃費車輛，召回率更重要，因此確定β>1。對于模型的運行速度，可以通過平均檢測時間(MTTD)指標，MTTD值越小，模型預測速度越快。

均方根誤差(RMSE)、平均絕對誤差百分比(MAPE)和相關系數R2可以用來進一步驗證模型的性能。其公式如下

(17)

(18)

(19)

其中，n表示數據集，xm表示測得的數據值，xp表示預測值，xmean表示均值。

3.3 實驗結果與算法對比

根據IGA-IBP算法結合TensorFlow1.0框架對 2014年的高速公路收費數據進行訓練。數據分類預測模型算法較多，為了驗證IGA-IBP算法預測結果的性能，本文選取了決策樹(decision tree，DT)、K最近鄰(K-nearest neighbor，KNN)、IGA-BP和GA-IBP算法的預測模型與提出的IGA-IBP模型對此。

不同算法模型在高速公路逃費預測方面的準確率如圖3所示。從圖中可以看出，5種算法模型均有較高的準確率，但算法中的IGA-IBP算法準確率最高，到達95.1%。因為該算法動態調整學習率使得損失函數最優，改進的遺傳算法加快網絡結構收斂速度，同時也優化了BP神經網絡的初始值。

圖3 不同算法模型準確率對比

不同的需求需要采取不同的方法，本文根據實際情況以及3.2節的描述，在β的取值范圍中，令β=2，根據式(16)計算各模型的Fβ值。表4是各模型在訓練集上Fβ和MTTD參數對比。對于IGA-BP算法、GA-IBP算法和IGA-IBP算法中的GA存在隨機操作，每次操作得到的數據不同，例如運行時間等，因此，本文實驗室結果為多次實驗后的平均值。

表4 算法模型參數對比

從表4可見，各組中IGA-IBP算法的Fβ值是最大的，表明IGA-IBP模型在準確率和召回率兩方面是最平衡的，預測時間MTTD為215 s，預測耗時小，模型運行速度快。KNN模型的Fβ值相比其它模型最低，運行速度最慢，可見，針對本文數據預測，KNN模型性能最差。IGA-BP和DT模型Fβ值和運行速度比較接近，兩者表現整體在訓練集上不相上下，GA-IBP模型雖然Fβ值較高，但是運行時間過長，原因是GA-IBP模型全局搜索能力較弱。

對于各個算法模型的在訓練集和測試集上的參數性能對比，見表5。

從表5可以看出，考慮預測模型的RMSE值時，DT、KNN、IGA-BP、GA-IBP和IGA-IBP測得的值分別為0.47、0.48、0.36、0.22、0.20，IGA-IBP均方根誤差最小，對于MAPE，IGA-IBP的Test值為4.14也是最小的，這些值說明了IGA-IBP偏差程度很小，收斂速度快，具有很高的一致性。另一方面，預測模型的相關系數R2,DT、KNN、IGA-BP、GA-IBP和IGA-IBP對應的值分別為0.71、0.63、0.76、0.88、0.91，從此處指標可以說明IGA-IBP訓練值和預測值有很高的相似度，預測逃費的值與測量值更接近，得出的預測結果更準確。

表5 不同算法模型的評價比較值

通過以上分析，IGA-IBP比其它算法模型在綜合評價指標Fβ方面更優，在高速公路逃費數據的訓練集和測試集方面兩者誤差比很小，而精確度高，IGA-IBP神經網絡加快了收斂速度，較高的相關系數對于IGA-IBP則表現出模型具有很好的泛化能力。因此將IGA-IBP模型運用在高速公路逃費實際預測上是可行的。

4 結束語

本文基于高速公路傳統逃費預測方法準確率和可靠性低下，人工稽查效率低下、漏查等問題提出了IGA-IBP算法，首先優化遺傳算法，提出6個黃金分割變異算子，找出最優初始權值；其次，改進BP神經網絡算法，分步動態調整輸入層和隱含層之間的學習率，考慮上一次學習率的變化影響，而不同車輛到達收費站的行程時間特征屬性不同，因此需動態計算車輛行駛時間。實驗結果表明，本文提出的IGA-IBP算法調高了學習速度和預測準確率，在RMSE、MAPE和R2性能均優于傳統的算法，對交通部門的決策有著重要的意義。