基于HGA的智能交通調(diào)度優(yōu)化方法研究＊

劉長華 王 忠

（中國民航飛行學(xué)院飛行技術(shù)與飛行安全科研基地1） 廣漢 618307） （四川大學(xué)電氣信息工程學(xué)院2） 成都 610065）

公共車輛運營調(diào)度管理通常分為3個階段完成：計劃、調(diào)度和控制.調(diào)度是關(guān)鍵的中間環(huán)節(jié)，車輛運營調(diào)度問題就是針對一項可分解的運輸任務(wù)，在一定約束下如何安排運作時間和先后順序，以獲得運輸成本或時間最優(yōu)化.公交車輛調(diào)度包括靜態(tài)調(diào)度和動態(tài)調(diào)度，本文著重研究靜態(tài)調(diào)度，即：運營車的發(fā)車時刻表的編排過程.采用智能化算法，即將免疫算法與遺傳算法有機結(jié)合，提出一種改進型混合遺傳算法來求解車輛調(diào)度優(yōu)化問題，在有限的算法步驟內(nèi)，找出所有滿足約束條件的排班方案中的最優(yōu)方案或接近最優(yōu)的方案，從而可以提高公交企業(yè)的管理和服務(wù)水平.

1 調(diào)度的數(shù)學(xué)模型

遺傳算法（genetic algorithms，GA）是一種基于自然選擇和基因遺傳學(xué)原理的自適應(yīng)全局優(yōu)化概率搜索方法.它的創(chuàng)立有2個研究目的：（1）抽象和嚴(yán)謹(jǐn)?shù)亟忉屪匀唤绲倪m應(yīng)過程；（2）為了將自然生物系統(tǒng)的重要機理運用到工程系統(tǒng)中.GA從許多點開始并行操作，在解空間進行高效啟發(fā)式搜索，因而可以有效地防止搜索過程收斂于局部最優(yōu)解；遺傳算法在計算機上模擬生物的進化過程和基因的操作，通過目標(biāo)函數(shù)來計算適配值，并不需要對象的特定知識，它具有全局尋優(yōu)的能力，能解決高度復(fù)雜的問題，被廣泛應(yīng)用于自動控制、圖形處理、電力調(diào)度等方面［1－5］.

調(diào)度系統(tǒng)所采用的數(shù)學(xué)模型對運行環(huán)境做了簡化：車的速度恒定，保持勻速行駛，無特殊事件發(fā)生；以min作為最小的時間單位，這對安排時刻表是合理的；假設(shè)客流模型能反映該段線路上的日?？土髁浚僭O(shè)到站乘客服從均勻分布，在不同時段有不同的分布密度）.

首班車發(fā)車時刻為早上6點整，末班車發(fā)車時刻為22點整，所有運營車都在整min時刻發(fā)車，1d之內(nèi)的總班次為m，總時間為16h，即960 min.用xm表示第m輛運營車發(fā)車時刻距首發(fā)時刻的時間，以min為單位.決策變量為X＝［x1，x2，…，xn］T；染色體X 是一個完整的發(fā)車時刻表，其中的每個基因為一個車輛的發(fā)車時刻，約束條件為：

1）選擇算子 采用比例選擇法，也稱為輪盤賭法.各個個體被選中的概率與其適應(yīng)度的大小成正比.在一次選擇中個體被選中概率為

式中：Fi為該個體的適應(yīng)度.

2）交叉算子 首先將群體中的M個個體以隨機方式組成M／2對配對個體組，然后對每個個體組以概率P進行交叉運算，先在個體編碼串中隨機設(shè)置一個交叉點，然后在該點相互交換2個配對個體的部分染色體.交叉點的選擇必須保證新的個體符合約束條件.

3）變異算子 采用均勻變異操作.依次指定個體編碼串當(dāng)中的個體基因座為變異點，對每個變異點以很小的變異概率p從對應(yīng)基因的取值范圍內(nèi)取一個均勻分布的隨機數(shù)來代替原來的基因.任一個基因xk的取值范圍是（xk－1，xk＋1），變異點的新基因值為

2 免疫機理引入遺傳算法［6－7］

GA由于其運算簡單和解決問題的有效能力而被廣泛應(yīng)用到眾多領(lǐng)域.理論上已證明，遺傳算法能從概率的意義上以隨機的方式尋求到問題的最優(yōu)解.GA在應(yīng)用中也會出現(xiàn)一些問題，主要是容易產(chǎn)生早熟現(xiàn)象、局部尋優(yōu)能力差等.一般來說基本遺傳算法的求解效果往往不是最佳的；另外GA也無法避免多次搜索同一個可行解，這也是影響GA運行效率的一個因素.而有些尋優(yōu)算法具有很強的局部搜索能力，可以預(yù)計在GA中融合這些優(yōu)化算法的思想、構(gòu)成一種混合遺傳算法是提高GA運行效率和求解質(zhì)量的一個有效手段.

免疫算法效仿生物免疫系統(tǒng)，把外來侵犯的抗原和免疫產(chǎn)生的抗體分別與實際求解問題的目標(biāo)函數(shù)以及問題的解相對應(yīng)，生成的抗體能有效地排除抗原，也就相當(dāng)于求得了問題的最優(yōu)解；對與抗原親和力高的抗體進行記憶能促進快速求解.它具有以下特點.

1）抗體的多樣性 通過細(xì)胞分裂和分化作用，免疫系統(tǒng)可產(chǎn)生多樣性的抗體來抵御各種抗原.

2）自我調(diào)節(jié)能力.免疫系統(tǒng)具有維持免疫平衡的機制，通過對抗體的抑制和促進作用，能自我調(diào)節(jié)產(chǎn)生適當(dāng)數(shù)量的必要的個體.要求免疫算法在進化過程中一旦發(fā)現(xiàn)最優(yōu)個體，在兼顧群體多樣性的同時，類似個體亦將大量繁殖.

免疫系統(tǒng)的算法是在個體基礎(chǔ)上發(fā)展的；但物種宏觀進化對個體免疫系統(tǒng)的進化是有重要影響的.免疫系統(tǒng)隨著物種的進化一方面慢速進化，另一方面為了適應(yīng)病原體環(huán)境而快速進化.它克服通常GA收斂方向無法控制的缺陷，收斂方向能得以控制.IGA可以看作是一種改進的遺傳算法，一種新型計算智能方法，是具有免疫功能的遺傳算法.它保留了遺傳算法的全局搜索特性，克服遺傳算法由于交叉搜索而在局部搜索解空間上效率較差的缺點，又在很大程度上避免未成熟收斂，許多方面表現(xiàn)超越遺傳算法和免疫算法的優(yōu)點.

3 IGA應(yīng)用于公交靜態(tài)調(diào)度

3.1 IGA的設(shè)計思想

IGA中的最優(yōu)個體（抗體），即為每代適應(yīng)度最高的可行解.從概率上來說，最優(yōu)個體和全局最優(yōu)解之間的空間距離可能要小于群體中其他個體與之的空間距離；和最優(yōu)個體之間空間距離較小的個體也可能有較高的適應(yīng)度，因此，最優(yōu)個體是求解問題特征信息的直接體現(xiàn).從免疫學(xué)的角度而言，當(dāng)有抗原入侵時，與之相匹配的抗體被激發(fā)（免疫應(yīng)答），使得有用的抗體一旦產(chǎn)生，就能得以保留.由上述分析可見，新算法成功與否的關(guān)鍵在于是否實施了精英保留策略以及是否充分利用每代最優(yōu)個體信息.借鑒生物免疫機制，簡單免疫進化算法中子代個體的生殖方式為

由式（4）式可得，一旦在某一代群體中確定出最優(yōu)個體（抗體），那么在下一代群體中類似的個體（抗體），即為免疫應(yīng)答在算法當(dāng)中的體現(xiàn).另外從進化角度而言，這里子代個體所表現(xiàn)出的性狀不再僅僅視為是對父代個體突變的結(jié)果，而被視為是對父代性狀遺傳和變異的綜合體現(xiàn)，IGA把子代個體這樣的產(chǎn)生方式稱之為生殖.

在IGA中，子代群體的分布是隨迭代而不斷進行有規(guī)律調(diào)整的過程，這是受生物免疫系統(tǒng)自我調(diào)節(jié)功能啟發(fā)的結(jié)果.通過對標(biāo)準(zhǔn)差的動態(tài)調(diào)整，在進化的早期和中期，生成的群體在加大對最優(yōu)個體附近解空間的投點密度的同時，也兼顧了對最優(yōu)個體附近解空間以外區(qū)域的搜索，這樣的群體既能保持較好的多樣性，又可有效避免不成熟收斂這種現(xiàn)象；在進化后期，隨著局部搜索能力的不斷加強從而算法能以更高精度逼近全局最優(yōu)解.所以標(biāo)準(zhǔn)差的動態(tài)調(diào)整是IGA的重要技術(shù)環(huán)節(jié)，可在群體多樣性和選擇力度之間起到調(diào)節(jié)的作用，相比與現(xiàn)有的其他進化算法而言，IGA中的群體只是起搜索引擎的作用，最優(yōu)個體的進化是基于在一定概率規(guī)則引導(dǎo)下的一種統(tǒng)計結(jié)果.

綜上所述，IGA算法的核心在于充分利用最優(yōu)個體的信息，以最優(yōu)個體的進化來代替群體的進化，通過標(biāo)準(zhǔn)差的調(diào)整把局部搜索和全局搜索在進化過程中有機結(jié)合起來.該算法的實現(xiàn)手段著重體現(xiàn)在最優(yōu)個體的保留、生殖以及標(biāo)準(zhǔn)差的動態(tài)調(diào)整上，和現(xiàn)有其他算法相比，它具有搜索效率高和不易陷入局部最優(yōu)解的優(yōu)點.

3.2 IGA應(yīng)用操作步驟

現(xiàn)仍采用上面建立的數(shù)學(xué)模型，初始規(guī)模N仍為200且不隨進化代數(shù)而發(fā)生變化，便于IGA和GA比較.利用IGA來進行優(yōu)化的步驟如下.

1）在解空間內(nèi)隨機生成初始群體，并計算其適應(yīng)度，確定最優(yōu)個體，并給出σ0的取值，A取為1，取為3，σξ取為0.

2）根據(jù)式（4）進行進化操作，在解空間內(nèi)生成子代群體，規(guī)模為N.

4）重復(fù)執(zhí)行步驟2）和3），直至達到終止條件，這里T取為100，選擇最后一代的最優(yōu)個體作為尋優(yōu)的結(jié)果.

4 計算實例與分析

為了確定交叉概率、變異概率、進化代數(shù)等遺傳算法參數(shù)，進行了許多實驗，最終確定了效果較好的參數(shù)為：變異概率取0.000 5，交叉概率取為0.6.另外，群體規(guī)模取200，遺傳代數(shù)取為600，這樣可以兼顧運算量和運算效果.

圖1分別畫出了遺傳算法和免疫遺傳算法中各代個體目標(biāo)平均值和各代最優(yōu)個體目標(biāo)平均值隨進化代數(shù)的變化規(guī)律，從圖中明顯可以看出，IGA的收斂速度要優(yōu)于GA，收斂更快.將IGA應(yīng)用于公交智能調(diào)度管理系統(tǒng)能夠得到較好的結(jié)果，可以迅速得到最優(yōu)解.IGA是對GA的改進，從性能上也有了更大的進步.

圖1 遺傳算法和免疫遺傳算法應(yīng)用對比

5 結(jié) 束 語

本文在遺傳算法的基礎(chǔ)上采用了一種較新的混合遺傳算法－免疫遺傳算法對公交靜態(tài)調(diào)度進行了研究，并對二者的應(yīng)用結(jié)果進行了仿真和比較，結(jié)果表明IGA有效的克服了簡單GA的不足之處，并提高了尋優(yōu)過程當(dāng)中目標(biāo)函數(shù)的收斂速度，并得到了合理的發(fā)車時刻表，可以提高公交企業(yè)的服務(wù)水平，對改善城市交通問題和節(jié)約市民出行時間有實際意義.由于公交車在運行過程中受到諸多客觀因素的影響，比如車輛可能沒有按計劃到達預(yù)定車站，在車輛運行的過程中要對公交車運行的實際情況進行實時調(diào)度，因此還需要對動態(tài)調(diào)度做進一步的研究.

［1］倪長健.免疫進化算法研究及其在水問題中的應(yīng)用［D］.成都：四川大學(xué)水電學(xué)院，2003.

［2］周 明，孫樹棟.遺傳算法原理及應(yīng)用［M］.北京：國防工業(yè)出版社，1999.

［3］李躍鵬，安 濤.基于遺傳算法的公交車輛智能排班研究［J］.交通運輸系統(tǒng)工程與信息，2003，3（1）：41－45.

［4］王小平，曹立明.遺傳算法理論應(yīng)用與軟件實現(xiàn)［M］.西安：西安交通大學(xué)出版社，2002.

［5］Marian T B.Development of a transportation data processing system for Metropolitan［C］／／Proceedings of the IEEE－IEE Vehicle Navigation and Information Systems Conference，1993：186－190.

［6］Malmborg C J.A genetic algorithm for service level based vchicle scheduling［J］.European Journal of Operational Research，1996，93：121－134.

［7］De Jong K A.An analysis of the behavior of a class of genetic adaptive［D］.Ph.D Dissertation，University of Michigan，1975.