基于遺傳算法的交通網(wǎng)絡(luò)的研究

楊長安 周新志

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

關(guān)鍵詞：車流量；自適應(yīng)；遺傳算法；局部收斂

中圖法分類號(hào)：U 491.5文獻(xiàn)標(biāo)識(shí)碼：A

0引言

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

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

一、遺傳算法運(yùn)用的設(shè)計(jì)

1.模型的建立

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

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

縱向平均滯留量為：

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

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

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

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

,

交叉路口橫縱向放行的平均時(shí)間也應(yīng)該在一個(gè)范圍內(nèi)：

然而，針對本研究的交通模型，采用求解多目標(biāo)優(yōu)化的方法[5-6]找出這個(gè)模型的最優(yōu)解，所以綜上所述，總的模型應(yīng)為：

2.賭輪選擇

選擇將遺傳搜索引導(dǎo)到搜索空間中更有前途的區(qū)域，是模型的驅(qū)動(dòng)力。針對于多目標(biāo)優(yōu)化模型有多個(gè)目標(biāo)函數(shù)，搜索空間復(fù)雜等特點(diǎn)，利用賭輪選擇，增強(qiáng)了空間尋優(yōu)能力，也避免了標(biāo)準(zhǔn)化誤差等選擇問題。其基本思想是每個(gè)種群的選擇概率（即生存概率）正比于它的適應(yīng)值。

計(jì)算種群中所有方案適應(yīng)值的和：

根據(jù)種群的適應(yīng)度值，計(jì)算相應(yīng)的選擇概率：

(k=1,2,…pop_size)

計(jì)算累計(jì)概率值：

(k=1,2,…pop_size)

3.小生境

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

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

其中 、 為共享函數(shù)前后個(gè)體 的適應(yīng)度值。n為群體規(guī)模， 是不同于 的個(gè)體。在計(jì)算出各個(gè)體的小生境數(shù)之后，可以使小生境數(shù)較小（相似程度較小）的個(gè)體能夠有更多的機(jī)會(huì)遺傳到下一代群體中，這樣就增加了群體和解的多樣性。

4.自動(dòng)適應(yīng)的適應(yīng)度函數(shù)

在利用遺傳算法求解優(yōu)化模型時(shí)，能否收斂到最優(yōu)解取決于適應(yīng)度函數(shù)的取法。本文針對這類有等式約束的特殊模型提出了相應(yīng)的自適應(yīng)適應(yīng)度函數(shù)。設(shè) 式的適應(yīng)度函數(shù)為 ， 式的適應(yīng)度函數(shù)為 。其中 為各個(gè)群體的值， 與 是種群排隊(duì)后的編號(hào)。則這個(gè)多目標(biāo)優(yōu)化模型總的適應(yīng)度函數(shù)為：

其中t為函數(shù) 的權(quán)重。t在算法迭代過程中根據(jù)實(shí)際情況而變化。因?yàn)槲覀円?式等于0或者很接近于0，所以要統(tǒng)計(jì) 式的最小個(gè)體值，即 是否為0，或者給一個(gè)范圍，讓群體 的最小值小于一個(gè)常數(shù)，超過這個(gè)范圍立刻增加權(quán)重，從而迫使達(dá)到滿足等式約束的條件。

5.算法流程圖

圖2 流程圖

6.具體算法步驟

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

第二步 ：計(jì)算適應(yīng)度值，判斷是否滿足終止條件，是則退出，否則向下進(jìn)行。

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

第四步：根據(jù)⑶式計(jì)算出不同個(gè)體的共享度，利用⑷式更新適應(yīng)度值，再通過1.2計(jì)算相應(yīng)的選擇概率。

第五步: 采用賭輪選擇算法的算子，根據(jù)各個(gè)種群的適應(yīng)度選擇。

第六步 ：使用交叉和變異，并對種群進(jìn)行重組。為了更好地避免過早收斂，可以當(dāng)?shù)侥骋淮鷷r(shí)，使用一、兩次遷徙算子。

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

二、實(shí)驗(yàn)仿真

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

圖3 傳統(tǒng)GA[7]仿真圖

圖4 改進(jìn)GA仿真圖

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

表1 最優(yōu)流量/滯留量關(guān)系對比

道路 傳統(tǒng)[7]GA 改進(jìn)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中各條道路最優(yōu)流量的單位為輛，滯留量的單位為輛/s。顯然，從表1中各條道路流量/滯留量的數(shù)據(jù)可以對比出，在各條道路中，改進(jìn)遺傳算法得出的流量較大，而滯留量更接近于0。充分說明改進(jìn)遺傳算法得出的效果更好。于是通過實(shí)驗(yàn)仿真，我們就得出了一個(gè)城市交通網(wǎng)絡(luò)各條道路的最優(yōu)平均流量，即交通網(wǎng)絡(luò)的最大通行能力。因此，只要控制住流入每條路的平均流量，就可以讓一個(gè)交通系統(tǒng)處于最優(yōu)效率中。

三、結(jié)論

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

參考文獻(xiàn)

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

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

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

[4]姚亞夫, 曹鋒. 多路口模糊控制及其仿真研究[J].機(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的城市交叉口信號(hào)控制模糊規(guī)則優(yōu)化[J].系統(tǒng)工程學(xué)報(bào). 2004,19(1):89-93.

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

注：文章內(nèi)所有公式及圖表請以PDF形式查看。