一種改進公交調度算法的研究

陳 艷，刁志剛

（淮安信息職業技術學院 江蘇 淮安 223002）

隨著世界城市化進程的快速發展，城市人口逐漸增加、人們的社會生活和經濟生活日益豐富，由此對交通的要求也越來越高，智能交通正在不斷改善人們的交通狀況。公共智能交通調度是近年來世界上受人矚目且發展迅猛的應用研究開發領域，所謂智能交通系統（Intelligent Transportation System，ITS），就是通過采用先進的電子技術、信息技術、通信技術等高新技術，對傳統的交通運輸系統及管理體制進行改造，從而形成一種信息化、智能化、社會化的新型現代交通系統。ITS強調的是運輸設備的系統性、信息交流的交互性以及服務的廣泛性。智能交通系統的7大領域包括:出行和交通管理系統、出行需求管理系統、公共交通運營系統、商用車輛運營系統、電子收費系統、應急管理系統、先進的車輛控制和安全系統。由于ITS是將出行者、道路和交通運輸工具三者作為一個整體系統來綜合考慮，因此使交通運輸基礎設施得以發揮最大效能，車輛堵塞和交通擁擠得到有效解決，出行者的安全度和舒適度得到明顯改善，并通過節約能源和保護環境使全社會獲得巨大的社會經濟效益。

文中提出了基于改進遺傳算法的思想構造了公共交通線網發車間隔優化數學模型，將遺傳算法引入到模型求解中，重點對改進遺傳算法應用于城市公交運營優化問題的算法步驟進行闡述。

1 遺傳算法基本原理

遺傳算法主要操作步驟如下:

1）選擇編碼策略，把參數集合X和域轉換為位串結構空間S；

2）定義適應度函數 f（X）；

3）確定遺傳策略，包括群體規模，選擇、交叉、變異算子及其概率。

4）生成初始種群P；

5）計算群體中各個體的適應度值；

6）按照遺傳策略，將遺傳算子作用于種群，產生下一代種群；

迭代終止判定。

遺傳算法涉及6大要素:參數編碼，初始群體的設定，適應度函數的設計，遺傳操作的設計，控制參數的設定，迭代終止條件。

遺傳操作產生后代:遺傳算法在運行早期個體差異較大，當采用傳統的轉輪法時，即認為后代產生的概率和適值大小成正比。這樣會使遺傳算法早期個別好的個體的后代充斥整個種群，造成早熟現象。而在遺傳算法后期，適值趨于一致，優秀個體在后代中優勢不明顯，從而使整個種群進化速度趨于停滯。

計算某一代群體中某個染色體被復制產生下一代的概率:

式中:Ri-第i個染色體的選擇概率；fi-第i個染色體的適值；N-種群中染色體個數；S-溫度；S0-初始溫度；l-遺傳代數。

計算各染色體的累計概率λk:

式（3）在[0，l]區間內產生一個均勻分布的隨機數ξ。如果ξ≤A，則選擇第一個染色體進行復制；如果λk＜ξ≤A，則選擇第ξ個染色體。如此循環N次，就會產生種群規模同樣為N的下一代種群。

2 改進優化遺傳算法描述

在GA的應用研究中，應從兩個方面加以深入:1）如何充分利用GA的特長和優勢，在求解問題時發揮這些優勢作用。這其中也包括充分利用GA現有的改進成果，如已提出的優秀遺傳算子、參數設置方法、遺傳結構及改進的變形GA等；2）如何加強GA的優勢，如提高GA的魯棒性、適應性等?？傊?，以提高GA搜索效率和魯棒性為目的，以GA的結構、基因操作和參數設置都向自適應、自組織形式發展，并進行系統綜合為主要實現方式的GA綜合改進算法的研究是GA應用研究的主要方向。本章基于這一思想，提出一種綜合改進遺傳算法，它的主要特點在于它充分利用已有各種改進算法的優點，將它們和各種優秀遺傳算子綜合在一個GA結構中，取長補短，協同作用，使GA的性能得到大幅度提高。

文中的綜合改進遺傳算法采用了并行結構，共有3個子種群I，II，III。每個種群采用不同的遺傳策略，分別以各自的方式并行執行進化。種群II，III的進化采用SGA結構，分別利用實際應用效果較好的自適應遺傳算法（AGA）和模擬退火遺傳算法（SAGA）執行微進化。為了加快進化速度，除了種群Ⅱ，Ⅲ各自單獨的微進化外，加入了第二層種群間的宏進化。它將微進化過程產生的較好個體保留，組成新的個體集-種群I進行強進化。該個體集以較小的交叉率（足）、變異率（只）進行本地進化的遺傳操作，主要用于局部搜索，以盡快發現最優解。

3 算法的實現

為了提高GA的搜索性能，人們提出了許多改進GA。在以后的研究中，GA的結構、基因操作和參數設置都會向自適應、自組織形式發展并將進行系統的綜合。因此，應將各種不同的改進的GA綜合到一個結構中，取長補短，協同作用，得到功能更強大、性能更優越的綜合改進GA。

在文中的改進GA中，包含了采用不同方法得到兩種各具特色的改進的GA。雖然兩種GA的實現方式不同，但它們的基本思想是一致的，即通過GA進化過程中遺傳算子和參數的自適應改變，使GA在求解不同問題或同一問題的不同階段自動調整各種遺傳因素的作用強度，以更好的適應復雜、變化的環境。首先初始化隨機產生兩個子種群II，Ⅲ。而種群I通過選取II，Ⅲ中的較好個體而產生。

3.1 種群II的進化

種群II采用自適應遺傳算法，在整個進化過程中，Pc和Pm及適應度函數調整方案都隨著遺傳進程作自適應改變。

1）適應度函數的調整

為了保證整個進化過程中適當的選擇壓力，在選擇操作之前，借鑒模擬退火思想對個體適應度進行調整，調整公式如下:

式中fi——調整前第i個個體的適應度；

Fi——調整后第i個個體的適應度；

M一種群規模；

n一遺傳代數；

T—退火溫度；

To——初始溫度，可根據具體情況選擇。

這樣在溫度高對（算法的前期），適應度很高的個體優勢不會特別突出以至產生超級

個體，適應度相近的個體產生后代的概率相近。而溫度不斷下降后，拉伸作用加強，使

適應度相近的個體適應度差異放大，從而使優秀的個體優勢更加明顯，增加了進化后期的選擇壓力，避免了進化遲滯現象。

2）自適應公式的確定

文中采用兩點交叉加高段位突變功能的交叉操作，變異操作采用簡單的位點變異，

同時為防止超級個體的產生，加入了強制變異算子，并使用Sriavivas提出的自適應交叉、變異率。當算法提前收斂時，加大￡和己，而在算法初期減小只和己。同時為保持優良個體，對于高適應度個體采用較低的只和己；對低適應度的個體采用較高的￡和己，以利于較好個體的產生。自適應公式如下:

式中fmax-群體的最大適應度；fˉ-該群體的平均適應度；f′-交叉的兩個個體中較大的適應度值；f-參加變異的個體的適應度值。

3.2 種群Ⅲ的進化

種群Ⅲ采用模擬退火遺傳算法。模擬退火算法和遺傳算法兩種算法都是全局隨機優化算法，它們在傳統的基于梯度的優化方法難以解決的復雜優化問題中顯示了優良的求解特性，得到廣泛研究和應用。雖然遺傳算法有較強的全局搜索性能，但它的爬山能力弱，在實際應用中容易產生早熟收斂的問題，且在進化后期搜索效率較低。而模擬退火算法卻具有擺脫局部最優點的能力，能抑制遺傳算法的早熟現象。因此，考慮將模擬退火的思想引入遺傳算法，有效地緩解了遺傳算法的選擇壓力。為了保持GA的基本特點不變，保留GA的優點，交叉算子未作任何改動，仍然使用自適應交叉率。只是在變異算子中引入模擬退火機制。對任一參與變異的個體，隨機產生一個新個體串，若新個體的適應度高于變異個體，則接受新個體串（即以新個體代替變異個體）；否則，以下面的概率接受新個體

其中 g=1，2，3，…；

f-變異個體的適應度；

f′-隨機產生個體的適應度；

g-隨著進化代數而增加；

T0-初始退火溫度。

3.3 種群I的進化

種群I為保留種群，由種群Ⅱ，Ⅲ中最好的個體構成，各子種群每經過一定的間隔（實驗中取進化8次）選擇各種群中的最好個體構成種群I。這樣，種群I的個體質量將始終保持較高的水平。種群I的作用主要是將3個種群產生的較優個體集中在一起進行“強制進化”，在它們所形成的較優區域內進行小范圍精細搜索，以盡快找到最優解。此時，最優解的區域已基本確定，對算法探索新搜索空間的要求大大下降，應加強算法的局部搜索能力，以算法的利用性為主，提高解的品質。為了防止交叉、變異算子對較優個體的破壞，種群I采用較低的交叉、變異率，以取得類似爬山算子的效果。這里取Pc=0.4，Pm=0.002。由于采用多種群同時進化策略，各子種群以不同的方式并行執行進化以獲得適應不同環境的進化種群；該綜合改進遺傳算法可從不同方向進行搜索，得到各種不同的性能優異的模式和個體。 終止循環的條件采用設定最大代數的方法。

4 流程圖

該遺傳算法的流程圖如圖1所示。

5 模擬試驗

文中以淮安市科技局2011年立項項目 “智能公交站臺預報系統”公交線路1為例。早上第一班車的發車時間是5:30，最后一班車的發車時間是21:30，全天一共運行960分鐘，分為20個時段，每個時段48分鐘。1路車共有20個站點，線路總長為n公里。1路公交車的車型定員為35人。初次選定 α=0.5，β=0.5，種群大小為 500，初始溫度為 500，最大遺傳代數為30。經過多次的模擬實驗，可以得到線路1的由南向北的最佳的發車間隔是6 4 3 2 4 2 4 5 3 4 5 5 2 4 2 5 3 4 5 8。即發車時間依次為:5:30 5:36 5:42 5:48 5:52 5:56 6:00……6:36 6:40 6:43……7:25 7:28 7:30……8:14 8:16 8:20……9:06 9:08 9:52......10:36 10:40 10:45……11:25 11:30 11:33……12:12 12:15 12:19……13:00 13:04 3:09……13:50 13:55 14:00……14:55 15:00 15:02……15:46 15:48 15:52……16:30 16:32 16:36 16:38……17:22 17:24 17:29……18:9 18:14 18:17……18:59 19:02 19:06……19:46 19:50 19:55……20:35 20:40 20:48 20:56……21:22 21:30

圖1 算法流程圖Fig.1 Flowchart of algorithm

用同樣的方法模擬由北向南的調度時間，和由南向北的發車時間大概是一致的，這主要是因為不同方向的客流量是差不多的，這是因力1路車的南邊終點站是汽車南站，北邊終點站是汽車北站和火車站，這于現實情況也是相符的。通過以上簡單的模擬試驗，可以看出，綜合改進的遺傳算法應用在公交調度系統中，可以快速得出調度結果，具有一定的使用價值。

6 結束語

公共交通線發車調度時長主要集中在優化發車間隔、車次多少等。目前任何城市全面構筑智能公共交通系統，特別是公共交通智能化調度系統還有一定的困難，因此實時地確定所有線路的發車間隔還比較困難。如果智能公共交通系統建立在優化的網絡基礎上，會使其發揮更加突出的作用。本文是從公共交通線網發車間隔的調度為出發點，對公交網絡系統進行優化，提出了公共交通線網發車間隔優化數學模型，將遺傳算法引入到模型求解中，實例證明模型和算法具有實用性和可靠性。

[1]Brouwer D R，Jansen J D，Vefring E H，et a1.Improved reservoir mangement through optimal control and continuous model updat—ing[C]//SPE Annual Technical Conference and Exhibition，Houston，Texas，U S A，2004.

[2]Sarma P，Aziz K，Durlofsky L J.Implementation of adjoint solution for optimal control of smart wells[C]//2005 SPE Resevoir Simulaiton Symposium，Houston，Texas，U S A，31 January，2005.

[3]楊曉光.先進的公共汽車交通優先系統結構 （ABPS）[C]//城市交通研究中心，2005.

[4]楊新苗.城市公交發展技術保障體系關鍵技術研究[D].南京：東南大學，2002.

[5]郭振宇.上海巴士公交信息化中的關鍵技術[D].上海：上海交通大學，2005.

[6]高自友，吳建軍，毛保華，等.交通運輸網絡復雜性及其相關問題的研究[J].交通運輸系統工程與信息，2005，5（2）：79-84.

GAO Zi-you，WU Jian-jun，MAO Bao-hua.Study on the complexity of traffic networks and related problems[J].Journal ofTransportation SystemsEngineering and Information Technology，2005，5（2）：79-84.

[7]高自友，趙小梅，黃海軍，等.復雜網絡理論與城市交通復雜性問題的相關研究[J].交通運輸系統與信息，2006，6（3）：41-47.

GAO Zi-you，ZAO Xiao-mei，HUANG Hai-jun.Reasearch on problems related to complex networks and urban traffic systems[J].Journal of Transportation Systems Engineering and Information Technology，2006，6（3）：41-47.

[8]張晨，張寧.上海公交網絡拓撲性質研究[J].上海理工大學學報，2006，28（5）：489-494.

ZHANG Chen，ZHANG Ning.Topology research on shanghai public traffic network[J].Journal of University of Shanghai for Science and Technology，2006，28（5）：489-494.

[9]崔寶俠，姚艷君，段勇.基于改進遺傳算法的公交智能高度[J].沈陽工業大學學報，2010，32（4）：405-410.

CUI Bao-xia，YAO Yan-jun，DUAN Yong. Intelligent scheduling of public traffic vehicle based on improved genetic algorithm[J].Journal of Shenyang Un iversity of Technology，2010，32（4）：405-410.