摘要：最優(yōu)路徑搜尋是路徑誘導(dǎo)問題的核心，文章在路徑優(yōu)化問題的求解中，將遺傳算法和蟻群思想進行融合，首先利用前部分遺傳操作迅速產(chǎn)生優(yōu)化解，并由此衍生的初始信息素進行蟻群計算，并將后部分遺傳操作引入蟻群算法以保證群體多樣性以防陷入局部，仿真實驗驗證了算法的正確性和有效性。在系統(tǒng)實現(xiàn)部分，基于GIS環(huán)境，利用面向?qū)ο蟮某绦蛟O(shè)計語言C++，在VC集成開發(fā)環(huán)境下，通過MapInfo獲取地圖，并且把得到的路徑優(yōu)化結(jié)果回顯在地圖上。
　　關(guān)鍵詞：遺傳算法；蟻群算法；路徑優(yōu)化；算法融合；雙遺傳蟻群算法
　　
　　路徑誘導(dǎo)是基于交通信息為出行者提供最優(yōu)路徑，以提高路網(wǎng)的使用效率。如何在短時間內(nèi)根據(jù)這些信息快速確定出最佳出行路徑是路徑誘導(dǎo)的核心問題。其理論、模型與算法的優(yōu)劣直接影響路徑誘導(dǎo)系統(tǒng)的功能。近年來，國內(nèi)外在這個研究領(lǐng)域中雖然進行了多方努力，取得了比較可觀的成果。但所建模型普遍存在計算量大、優(yōu)化時間長以及無法快速得到路經(jīng)優(yōu)化結(jié)果等問題?；谏鲜鲆蛩乜紤]，本文在路徑優(yōu)化問題的求解中，將遺傳算法和蟻群思想進行融合，首先利用前部分遺傳操作迅速產(chǎn)生優(yōu)化解，并由此衍生的初始信息素進行蟻群計算，并將后部分遺傳操作引入蟻群算法以保證群體多樣性以防陷入局部，使得問題求解更加容易，對許多工程應(yīng)用更具有實際意義，仿真實驗驗證了算法的正確性和有效性；在系統(tǒng)實現(xiàn)部分，基于GIS環(huán)境，利用面向?qū)ο蟮某绦蛟O(shè)計語言C++，在VC集成開發(fā)環(huán)境下，通過MapInfo獲取地圖，并且把得到的路徑優(yōu)化結(jié)果回顯在地圖上。
　　
　　一、遺傳算法（Genetic Algorithm，GA）介紹
　　
　　遺傳算法是20世紀(jì)60年代，由美國Michigan大學(xué)的J.H.Holland教授首先提出的，是模擬生物的遺傳和長期進化過程發(fā)展起來的一種搜索和優(yōu)化算法。它模擬了生物界“生存競爭，優(yōu)勝劣汰，適者生存”的機制，用逐次迭代法搜索尋優(yōu)。遺傳算法是一種優(yōu)化或者說是一種搜索算法，在某種意義上，它是“仿生學(xué)”在數(shù)學(xué)領(lǐng)域的直接應(yīng)用。最優(yōu)化問題的求解過程是從眾多的物種中選出最優(yōu)的解，生物進化的適者生存規(guī)律使得具有生存能力的染色體以最大的可能生存。這樣的共同特點使得遺傳算法可以在優(yōu)化問題中應(yīng)用。
　　遺傳算法的過程：剛開始時，隨機產(chǎn)生一些個體，構(gòu)成一個種群，一個種群中個體的數(shù)目即種群的規(guī)模（Population Size，N），N在求解過程中是不變的，然后通過幾種GA操作（選擇、交叉、變異等）作用在種群上，產(chǎn)生出一代代的新種群（每代有N個個體），從每一代種群中選出適應(yīng)度f高的優(yōu)質(zhì)個體，在解空間上成為候補解集合，直到滿足要求的收斂指標(biāo)，即求得了問題的解。
　　遺傳算法的計算流程如圖1所示。
　　
　　
　　二、蟻群算法（Ant Colony Algorithm，ACA）的基本思路
　　
　　蟻群算法是從自然界真實螞蟻覓食的群體行為得到啟發(fā)而提出的，其很多觀點都來源于螞蟻覓食原理。螞蟻
　　在運動過程中，能夠在它所經(jīng)過的路徑上釋放一種特殊的分泌物——信息素來尋找路徑。當(dāng)它們碰到一個還沒有走過的路口時，就隨機地挑選一條路徑前行，同時釋放出與路徑長度有關(guān)的信息素。螞蟻走的路徑越長，則釋放的信息素越小。當(dāng)后來的螞蟻再次碰到這個路口的時候，選擇信息量較大的路徑的概率相對較大，從而形成了一個正反饋機制。最優(yōu)路徑上的信息量越來越大，而其他路徑上的信息量卻會隨著時間的流逝而逐漸消減，最終整個蟻群會找出最優(yōu)路徑。蟻群行為具有非常高的自組織性，螞蟻之間交換著路徑信息，最終通過蟻群的自催化行為找到最優(yōu)路徑。因此，由大量螞蟻組成的蟻群的集體行為表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后者選擇該路徑的概率越大。螞蟻個體之間就是通過這種信息的交流達到以最短路徑搜索食物的目的。
　　蟻群算法的計算流程如圖2所示。
　　
　　
　　三、路徑誘導(dǎo)問題
　　
　　隨著道路負(fù)荷的加重，僅靠修建道路是解決不了問題的，必須利用ITS的各種方式提高現(xiàn)有交通條件的利用率，使交通流的分布更加合理。路徑誘導(dǎo)就是其中的一個重要手段，路徑誘導(dǎo)系統(tǒng)的主要對象是個別公共交通和個人交通車輛，其主要目的是提供基于交通信息的出行路線誘導(dǎo)。對于對路網(wǎng)情況熟悉的駕駛員可以通過提供個性化的路徑引導(dǎo)服務(wù)，減少其出行時間；對于不熟悉路網(wǎng)情況的駕駛員可以引導(dǎo)他們按照正確的道路行駛，同時還可以減少環(huán)境污染。
　　
　　四、雙遺傳蟻群算法求解路徑問題
　　
　　遺傳算法的特點在于能夠全局群體搜索，計算過程保留多種搜索途徑齊頭并進的優(yōu)勢；搜索過程不容易陷入局部最優(yōu)，對參數(shù)設(shè)置不敏感，但由于算法過程隨機處理較多，要尋求最優(yōu)解往往耗時太長，在理想時間內(nèi)只可獲得次優(yōu)解。蟻群算法的特點在于對于初始設(shè)置參數(shù)比較敏感，能直接影響算法計算進程；理想狀況中收斂速度快，但有時容易陷入局部搜索。初期信息素匱乏，求解速度慢。基于以上特點，結(jié)合當(dāng)前已有的遺傳算法和蟻群算法在路徑誘導(dǎo)問題中的研究，本文提出一種新的算法思想——雙遺傳蟻群算法（DGACA）。其基本思想是汲取兩種算法的優(yōu)點，克服各自的缺陷，優(yōu)勢互補。在算法開始首先應(yīng)用遺傳算法，根據(jù)其初期快速收斂的特點，產(chǎn)生一定程度上的優(yōu)化解，然后將該優(yōu)化解應(yīng)用于蟻群算法，產(chǎn)生信息素的初期參數(shù)值，然后利用蟻群計算方法求解。在求解中，再次應(yīng)用GA到每一次迭代過程，以蟻群算法每一代形成的解作為GA的初始群，GA計算完成的結(jié)果返回作為ACA新的最優(yōu)解。過程中應(yīng)用到GA兩次GA1和GA2。GA1主要用于快速粗略尋優(yōu)，以快為主，可修正GA減少交叉操作概率，刪減變異環(huán)節(jié)，GA2主要用于防誤陷局部極點，可增大交叉操作概率，刪減選擇操作。這就是雙遺傳蟻群操作基本思路。算法中雖然兩次利用了遺傳計算，但將常見的6次遺傳操作壓縮為4次，所以較大地壓縮了低效算法時間，保證搜索速度。
　　雙遺傳蟻群算法求解路徑誘導(dǎo)問題的整體計算步驟如下：
　　step1：路徑誘導(dǎo)問題初始化，設(shè)定相應(yīng)數(shù)值。
　　step2：GA1參數(shù)初始化，設(shè)定目標(biāo)函數(shù)，適應(yīng)度函數(shù)，變異率，迭代次數(shù)等。
　　step3：進行GA1計算，得到第一階段的優(yōu)化解。
　　step4：根據(jù)上述優(yōu)化解對ACA參數(shù)進行初始化。
　　step5：由當(dāng)前設(shè)定數(shù)值進行常規(guī)ACA計算，直到產(chǎn)生完成路徑。
　　step6：以當(dāng)前的解群和最優(yōu)解作為初始化GA2。
　　step7：進行GA2計算，得到新的全局最優(yōu)解。
　　step8：返回ACA計算中，信息素更新。
　　step9：判斷是否滿足ACA結(jié)束條件，若不滿足轉(zhuǎn)step5，否則轉(zhuǎn)step10。
　　step10：計算完成，輸出結(jié)果。
　　
　　五、動態(tài)誘導(dǎo)系統(tǒng)的開發(fā)與實現(xiàn)
　　
　　本文所應(yīng)用的開發(fā)方法是基于組件式技術(shù)的二次開發(fā)。通過Visual C++6.0加載MAPX開發(fā)組件，實現(xiàn)對于地圖數(shù)據(jù)和圖形化的交通信息的存儲、管理。然后利用C++語言來完成遺傳算法各種操作的實現(xiàn)，包括抽取路網(wǎng)代碼的實現(xiàn)、編碼問題的實現(xiàn)、選擇算子的實現(xiàn)、交叉算子的實現(xiàn)、變異算子的實現(xiàn)和隨機生成路徑的實現(xiàn)。
　　本系統(tǒng)先通過以下的路線信息表以路線信息進行存儲：
　　
　　通過表3可知，通過節(jié)點的相連，整個交通線路形成一個網(wǎng)絡(luò)連通圖，實現(xiàn)了在MapInfo表中隱含拓?fù)潢P(guān)系，這樣的數(shù)據(jù)結(jié)構(gòu)為算法的實現(xiàn)提供了基礎(chǔ)。
　　選擇地圖中的從MapInfo轉(zhuǎn)換，可以得到地圖，如圖3所示：
　　當(dāng)要求路徑時，按一下左下角的第二個圖標(biāo)，就出現(xiàn)圖4所示的對話框。
　　當(dāng)依次輸入起點與終點并按搜索時，系統(tǒng)自動調(diào)用遺傳算法的各種操作的程序代碼，進行最優(yōu)路徑的計算，將得到的結(jié)果用粗線在地圖上表示出來，如圖5所示。
　　
　　
　　六、結(jié)論
　　
　　本文結(jié)合GIS環(huán)境的特點，提出了利用MapInfo建立路網(wǎng)信息的存儲機制；提出了一種基于不定長編碼的改進遺傳算法，并設(shè)計了相應(yīng)的交叉、變異算子，保證生成路徑的合法性，減小了搜索空間，提高了搜索效率；在VC++開發(fā)環(huán)境中通過加載MAPX組件建立了原型系統(tǒng)并給出了實驗的仿真結(jié)果，仿真結(jié)果表明本文所提出的改進遺傳算法在解決路徑優(yōu)化問題上具有良好的效果。
　　
　　參考文獻：
　　1、陳國良等.遺傳算法及其應(yīng)用[M].國防