基于蟻群算法的三峽升船機(jī)船廂設(shè)備巡視點(diǎn)檢路線規(guī)劃①

徐 浩, 龔國(guó)慶, 陳 林

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

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

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

1.1 巡視點(diǎn)檢特點(diǎn)

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

1.2 點(diǎn)檢路線無(wú)向加權(quán)圖

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

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

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

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

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

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

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

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

2 建立蟻群算法模型

2.1 蟻群算法計(jì)算流程

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

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

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

蟻群算法中, 初始化參數(shù)包括以下幾類: (1)螞蟻數(shù)量m, 一般設(shè)置為目標(biāo)數(shù)的1.5倍, 螞蟻數(shù)量過(guò)大會(huì)導(dǎo)致信息素濃度相差較小, 收斂速度減慢. 白班巡視點(diǎn)位為18個(gè), 設(shè)定螞蟻數(shù)量為m=27. 中班巡視點(diǎn)位為16個(gè), 設(shè)定螞蟻數(shù)量為m=24. (2)信息素因子α, 反映了信息素對(duì)路徑選擇的重要程度, 其取值范圍通常在[1, 4]之間.α設(shè)置過(guò)大會(huì)降低路徑選擇的隨機(jī)性； 過(guò)小容易過(guò)早陷入局部最優(yōu), 設(shè)置信息素因子為α=2. (3)啟發(fā)函數(shù)因子β, 反映了啟發(fā)式信息在路徑選擇中的重要程度, 其值影響收斂速度, 如果值設(shè)置過(guò)大, 雖然收斂速度加快, 但是易陷入局部最優(yōu)； 其值過(guò)小很難找到最優(yōu)解, 設(shè)置啟發(fā)函數(shù)因子為β=4. (4)信息素?fù)]發(fā)因子ρ,反映了信息素?fù)]發(fā)情況. 當(dāng)ρ取值過(guò)大時(shí), 容易影響隨機(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)移概率表示螞蟻選擇下一個(gè)目標(biāo)的可能性,其概率數(shù)值與路徑的信息素濃度, 還有路徑的啟發(fā)信息相關(guān), 狀態(tài)轉(zhuǎn)移概率的表達(dá)式如下:

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

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

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

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

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

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

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

圖3(a)展示了基于蟻群算法計(jì)算出的白班巡視最佳巡視路線, Matlab程序執(zhí)行時(shí)間為1.65 s, 以零層甲板4#為巡視起點(diǎn), 白班的最佳巡視路線巡視點(diǎn)位依次為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ù)三層同步軸走道完成上下游之間的移動(dòng), 而南北側(cè)的移動(dòng)需通過(guò)船廂零層的防撞桁架走道.

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

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

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

圖4(a)展示了基于蟻群算法計(jì)算出的中班巡視最佳巡視路線, Matlab程序執(zhí)行時(shí)間為1.288秒, 同樣以船廂零層甲板4#為巡視起點(diǎn), 中班的最佳巡視路線巡視點(diǎn)位依次為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ù)此條巡視路線, 人員需在船廂零層甲板完成上下游之間的移動(dòng), 而南北側(cè)的移動(dòng)需通過(guò)船廂負(fù)二層走道, 該計(jì)算路線符合升船機(jī)現(xiàn)場(chǎng)巡視實(shí)際情況, 巡視路線不會(huì)因?yàn)榇瑤\(yùn)行工況發(fā)生改變. 圖4(b)說(shuō)明了計(jì)算過(guò)程中巡視路線的最短距離收斂軌跡與平均距離收斂軌跡, 收斂軌跡顯示計(jì)算過(guò)程正常收斂.

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

4 結(jié)論

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

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

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