基于狀態空間模型的智能優化算法及其應用

李雪　李茂軍　王鼎湘　成立　張家臣

摘 要：針對城市公共交通系統中公交優化調度問題的具體特征，提出一種基于狀態空間模型的實數編碼智能優化算法（SIA）。SIA引入遺傳算法（GA）的基本理念。通過構造狀態進化矩陣來指導算法的搜索方向，再通過選種池的優勝劣汰的選擇機理來實現算法朝最優解逼近。將該算法與GA分別應用到公交優化調度問題中，考慮發車時間間隔的約束，建立以企業和乘客的利益最大化為目標的數學模型。實例仿真結果表明，SIA在尋優精度和計算量方面優于GA，驗證了該算法的有效性。

關鍵詞：公交調度；時間間隔；狀態空間模型；狀態進化矩陣；選種池

中圖分類號：U491.2TP18 文獻標識碼：A

Abstract：An intelligent optimization algorithm with real strings based on state space model （SIA） was presented to solve bus dispatching problem in urban public transport system. The basic idea of genetic algorithm （GA） was introduced to SIA. The state evolution matrix was constructed to guide the search direction of the algorithm， then through the selection mechanism of selection pool to approach optimal solution. This algorithm and GA were applied to the public transport optimization dispatching problem. Mathematical model was set up by considering the time interval，and the benefit maximization of enterprises and passengers. The results of example simulation show that SIA is better than GA in optimization accuracy and amount of calculation.

Key words：pubic transport dispatching；time interval；state space model；state evolution matrix； selection pool

1 引 言

隨著現實世界中交通擁堵情況日趨嚴重，調節城市公共交通運營工作成為舒緩交通狀況、改善城區生活質量的重要手段之一。城市公共交通運營工作可以轉化為公交優化調度問題進行處理，而本文以公交線路發車間隔的設定來進行公交優化，即要求在一個調度周期（公交線路一天的運營時間）內，根據車流情況，在滿足整體社會效益和經濟效益的情況下，優化各時段的發車時間間隔，以使得公交公司和乘客花費成本最低。隨著對公交優化調度問題研究的不斷深入，國內外許多學者提出了大量方法來解決該問題，取得了一定的成果。如Qing和Han[1-2]等人從發車間隔對公交系統的影響出發，提出用遺傳算法進行公交車發車時間間隔優化；Gong和Cheng[3-5]等人了改進型遺傳算法用以優化發車頻率問題；文獻[6]通過兩種算法融合，采用優勢互補的特點為優化公交調度問題提供了一種有效途徑；文獻[7-9]則分別介紹了不同算法在求解公交調度問題最優解過程中的方法。

以上所提及的優化方法對于本文進行優化公交車調度問題具有重要的指導意義。本文提出一種基于離散系統狀態空間模型的實數編碼智能優化算法[10]。由于狀態空間模型的引入不僅能把種群信息以最小信息形式描述出來，而且還能清楚顯示算法迭代尋優過程中個體的狀態變化，因而該模型可以將問題的求解過程表示為動力學求解過程。基于此，該算法通過構造一個狀態進化矩陣來替代遺傳算法中的交叉與變異算子功能來產生一組進化解。通過選種池的選擇作用產生較優解。相比于遺傳算法易陷入早熟停滯、計算量大和局部搜索能力差等缺點[11]，本文提出的算法具有計算量較小、計算精度較高、計算速度較快等特點。最后給出一個公交車發車時間間隔優化實例，仿真結果驗證了這種算法的有效性。

2 基于狀態空間模型的智能優化算法

2.1 概述

近年來，國內外有不少學者熱衷于用不同的方法來解決公交調度優化問題。其中，遺傳算法成為人們尋求解決優化問題的重要途徑，它通過迭代執行選擇、交叉、變異三個遺傳算子的遺傳操作，使問題的解逐步向最優解方向靠近。本文提出的基于狀態空間模型的實數編碼智能優化算法是一種以離散系統狀態空間模型為基礎，引入遺傳算法理念的優化算法。它將實數編碼問題的解方便地以狀態空間模型的方式表示，使得問題的求解過程更直觀、高效。

基于狀態空間模型的智能優化算法將問題的求解過程表示為離散系統的動力學求解過程，即X′（k+1）=GX（k）（1）其中，狀態向量X（k）表示為第k代群體，它是一個N×M矩陣（N表示為種群中個體總數量，M為每個個體包含的變量數）。G為狀態進化矩陣（N×N方陣），G的構造是本算法研究的核心內容，可以依照遺傳算法的基本思想構造。本文以遺傳算法的基本理念構造G，此矩陣替代了在遺傳算法中起交叉、變異的遺傳操作。本算法采用在約束范圍內隨機生成的方式來產生初始群體X（0），再通過G矩陣生成群體X′（1），即種群X（k）通過G矩陣生成新的種群X′（k+1）（k=0，1，….）。在種群X′（k+1）中判斷其個體是否滿足算法約束條件，若不滿足，則需進行約束處理，再將包含X（k）與X′（k+1）的共2N個投入選種池。選種池是依照遺傳算法中優勝劣汰的思想啟發而設計，通過計算2N個個體適應度函數值選擇適應度值較大的N個個體組成新一代群體X（k+1），再置X（k+1）為X（k），如此循環迭代，直到滿足停機條件后結束，如圖1所示。

3 SIA用于公交優化調度

3.1 公交優化調度問題的數學描述

1）模型假設條件

公交發車時間間隔模型的建立要考慮到多種因素的影響，如公交公司滿意度、乘客滿意度、運行環境等。在同一時段內，若發車間隔較短，公交公司發車次數較多，平均每輛車的載客量減少，環境污染指數升高，不利于公交公司的經濟效益和社會效益；若發車間隔較長，乘客平均等待時間較長，乘客的時間損失較大，會影響乘客的情緒，車內人流擁擠，也會影響乘客的舒適度，從而進一步影響乘客一天的生活和工作質量，乘客損失費用較高；若公交車運行環境擁擠，平均每輛車走完全程耗時相對較多，影響公交公司和乘客的整體利益，應適當的調整發車間隔，以舒緩城市交通環境。綜上所述，本文對此模型作如下假設：

（1）公車各時段運行環境良好，且營運期間無特殊狀況發生；

（2）公車運行期間為恒速行駛；

（3）公車額定載客人數相同；

（4）公車運營一趟的成本為固定值；

（5）同一時段公車發車頻率相同；

（6）各時段內到達站點的乘客服從均勻分布；

（7）將乘客上下車時間算入等車時間；

（8）全程實行統一票價，票價2元/人。

2）數學模型的建立

從以上仿真結果可以看出，在α=0.7的情況下，即充分考慮公交公司利益時，發車間隔明顯比其他兩種情況大；α=0.3時，充分考慮乘客利益，發車間隔明顯比其他兩種情況小，符合現實情況。同時，根據表2中的客流情況可以看出，時段1和時段4的客流量相對較大，在仿真結果中，這兩個時段的發車間隔整體較其他時段小，達到了根據客流合理分配發車間隔的目的。對比GA和SIA優化的發車間隔及其對應的目標函數，可以看出SIA的優化結果明顯優于GA，SIA有效性得到驗證。

相較于傳統遺傳算法，SIA的優勢在于，通過狀態空間模型中矩陣的乘法操作來搜索可行域區間，替代了GA的交叉和變異操作，也在一定程度上減小了算法的計算量。同時，SIA采用實數編碼，雖然需要對連續的可行域區間進行離散化，但離散化的計算量較小。而一般情況下，GA采用二進制編碼，編碼長度決定了算法的尋優精度，精度要求越高，算法編碼越長，過長的二進制編碼在解碼的過程中大大增加了算法的計算量，影響算法效率。故在對尋優精度要求更高的情況下，SIA的優勢更加突出。

5 結 論

本文針對公交車調度優化中傳統智能算法的不足，提出了一種基于離散系統狀態空間模型的實數編碼智能優化算法。主要分析了SIA相較于GA在尋優精度和計算量方面的優勢。仿真結果表明，在相同的算法條件下，SIA的優化結果明顯優于GA，驗證了SIA的有效性。參考文獻

[1] 韓印.基于遺傳算法的智能公交發車頻率優化研究[J].計算機工程與應用，2008，44（33）：243-245.

[2] 覃運梅，王玲玲.基于遺傳算法的公交發車間隔模型[J].交通標準化，2009，（2）：190-192.

[3] 龔成清.改進遺傳算法在公交調度優化中的應用[J].微型電腦應用，2012，28（10）：48-51.

[4] 陳玲玲，蘇勇.改進遺傳算法在公交車優化調度中的應用[J].科學技術與工程，2009，9（12）：3567-3569.

[5] Jinling Du， Chunxiao Wang， Feng Zhang. Multi-objective Optimization of Bus Dispatching Based on Improved Genetic Algorithm[C]//2011 Seventh International Conference on Computational Intelligence and Security.China：IEEE，2011.

[6] Minan TANG， Enen REN， Chunyan ZHAO. Route Optimization for Bus Dispatching Based on Genetic Algorithm-Ant Colony Algorithm[C]//2009 International Conference on Information Management， Innovation Management and Industrial Engineering.China：IEEE，2009.

[7] 付阿利，雷秀娟.粒子群優化算法在公交車智能調度中的應用[J].計算機工程與應用，2008，44（15）：239-241.

[8] 王敏.免疫克隆算法求解公交發車頻率問題[J].計算機應用研究，2010，27（12）：4483-4485.

[9] 白子健.快速公交線路組合頻率優化的禁忌模擬退火算法仿真[J].計算機應用研究，2008，25（2）：355-358.

[10]李茂軍，賈玲. 一種基于狀態空間模型的進化算法[J]. 計算技術與自動化. 2014，33（2）：85-88.

[11]江中央.求解全局優化問題的混合自適應正交遺傳算法[J].軟件學報，2010，21（6）：1296-1307.