基于改進(jìn)的遺傳算法在京津冀交通網(wǎng)絡(luò)優(yōu)化問(wèn)題中的應(yīng)用

紀(jì)楠　梁彥冰

摘要：本文在經(jīng)濟(jì)快速發(fā)展的大背景和公共交通網(wǎng)絡(luò)擁堵日益嚴(yán)重的現(xiàn)狀下，在建立多目標(biāo)交通網(wǎng)絡(luò)優(yōu)化模型的基礎(chǔ)上。利用改進(jìn)的遺傳算法進(jìn)行求解。最后利用京津冀13個(gè)城市的數(shù)據(jù)進(jìn)行仿真模擬，驗(yàn)證改進(jìn)的遺傳算法可以應(yīng)用與交通網(wǎng)絡(luò)優(yōu)化問(wèn)題的研究。

關(guān)鍵詞：遺傳算法 多目標(biāo)優(yōu)化模型 交通網(wǎng)絡(luò)優(yōu)化

一、背景

近年來(lái)，隨著經(jīng)濟(jì)的發(fā)展和城市人口激增，我國(guó)許多城市交通擁堵?tīng)顩r日益嚴(yán)重，交通網(wǎng)絡(luò)優(yōu)化正在受到越來(lái)越多的關(guān)注。本文在京津冀一體化發(fā)展的背景下，結(jié)合《京津冀協(xié)同發(fā)展規(guī)劃綱要》中指出的“要在京津冀交通一體化、生態(tài)環(huán)境保護(hù)、產(chǎn)業(yè)升級(jí)轉(zhuǎn)移等重點(diǎn)領(lǐng)域率先取得突破。”的政策導(dǎo)向，探討基于改進(jìn)的遺傳算法在京津冀交通優(yōu)化問(wèn)題中的應(yīng)用。

二、多目標(biāo)優(yōu)化模型的建立

交通網(wǎng)絡(luò)主要分為兩種類(lèi)型，一種是連續(xù)的，即道路交通容量的提高，第二種是離散的，這種離散的道路增加了道路的跳躍能力。實(shí)際的交通網(wǎng)絡(luò)往往是兩者的結(jié)合。因此，在本文中，我們建立多目標(biāo)優(yōu)化模型，穩(wěn)定網(wǎng)絡(luò)的目標(biāo)函數(shù)的簡(jiǎn)單表達(dá)式如下：

數(shù)學(xué)期望和方差是

三、基于遺傳算法的模型求解

遺傳算法在沒(méi)有任何初始值信息的情況下，可以非常有效地實(shí)現(xiàn)全局最優(yōu)，但明顯的缺點(diǎn)是，該方法包含許多可變參數(shù)，不同的參數(shù)值對(duì)結(jié)果有不同的影響。在傳統(tǒng)的遺傳算法中，參數(shù)值的確定是基于程序員的經(jīng)驗(yàn)，通過(guò)實(shí)驗(yàn)和失敗經(jīng)驗(yàn)得到的。顯然，這需要更多的時(shí)間，但它能保證最好。本文采用擬正交實(shí)驗(yàn)法，選擇遺傳算法的初始參數(shù)。

與染色體對(duì)應(yīng)的隸屬函數(shù)參數(shù)使用實(shí)數(shù)編碼。一方面，為了避免搜索空間過(guò)大而提高搜索效率，種群規(guī)模不能太大。另一方面，種群選擇的規(guī)模也與解決非線性問(wèn)題的困難程度有關(guān)。我們選擇的參數(shù)如下：

進(jìn)化產(chǎn)生的最大數(shù)量為200；

種群數(shù)量為50人：

變異概率Pm=0.01：

交叉概率Pc=0.7

利用謝菲爾德遺傳算法工具箱實(shí)現(xiàn)遺傳算法，采用二進(jìn)制編碼的個(gè)體編碼，交叉算子采用最簡(jiǎn)單的單點(diǎn)交叉算子，利用隨機(jī)突變的方法選擇突變。采用交叉概率和變異概率的自適應(yīng)調(diào)節(jié)方法。為了避免“早熟”現(xiàn)象，本文采用改進(jìn)的自適應(yīng)交叉和變異概率調(diào)整算法。

四、仿真分析

我們選取京津冀地區(qū)13個(gè)主要城市的緯度和經(jīng)度數(shù)據(jù)進(jìn)行仿真分析，數(shù)據(jù)如下表1所示：

計(jì)算步驟：

步驟1.處理數(shù)據(jù)（將經(jīng)度和緯度數(shù)據(jù)轉(zhuǎn)換成平面坐標(biāo)數(shù)據(jù)）

步驟2.建立交通網(wǎng)絡(luò)優(yōu)化模型。

步驟3.使用改進(jìn)的算法求解模型。

步驟4.仿真結(jié)果分析（根據(jù)表1中的數(shù)據(jù)，選擇優(yōu)先點(diǎn)的1-3點(diǎn)，其它點(diǎn)考慮距離和流量，優(yōu)化結(jié)果如圖1所示）

五、結(jié)論

本文首先建立了交通網(wǎng)絡(luò)優(yōu)化模型，然后從算子理論出發(fā)改進(jìn)遺傳算法。仿真實(shí)驗(yàn)結(jié)果表明，改進(jìn)的遺傳算法可以解決交通網(wǎng)絡(luò)優(yōu)化模型。