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

劉長(zhǎng)華 王 忠

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.1 IGA的設(shè)計(jì)思想

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

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

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

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

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

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

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

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

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

4 計(jì)算實(shí)例與分析

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

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

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

5 結(jié) 束 語(yǔ)

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

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

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

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

［4］王小平，曹立明.遺傳算法理論應(yīng)用與軟件實(shí)現(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.