基于遺傳算法的均衡交通分配研究

夏小棠,李庭洋

(1.武漢科技大學城市設計學院,湖北武漢430081;2.武漢城市職業學院,湖北武漢430064)

1 引言

在城市及區域交通規劃中,交通分配作為一個重要環節起了關鍵的作用。隨著人工智能、數學規劃等方法的發展,對交通分配模型的研究與應用也日趨成熟。國際上按照wordd rop提出的第1和第2原則,將交通分配模型劃分為均衡模型和非均衡模型[1]。均衡交通分配理論在近幾年發展較快,與非均衡交通分配模型相比,這類模型具有思路明確、結構嚴謹、結果合理、有利于宏觀研究等優點。

近幾年,對均衡分配問題的求解出現許多新的算法,雖然這些算法的運算復雜度在一定程度上降低了,但處理大規模復雜的交通網絡問題仍比較困難。這都迫切需要一種新的算法使之能建立易于編程的、計算能力快的、更貼近實際交通狀況的預測模型。因此,本文嘗試將易于計算機編程,且具有全局搜索功能以及并行運算特點的遺傳算法應用于求解均衡交通分配模型。

2 遺傳算法的一般理論

遺傳算法(Genetic A lgorithm)是一種模擬生物在自然界環境中遺傳和進化過程而形成的一種全新的全局搜索和優化方法。它從任一初始群體出發,通過隨機選擇、交叉和變異等遺傳算子,使種群一代代進行到空間中最好的區域,直至達到最優點。其主要特點包括直接對結構對象進行操作,不要求函數連續性以及求導;全局尋優能力更強;有內在的并行性。遺傳算法已成為當今影響最廣泛的進化方法之一,是現代有關智能計算問題中的關鍵技術,被人們廣泛地應用于不同的領域,如信號處理、自適應控制、組合優化、人工生命和機器學習。

2.1 編碼

編碼實際上就是從解空間把問題的可行解轉換到遺傳算法的搜索空間。編碼一般有3種方式,即符號編碼方式、浮點數編碼方式以及二進制編碼方式。二進制編碼方式中,每個自變量用s位二進制的子串表示,n個問題用s×n表達,假設 的取值范圍在xi min～xi max,則編碼的區間為[0,2s]。

2.2 遺傳操作

2.2.1 選擇

選擇就是以適應度高的個體為依據,從群體中把父個體選擇出來,并令其產生相應的后代,淘汰適應度低的個體。常用的選擇方法主要有以下幾種：比例的變換,競爭的選擇,輪盤賭的選擇,穩態復制,排序,共享等。Holland提出的輪盤賭選擇法(roulettew heel selection)是諸多選擇方法中最有名、最常用的方法。

2.2.2 交叉

交叉是依照交叉概率,將種群中的2個能夠相互配對的父個體的部分結構按照某種特定的方式替換和重組形成2個新的個體。交叉的方法可以根據編碼方法不同而變化,例如二進制編碼進行的二進制交叉,實值編碼進行的實值交叉等。在二進制交叉中又可以分為均勻交叉、單點交叉以及多點交叉。實值交叉通常有中間交叉、離散交叉、算術交叉等。

2.2.3 變異

變異是根據某一個很小的概率隨機地改變群體中個體的某些基因。依據個體編碼表示方法的不同,變異方法也不同,如二進制編碼中的1變成0,0變成1。變異算法有2個重要作用,包括使遺傳算法具有較強的局部隨機搜索能力;使遺傳算法能維持群體多樣性,防止未成熟收斂的現象出現。

2.3 終止條件

算法終止,即最優個體的適應度達到設定的閥值;最優個體的適應度以及群體適應度不再變化時;迭代次數達到預先設定的次數。

2.4 遺傳算法在約束優化問題上的處理方法

遺傳算法用于約束優化問題的求解常用的有幾種方法,包括可行域、混合法、算子修正法、罰函數法[2]。采用線性約束的等式消除某些變量,用其他的線性組合代替變量,并修改線性不等式;采用專門設計的修正算子,對不可行染色體進行修復,保證后代一直是可行的;采用罰函數法,通過懲罰不可行解將有約束的問題轉化為無約束的問題,使得遺傳算法可以在可行域和不可行域中搜索到最優解。

3 基于遺傳算法的用戶均衡分配模型

3.1 用戶均衡模型

交通分配就是將OD矩陣q中的交通需求量安排到路網中,從而形成路段流量 x,該過程按照Wardrop第一原則(UE原則)進行,用求解數學規劃的問題算出符合UE條件的流量分布,公式如下：

約束條件：

路段流量由公式計算：

其中,路段時間函數被假定成路段交通流量的單調、連續上升函數,只與自身的路段流量有關。目標函數是路段時間函數的積分。約束條件令每個OD對之間所有路徑流量的和等于相應的OD需求,約束條件描述了路徑流與路段流之間的關系。

3.2 模型的設計

3.2.1 算例

某一簡化的交通網絡見圖1。

圖1 交通網絡圖

其中,OD量為300,3個路段的時間阻抗函數為：

α、β是調教系數,建議 α=0.15,β=4。

3.2.2 模型分析及求解過程

該交通網絡的用戶均衡,交通分配問題可以表示成數學規劃模型。

其中ta為路段的阻抗函數,a=1,2,3;qrs為OD流量為r、s間第k條路段的流量,即將OD流量qrs、路阻函數 ta帶入優化模型,得到公式如下：

采用罰函數法將目標函數轉換成增廣目標函數p(X,u),公式如下：

式中 T(X,u)為增廣目標函數;z(X)同上;u為懲罰因子,且 u＞0,當 u→∞時,目標函數逼近最優解。通過遺傳算法求解。

(1)可行解采用二進制編碼,每個自變量的取值范圍在[0,300],用8位二進制數表示,染色體串的長度為8×3=24。

(2)個體適應度函數：

F(X)=1/z(X) (7)

(3)解碼方法：

得到結果：x1=0+xi(300-0)/(28-1)。

(4)遺傳算子為比例遺傳算子,種群適應度之和F的計算公式如下：

對染色體選擇的概率計算使用公式如下：

pi,pi=F(Xi)/F,i=1,2,…,popsize

對染色體累加的概率計算使用公式如下：

對于產生一個位于[0,1]區間的長度為popsize隨機數的序列,其中的任意的一個數r若滿足qi-1＜r＜qi,則選第 i染色體(i=1,2,…,popsize),這樣就得到新的種群。運算交叉,單點交叉算子;運算變異,基本位變異算子。遺傳算法的運行參數。設定群體的規模(popsize)為100,交叉概率為0.95,變異概率為0.001。經過計算,得到結果如下：X1=118.309 2,X2=122.535 3,X 3=59.154 6;t1=40.154 1,t2=40.145,t3=40.1451最優值：z(X)=11 028.385。從最后的運行結果可知,所有路徑的交通時間趨于相等,即t1=t2=t3=40.145 1,系統朝著均衡方向發展,整個路網達到用戶最優狀態。

4 結語

從實例分析可見采用遺傳算法解決用戶最優的均衡交通分配模型是可行的。由于遺傳算法模型簡單,易于計算機編程且求解速度快,對函數的可微性或連續行等沒有要求,只要所要求解的問題的目標函數是可計算的便可,在計算機的幫助下,可靈活的處理許多交通網絡問題,方便了使用者的具體操作。

[1]陸化普,黃海軍.交通規劃理論研究前沿[M].北京：清華大學出版社,2007.

[2]玄光男,程潤偉.遺傳算法與工程優化[M].北京：清華大學出版社,2006.

[3]姜友華,王新生.遺傳算法用于產生可供選擇的城市規劃方案[J].武漢大學學報,2002,35(3),63～65.

[4]雷英杰,張善文,李續文,等.M ATLAB遺傳算法工具箱及應用[M].西安：西安電子科技大學出版社,2005.

[5]Booker,Goldberg L B,Holland J H.Classififier Systems and Genetic A lgo rithm s[J].A rtificial In telligence,1989(40)：235～280.

[6]Feng C,Lin J.Using a genetic algorithm to generative sketch m aps for u rban planning[J].Com puters Environment and Urban system,199,23(2)：92～ 100.

[7]Richad JB,John T T,M ichael R B.M ultiobjective u rban p lanning using genetic A lgorithm[J].Jou rnalof U rban and Development,1999,125(2)：86～ 99.