游　堯，林培群（華南理工大學(xué)土木與交通學(xué)院，廣東 廣州 510640）

基于智能優(yōu)化算法的動(dòng)態(tài)路徑誘導(dǎo)方法研究進(jìn)展

游堯，林培群
（華南理工大學(xué)土木與交通學(xué)院，廣東 廣州 510640）

采用綜述的方法對(duì)當(dāng)前動(dòng)態(tài)路徑誘導(dǎo)方法中一些有代表性的智能優(yōu)化算法進(jìn)行了深刻的探討與總結(jié),為未來(lái)進(jìn)行深入而廣泛的智能交通系統(tǒng)研究及應(yīng)用奠定基礎(chǔ)。主要從算法特性、改進(jìn)效果、性能評(píng)價(jià)等方面詳細(xì)討論了智能優(yōu)化算法在動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)中的常見(jiàn)改進(jìn)機(jī)制及其效果，給出了這些優(yōu)化算法的基本思想、優(yōu)缺點(diǎn)及其應(yīng)用局限性；并對(duì)智能優(yōu)化算法性能評(píng)價(jià)方法的研究現(xiàn)狀進(jìn)行了詳細(xì)的分析與總結(jié)，為建模人員和研究人員對(duì)智能交通系統(tǒng)中動(dòng)態(tài)路徑誘導(dǎo)方法的選擇和研究提供支持；最后結(jié)合算法應(yīng)用分析成果，展望了智能優(yōu)化算法在動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)中的應(yīng)用發(fā)展前景和智能交通系統(tǒng)中進(jìn)一步研究未來(lái)動(dòng)態(tài)路徑誘導(dǎo)算法的重要研究方向。

動(dòng)態(tài)路徑誘導(dǎo)方法；研究進(jìn)展；智能優(yōu)化算法；蟻群算法；遺傳算法

第1卷 第1期|2015年2月

0　引言

面對(duì)規(guī)模越來(lái)越大的城市交通網(wǎng)絡(luò)，路徑尋優(yōu)的效率問(wèn)題使得基于純數(shù)學(xué)理論的最優(yōu)路徑算法面臨新的挑戰(zhàn)。傳統(tǒng)的圖論方法（如Dijkstra算法）和數(shù)學(xué)規(guī)劃方法計(jì)算量大，以致計(jì)算時(shí)間長(zhǎng)；而且根據(jù)幾何距離、道路質(zhì)量為路阻計(jì)算最優(yōu)路徑，不能客觀描述現(xiàn)實(shí)交通網(wǎng)絡(luò)的時(shí)變性。文獻(xiàn)[1]指出，路徑誘導(dǎo)是一個(gè)對(duì)實(shí)時(shí)性要求相當(dāng)高的系統(tǒng)，過(guò)分追求模型的精確和復(fù)雜并沒(méi)有多大幫助。描述交通網(wǎng)絡(luò)的模型越復(fù)雜，算法的靈敏性就會(huì)減弱，最優(yōu)路徑的求解復(fù)雜度也越大，計(jì)算中的省略誤差通常也越大，這些都會(huì)降低模型精確帶來(lái)的優(yōu)勢(shì)。近年來(lái)，一些學(xué)者采用對(duì)模型精度要求較低的智能化方法研究動(dòng)態(tài)交通誘導(dǎo)問(wèn)題，智能優(yōu)化算法[2-3]放寬了優(yōu)化問(wèn)題目標(biāo)函數(shù)，加之本身的靈活性，在解決復(fù)雜結(jié)構(gòu)優(yōu)化問(wèn)題方面有著傳統(tǒng)優(yōu)化算法無(wú)法比擬的優(yōu)越性。因此，智能優(yōu)化算法在各個(gè)領(lǐng)域的優(yōu)化計(jì)算中都得到廣泛的應(yīng)用，依賴這類算法，理論上可以在盡可能短的時(shí)間內(nèi)找到問(wèn)題的最優(yōu)解或近似最優(yōu)解。

1　動(dòng)態(tài)路徑誘導(dǎo)方法研究現(xiàn)狀

基本智能優(yōu)化算法缺乏堅(jiān)實(shí)的理論基礎(chǔ)，同時(shí)，其效率低、容易陷入局部最優(yōu)等缺陷，難以滿足動(dòng)態(tài)路徑誘導(dǎo)的實(shí)際需要。因此，在應(yīng)用領(lǐng)域的研究也多是采用實(shí)驗(yàn)的方法，針對(duì)特殊的問(wèn)題，設(shè)計(jì)特殊的優(yōu)化算子，通過(guò)反復(fù)實(shí)驗(yàn)來(lái)確定算法參數(shù)，其設(shè)計(jì)步驟如圖1所示。通過(guò)優(yōu)化設(shè)計(jì)而形成的方法在精度、精度時(shí)間比等評(píng)價(jià)指標(biāo)[4]上往往能取得滿意的效果。

圖1　基于智能優(yōu)化算法的動(dòng)態(tài)路徑誘導(dǎo)方法設(shè)計(jì)步驟

數(shù)值實(shí)驗(yàn)是驗(yàn)證算法的重要方法，選取合適的測(cè)試樣本是數(shù)值實(shí)驗(yàn)的關(guān)鍵。實(shí)驗(yàn)的內(nèi)容就是算法的整體性能評(píng)價(jià)、算子測(cè)試以及參數(shù)測(cè)試。數(shù)值實(shí)驗(yàn)的結(jié)果一般反饋到參數(shù)選取階段，通過(guò)參數(shù)的相關(guān)性和靈敏度測(cè)試，可以大致地確定參數(shù)變化對(duì)算法運(yùn)行的影響。經(jīng)過(guò)實(shí)驗(yàn)，發(fā)現(xiàn)一些能夠取得較好運(yùn)行效果的參數(shù)，如若達(dá)不到預(yù)期還可以優(yōu)化算子設(shè)計(jì)。

1.1基于蟻群算法的動(dòng)態(tài)交通誘導(dǎo)方法

蟻群算法[5]是受自然界螞蟻尋路行為啟發(fā)產(chǎn)生的一種具有自適應(yīng)特性的模擬仿生算法，不需要建立復(fù)雜的數(shù)學(xué)模型和大量數(shù)學(xué)計(jì)算，簡(jiǎn)單易實(shí)現(xiàn)。蟻群算法自問(wèn)世以來(lái)表現(xiàn)出了強(qiáng)大的生命力，具有并行性、正反饋性、健壯性等特點(diǎn)，且搜索過(guò)程不需要人工干預(yù)，在求解旅行商（TSP）問(wèn)題、分配問(wèn)題、job-shop調(diào)度問(wèn)題上都取得了較好的效果[6-9]?；鞠伻核惴ㄔ谄溟_(kāi)始時(shí)，信息素的作用不明顯；雖然過(guò)程中正反饋機(jī)制能強(qiáng)化得到較好解，但卻使算法出現(xiàn)停滯現(xiàn)象，即只取得了局部最優(yōu)解就停止，而未達(dá)到全局最優(yōu)解。因此，學(xué)者對(duì)其進(jìn)行了一系列改進(jìn)研究以適應(yīng)動(dòng)態(tài)交通網(wǎng)絡(luò)實(shí)時(shí)性與快速性的特點(diǎn)。

杜長(zhǎng)海、黃席樾等人[10]提出帶方向的信息素更新和混沌選擇策略來(lái)改進(jìn)蟻群算法，算法將路網(wǎng)節(jié)點(diǎn)間的相對(duì)位置信息引入信息素更新，以加快搜索速度；使用混沌擾動(dòng)改進(jìn)選擇策略，以避免出現(xiàn)早熟停滯現(xiàn)象。其優(yōu)點(diǎn)在于通過(guò)對(duì)自然界中螞蟻尋路行為的模擬，在全局范圍內(nèi)動(dòng)態(tài)確定車輛最優(yōu)行駛路線，提高了整個(gè)交通系統(tǒng)的效率。

Yang[11]結(jié)合實(shí)時(shí)的城市道路交通流信息來(lái)解決城市動(dòng)態(tài)路徑誘導(dǎo)難題，提出了一種基于蟻群優(yōu)化的算法，為司機(jī)提供實(shí)時(shí)最佳路徑。算法使用優(yōu)先級(jí)高的干線道路循環(huán)和實(shí)時(shí)交通信息，減少并避免駕駛困難的道路；考慮到具體城市交通的特點(diǎn)，采用限制搜索區(qū)域機(jī)制來(lái)減少螞蟻的時(shí)間復(fù)雜度，提高了算法的搜索性能。

周明秀、程科等人[12]提出了動(dòng)態(tài)路徑規(guī)劃中改進(jìn)蟻群算法的方法，算法改進(jìn)距離啟發(fā)因子以增加目標(biāo)節(jié)點(diǎn)對(duì)下一節(jié)點(diǎn)的影響，從而提高全局搜索能力，避免陷于局部最優(yōu)解，提高收斂速度；引入多個(gè)路徑質(zhì)量約束來(lái)改進(jìn)信息素更新，模擬出行者在選擇路徑時(shí)表現(xiàn)的多目標(biāo)性及各目標(biāo)屬性的特點(diǎn)。算法保證了在較短時(shí)間內(nèi)得到全局最優(yōu)解，有效地克服了傳統(tǒng)蟻群算法中收斂速度慢、易陷入局部最優(yōu)解的缺陷。

黨希望[13]提出基于主次種群策略的蟻群算法的動(dòng)態(tài)路徑優(yōu)化算法，相應(yīng)的加入了信息素交流機(jī)制和信息素更新方法，并根據(jù)動(dòng)態(tài)路網(wǎng)模型和TSP模型的不同，適時(shí)改進(jìn)了路徑交叉變異策略和路徑去交叉策略；將小窗口策略和PASPAS算法中狀態(tài)轉(zhuǎn)移參數(shù)的歸一化處理結(jié)合起來(lái)，減少了數(shù)據(jù)處理量，增加了狀態(tài)轉(zhuǎn)移概率的準(zhǔn)確性。算法結(jié)合路徑交叉變異策略和路徑去交叉策略的優(yōu)勢(shì)，雖然時(shí)間復(fù)雜度略有提升，但解質(zhì)量和搜索能力得到了改善。

劉偉[14]給出了一種基于信息素?cái)U(kuò)散策略的雙種群蟻群算法——PDDPAS算法。算法選取了三個(gè)不同規(guī)模的TSP問(wèn)題對(duì)PDDPAS算法進(jìn)行實(shí)驗(yàn)，分別對(duì)PDDPAS算法性能、參數(shù)的設(shè)置、信息素?cái)U(kuò)散的策略進(jìn)行考察，得出了相應(yīng)的設(shè)置方案。PDDPAS算法使用信息素?cái)U(kuò)散策略提高了算法的全局尋優(yōu)能力，使用雙種群策略提高了算法的收斂速度。

董永峰、劉艷柳等人[15]提出了一種基于改進(jìn)蟻群算法的求解K最短路徑方法，實(shí)現(xiàn)了動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)中K最短路徑的搜索，通過(guò)引入方向函數(shù)作為新的啟發(fā)式因子，使其能在更少的繁殖代數(shù)下搜索到全局最優(yōu)解，提高了算法的全局搜索能力。在求解K最短路徑時(shí)將交叉口延誤時(shí)間這一因素加入了目標(biāo)函數(shù)中，使之符合出行者的出行行為。

林娜、霍志勝等人[16]提出基于免疫遺傳的多路搜索蟻群動(dòng)態(tài)路徑誘導(dǎo)算法，利用了蟻群系統(tǒng)算法的動(dòng)態(tài)性、正反饋性和分布式計(jì)算的優(yōu)點(diǎn)；同時(shí)兼容了免疫遺傳算法的全局搜索能力以及容易和其他算法相結(jié)合等特點(diǎn)。隨著動(dòng)態(tài)因素的增加，算法的復(fù)雜性也在增加，因此算法的效率在降低，同時(shí)算法又易陷入局部最優(yōu)狀態(tài)。

HUANG[17]通過(guò)在實(shí)時(shí)交通信息網(wǎng)絡(luò)中采用蟻群算法找出最優(yōu)路徑，然后利用群決策理論提出了基于蟻群算法和群體決策的動(dòng)態(tài)路徑優(yōu)化方法。算法考慮了相鄰交叉口距離以及部分交通流飽和度兩個(gè)參數(shù)，結(jié)合蟻群算法和最優(yōu)路徑，通過(guò)不同群體決策算法的結(jié)果比較得到了最優(yōu)動(dòng)態(tài)路徑優(yōu)化方法。

總的來(lái)說(shuō)，基于蟻群算法及其改進(jìn)算法的動(dòng)態(tài)路徑誘導(dǎo)研究一直都未停止，研究者嘗試各種策略來(lái)解決基本蟻群算法的應(yīng)用缺陷以及探索其能夠適合的結(jié)合算法。特別是基于蟻群算法的動(dòng)態(tài)路徑誘導(dǎo)應(yīng)用研究已經(jīng)比較成熟，在適應(yīng)性、加速收斂、防止早熟停滯、解的多樣性與全局性等性能上都得到了較大提高[18]，能滿足動(dòng)態(tài)路徑誘導(dǎo)需求。

1.2基于遺傳算法的動(dòng)態(tài)交通誘導(dǎo)方法

大家公認(rèn)的遺傳算法[19]是建立在自然選擇和群眾遺傳學(xué)機(jī)理基礎(chǔ)上的隨機(jī)、迭代、進(jìn)化、廣泛適應(yīng)性的搜索方法，其最先由John Holland于1975年提出，從此以后，它逐漸發(fā)展成為一種通過(guò)模擬自然進(jìn)化過(guò)程解決最優(yōu)化問(wèn)題的計(jì)算模型，近年來(lái)，基于遺傳算法的動(dòng)態(tài)路徑誘導(dǎo)方法的應(yīng)用研究也越來(lái)越深入。

楊兆升等人[20]基于從出行點(diǎn)出發(fā)，徑流量最大的通道到達(dá)目的點(diǎn)的路徑就是對(duì)應(yīng)于交通網(wǎng)絡(luò)的最短路徑假設(shè)提出了一種將交通流比擬成自然流體的神經(jīng)網(wǎng)絡(luò)誘導(dǎo)模式，并用遺傳算法來(lái)優(yōu)化流體神經(jīng)網(wǎng)絡(luò)的參數(shù)。計(jì)算表明，這種方法較傳統(tǒng)K路最短算法優(yōu)越，并且成功率較高。

Hitoshi等人[21]為實(shí)現(xiàn)車輛實(shí)時(shí)導(dǎo)航，提出了基于遺傳算法的動(dòng)態(tài)路徑選擇方法，研究分析了遺傳算法用于動(dòng)態(tài)路徑誘導(dǎo)的優(yōu)勢(shì)，設(shè)計(jì)了從當(dāng)前遺傳算法路徑解集中產(chǎn)生新路徑的方法，對(duì)路口交通燈下的等待、換道等行為進(jìn)行了模擬實(shí)現(xiàn)，通過(guò)與Dijkstra算法的對(duì)比實(shí)驗(yàn)，驗(yàn)證了遺傳算法的用于動(dòng)態(tài)車輛導(dǎo)航的高效性。但是文中很少涉及遺傳算法在動(dòng)態(tài)路徑誘導(dǎo)方面的具體算子設(shè)計(jì)，具有較大的局限性。

張水艦、李永樹(shù)等人[22]在建立時(shí)間依賴的動(dòng)態(tài)交通網(wǎng)絡(luò)模型的基礎(chǔ)上，提出了基于遺傳算法GA 和GIS的動(dòng)態(tài)路徑誘導(dǎo)算法，設(shè)計(jì)了基于改進(jìn)輪盤賭方式的個(gè)體選擇方式和高效的算子交叉、變異規(guī)則，仿真實(shí)驗(yàn)表明時(shí)間依賴動(dòng)態(tài)交通網(wǎng)絡(luò)模型適用性較高、算法收斂性良好，在一定程度上消除了動(dòng)態(tài)誘導(dǎo)中的Bracess現(xiàn)象。

遺傳算法中的關(guān)鍵是初始種群，初始種群的好壞將直接影響算法的收斂速度和收斂結(jié)果。鄒亮、徐建閩等人[23]提出了一種以隨機(jī)Dijkstra最短路徑算法為基礎(chǔ)，運(yùn)用遺傳算法來(lái)求解動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)中最短路徑問(wèn)題的算法，不僅能夠較快地求出較優(yōu)的路徑，而且對(duì)網(wǎng)絡(luò)沒(méi)有任何的約束條件，對(duì)離散和連續(xù)的動(dòng)態(tài)網(wǎng)絡(luò)模型都有效。

李松江[24]通過(guò)有損算法來(lái)減少遺傳算法初始種群的規(guī)模，從而提升了遺傳算法的整體效率；還將模擬退火算法引入到遺傳算法中，解決遺傳算法過(guò)早收斂的缺點(diǎn)。而且考慮到用戶的出行習(xí)慣，通過(guò)對(duì)適應(yīng)度函數(shù)的修改，可以使算法更人性化，更符合人機(jī)工程。通過(guò)實(shí)例驗(yàn)證了算法的可行性，較一般的遺傳算法和有損算法有著更高的搜索效率和更精確的最優(yōu)解。

李春元、魏武等人[25]鑒于采用序號(hào)編碼方式進(jìn)行遺傳操作時(shí)會(huì)產(chǎn)生大量無(wú)效路徑，結(jié)合城市道路交叉口左轉(zhuǎn)、右轉(zhuǎn)、直行等轉(zhuǎn)向行為，設(shè)計(jì)了一種新的基于轉(zhuǎn)向行為的編碼方式，減少了染色體在交叉、變異時(shí)的無(wú)效路徑的生成。算例表明，這種編碼方式可以有效提高算法收斂性，更容易獲得最優(yōu)解。

孫霞[26]通過(guò)引入一種新的帶染色體交叉控制策略的改進(jìn)遺傳算法，保證了一對(duì)適應(yīng)值有一定差異的染色體進(jìn)行交叉，使產(chǎn)生的后代性狀分離，并配合引入單點(diǎn)交叉算子，可以增加種群中個(gè)體的多樣性，擴(kuò)展解的搜索空間，避免了局部極值解；配合單點(diǎn)交叉算子，消除了傳統(tǒng)遺傳算法中早熟收斂的不足，并使所求最優(yōu)路徑更加貼近實(shí)時(shí)的交通狀態(tài)，切實(shí)達(dá)到誘導(dǎo)目的，提高整體路網(wǎng)的運(yùn)行效率。

趙丹[27]研究了適用于動(dòng)態(tài)最優(yōu)路徑求解的改進(jìn)自適應(yīng)遺傳算法，通過(guò)引入個(gè)體適應(yīng)度改進(jìn)算子選擇、設(shè)置不隨適應(yīng)度改變的遺傳率和變異率，解決了局部極小和收斂速度慢的問(wèn)題。建立城市路網(wǎng)模型和車輛路徑模型，把改進(jìn)的自適應(yīng)遺傳算法應(yīng)用到動(dòng)態(tài)交通條件下路徑誘導(dǎo)的最優(yōu)求解，仿真比較結(jié)果驗(yàn)證了改進(jìn)自適應(yīng)遺傳算法用于動(dòng)態(tài)最優(yōu)路徑計(jì)算、效率和實(shí)用性方面的優(yōu)勢(shì)。

Mainali等人[28]在分層網(wǎng)絡(luò)上提出基于遺傳算法的高層網(wǎng)絡(luò)修剪方法，以此提高交通網(wǎng)絡(luò)計(jì)算效率。路網(wǎng)由子網(wǎng)和始發(fā)地、目的地與邊界路口相交的高級(jí)網(wǎng)絡(luò)構(gòu)成，在搜索過(guò)程中減少高層網(wǎng)絡(luò)邊界路口的數(shù)量以提高搜索速度，但同時(shí)導(dǎo)致搜索路徑精度下降，因此在遺傳算法評(píng)價(jià)函數(shù)中引入了搜索時(shí)間與優(yōu)化目標(biāo)權(quán)重參數(shù)，以此提高搜索精度。使用道路網(wǎng)進(jìn)行修剪搜索驗(yàn)證，結(jié)果表明，該方法提高了計(jì)算效率且準(zhǔn)確性喪失較小。

總之，遺傳算法作為一種模擬生命進(jìn)化機(jī)制的隨機(jī)搜索優(yōu)化方法，以其簡(jiǎn)單通用、魯棒性強(qiáng)、適于并行處理以及應(yīng)用范圍廣等特點(diǎn)得到了學(xué)者的青睞，但其易出現(xiàn)早熟現(xiàn)象以及對(duì)初始種群很敏感。為了適用于動(dòng)態(tài)交通網(wǎng)絡(luò)，研究者在算子設(shè)計(jì)、初始解選擇等方面[29]進(jìn)行了改進(jìn)設(shè)計(jì)，通過(guò)仿真實(shí)驗(yàn)等手段證明改進(jìn)算法的合理性與高效性。

1.3基于其他智能優(yōu)化算法的動(dòng)態(tài)交通誘導(dǎo)方法

遺傳算法、蟻群算法在動(dòng)態(tài)路徑誘導(dǎo)中的應(yīng)用研究較為常見(jiàn)，形成了一套比較完整的動(dòng)態(tài)路徑誘導(dǎo)應(yīng)用理論體系。除此之外，神經(jīng)網(wǎng)絡(luò)算法[30]、粒子群優(yōu)化算法[31]的動(dòng)態(tài)路徑誘導(dǎo)的應(yīng)用研究相對(duì)較少；禁忌算法[32]、模擬退火算法[33]等算法應(yīng)用研究目前則主要停留在靜態(tài)路徑規(guī)劃階段。

李菲、肖洪祥[34]在動(dòng)態(tài)路徑優(yōu)化中引入了一種神經(jīng)動(dòng)態(tài)規(guī)劃算法，解決傳統(tǒng)算法計(jì)算大規(guī)模路網(wǎng)的優(yōu)化問(wèn)題時(shí)所表現(xiàn)出來(lái)的計(jì)算時(shí)間長(zhǎng)、存儲(chǔ)空間大等缺陷。它將傳統(tǒng)的動(dòng)態(tài)規(guī)劃和BP神經(jīng)網(wǎng)絡(luò)結(jié)合起來(lái)，通過(guò)逼近Q學(xué)習(xí)算法來(lái)尋求一種最優(yōu)策略，最終達(dá)到路徑優(yōu)化的目的。實(shí)驗(yàn)表明，該方法的實(shí)時(shí)性、并行性和全局性都優(yōu)于傳統(tǒng)動(dòng)態(tài)規(guī)劃。

馬艷麗、裴玉龍[35]將混沌神經(jīng)網(wǎng)絡(luò)應(yīng)用于動(dòng)態(tài)路徑誘導(dǎo)，在神經(jīng)網(wǎng)絡(luò)中引入混沌動(dòng)態(tài)，利用其遍歷性進(jìn)行隨機(jī)搜索，再由退火策略控制混沌動(dòng)態(tài)逐漸消失并轉(zhuǎn)入HNN進(jìn)一步優(yōu)化，從而可保證網(wǎng)絡(luò)收斂到一個(gè)最優(yōu)或近似最優(yōu)的穩(wěn)定平衡點(diǎn)。通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了將混沌神經(jīng)網(wǎng)絡(luò)應(yīng)用于動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)總能保證網(wǎng)絡(luò)收斂至全局最優(yōu)，有效克服了Hopfield神經(jīng)網(wǎng)絡(luò)易陷入局部最優(yōu)解的缺點(diǎn)，具有更高的搜索效率。

吳成東，楊麗英等人[36]提出了將神經(jīng)網(wǎng)絡(luò)與遺傳算法結(jié)合的動(dòng)態(tài)路徑誘導(dǎo)方法，研究了基于神經(jīng)網(wǎng)絡(luò)的交通信息實(shí)時(shí)預(yù)測(cè)方法，構(gòu)造了具有時(shí)變性的路阻矩陣，解決了傳統(tǒng)靜態(tài)路阻存在的時(shí)變性差等局限性問(wèn)題；提出了適用于路徑優(yōu)化的編碼方式、適應(yīng)度函數(shù)和遺傳操作算子，解決了求解效率和求解質(zhì)量的平衡問(wèn)題。

CHEN[37]在分析粒子群優(yōu)化算法的最基本原理和特征基礎(chǔ)上，從算法初始化、譯碼、健壯性計(jì)算、位置與速度更新等多個(gè)方面進(jìn)行分析，針對(duì)動(dòng)態(tài)交通網(wǎng)絡(luò)特點(diǎn)設(shè)計(jì)具體的改進(jìn)方法，將粒子群優(yōu)化算法應(yīng)用在動(dòng)態(tài)路徑誘導(dǎo)中。仿真實(shí)驗(yàn)表明，當(dāng)用于動(dòng)態(tài)路徑道路網(wǎng)絡(luò)搜索時(shí)，粒子群優(yōu)化算法具有速度快、準(zhǔn)確性高的特點(diǎn)，因此表明了粒子群優(yōu)化算法用于動(dòng)態(tài)路徑誘導(dǎo)的可行性與高效性。

陳曦[38]在分析常規(guī)粒子群優(yōu)化算法的基礎(chǔ)上，針對(duì)動(dòng)態(tài)交通問(wèn)題，采用一種帶變異因子的改進(jìn)的粒子群優(yōu)化算法。這種免疫粒子群優(yōu)化算法結(jié)合了粒子群優(yōu)化算法具有的全局尋優(yōu)能力和免疫系統(tǒng)的免疫信息處理機(jī)制，并且實(shí)現(xiàn)簡(jiǎn)單，改善了粒子群優(yōu)化算法擺脫局部極值點(diǎn)的能力，提高了算法進(jìn)化過(guò)程中的收斂速度和精度，實(shí)驗(yàn)表明其提出的算法具有較好的性能。

DENG[39]提出一種基于神經(jīng)網(wǎng)絡(luò)模型和粒子群算法相結(jié)合的優(yōu)化方法，算法搜索時(shí)使用改進(jìn)間接路徑編碼方案，簡(jiǎn)單、收斂速度快，不易陷入局部最優(yōu)解；針對(duì)不同拓?fù)浣煌ňW(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行模擬實(shí)驗(yàn)，均能以較高成功率找到最優(yōu)解和近似最優(yōu)解。混合算法大大提高了流體神經(jīng)元網(wǎng)絡(luò)的收斂效率，同時(shí)，神經(jīng)網(wǎng)絡(luò)模型和粒子群算法都是并行算法，很容易運(yùn)行在并行計(jì)算機(jī)甚至神經(jīng)計(jì)算機(jī)上，從而大大減少計(jì)算時(shí)間。

楊清波[40]采取了一種新的群智能優(yōu)化算法——人工魚群算法[41]來(lái)實(shí)現(xiàn)GIS環(huán)境下的動(dòng)態(tài)交通最優(yōu)路徑的求解，針對(duì)原始人工魚群算法初始魚群覆蓋空間的不確定性和收斂速度慢等問(wèn)題進(jìn)行了改進(jìn)研究。采用網(wǎng)格化魚群，使初始人工魚群在海域中均勻分布，利于人工魚更快的在全局范圍內(nèi)尋優(yōu)；算法中設(shè)立一個(gè)公告板，用來(lái)記錄最優(yōu)人工魚的狀態(tài)和該人工魚位置的食物濃度，以記錄歷史最優(yōu)狀態(tài)。通過(guò)實(shí)驗(yàn)對(duì)算法中各參數(shù)的選擇進(jìn)行了研究，得到了較優(yōu)的參數(shù)組合，并驗(yàn)證了改進(jìn)算法的有效性。

2　算法性能評(píng)價(jià)研究現(xiàn)狀

目前，常見(jiàn)的禁忌搜索算法、模擬退火算法、粒子群優(yōu)化算法、遺傳算法、蟻群算法等常被用來(lái)解決各個(gè)領(lǐng)域的NP完全問(wèn)題。智能優(yōu)化算法對(duì)解決組合優(yōu)化問(wèn)題都有較好的應(yīng)用，但隨著實(shí)際問(wèn)題的變化，各智能算法都有其不足之處。因此，建立一套符合智能優(yōu)化算法特點(diǎn)的評(píng)價(jià)標(biāo)準(zhǔn)對(duì)于其改進(jìn)與應(yīng)用研究十分必要。傳統(tǒng)優(yōu)化算法的性能指標(biāo)主要有兩個(gè)[42]：收斂性和收斂速度，但其基于確定型的搜索算法，并不適合用于智能優(yōu)化算法的評(píng)價(jià)。

動(dòng)態(tài)路徑誘導(dǎo)算法應(yīng)用研究當(dāng)中，主要通過(guò)比較算法時(shí)間復(fù)雜度、收斂速度等傳統(tǒng)優(yōu)化算法評(píng)價(jià)指標(biāo)評(píng)價(jià)算法應(yīng)用的有效性，也有通過(guò)比較找到最優(yōu)解的概率及其穩(wěn)定性等模糊性指標(biāo)，但缺乏完整的評(píng)價(jià)體系及理論依據(jù)。楊勁秋[4]詳細(xì)分析了傳統(tǒng)優(yōu)化算法的評(píng)價(jià)標(biāo)準(zhǔn)在智能優(yōu)化算法評(píng)價(jià)中的局限性，根據(jù)智能優(yōu)化算法的特點(diǎn)，提出了智能優(yōu)化算法的一系列具有可操作性的評(píng)價(jià)指標(biāo)，并提出了基于隨機(jī)搜索的性能評(píng)價(jià)及優(yōu)化解概率的分階段估計(jì)方法，對(duì)智能優(yōu)化算法的行為及其算子給出了具體的評(píng)價(jià)方法。

3　結(jié)論與展望

動(dòng)態(tài)路徑誘導(dǎo)是智能交通系統(tǒng)中最為人們所期許的功能之一，一般應(yīng)具有通過(guò)考慮交通網(wǎng)絡(luò)的變化來(lái)提供最小出行時(shí)間路徑的功能。本文研究了目前常見(jiàn)智能優(yōu)化算法在動(dòng)態(tài)路勁誘導(dǎo)中的應(yīng)用研究情況，為了更好地評(píng)價(jià)各種智能優(yōu)化算法在動(dòng)態(tài)交通誘導(dǎo)問(wèn)題上的應(yīng)用效果，提出了具有偏好的智能優(yōu)化算法多指標(biāo)評(píng)價(jià)模型。國(guó)內(nèi)外有很多學(xué)者都曾對(duì)動(dòng)態(tài)交通網(wǎng)絡(luò)的特點(diǎn)，有針對(duì)性地進(jìn)行算子設(shè)計(jì)、參數(shù)優(yōu)化等研究工作，但該問(wèn)題的研究大多停留在假定性較強(qiáng)的理論層次，動(dòng)態(tài)路徑誘導(dǎo)算法的實(shí)時(shí)性仍然還是一個(gè)很少有人涉足的研究領(lǐng)域[2]。

智能交通系統(tǒng)中的路徑誘導(dǎo)算法是一個(gè)復(fù)雜的系統(tǒng)工程，具有很強(qiáng)的理論性和實(shí)現(xiàn)上的挑戰(zhàn)性。隨著車聯(lián)網(wǎng)、移動(dòng)互聯(lián)網(wǎng)等技術(shù)的發(fā)展，結(jié)合智能交通系統(tǒng)的實(shí)際需求，基于智能優(yōu)化算法的動(dòng)態(tài)路徑誘導(dǎo)算法將會(huì)有更廣闊的前景，其應(yīng)用研究可以分為以下三個(gè)方向。

（1）應(yīng)用算法類型的多元化。一方面，隨著研究的不斷深入以及遺傳算法與蟻群算法的應(yīng)用實(shí)踐，智能優(yōu)化算法的優(yōu)勢(shì)逐漸表現(xiàn)出來(lái)，受到更多研究者和交通部門的重視；另一方面，最優(yōu)路徑搜索問(wèn)題也屬于組合優(yōu)化問(wèn)題，智能優(yōu)化算法在一系列NP問(wèn)題已經(jīng)證明了其優(yōu)越性，而傳統(tǒng)算法難以解決規(guī)模越來(lái)越龐大的動(dòng)態(tài)交通網(wǎng)絡(luò)尋優(yōu)問(wèn)題。

（2）算法之間的結(jié)合性發(fā)展。單個(gè)智能優(yōu)化算法具有的某些缺點(diǎn)難以滿足動(dòng)態(tài)交通網(wǎng)絡(luò)實(shí)際需要，如果采用混合算法，用其他智能優(yōu)化算法的思想對(duì)某種智能優(yōu)化算法進(jìn)行改進(jìn)，往往能取得更好的效果。（3）發(fā)展基于多目標(biāo)優(yōu)化的智能優(yōu)化算法。

實(shí)際問(wèn)題中常常需要同時(shí)考慮路程最短、時(shí)間最少、費(fèi)用最省、風(fēng)險(xiǎn)最小等多種因素，即節(jié)點(diǎn)之間的權(quán)重屬性有多個(gè)。因此研究多目標(biāo)具有很現(xiàn)實(shí)的意義，多目標(biāo)所得的解是一種“折中”的解。

[1]李威武，王慧.智能交通系統(tǒng)中路徑誘導(dǎo)算法研究進(jìn)展[J].浙江大學(xué)學(xué)報(bào)：工學(xué)版，2005，39（6）：819-825.

[2]黃席越，張著洪，胡小兵，等.現(xiàn)代智能算法理論及應(yīng)用[M].北京：科學(xué)出版社，2005.

[3]鐘一文.智能優(yōu)化方法及其應(yīng)用研究[D].杭州：浙江大學(xué)，2005.

[4]楊勁秋.智能優(yōu)化算法評(píng)價(jià)模型研究[D].杭州：浙江大學(xué)，2011.

[5]Schoonderwoerd R,Holland O,Bruten J,et al.Ant-Based Load Balancing in Telecommunications Networks[J].Adap?tive Behavior,1996,5(2):169-207.

[6]Colorni A,Dorigo M,Maniezzo V,et al.Ant System for Job-Shop Scheduling[J].Belgian J of Operations Research Statis?tics and Computer Science,1994,34(1):39-53.

[7]Dorigo M,Maniezzo V,Colorni A.Ant System:Optimization by a Colony of Cooperating Agents[J].IEEE Transactions on System,Man,and Cybernetics-Part B,1996,26(1):29-41.

[8]Dorigo M,Gambardella L M.Ant Colony System:A Coopera?tive Learning Approach to the Traveling Salesman Problem [J].IEEE Transactions on Evolutionary Computation,1997,1 (1):53-66.

[9]Mohemmed A W,Sahoo N C,Geok T K.Solving Shortest Path Problem Using Particle Swarm Optimization[J].Applied Soft Computing,2008,8(4):1643-1653.

[10]杜長(zhǎng)海，黃席樾.改進(jìn)的蟻群算法在動(dòng)態(tài)路徑誘導(dǎo)中的應(yīng)用研究[J].計(jì)算機(jī)工程與應(yīng)用，2008，44（27）：236-239.

[11]YANG Jian-ren.A Dynamic Route Guidance Algorithm Based on Modified Ant Colony Optimization[C]//Computer Network and Multimedia Technology.Wuhan:IEEE,2009: 1-3.

[12]周明秀，程科.動(dòng)態(tài)路徑規(guī)劃中的改進(jìn)蟻群算法[J].計(jì)算機(jī)科學(xué)，2013，40（1）：314-316.

[13]黨希望.基于主次種群蟻群算法的動(dòng)態(tài)路徑優(yōu)化研究[D].成都：西南交通大學(xué)，2013.

[14] 劉偉.基于蟻群算法的動(dòng)態(tài)路徑誘導(dǎo)研究[D].成都：西南交通大學(xué)，2008.

[15]董永峰，劉艷柳，張娜.基于改進(jìn)蟻群算法的動(dòng)態(tài)多路徑誘導(dǎo)系統(tǒng)研究[J].河北工業(yè)大學(xué)學(xué)報(bào)，2010，39 （3）：46-51.

[16] 林娜，霍志勝.一種基于免疫遺傳的多路搜索蟻群動(dòng)態(tài)路徑誘導(dǎo)算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2013（3）：590-594.

[17]HUANG Yan-guo,LUO Qiang.Dynamic Path Optimization Method Based on Ant Colony Algorithm and Group Deci?sion-making[C]//Proceedings of the 10th World Congress on Intelligent Control and Automation.Beijing:IEEE, 2012:300-304.

[18]牛新征，佘堃，路綱.蟻群算法研究的新進(jìn)展和展望[J].計(jì)算機(jī)應(yīng)用研究，2007，2（4）：12-15.

[19]Holland J H.Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology,Con?trol,and Artificial Intelligence[M].Ann Arbor:The Univer?sity of Michigan Press,1975.

[20]WEN Hui-min,YANG Zhao-sheng.Study on the Shortest Path Algorithm Based on Fluid Neural Network of In-Vehi?cle Traffic Flow Guidance System[C]//Proceedings of the IEEE International Conference on Vehicle Electronics. Changchun:IEEE,1999:110-113.

[21]Hitoshi Kanoh,Hideki Kozuka.Evaluation of GA-Based Dynamic Route Guidance for Car Navigation Using Cellu?lar Automata[C]//Intelligent Vehicle Symposium.IEEE, 2002:178-183.

[22] 張水艦，李永樹(shù).利用GA和GIS的動(dòng)態(tài)路徑誘導(dǎo)算法[J].武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2009，34（12）：1476-1479.

[23]鄒亮，徐建閩.基于遺傳算法的動(dòng)態(tài)網(wǎng)絡(luò)中最短路徑問(wèn)題算法[J].計(jì)算機(jī)應(yīng)用，2005，25（4）：742-744.

[24]李松江.基于改進(jìn)遺傳算法的動(dòng)態(tài)路徑誘導(dǎo)系統(tǒng)的研究[D].長(zhǎng)春：長(zhǎng)春理工大學(xué)，2010.

[25]李春元，魏武.基于改進(jìn)遺傳算法的最優(yōu)路徑求解[J].交通與計(jì)算機(jī)，2007，25（5）：88-92.

[26] 孫霞，黃席樾.基于改進(jìn)遺傳算法的城市交通路徑誘導(dǎo)系統(tǒng)的研究[D].重慶：重慶大學(xué)，2007.

[27]趙丹.城市交通路徑誘導(dǎo)算法研究[D].西安：長(zhǎng)安大學(xué)，2009.

[28]Mainal M K,Mabu S,Hirasawa K.Pruning High-Level Net?work Using Genetic Algorithm for Efficient Hierarchical Route Planning in Road Networks[C]//IEEE Annual Confer?ence.Tokyo:IEEE,2011:2903-2909.

[29]Chang W A,Ramakrishna R S.A Genetic Algorithm for Shortest Path Routing Problem and the Sizing of Popula?tions[J].IEEE Transactions on Evolutionary Computation, 2002,6(6):566-579.

[30]DING Zhen,Leung Henry,ZHU Zhi-wen.A Study of theTransiently Chaotic Neural Network for Combinatorial Opti?mization[J].Mathematical and Computer Modeling,2002, 36(2):1007-1020.

[31]Bo-Yang Q U,Ponnuthurai Nagaratnam Suganthan,Shi-Zheng Zhao.Current Position-Based Fitness Euclideandistance Ratio Particle Swarm Optimizer for Multi-Modal Optimization[C]//Nature and Biologically Inspired Comput?ing.Fukuoka:IEEE,2011:383-388.

[32]Glover F.Future Paths of Integer Programming and Links to Artificial Intelligence[J].Computer and Operations Research,1986(5):533-549.

[33]LV Guang-ming,SUN Xiao-meng,WANG Jian.A Simulat?ed Annealing-New Genetic Algorithm and its Application [C]//Electronics and Optoelectronics.Dalian:IEEE,2011: 246-249.

[34]李菲，肖洪祥.基于神經(jīng)動(dòng)態(tài)規(guī)劃算法的最優(yōu)路徑選擇[J].桂林工學(xué)院學(xué)報(bào)，2009，29（1）：54-57.

[35]馬艷麗，裴玉龍.基于混沌神經(jīng)網(wǎng)絡(luò)的駕駛員動(dòng)態(tài)路徑誘導(dǎo)算法研究[J].交通運(yùn)輸系統(tǒng)工程與信息，2007，7 （1）：57-60.

[36]吳成東，楊麗英，許可.神經(jīng)網(wǎng)絡(luò)和遺傳算法在動(dòng)態(tài)路徑誘導(dǎo)中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2006（5）：177-179.

[37]CHEN Qun.Dynamic Route Guidance Method Based on Particle Swarm Optimization Algorithm[C]//2009 Second International Conference on Intelligent Computation Tech?nology and Automation.Changsha:IEEE,2009:267-270.

[38]陳曦.粒子群優(yōu)化算法的改進(jìn)及在動(dòng)態(tài)交通分配問(wèn)題中的應(yīng)用[D].長(zhǎng)沙：長(zhǎng)沙理工大學(xué)，2007.

[39]DENG Yan-fang,TONG Heng-qing,et al.Dynamic Short?est Path in Stochastic Traffic Networks Based on Fluid Neu?ral Network and Particle Swarm Optimization[C]//2010 Sixth International Conference on Natural Computation. Yantai:IEEE,2010:2325-2329.

[40]楊清波.GIS環(huán)境下的動(dòng)態(tài)交通最優(yōu)路徑算法研究[D].長(zhǎng)沙：中南大學(xué)，2012.

[41]李曉磊，邵之江，錢積新.一種基于動(dòng)物自治體的尋優(yōu)模式：魚群算法[J].系統(tǒng)工程理論與實(shí)踐，2002，22 （11）：32-38.

[42]FU L P,LRILETT R.Expected Shortest Paths in Dynamic and Stochastic Traffic Networks[J].Transportation Re?search B,1998,32(7):499-516.

New Trends of Dynamic Route Guidance Methods Based on Intelligent OptimizationAlgorithms

YOU Yao,LIN Pei-qun
(School of Civil Engineering and Transportation,South China University of Technology, Guangzhou 510640,China)

Some representative intelligent optimization algorithms in the dynamic route guidance meth?ods were discussed and summed up by the review method,which laid a foundation for the future research in the intelligent transportation system deeply and widely.The improvement mechanism and the applica?tion results of the intelligent optimization algorithm are analyzed from the view of the algorithm character?istics,improvement effect,performance evaluation,etc.And the basic idea,advantages,disadvantages and limitations of these algorithms were given.Besides,the research status of evaluation methods of the intelligent optimization algorithm performance was analyzed,which helped engineers and researchers to select the most suitable variability modeling techniques.Finally,combining with the analysis results of algorithms application,the application prospect and some important research directions in the future fur?ther research of the intelligent optimization algorithms in intelligent transportation system were forecast. Key words:dynamic route guidance methods;research progress;intelligent optimization algorithms; ant colony optimization;genetic algorithm

U495

A

2095-9931（2015）01-0020-07

10.16503/j.cnki.2095-9931.2015.01.004

2014-10-22