基于ＧＩＳ的遺傳算法在路徑誘導(dǎo)中的應(yīng)用與實(shí)現(xiàn)

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