基于遺傳算法的交通網絡的研究

楊長安 周新志

摘要：目前城市中的道路錯綜復雜，如何控制交通網絡中的流量使得交通系統中的通行力最大，是交通信息化控制的關鍵部分。在本文研究中，加入了賭輪選擇和小生境混合的自適應遺傳算法來研究智能交通問題。本文擁有多個優化目標，利用賭輪選擇，增加了全局尋優能力；而利用小生境則是解決我們求多目標優化時，盡可能將整個Pareto最優解分散在集合內；使用自適應適應度函數是為了在計算的過程中避免局部收斂。因此，本遺傳算法較傳統遺傳算法[1-2]在解決交通網絡的問題時，完全避免了標準化誤差、統計不完善、局部收斂等問題。

關鍵詞：車流量；自適應；遺傳算法；局部收斂

中圖法分類號：U 491.5文獻標識碼：A

0引言

社會的進步和經濟的發展，使現代交通成為了人們生活中必不可少的部分。但隨著人們對交通工具需求量增大，城市道路面臨著日益擁擠的巨大問題。交通擁擠導致時間延誤，交通事故增多，環境污染加劇等問題，嚴重影響城市的發展和建設。因此，各國迫切希望對城市交通控制系統進行改善，并展開了積極研究。

目前解決智能交通問題的方法主要有：專家控制系統、模糊數學控制系統[6]、基于元胞自動機的城市交通信號自組織控制方法[4]、遺傳算法[1-2]等。本研究正是使用遺傳算法解決交通問題，在本遺傳算法中，加入了賭輪選擇、小生境及自適應函數等方法，使得交通網絡中道路的通行力盡可能最大。

一、遺傳算法運用的設計

1.模型的建立

首先我們把要研究的m+n條交錯道路所組成的交通系統抽象成一個m+n網絡。即橫向有m條道路，縱向有n條，每一條直線是一條道路，每一個交叉點就是一個交叉路口。我們對模型進行簡化，把東西向道路通過的車輛流看成一個橫向的流量，南北向道路通過的車輛流看成一個縱向的流量，即東西橫向流量與南北縱向流量。同時在每個交叉口與交叉口之間設立觀測點，用于測量它們之間路段的流量設為 。由于一條道路上各個路段的流量不一定相同，這里我們把道路各個路段的流量相加求平均，作為整條道路的平均流量：

設東西向道路的平均流量為 。南北向道路的平均流量為 。對任意一個交叉路口橫向放行車輛的平均時間設為 （ ），縱向放行車輛的平均時間設為 （ ， ）。則單個十字交叉路口一個周期內的橫向平均滯留量為:

縱向平均滯留量為：

所以交叉路口總的滯留量為:

其中 為該交叉路口的周期， ， 分別為該交叉口的車輛可以離開的最大橫縱向流量，即它的通行力。由于研究的需要，我們希望在這個交通系統中總的平均流量盡量大，即:

理想情況下，我們已知每個交叉路口的最小滯留量為0，因此把所有的交叉口滯留量加起來求它的最小值：

相鄰交叉口之間的路段都有最大容量 ，于是有：

,

交叉路口橫縱向放行的平均時間也應該在一個范圍內：

然而，針對本研究的交通模型，采用求解多目標優化的方法[5-6]找出這個模型的最優解，所以綜上所述，總的模型應為：

2.賭輪選擇

選擇將遺傳搜索引導到搜索空間中更有前途的區域，是模型的驅動力。針對于多目標優化模型有多個目標函數，搜索空間復雜等特點，利用賭輪選擇，增強了空間尋優能力，也避免了標準化誤差等選擇問題。其基本思想是每個種群的選擇概率（即生存概率）正比于它的適應值。

計算種群中所有方案適應值的和：

根據種群的適應度值，計算相應的選擇概率：

(k=1,2,…pop_size)

計算累計概率值：

(k=1,2,…pop_size)

3.小生境

求解多目標最優化問題時，一般希望所得到的解能盡可能地分散在整個Pareto最優解集合內，而不是集中在其Pareto最優解集合內的某一個較小的區域上。為達到這個要求，可以利用小生境遺傳算法。這種方法稱為共享函數法，將共享函數的概念引入到求解多目標最優化問題的遺傳算法中。算法對相同個體或類似個體的數量加以限制，以便能夠產生較多不同的最優解。具體為:

其中 為不同個體的共享度； 為不同個體的歐式距離； 為距離參數,可根據最優解分布情況設定。通過共享函數，可以對種群中聚集在一小塊的個體加以懲罰,使其適應度減少。

其中 、 為共享函數前后個體 的適應度值。n為群體規模， 是不同于 的個體。在計算出各個體的小生境數之后，可以使小生境數較?。ㄏ嗨瞥潭容^?。┑膫€體能夠有更多的機會遺傳到下一代群體中，這樣就增加了群體和解的多樣性。

4.自動適應的適應度函數

在利用遺傳算法求解優化模型時，能否收斂到最優解取決于適應度函數的取法。本文針對這類有等式約束的特殊模型提出了相應的自適應適應度函數。設 式的適應度函數為 ， 式的適應度函數為 。其中 為各個群體的值， 與 是種群排隊后的編號。則這個多目標優化模型總的適應度函數為：

其中t為函數 的權重。t在算法迭代過程中根據實際情況而變化。因為我們要讓 式等于0或者很接近于0，所以要統計 式的最小個體值，即 是否為0，或者給一個范圍，讓群體 的最小值小于一個常數，超過這個范圍立刻增加權重，從而迫使達到滿足等式約束的條件。

5.算法流程圖

圖2 流程圖

6.具體算法步驟

第一步 ：先隨機生成N組初始群體。

第二步 ：計算適應度值，判斷是否滿足終止條件，是則退出，否則向下進行。

第三步：把群體先帶入 式，計算它們的函數值，利用函數值的大小編序號。最小的值編為1，次之編為2，直到n；然后把群體帶入 ，計算它們的函數值，相對于前面 式的編號不同。這里最大的值編為1，次之編為2，直到n。然后把它們代入1.4，求種群的整合適應度值。

第四步：根據⑶式計算出不同個體的共享度，利用⑷式更新適應度值，再通過1.2計算相應的選擇概率。

第五步: 采用賭輪選擇算法的算子，根據各個種群的適應度選擇。

第六步 ：使用交叉和變異，并對種群進行重組。為了更好地避免過早收斂，可以當迭代到某一代時，使用一、兩次遷徙算子。

第七步：檢查看是否滿足終止條件。是則退出程序，否則跳轉至第三步。

二、實驗仿真

設有三縱三橫的城市網絡，橫向的平均流量設為 ，縱向平均流量設為 。設每個交叉口的橫縱通行能力相同分別為3.0、3.1、2.9、3.1、3.6、3.1、2.7、3.1、2.5，單位是輛/s。每個十字一個周期的通行時間取120s。便于實驗仿真，隨機取60個種群（每個種群由9個交叉口流量觀測數據構成），迭代200次，代溝取0.9，選擇概率取0.85，變異概率取0.04。距離參數 ，根據最優解分布情況設定。適應度函數取，其中 是種群在流量適應度值的順序， 是種群在滯留適應度值的順序，t為權重。根據這個模型要求，我們設定當 ，t =3；當 ，t =6；其它t =12。分別用傳統GA[7]和改進GA做實驗仿真，圖3為傳統GA[7]得出的流量/滯留量仿真圖，圖4為本文改進的GA得出的流量/滯留量仿真圖。

圖3 傳統GA[7]仿真圖

圖4 改進GA仿真圖

圖中每個點表示一個種群搜索到的值。縱坐標表示滯留車輛，單位輛；橫坐標表示流量大小，單位輛/s。從圖中可以看出滯留量隨著流量的逐漸增大而增多。根據分析需要，我們要統計的是平均流量最大，而總的滯留量又恰好為0 或很接近0 時的值。于是，從圖3中可以看出整個交通網絡最優流量為3.5823 輛/s,滯留量為6.4625輛。從圖4 中可以看出整個交通網絡最優流量為4.1248輛/s，滯留量為0.1880輛。針對通過遺傳算法得到的最優解，我們求出各條道路的流量與滯留量，進行深入的對比。下面為傳統GA[7]和改進GA分析對比表：

表1 最優流量/滯留量關系對比

道路 傳統[7]GA 改進GA

流量 滯留量 流量 滯留量

道路1 0.5116 0.9212 0.5882 0.0273

道路2 0.6328 1.1424 0.7291 0.0329

道路3 0.5985 1.0797 0.6896 0.0314

道路4 0.6547 1.1810 0.7538 0.0343

道路5 0.4560 0.8225 0.6525 0.0239

道路6 0.6183 1.1154 0.7119 0.0324

表1中各條道路最優流量的單位為輛，滯留量的單位為輛/s。顯然，從表1中各條道路流量/滯留量的數據可以對比出，在各條道路中，改進遺傳算法得出的流量較大，而滯留量更接近于0。充分說明改進遺傳算法得出的效果更好。于是通過實驗仿真，我們就得出了一個城市交通網絡各條道路的最優平均流量，即交通網絡的最大通行能力。因此，只要控制住流入每條路的平均流量，就可以讓一個交通系統處于最優效率中。

三、結論

本文主要討論遺傳算法在交通網絡控制中的運用。通過對各個交叉路口設置觀測點，監測出各個交叉路口的流量，計算各條道路的平均流量，通過遺傳算法的模型計算，得出整個交通網絡系統中的最優流量。如果處理的交通網絡較大，會有多個等式約束條件。本文采用解多目標優化模型的方法[5-6]，先通過計算適應度值將多目標轉換成單一優化模型，利用小生境將整個Pareto最優解分散在集合內，再通過賭輪選擇算子，得到選擇概率，通過反復迭代遺傳種群，得出多個Pareto解。最后選擇流量最大而滯留接近為0的那個解，即整個交通系統的最優流量。

參考文獻

[1]陳國良. 遺傳算法及其應用[M]. 北京: 人民郵電出版社. 2001:69-478.

[2]王小平, 曹立明. 遺傳算法[M]. 西安: 西安交通大學出版社. 2002．

[3]Langton. C G Studying Artificial Life With Cellular Automata. Physica 22D,1986:120-149.

[4]姚亞夫, 曹鋒. 多路口模糊控制及其仿真研究[J].機械工程與自化. 2006(3):108-112.

[5]Deb K, Pratap A, Agarwal S, Meyarivn T1.A Fast and Elitist Multi-objective Genetic Algorithm[J],NSGAⅡ.IEEE Transactions on Evolutionary Computation, 2002, 6:182 -197.

[6]李艷, 樊曉平. 基于GA的城市交叉口信號控制模糊規則優化[J].系統工程學報. 2004,19(1):89-93.

[7]盛躍賓,陳定昌.有等式約束優化問題的粒子群優化算法[J].計算機工程與設計,2006,27(13):2412-2418.

注：文章內所有公式及圖表請以PDF形式查看。