基于改進蟻群算法的橋式起重機路徑規劃問題研究

周 浩，曹旭陽，王殿龍，陳敬濤

（大連理工大學機械工程學院，遼寧 大連 116024）

1 引言

橋式起重機具有占地資源少、負載能力強、操作靈活等優點，廣泛應用于車間、倉庫、船廠、港口等場所的物料搬運。但現有的橋式起重機的工作效率很大程度上仍要依賴駕駛員的熟練程度，此外如何在高危和有害的作業場所自動化地完成避障搬運任務也是亟需解決的問題[1]。圍繞橋式起重機自動化運行，路徑規劃問題成為了重要研究課題。常用的路徑規劃算法有人工勢場法、A*算法、Dijkstra 算法、遺傳算法、蟻群算法等[2]。其中蟻群算法及其改進算法得到了較為廣泛的應用。文獻[3]修改概率公式中的期望值，對路徑中三種不同拐點角度賦值，進而修改信息激素更新規則，改進后算法所尋路徑優于基本算法，但在評價函數中沒有考慮拐點數量的影響；文獻[4]建立α（信息素啟發式因子）和β（期望啟發式因子）的互鎖關系，動態自適應調整α 和β，提出廣義信息素更新規則，取得了較好的仿真實驗效果，但互鎖關系由取值經驗與仿真實驗獲得；文獻[5]研究改進遺傳算法在橋式起重機中的應用，修改目標函數解的遺傳表示，替補柵格集合由原來的8個改為4 個，雖然減少了節點數量，但也降低了環境適應性[3-5]。

所以，針對傳統蟻群算法收斂速度慢，容易陷入局部最優等缺點，改進算法的自適應啟發函數和信息素更新機制，同時根據橋式起重機的運行特征，提出新的評價標準。最后通過MATLAB仿真研究驗證改進算法的可行性和有效性。

2 柵格地圖構建

采用柵格法來構建橋式起重機二維有限空間運行環境地圖，如圖1 所示。設置柵格空間的左下角為坐標原點，以原點水平方向為x軸，以原點垂直方向為y軸，然后以起重機單位運動步長L為指標來劃分x軸和y軸上的柵格區域，每一個柵格方塊都能夠以唯一直角坐標xy的方式表示出來。然后由柵格陣列左上角的首個柵格起，按照從左至右，從上至下給每個柵格編定序號圖中白色柵格為自由柵格，黑色柵格為障礙柵格，障礙不滿一個柵格則填充滿此柵格[6-7]。圖中坐標與序號編碼對應關系，如式（1）所示。

式中：Nx—每一行的柵格總數；mod—求余操作；int—取整操作。

圖1 柵格法環境模型Fig.1 The Environment Model Created by Grid Method

3 傳統蟻群算法

蟻群算法是一種具有分布計算、信息正反饋和啟發式搜索特征的新型啟發式智能優化算法，其數學模型可表示為：在覓食過程中，各螞蟻間通過遺留在路徑上信息素濃度強弱和節點狀態轉移概率大小來實現最短路徑搜索功能[8]。將螞蟻放在設置的柵格地圖起始點后，根據狀態轉移概率公式計算其訪問下個柵格的概率。計算公式：

式中：allowed—除了禁忌表以外螞蟻可以選擇的柵格；ηij—啟發函數，決定螞蟻選擇哪條路徑，表達式為ηij=1/dij。其中，dij為i柵格與j柵格的距離；α 是信息啟發式因子，表示螞蟻在運動過程中所積累的信息素在路徑選擇時所起的作用；β 是期望啟發式因子，表示啟發信息對于螞蟻路徑選擇的重要程度。為了使選擇具有隨機性，不陷入局部最優，采用輪盤賭算法來選擇下一個柵格。

計算各螞蟻經過的路徑長度，當執行路徑搜索任務的所有螞蟻在完成一次循環搜索后，記錄當前迭代下的最優解，同時對路徑上的信息素濃度進行更新，信息素更新公式：

上的信息素增量。

4 蟻群算法的改進

4.1 自適應啟發函數改進

傳統蟻群算法中啟發函數為相鄰兩個柵格之間距離的倒數，數值差異小，啟發性弱，降低了算法的搜索效率。A*算法將當前柵格，可選柵格以及目標柵格的位置關系建立自適應構造估價函數，通過估價函數來選擇下一步柵格[9]。

式中：g（n）—起始柵格到可選柵格n的代價；h（n）—可選柵格n到目標柵格的代價。

結合A*算法估價函數的基本思想，構建蟻群算法的自適應啟發函數，自適應的啟發函數中加入了當前柵格和目標點之間的距離，這樣可以更快的找到最短路徑，減小迭代次數。

式中：dij—當前柵格i與柵格j的距離；djE—柵格j與目標點E的距離。

4.2 信息素更新機制改進

傳統蟻群算法在螞蟻完成一次迭代后，對所有到達目標點螞蟻走過的路徑都進行信息素的更新。這種方式導致整個尋優過程效率降低，后續螞蟻不能夠迅速地找到信息素濃度高的較優路徑。狼群算法是基于狼群群體智能，模擬狼群捕食行為及其獵物分配方式，抽象出“勝者為王”的頭狼產生規則和“強者生存”的狼群更新機制的一種群體智能算法[10]。為了提高蟻群算法的收斂速度和避免陷入局部最優，借鑒狼群算法中“強者生存”的狼群更新機制對路徑上的信息素進行更新。換言之，每次迭代結束之后，增加局部最優路徑上的信息素量，減少局部最差路徑上的信息素量。其更新規則由公式給出。

式中：δ—局部最優路徑的螞蟻數量；ω—局部最差路徑的螞蟻數量；L1—局部最優路徑的路徑長度；L2—局部最差路徑的路徑長度。

為驗證改進后算法的有效性，應用MATLAB 對傳統蟻群算法和改進蟻群算法進行仿真，仿真實驗參數設置如下：m=50，α=1，β=7，ρ=0.5，Q=1，得到在兩種環境下的算法仿真結果，如圖2、圖3 所示。為減小誤差，進行20 次獨立重復實驗，得到實驗數據統計結果，如表1 所示。從仿真結果可以看出，在不同的柵格地圖下，改進蟻群算法的路徑長度最大值和平均值都要優于傳統蟻群算法，同時有效降低了算法的迭代次數，提高收斂速度，此外算法運行時間也得到一定優化。

圖2 環境1 算法仿真結果Fig.2 The Results of Algorithm Simulation in the First Environment Model

圖3 環境2 算法仿真結果Fig.3 The Results of Algorithm Simulation in the Second Environment Model

表1 路徑規劃統計結果Tab.1 The Results of Path Planning

4.3 結果評價標準改進

不同于在柵格地圖仿真環境下研究路徑規劃算法，在考慮車間環境以及橋式起重機機械電氣特性后，路徑最短的一個評價標準在實際的工程應用中并不一定能得到最優路徑。最優路徑不僅需要考慮路徑的長短，還受到運行時間以及穩定性的影響，所以提出以路徑長度、運行時間和穩定性為代價的改進評價標準，最優路徑即為代價最小的路徑。

在橋式起重機搬運物料的過程中多為勻速運動，所以除路徑長度外大小車的啟停是運行時間的主要影響因素。橋式起重機啟停多采用梯形加減速[11]，加減速過程必然會有速度的丟失，從而造成運行時間的增加。顯然，在仿真環境下沒有辦法實現控制橋式起重機的加減速過程，但可以抽象出節點數量來控制啟停次數，通過減少節點數量來降低運行時間。

橋式起重機柔性鋼絲繩的連接方式以及外力作用會引起吊重的擺動，從而很難實現精確定位，降低了工作效率，同時這種周期性的擺振也易引起鋼結構的疲勞，影響了起重機的穩定性運行。為了研究路徑對運行穩定性的影響，將復雜的三維橋式起重機模型簡化，如圖4 所示。

圖4 三維橋式起重機簡化模型Fig.4 The Sketch of a Three Dimensional Overhead Crane

式中：x、y—大、小車的位移；α、β—吊重在X、Y方向的擺角；ux、uy—大、小車的控制輸入；fx、fy—X、Y方向的摩擦力；l—吊重繩長；mp—吊重質量，小車質量為mt。應用拉格朗日方程和虛位移原理來建立系統的動力學模型。在線性簡化后上得到二自由度擺角的數學模型[11]。

在第二節改進算法的基礎上，改進結果評價標準，為驗證改進評價標準的有效性，在環境1 下對該算法進行仿真，從仿真結果可以看出，改進后的評價標準在犧牲一定路徑長度的基礎上減少了節點的數量，獲得更優的工程應用路徑。

表2 路徑規劃統計結果Tab.2 The Results of Path Planning

5 結論

針對蟻群算法收斂速度慢，容易陷入局部最優的缺點，借鑒A*算法估價函數的基本思想和狼群分配原則中“強者生存”的狼群更新機制改進自適應啟發函數以及信息素更新機制。根據橋式起重機的運行特征，研究容易被忽略的路徑工程應用問題，通過對橋式起重機大小車啟停和吊物搖擺的運動動力學分析，抽象出兩個仿真因子：路徑長度和節點數量，提出以路徑長度、運行時間和穩定性等性能參數為代價的新的評價標準。柵格環境下的橋式起重機路徑規劃仿真結果表明，改進的蟻群算法提高算法的收斂速度，避免搜索陷入局部最優，通過改進的評價標準可以得到較優的工程應用路徑。