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

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

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

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

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

第1卷 第1期|2015年2月

0　引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3　結(jié)論與展望

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

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

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

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

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

[1]李威武，王慧.智能交通系統(tǒng)中路徑誘導(dǎo)算法研究進(jìn)展[J].浙江大學(xué)學(xué)報：工學(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)化算法評價模型研究[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]杜長海，黃席樾.改進(jìn)的蟻群算法在動態(tài)路徑誘導(dǎo)中的應(yīng)用研究[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]周明秀，程科.動態(tài)路徑規(guī)劃中的改進(jìn)蟻群算法[J].計算機(jī)科學(xué)，2013，40（1）：314-316.

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

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

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

[16] 林娜，霍志勝.一種基于免疫遺傳的多路搜索蟻群動態(tài)路徑誘導(dǎo)算法[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ī)應(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] 張水艦，李永樹.利用GA和GIS的動態(tài)路徑誘導(dǎo)算法[J].武漢大學(xué)學(xué)報：信息科學(xué)版，2009，34（12）：1476-1479.

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

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

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

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

[27]趙丹.城市交通路徑誘導(dǎo)算法研究[D].西安：長安大學(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)動態(tài)規(guī)劃算法的最優(yōu)路徑選擇[J].桂林工學(xué)院學(xué)報，2009，29（1）：54-57.

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

[36]吳成東，楊麗英，許可.神經(jīng)網(wǎng)絡(luò)和遺傳算法在動態(tài)路徑誘導(dǎo)中的應(yīng)用[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)及在動態(tài)交通分配問題中的應(yīng)用[D].長沙：長沙理工大學(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)境下的動態(tài)交通最優(yōu)路徑算法研究[D].長沙：中南大學(xué)，2012.

[41]李曉磊，邵之江，錢積新.一種基于動物自治體的尋優(yōu)模式：魚群算法[J].系統(tǒng)工程理論與實踐，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