徐 浩, 龔國慶, 陳 林

(長江三峽通航管理局, 宜昌 443002)

三峽升船機(jī)是世界建設(shè)規(guī)模最大的全平衡齒輪齒條爬升式升船機(jī), 為了維護(hù)設(shè)備正常運轉(zhuǎn), 工作人員需每日對船廂設(shè)備進(jìn)行巡視點檢. 三峽升船機(jī)設(shè)備巡視點檢是一種預(yù)防性的、主動性的、周期性的設(shè)備檢查過程, 是設(shè)備運行管理的重要組成部分[1]. 三峽升船機(jī)設(shè)備巡視的路徑規(guī)劃可以視為TSP旅行商問題, 在實現(xiàn)遍歷每個目標(biāo)點的基礎(chǔ)上實現(xiàn)路線最短. 蟻群算法是近幾年優(yōu)化領(lǐng)域中新出現(xiàn)的一種啟發(fā)式仿生類并行智能進(jìn)化系統(tǒng), 該算法采用分布式并行計算和正反饋機(jī)制, 蟻群算法的特征適用于巡視問題的求解[2,3].

1 點檢路線空間結(jié)構(gòu)模型

1.1 巡視點檢特點

根據(jù)三峽升船機(jī)設(shè)備巡視要求, 現(xiàn)場管理人員需在早、中、晚班期間完成升船機(jī)船廂設(shè)備的巡視檢查.點檢人員使用手持式點檢儀, 通過識別RFID設(shè)備識別卡, 讀取點檢目錄, 人為確認(rèn)設(shè)備狀態(tài)并記錄[1]. 整個點檢路線完成后, 將點檢儀采集到的數(shù)據(jù)上載到系統(tǒng)管理軟件中[4]. 所有點檢點位識別卡均被讀取則視為一輪巡視的結(jié)束, 三峽升船機(jī)設(shè)備巡視存在遍歷性要求. 三峽升船機(jī)船廂在結(jié)構(gòu)上可分為4層, 內(nèi)部共有4個驅(qū)動點及相關(guān)電氣控制設(shè)備. 由于升船機(jī)結(jié)構(gòu)的對稱性,不同區(qū)域的巡視線路呈現(xiàn)局部相似性. 根據(jù)船廂內(nèi)部設(shè)備分布和步行線路布置, 部分巡視點位存在路線唯一性.

1.2 點檢路線無向加權(quán)圖

通過測量巡視點位之間的相互距離可建立點位之間的鄰接矩陣, 鄰接矩陣表示點位之間的相互距離和通過關(guān)系. 結(jié)合巡視點檢結(jié)合巡視路線的遍歷性、局部相似性及路線唯一性特點, 建立巡視點位無向加權(quán)圖, 巡視路線無向加權(quán)圖如圖1所示.

圖1 白班及中班巡視路線無向加權(quán)圖

基于實際巡視情況, 將距離相隔較近的巡視點位進(jìn)行合并, 例如船廂電氣動力室與電氣傳動室點位距離較近, 同一區(qū)域合并為一個點位. 同時不考慮單向出入口點位, 例如上下廂頭船廂門啟閉機(jī)點位與對應(yīng)驅(qū)動點點位之間有且僅有唯一往返路線.

圖1(a)表示白班期間船廂設(shè)備巡視點位的加權(quán)無向圖, 圖1(b)表示中班期間船廂設(shè)備巡視點位的加權(quán)無向圖. 圓圈表示各個巡視點位, 點位之間都允許雙向通行. 圓圈之間的數(shù)字表示加權(quán)權(quán)重, 其加權(quán)權(quán)重由點位間的相互距離和空間位置關(guān)系共同決定.

1.3 建立巡視點位空間坐標(biāo)

傳統(tǒng)的蟻群算法多適用于解決二維平面路徑規(guī)劃問題, 而升船機(jī)船廂在垂直方向具有多層結(jié)構(gòu), 不同層次直線距離較近的目標(biāo)位無法直接連接, 因此難以將升船機(jī)巡視路線展開到二維平面進(jìn)行研究. 根據(jù)圖1中點位之間的加權(quán)權(quán)重, 在笛卡爾坐標(biāo)系中設(shè)定巡視點位所在的空間坐標(biāo), 表1、表2表示了巡視點位的空間坐標(biāo). 該空間坐標(biāo)基于無向圖加權(quán)權(quán)重得來, 坐標(biāo)點之間的直線距離基本符合權(quán)重關(guān)系, 但坐標(biāo)與巡視點位實際位置并不相同.

表1 白班巡視點位空間坐標(biāo)

表2 中班巡視點位空間坐標(biāo)

2 建立蟻群算法模型

2.1 蟻群算法計算流程

當(dāng)螞蟻在食物和巢穴之間往返時, 他們會在經(jīng)過的路線上鋪設(shè)一種被稱為信息素的化學(xué)物質(zhì), 螞蟻可以嗅到這種信息素, 并且選擇信息素濃度最大的線路,經(jīng)過一條線路的螞蟻越多, 這條線路上的信息速度濃度也越大, 更多的螞蟻就會選擇這條線路, 螞蟻的這種正反饋行為夠幫助它們很快找到最短覓食線路, 蟻群算法就是受到這種行為啟發(fā), 以人工螞蟻模擬真實螞蟻行為的分布式算法[5]. 蟻群算法的基本流程如圖2.

該算法假設(shè)將m只螞蟻放入n個隨機(jī)選擇的巡視點位中, 每只螞蟻根據(jù)狀態(tài)轉(zhuǎn)移概率選擇下一個點位,狀態(tài)轉(zhuǎn)移概率與信息素濃度或者點位間的距離有一定關(guān)系. 每只螞蟻完成路線后, 信息素將會更新. 當(dāng)所有數(shù)量的螞蟻完成巡視路徑, 或者迭代次數(shù)達(dá)到上限值后, 流程將中斷并輸出最優(yōu)解, 一般即為最佳路徑. 本次算法采用ant-cycle模型進(jìn)行計算, 該模型更偏重于考慮整體信息, 避免計算中產(chǎn)生局部最優(yōu), 該模型更加適合TSP問題[6].

2.2 基本參數(shù)設(shè)置

蟻群算法中, 初始化參數(shù)包括以下幾類: (1)螞蟻數(shù)量m, 一般設(shè)置為目標(biāo)數(shù)的1.5倍, 螞蟻數(shù)量過大會導(dǎo)致信息素濃度相差較小, 收斂速度減慢. 白班巡視點位為18個, 設(shè)定螞蟻數(shù)量為m=27. 中班巡視點位為16個, 設(shè)定螞蟻數(shù)量為m=24. (2)信息素因子α, 反映了信息素對路徑選擇的重要程度, 其取值范圍通常在[1, 4]之間.α設(shè)置過大會降低路徑選擇的隨機(jī)性； 過小容易過早陷入局部最優(yōu), 設(shè)置信息素因子為α=2. (3)啟發(fā)函數(shù)因子β, 反映了啟發(fā)式信息在路徑選擇中的重要程度, 其值影響收斂速度, 如果值設(shè)置過大, 雖然收斂速度加快, 但是易陷入局部最優(yōu)； 其值過小很難找到最優(yōu)解, 設(shè)置啟發(fā)函數(shù)因子為β=4. (4)信息素?fù)]發(fā)因子ρ,反映了信息素?fù)]發(fā)情況. 當(dāng)ρ取值過大時, 容易影響隨機(jī)性和全局最優(yōu)性,ρ取值范圍通常在[0.2, 0.5]之間,設(shè)置信息素?fù)]發(fā)因子0.2. (5)信息素常數(shù)Q, 表示每一輪螞蟻釋放的信息素總量.Q越大則收斂速度越快, 但是容易陷入局部最優(yōu), 設(shè)置信息素常數(shù)為Q=50[6].

狀態(tài)轉(zhuǎn)移概率表示螞蟻選擇下一個目標(biāo)的可能性,其概率數(shù)值與路徑的信息素濃度, 還有路徑的啟發(fā)信息相關(guān), 狀態(tài)轉(zhuǎn)移概率的表達(dá)式如下:

若螞蟻已經(jīng)到達(dá)過點位j, 則計算轉(zhuǎn)移概率為零,實際在程序中表示為無窮小的數(shù)值, 螞蟻下次只會選擇未到達(dá)的目標(biāo)點位.

隨著計算程序的進(jìn)行, 螞蟻不斷堆積信息素. 為了避免信息素一直在路徑上殘留, 在每只螞蟻完成路徑規(guī)劃后, 需對路徑殘留的信息素總量進(jìn)行更新. 以t時刻作為初始值, 經(jīng)過n時刻后, 其中一條路徑(i,j)上的信息素濃度可更新為:

式中, Δ τij(t)為本次巡視路徑(i,j)上增加的信息素濃度；Δτijk(t)表示第k只螞蟻在本次巡視中留在路徑(i,j)上的信息素濃度.

根據(jù)蟻群算法的原理,m只螞蟻將通過信息素濃度的正反饋選擇出一條最佳路徑, 該路徑相對于其他路徑信息素總量更高, 通過這種方法可以在三峽升船機(jī)船廂中選擇出一條最適合的巡視點檢路線.

3 計算結(jié)果及參數(shù)對比

基于Matlab軟件, 可實現(xiàn)蟻群算法的迭代計算.在程序計算過程中, 局部的巡視點位之間的距離權(quán)重相差不大, 例如中班的3.3#點位與3.2#、4.2#點位的距離, 計算中存在局部最優(yōu)的情況, 中班巡視路線的最短距離和平均軌跡的收斂性不如白班巡視路線. 在基本蟻群算法當(dāng)中, 理論上要求所有螞蟻選擇的同一路線為最優(yōu)路線, 但實際巡視路線的計算中, 受到循環(huán)次數(shù)和實際路線點位的影響, 并不需要所有螞蟻走出最佳路徑, 只需要一只找到最短路徑即可[7], 因此升船機(jī)巡視路線以距離最短且實際可通過的路徑作為最優(yōu)解.

3.1 白班巡視路線計算結(jié)果

圖3(a)展示了基于蟻群算法計算出的白班巡視最佳巡視路線, Matlab程序執(zhí)行時間為1.65 s, 以零層甲板4#為巡視起點, 白班的最佳巡視路線巡視點位依次為4#, 4.1#, 4.2#, aa#, bb#, 1.2#, 1.1#, 1#, A#, 2#, 2.1#,2.2#, cc#, dd#, 3.2#, 3.1#, 3#, B#, 4#, 根據(jù)此條巡視路線, 人員需在船廂負(fù)三層同步軸走道完成上下游之間的移動, 而南北側(cè)的移動需通過船廂零層的防撞桁架走道.

圖3 白班巡視最佳路線及收斂軌跡

該計算路線雖符合升船機(jī)現(xiàn)場巡視實際情況, 但在升船機(jī)船舶進(jìn)出廂, 或者船廂上下行時, 巡視人員無法通過防撞桁架走道, 此時只能通過船廂負(fù)二層走道1.2#-2.2#, 3.2#-4.2#實現(xiàn)南北側(cè)之間的移動. 圖3(b)說明了計算過程中巡視路線的最短距離收斂軌跡與平均距離收斂軌跡, 收斂軌跡顯示計算過程正常收斂[8].

3.2 中班巡視路線計算結(jié)果

圖4(a)展示了基于蟻群算法計算出的中班巡視最佳巡視路線, Matlab程序執(zhí)行時間為1.288秒, 同樣以船廂零層甲板4#為巡視起點, 中班的最佳巡視路線巡視點位依次為4#, 4.1#, 4.2#, 3.3#, 3.2#, 3.1#, 3#, A#,2#, 2.1#, 2.2#, 1.3#, 1.2#, 1.1#, 1#, B#, 4#. 根據(jù)此條巡視路線, 人員需在船廂零層甲板完成上下游之間的移動, 而南北側(cè)的移動需通過船廂負(fù)二層走道, 該計算路線符合升船機(jī)現(xiàn)場巡視實際情況, 巡視路線不會因為船廂運行工況發(fā)生改變. 圖4(b)說明了計算過程中巡視路線的最短距離收斂軌跡與平均距離收斂軌跡, 收斂軌跡顯示計算過程正常收斂.

圖4 中班巡視最佳路線及收斂軌跡

4 結(jié)論

本文以三峽升船機(jī)運行班組白班及中班的巡視路線作為研究對象, 目標(biāo)是找到一條到達(dá)所有設(shè)備巡視點位的前提下人員行走距離最短的路線. 基于蟻群算法, 能夠模擬一定數(shù)量螞蟻在巡視點位之間作出路線選擇, 最終分別計算出白班和中班的一條可通行的巡視路徑, 為三峽升船機(jī)現(xiàn)場管理人員的巡視提供了路線參考. 同時, 本文需在以下兩點作出改進(jìn):

(1)本文建立了巡視點位無向加權(quán)圖及相關(guān)空間坐標(biāo), 中空間坐標(biāo)僅考慮了距離和現(xiàn)場點位布置因素,與升船機(jī)船廂內(nèi)實際設(shè)巡視點位坐標(biāo)存在偏差, 同時在蟻群算法計算中可能產(chǎn)生進(jìn)一步的計算誤差.

(2)本文基于三峽升船機(jī)巡視路線進(jìn)行研究, 經(jīng)過建立優(yōu)化空間模型, 巡檢點位數(shù)量與實際點位相比有所減少, 在蟻群算法的模擬過程中存在計算效率較低的情況. 下一步需進(jìn)行蟻群算法參數(shù)優(yōu)化以及人員實際巡視效率提升等方面做更多研究.