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

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

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

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

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

5、賭輪選擇 選擇將遺傳搜索引導(dǎo)到搜索空間中更有前途的區(qū)域，是模型的驅(qū)動(dòng)力。針對(duì)于多目標(biāo)優(yōu)化模型有多個(gè)目標(biāo)函數(shù)，搜索空間復(fù)雜等特點(diǎn)，利用賭輪選擇，增強(qiáng)了空間尋優(yōu)能力，也避免了標(biāo)準(zhǔn)化誤差等選擇問(wè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)1.3小生境 求解多目標(biāo)最優(yōu)化問(wèn)題時(shí)，一般希望所得到的解能盡可能地分散在整個(gè)Pareto最優(yōu)解集合內(nèi)，而不是集中在其Pareto最優(yōu)解集合內(nèi)的某一個(gè)較小的區(qū)域上。為達(dá)到這個(gè)要求，可以利用小生境遺

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

7、決于適應(yīng)度函數(shù)的取法。本文針對(duì)這類(lèi)有等式約束的特殊模型提出了相應(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在算法迭代過(guò)程中根據(jù)實(shí)際情況而變化。因?yàn)槲覀円屖降扔?或者很接近于0，所以要統(tǒng)計(jì)式的最小個(gè)體值，即是否為0，或者給一個(gè)范圍，讓群體的最小值小于一個(gè)常數(shù)，超過(guò)這個(gè)范圍立刻增加權(quán)重，從而迫使達(dá)到滿足等式約束的條件。1.5算法流程圖圖2 流程圖1.6 具體算法步驟第一步 ：先隨機(jī)生成N組初始群體。 第二步 ：計(jì)算適應(yīng)度值，判斷是否滿足終止條件，是則退出，否則向下進(jìn)行。 第三步：

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

9、向的平均流量設(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è)交叉口流量觀測(cè)數(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è)模型要求，我們?cè)O(shè)定當(dāng)，t =3；當(dāng)，t =6；其它t =12。分別用傳統(tǒng)GA7和改進(jìn)GA做實(shí)驗(yàn)仿真，圖3為傳統(tǒng)GA7得出的流量/滯留量仿

10、真圖，圖4為本文改進(jìn)的GA得出的流量/滯留量仿真圖。圖3 傳統(tǒng)GA7仿真圖圖4 改進(jìn)GA仿真圖圖中每個(gè)點(diǎn)表示一個(gè)種群搜索到的值。縱坐標(biāo)表示滯留車(chē)輛，單位輛；橫坐標(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輛。針對(duì)通過(guò)遺傳算法得到的最優(yōu)解，我們求出各條道路的流量與滯留量，進(jìn)行深入的對(duì)比。下面為傳統(tǒng)GA7和改進(jìn)GA分

11、析對(duì)比表：表1 最優(yōu)流量/滯留量關(guān)系對(duì)比道路傳統(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ù)可以對(duì)比出，在各條道路中，改進(jìn)遺傳算法得出的流量較大，而滯留量更接近于0。充分說(shuō)明改進(jìn)遺傳算

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

13、遺傳種群，得出多個(gè)Pareto解。最后選擇流量最大而滯留接近為0的那個(gè)解，即整個(gè)交通系統(tǒng)的最優(yōu)流量。參 考 文 獻(xiàn) 1陳國(guó)良. 遺傳算法及其應(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.機(jī)械工程與自化. 2006(3):108-112. 5Deb K, Pratap A, Agarwal S, Meyarivn T1.A Fast and Elitist Multi-objectiv