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

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

2、量；自適應(yīng)；遺傳算法；局部收斂中圖法分類號：U 491.5 文獻(xiàn)標(biāo)識碼：A 0引言社會的進(jìn)步和經(jīng)濟(jì)的發(fā)展，使現(xiàn)代交通成為了人們生活中必不可少的部分。但隨著人們對交通工具需求量增大，城市道路面臨著日益擁擠的巨大問題。交通擁擠導(dǎo)致時間延誤，交通事故增多，環(huán)境污染加劇等問題，嚴(yán)重影響城市的發(fā)展和建設(shè)。因此，各國迫切希望對城市交通控制系統(tǒng)進(jìn)行改善，并展開了積極研究。目前解決智能交通問題的方法主要有：專家控制系統(tǒng)、模糊數(shù)學(xué)控制系統(tǒng)6、基于元胞自動機的城市交通信號自組織控制方法4、遺傳算法1-2等。本研究正是使用遺傳算法解決交通問題，在本遺傳算法中，加入了賭輪選擇、小生境及自適應(yīng)函數(shù)等方法，使得交通網(wǎng)絡(luò)中

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

4、行車輛的平均時間設(shè)為（），縱向放行車輛的平均時間設(shè)為（，）。則單個十字交叉路口一個周期內(nèi)的橫向平均滯留量為:縱向平均滯留量為：所以交叉路口總的滯留量為:其中為該交叉路口的周期，分別為該交叉口的車輛可以離開的最大橫縱向流量，即它的通行力。由于研究的需要，我們希望在這個交通系統(tǒng)中總的平均流量盡量大，即:理想情況下，我們已知每個交叉路口的最小滯留量為0，因此把所有的交叉口滯留量加起來求它的最小值：相鄰交叉口之間的路段都有最大容量，于是有：,交叉路口橫縱向放行的平均時間也應(yīng)該在一個范圍內(nèi)：然而，針對本研究的交通模型，采用求解多目標(biāo)優(yōu)化的方法5-6找出這個模型的最優(yōu)解，所以綜上所述，總的模型應(yīng)為：1.2

5、賭輪選擇 選擇將遺傳搜索引導(dǎo)到搜索空間中更有前途的區(qū)域，是模型的驅(qū)動力。針對于多目標(biāo)優(yōu)化模型有多個目標(biāo)函數(shù)，搜索空間復(fù)雜等特點，利用賭輪選擇，增強了空間尋優(yōu)能力，也避免了標(biāo)準(zhǔn)化誤差等選擇問題。其基本思想是每個種群的選擇概率（即生存概率）正比于它的適應(yīng)值。計算種群中所有方案適應(yīng)值的和：根據(jù)種群的適應(yīng)度值，計算相應(yīng)的選擇概率：(k=1,2,pop_size)計算累計概率值： (k=1,2,pop_size)1.3小生境 求解多目標(biāo)最優(yōu)化問題時，一般希望所得到的解能盡可能地分散在整個Pareto最優(yōu)解集合內(nèi)，而不是集中在其Pareto最優(yōu)解集合內(nèi)的某一個較小的區(qū)域上。為達(dá)到這個要求，可以利用小生境遺

6、傳算法。這種方法稱為共享函數(shù)法，將共享函數(shù)的概念引入到求解多目標(biāo)最優(yōu)化問題的遺傳算法中。算法對相同個體或類似個體的數(shù)量加以限制，以便能夠產(chǎn)生較多不同的最優(yōu)解。具體為: 其中為不同個體的共享度；為不同個體的歐式距離；為距離參數(shù),可根據(jù)最優(yōu)解分布情況設(shè)定。通過共享函數(shù)，可以對種群中聚集在一小塊的個體加以懲罰,使其適應(yīng)度減少。 其中、為共享函數(shù)前后個體的適應(yīng)度值。n為群體規(guī)模，是不同于的個體。在計算出各個體的小生境數(shù)之后，可以使小生境數(shù)較?。ㄏ嗨瞥潭容^?。┑膫€體能夠有更多的機會遺傳到下一代群體中，這樣就增加了群體和解的多樣性。1.4自動適應(yīng)的適應(yīng)度函數(shù)在利用遺傳算法求解優(yōu)化模型時，能否收斂到最優(yōu)解取

7、決于適應(yīng)度函數(shù)的取法。本文針對這類有等式約束的特殊模型提出了相應(yīng)的自適應(yīng)適應(yīng)度函數(shù)。設(shè)式的適應(yīng)度函數(shù)為，式的適應(yīng)度函數(shù)為。其中為各個群體的值，與是種群排隊后的編號。則這個多目標(biāo)優(yōu)化模型總的適應(yīng)度函數(shù)為：其中t為函數(shù)的權(quán)重。t在算法迭代過程中根據(jù)實際情況而變化。因為我們要讓式等于0或者很接近于0，所以要統(tǒng)計式的最小個體值，即是否為0，或者給一個范圍，讓群體的最小值小于一個常數(shù)，超過這個范圍立刻增加權(quán)重，從而迫使達(dá)到滿足等式約束的條件。1.5算法流程圖圖2 流程圖1.6 具體算法步驟第一步 ：先隨機生成N組初始群體。 第二步 ：計算適應(yīng)度值，判斷是否滿足終止條件，是則退出，否則向下進(jìn)行。 第三步：

8、把群體先帶入式，計算它們的函數(shù)值，利用函數(shù)值的大小編序號。最小的值編為1，次之編為2，直到n；然后把群體帶入，計算它們的函數(shù)值，相對于前面式的編號不同。這里最大的值編為1，次之編為2，直到n。然后把它們代入1.4，求種群的整合適應(yīng)度值。第四步：根據(jù)式計算出不同個體的共享度，利用式更新適應(yīng)度值，再通過1.2計算相應(yīng)的選擇概率。第五步: 采用賭輪選擇算法的算子，根據(jù)各個種群的適應(yīng)度選擇。第六步 ：使用交叉和變異，并對種群進(jìn)行重組。為了更好地避免過早收斂，可以當(dāng)?shù)侥骋淮鷷r，使用一、兩次遷徙算子。 第七步：檢查看是否滿足終止條件。是則退出程序，否則跳轉(zhuǎn)至第三步。2實驗仿真設(shè)有三縱三橫的城市網(wǎng)絡(luò)，橫

9、向的平均流量設(shè)為，縱向平均流量設(shè)為。設(shè)每個交叉口的橫縱通行能力相同分別為3.0、3.1、2.9、3.1、3.6、3.1、2.7、3.1、2.5，單位是輛/s。每個十字一個周期的通行時間取120s。便于實驗仿真，隨機取60個種群（每個種群由9個交叉口流量觀測數(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ù)這個模型要求，我們設(shè)定當(dāng)，t =3；當(dāng)，t =6；其它t =12。分別用傳統(tǒng)GA7和改進(jìn)GA做實驗仿真，圖3為傳統(tǒng)GA7得出的流量/滯留量仿

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

11、析對比表：表1 最優(yōu)流量/滯留量關(guān)系對比道路傳統(tǒng)GA7 改進(jìn)GA 流量滯留量流量滯留量道路10.51160.92120.58820.0273道路20.63281.14240.72910.0329道路30.59851.07970.68960.0314道路40.65471.18100.75380.0343道路50.45600.82250.65250.0239道路60.61831.11540.71190.0324 表1中各條道路最優(yōu)流量的單位為輛，滯留量的單位為輛/s。顯然，從表1中各條道路流量/滯留量的數(shù)據(jù)可以對比出，在各條道路中，改進(jìn)遺傳算法得出的流量較大，而滯留量更接近于0。充分說明改進(jìn)遺傳算

12、法得出的效果更好。于是通過實驗仿真，我們就得出了一個城市交通網(wǎng)絡(luò)各條道路的最優(yōu)平均流量，即交通網(wǎng)絡(luò)的最大通行能力。因此，只要控制住流入每條路的平均流量，就可以讓一個交通系統(tǒng)處于最優(yōu)效率中。3結(jié)論本文主要討論遺傳算法在交通網(wǎng)絡(luò)控制中的運用。通過對各個交叉路口設(shè)置觀測點，監(jiān)測出各個交叉路口的流量，計算各條道路的平均流量，通過遺傳算法的模型計算，得出整個交通網(wǎng)絡(luò)系統(tǒng)中的最優(yōu)流量。如果處理的交通網(wǎng)絡(luò)較大，會有多個等式約束條件。本文采用解多目標(biāo)優(yōu)化模型的方法5-6，先通過計算適應(yīng)度值將多目標(biāo)轉(zhuǎn)換成單一優(yōu)化模型，利用小生境將整個Pareto最優(yōu)解分散在集合內(nèi)，再通過賭輪選擇算子，得到選擇概率，通過反復(fù)迭代

13、遺傳種群，得出多個Pareto解。最后選擇流量最大而滯留接近為0的那個解，即整個交通系統(tǒng)的最優(yōu)流量。參 考 文 獻(xiàn) 1陳國良. 遺傳算法及其應(yīng)用M. 北京: 人民郵電出版社. 2001:69-478.2王小平, 曹立明. 遺傳算法M. 西安: 西安交通大學(xué)出版社. 20023Langton. C G Studying Artificial Life With Cellular Automata. Physica 22D,1986:120-149.4姚亞夫, 曹鋒. 多路口模糊控制及其仿真研究J.機械工程與自化. 2006(3):108-112. 5Deb K, Pratap A, Agarwal S, Meyarivn T1.A Fast and Elitist Multi-objectiv