基于蟻群算法的進(jìn)路搜索算法研究及應(yīng)用

吳相飛，敖銀輝

(廣東工業(yè)大學(xué) 機(jī)電工程學(xué)院，廣東 廣州 510006)

0 引言

地鐵信號聯(lián)鎖系統(tǒng)是提高地鐵運(yùn)輸效率、確保車站運(yùn)行安全的必要技術(shù)裝備。聯(lián)鎖一般來說是指在進(jìn)路、信號機(jī)、道岔和區(qū)段之間建立的一種相互制約關(guān)系[1-2]。在地鐵車站連鎖系統(tǒng)作業(yè)中，進(jìn)路的選排對接發(fā)車工作的效率和車站是否能通過有著直接的影響，如何合理有效地選排接發(fā)列車和調(diào)車工作進(jìn)路是確保行車安全和提升行車效率的重要研究內(nèi)容。

計(jì)算機(jī)聯(lián)鎖的進(jìn)路選排有很多種進(jìn)路搜索的方法，其中經(jīng)常使用的算法有A*進(jìn)路搜索算法和二叉樹遍歷搜索[3-6]。近年來很多的研究學(xué)者大量使用了智能優(yōu)化算法來求解路徑優(yōu)化方面的問題。例如文獻(xiàn)[7]將高度搜索算法用于搜索基本進(jìn)路和變更進(jìn)路的過程，該算法彌補(bǔ)了深度優(yōu)先算法和廣度優(yōu)先算法的缺陷，使得搜索目標(biāo)更加明確、搜索過程更加高效準(zhǔn)確；文獻(xiàn)[8]通過對地鐵車站站場圖和有向圖的結(jié)合，研究出了一種適用于地鐵車站站場實(shí)際狀況的進(jìn)路搜索算法，并給出了具體的描述內(nèi)容。本文結(jié)合以上文獻(xiàn)提出了一種基于蟻群算法的進(jìn)路搜索算法，其以蟻群算法為核心，具有精確、快速有效、占用空間小的特點(diǎn)，能高效地搜索出一條所需基本進(jìn)路。

1 地鐵站場數(shù)據(jù)結(jié)構(gòu)分析及建模

站場型數(shù)據(jù)結(jié)構(gòu)指的是依據(jù)地鐵車站站場信號布置地鐵車站平面圖，由地鐵車站各個(gè)信號點(diǎn)依據(jù)其在車站平面圖的位置鏈接組成，本質(zhì)就是節(jié)點(diǎn)的鏈接表[9-10]。廣州市地鐵三號線站場平面布置如圖1所示。為了簡化對車站站場的建模過程，只研究了列車進(jìn)路的選排，暫時(shí)沒有研究調(diào)車進(jìn)路的選排。

圖1 廣州市地鐵三號線站場平面布置

首先我們要簡化站場圖，站場下行接車口由兩個(gè)方向組成，分別是崗頂方向和廣州東方向。設(shè)上行信號機(jī)用S表示，下行信號機(jī)用X表示；用W開頭的一段數(shù)字代表道岔，如W0001號道岔；用T開頭的一段數(shù)字表示軌道區(qū)段，如T0001。如圖1所示，地鐵車站站場是由各個(gè)信號設(shè)備按一定的連接方式組成的設(shè)備網(wǎng)絡(luò)。地鐵車站信號設(shè)備主要包括信號機(jī)、道岔、軌道區(qū)段等，且這三者信號設(shè)備之間存在物理連接關(guān)系。將信號機(jī)、道岔、軌道區(qū)段都作為站場圖節(jié)點(diǎn)并進(jìn)行統(tǒng)一定義，按照由左向右、由下向上的順序?qū)?jié)點(diǎn)依次進(jìn)行編號。把兩節(jié)點(diǎn)間的長度和所用通行時(shí)間等屬性表示為該邊的權(quán)值(例如編號2節(jié)點(diǎn)和編號3節(jié)點(diǎn)之間的權(quán)值為6)，就可以把地鐵車站站場抽象為一個(gè)帶權(quán)有向圖，如圖2所示。

2 基于蟻群算法的進(jìn)路搜索

2.1 蟻群算法進(jìn)路搜索的描述

地鐵車站站場由各個(gè)信號設(shè)備按一定的連接方式組成一個(gè)設(shè)備網(wǎng)絡(luò)。將各信號設(shè)備抽象為節(jié)點(diǎn)集合N={n1,n2,n3,…,ni}，各信號設(shè)備之間的距離長度抽象為對應(yīng)的邏輯邊集合dij(i,j=1，2，…，N)，例如d23表示編號節(jié)點(diǎn)2和節(jié)點(diǎn)3之間的距離長度。用τij(t)表示t時(shí)刻在節(jié)點(diǎn)i和節(jié)點(diǎn)j之間路徑上的信息素強(qiáng)度，用于模擬螞蟻在地鐵道路上的分泌信息。在改進(jìn)蟻群算法中[11-12]，初始信息素強(qiáng)度設(shè)為：

τij(0)=W/(dij+dje).

(1)

其中:dje為節(jié)點(diǎn)j與終點(diǎn)e的直線距離；W為給定常數(shù)。螞蟻k(1,2，…，M)識別各條路徑上的信息素強(qiáng)度來決定轉(zhuǎn)移方向，禁忌表tabuk用來記錄螞蟻k經(jīng)過的路徑。設(shè)q0為特定參數(shù)，0

當(dāng)q≤q0時(shí)：

(2)

(3)

其中:allowedk={0,1,…,n-1}-tabuk，為螞蟻k下一步允許選擇的節(jié)點(diǎn)；α為信息啟發(fā)式因子，代表軌跡信息的相對重要性；β為期望啟發(fā)式因子，代表能見度的重要性；τij為邊(i,j)上的信息濃度;ηij為啟發(fā)函數(shù)，ηij=1/dij,反映了螞蟻由節(jié)點(diǎn)i運(yùn)動(dòng)到節(jié)點(diǎn)j的啟發(fā)程度。在螞蟻k完成了一次路徑搜索后，將其經(jīng)過路徑上的信息素濃度按照局部更新原則進(jìn)行更新。其局部信息濃度更新規(guī)則為：

τij(t+n)=(1-ρ)τij(t)+ρΔτij(t).

(4)

其中:ρ為信息素蒸發(fā)系數(shù);τij(t+n)為t+n時(shí)刻邊(i,j)上的信息素濃度；Δτij(t)為經(jīng)過n時(shí)刻邊(i，j)上的信息素變化量。如果螞蟻k經(jīng)過路徑(i,j),則：

(5)

其中:Q為給定的參數(shù);Lk為第k只螞蟻在本次循環(huán)搜索所走的路徑長度。當(dāng)實(shí)驗(yàn)中所有的螞蟻都完成一次循環(huán)搜索之后，則對這一次迭代最好進(jìn)路(最小值為Llocalmin)上的信息素進(jìn)行調(diào)整更新：

τij(t+n)=(1-μ)τij(t)+μΔτij.

(6)

其中:μ為給定參數(shù)，且：

(7)

記錄全局最優(yōu)解：通過MATLAB進(jìn)行實(shí)驗(yàn)仿真，當(dāng)?shù)竭_(dá)設(shè)定的迭代次數(shù)或有停滯情況出現(xiàn)時(shí)，則實(shí)驗(yàn)結(jié)束。記錄迭代位置中顯示的局部最優(yōu)解中值最小的解，就是本次實(shí)驗(yàn)的全局最優(yōu)解。

圖2 31個(gè)節(jié)點(diǎn)的加權(quán)有向圖

2.2 具體算法步驟和算法流程

2.2.1 進(jìn)路搜索算法步驟

(1) 初始化參數(shù)α、β、W、μ、Q、nmax(最大迭代次數(shù))，令nc=0(nc為當(dāng)前迭代次數(shù))。

(2) 計(jì)算所有節(jié)點(diǎn)的長度矩陣，按照公式(1)初始化信息素濃度矩陣，并將結(jié)果存放在τij(0)中。

(4)n小時(shí)以后，螞蟻從初始節(jié)點(diǎn)到達(dá)終點(diǎn)，按照公式(4)進(jìn)行實(shí)時(shí)更新。

(5) 重復(fù)(3)～(4)步驟，直到M只螞蟻都完成路徑的遍歷。

(6) 計(jì)算各邊的信息素增量Δτij和信息素量τij(t+n)，并記錄當(dāng)前迭代路徑，更新最優(yōu)路徑。

(7) 判斷有沒有到達(dá)提前設(shè)置的迭代次數(shù)，如果有就結(jié)束實(shí)驗(yàn)，輸出本次最優(yōu)進(jìn)路和長度值。

2.2.2 進(jìn)路搜索算法流程圖

進(jìn)路搜索算法流程如圖3所示。

3 實(shí)例仿真分析

以圖1地鐵站場平面圖為實(shí)例，可以任意選擇一條列車進(jìn)路進(jìn)行路徑的選排。下面以廣州東方向上行至珠江新城接車進(jìn)路的選排作為實(shí)例進(jìn)行仿真分析。

首先選中起始信號燈S0201和終點(diǎn)信號燈S0403，則相應(yīng)的進(jìn)路搜索起始節(jié)點(diǎn)和終止節(jié)點(diǎn)被確定，分別是節(jié)點(diǎn)2和節(jié)點(diǎn)18，參見圖2。之后利用蟻群算法搜索列車排路，求解從起始節(jié)點(diǎn)2到終止節(jié)點(diǎn)18的最短距離。主要實(shí)驗(yàn)參數(shù)如表1所示。

仿真實(shí)驗(yàn)結(jié)果如圖4所示。顯然利用蟻群算法對路徑的排路經(jīng)過約55次迭代以后，便快速到達(dá)局部最優(yōu)解，其適應(yīng)度F不再發(fā)生變化，此時(shí)F=1.560 2×104，得到的最優(yōu)個(gè)體是{2,3,10,11,12,25,26,17,18}，即為對應(yīng)的最優(yōu)進(jìn)路節(jié)點(diǎn)。經(jīng)過多次仿真實(shí)驗(yàn)表明，蟻群算法的初始種群都是隨機(jī)產(chǎn)生的，收斂速度也在不斷發(fā)生變化，卻總會(huì)在一定的迭代次數(shù)后收斂。雖然本文在經(jīng)典蟻群算法中對初始信息素濃度進(jìn)行了改進(jìn)，防止了螞蟻初始搜索進(jìn)路時(shí)的盲目搜索，但依然會(huì)陷入局部最優(yōu)。針對以上問題，可以采用對局部更新規(guī)則的改進(jìn)和全局更新規(guī)則的改進(jìn)，在一定程度上避免了搜索陷入局部最優(yōu)解，同時(shí)也增加了收斂到全局最優(yōu)解的速度。

圖3 進(jìn)路搜索算法流程

參數(shù)數(shù)值螞蟻數(shù)M50信息啟發(fā)因子α1期望啟發(fā)因子β1信息素?fù)]發(fā)因子ρ0.2給定參數(shù)μ2給定參數(shù)W0.01給定參數(shù)Q1給定參數(shù)q00.5初始迭代次數(shù)nc0最大迭代次數(shù)nmax200

4 結(jié)束語

通過MATLAB仿真實(shí)驗(yàn)證明，這種基于蟻群算法的進(jìn)路搜索算法能有效地搜索出一條實(shí)際的進(jìn)路，是一種具有可行性的進(jìn)路搜索選排算法，具有一定的實(shí)際應(yīng)用價(jià)值。由于蟻群算法在國內(nèi)的應(yīng)用還不成熟，是一種比較新穎的算法，尤其是在進(jìn)路搜索方面的應(yīng)用，因此對蟻群算法在進(jìn)路選排的應(yīng)用中還有待進(jìn)一步的研究。

圖4 蟻群算法仿真結(jié)果(適應(yīng)度進(jìn)化曲線)