基于蟻群算法的進路搜索算法研究及應用

吳相飛，敖銀輝

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

0 引言

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

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

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

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

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

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

2 基于蟻群算法的進路搜索

2.1 蟻群算法進路搜索的描述

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

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

(1)

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

當q≤q0時：

(2)

(3)

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

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

(4)

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

(5)

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

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

(6)

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

(7)

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

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

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

2.2.1 進路搜索算法步驟

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

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

(4)n小時以后，螞蟻從初始節(jié)點到達終點，按照公式(4)進行實時更新。

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

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

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

2.2.2 進路搜索算法流程圖

進路搜索算法流程如圖3所示。

3 實例仿真分析

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

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

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

圖3 進路搜索算法流程

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

4 結(jié)束語

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

圖4 蟻群算法仿真結(jié)果(適應度進化曲線)