基于改進(jìn)蟻群算法的橋式起重機(jī)路徑規(guī)劃問(wèn)題研究

周 浩，曹旭陽(yáng)，王殿龍，陳敬濤

（大連理工大學(xué)機(jī)械工程學(xué)院，遼寧 大連 116024）

1 引言

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

所以，針對(duì)傳統(tǒng)蟻群算法收斂速度慢，容易陷入局部最優(yōu)等缺點(diǎn)，改進(jìn)算法的自適應(yīng)啟發(fā)函數(shù)和信息素更新機(jī)制，同時(shí)根據(jù)橋式起重機(jī)的運(yùn)行特征，提出新的評(píng)價(jià)標(biāo)準(zhǔn)。最后通過(guò)MATLAB仿真研究驗(yàn)證改進(jìn)算法的可行性和有效性。

2 柵格地圖構(gòu)建

采用柵格法來(lái)構(gòu)建橋式起重機(jī)二維有限空間運(yùn)行環(huán)境地圖，如圖1 所示。設(shè)置柵格空間的左下角為坐標(biāo)原點(diǎn)，以原點(diǎn)水平方向?yàn)閤軸，以原點(diǎn)垂直方向?yàn)閥軸，然后以起重機(jī)單位運(yùn)動(dòng)步長(zhǎng)L為指標(biāo)來(lái)劃分x軸和y軸上的柵格區(qū)域，每一個(gè)柵格方塊都能夠以唯一直角坐標(biāo)xy的方式表示出來(lái)。然后由柵格陣列左上角的首個(gè)柵格起，按照從左至右，從上至下給每個(gè)柵格編定序號(hào)圖中白色柵格為自由柵格，黑色柵格為障礙柵格，障礙不滿一個(gè)柵格則填充滿此柵格[6-7]。圖中坐標(biāo)與序號(hào)編碼對(duì)應(yīng)關(guān)系，如式（1）所示。

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

圖1 柵格法環(huán)境模型Fig.1 The Environment Model Created by Grid Method

3 傳統(tǒng)蟻群算法

蟻群算法是一種具有分布計(jì)算、信息正反饋和啟發(fā)式搜索特征的新型啟發(fā)式智能優(yōu)化算法，其數(shù)學(xué)模型可表示為：在覓食過(guò)程中，各螞蟻間通過(guò)遺留在路徑上信息素濃度強(qiáng)弱和節(jié)點(diǎn)狀態(tài)轉(zhuǎn)移概率大小來(lái)實(shí)現(xiàn)最短路徑搜索功能[8]。將螞蟻放在設(shè)置的柵格地圖起始點(diǎn)后，根據(jù)狀態(tài)轉(zhuǎn)移概率公式計(jì)算其訪問(wèn)下個(gè)柵格的概率。計(jì)算公式：

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

計(jì)算各螞蟻經(jīng)過(guò)的路徑長(zhǎng)度，當(dāng)執(zhí)行路徑搜索任務(wù)的所有螞蟻在完成一次循環(huán)搜索后，記錄當(dāng)前迭代下的最優(yōu)解，同時(shí)對(duì)路徑上的信息素濃度進(jìn)行更新，信息素更新公式：

上的信息素增量。

4 蟻群算法的改進(jìn)

4.1 自適應(yīng)啟發(fā)函數(shù)改進(jìn)

傳統(tǒng)蟻群算法中啟發(fā)函數(shù)為相鄰兩個(gè)柵格之間距離的倒數(shù)，數(shù)值差異小，啟發(fā)性弱，降低了算法的搜索效率。A*算法將當(dāng)前柵格，可選柵格以及目標(biāo)柵格的位置關(guān)系建立自適應(yīng)構(gòu)造估價(jià)函數(shù)，通過(guò)估價(jià)函數(shù)來(lái)選擇下一步柵格[9]。

式中：g（n）—起始柵格到可選柵格n的代價(jià)；h（n）—可選柵格n到目標(biāo)柵格的代價(jià)。

結(jié)合A*算法估價(jià)函數(shù)的基本思想，構(gòu)建蟻群算法的自適應(yīng)啟發(fā)函數(shù)，自適應(yīng)的啟發(fā)函數(shù)中加入了當(dāng)前柵格和目標(biāo)點(diǎn)之間的距離，這樣可以更快的找到最短路徑，減小迭代次數(shù)。

式中：dij—當(dāng)前柵格i與柵格j的距離；djE—柵格j與目標(biāo)點(diǎn)E的距離。

4.2 信息素更新機(jī)制改進(jìn)

傳統(tǒng)蟻群算法在螞蟻完成一次迭代后，對(duì)所有到達(dá)目標(biāo)點(diǎn)螞蟻?zhàn)哌^(guò)的路徑都進(jìn)行信息素的更新。這種方式導(dǎo)致整個(gè)尋優(yōu)過(guò)程效率降低，后續(xù)螞蟻不能夠迅速地找到信息素濃度高的較優(yōu)路徑。狼群算法是基于狼群群體智能，模擬狼群捕食行為及其獵物分配方式，抽象出“勝者為王”的頭狼產(chǎn)生規(guī)則和“強(qiáng)者生存”的狼群更新機(jī)制的一種群體智能算法[10]。為了提高蟻群算法的收斂速度和避免陷入局部最優(yōu)，借鑒狼群算法中“強(qiáng)者生存”的狼群更新機(jī)制對(duì)路徑上的信息素進(jìn)行更新。換言之，每次迭代結(jié)束之后，增加局部最優(yōu)路徑上的信息素量，減少局部最差路徑上的信息素量。其更新規(guī)則由公式給出。

式中：δ—局部最優(yōu)路徑的螞蟻數(shù)量；ω—局部最差路徑的螞蟻數(shù)量；L1—局部最優(yōu)路徑的路徑長(zhǎng)度；L2—局部最差路徑的路徑長(zhǎng)度。

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

圖2 環(huán)境1 算法仿真結(jié)果Fig.2 The Results of Algorithm Simulation in the First Environment Model

圖3 環(huán)境2 算法仿真結(jié)果Fig.3 The Results of Algorithm Simulation in the Second Environment Model

表1 路徑規(guī)劃統(tǒng)計(jì)結(jié)果Tab.1 The Results of Path Planning

4.3 結(jié)果評(píng)價(jià)標(biāo)準(zhǔn)改進(jìn)

不同于在柵格地圖仿真環(huán)境下研究路徑規(guī)劃算法，在考慮車(chē)間環(huán)境以及橋式起重機(jī)機(jī)械電氣特性后，路徑最短的一個(gè)評(píng)價(jià)標(biāo)準(zhǔn)在實(shí)際的工程應(yīng)用中并不一定能得到最優(yōu)路徑。最優(yōu)路徑不僅需要考慮路徑的長(zhǎng)短，還受到運(yùn)行時(shí)間以及穩(wěn)定性的影響，所以提出以路徑長(zhǎng)度、運(yùn)行時(shí)間和穩(wěn)定性為代價(jià)的改進(jìn)評(píng)價(jià)標(biāo)準(zhǔn)，最優(yōu)路徑即為代價(jià)最小的路徑。

在橋式起重機(jī)搬運(yùn)物料的過(guò)程中多為勻速運(yùn)動(dòng)，所以除路徑長(zhǎng)度外大小車(chē)的啟停是運(yùn)行時(shí)間的主要影響因素。橋式起重機(jī)啟停多采用梯形加減速[11]，加減速過(guò)程必然會(huì)有速度的丟失，從而造成運(yùn)行時(shí)間的增加。顯然，在仿真環(huán)境下沒(méi)有辦法實(shí)現(xiàn)控制橋式起重機(jī)的加減速過(guò)程，但可以抽象出節(jié)點(diǎn)數(shù)量來(lái)控制啟停次數(shù)，通過(guò)減少節(jié)點(diǎn)數(shù)量來(lái)降低運(yùn)行時(shí)間。

橋式起重機(jī)柔性鋼絲繩的連接方式以及外力作用會(huì)引起吊重的擺動(dòng)，從而很難實(shí)現(xiàn)精確定位，降低了工作效率，同時(shí)這種周期性的擺振也易引起鋼結(jié)構(gòu)的疲勞，影響了起重機(jī)的穩(wěn)定性運(yùn)行。為了研究路徑對(duì)運(yùn)行穩(wěn)定性的影響，將復(fù)雜的三維橋式起重機(jī)模型簡(jiǎn)化，如圖4 所示。

圖4 三維橋式起重機(jī)簡(jiǎn)化模型Fig.4 The Sketch of a Three Dimensional Overhead Crane

式中：x、y—大、小車(chē)的位移；α、β—吊重在X、Y方向的擺角；ux、uy—大、小車(chē)的控制輸入；fx、fy—X、Y方向的摩擦力；l—吊重繩長(zhǎng)；mp—吊重質(zhì)量，小車(chē)質(zhì)量為mt。應(yīng)用拉格朗日方程和虛位移原理來(lái)建立系統(tǒng)的動(dòng)力學(xué)模型。在線性簡(jiǎn)化后上得到二自由度擺角的數(shù)學(xué)模型[11]。

在第二節(jié)改進(jìn)算法的基礎(chǔ)上，改進(jìn)結(jié)果評(píng)價(jià)標(biāo)準(zhǔn)，為驗(yàn)證改進(jìn)評(píng)價(jià)標(biāo)準(zhǔn)的有效性，在環(huán)境1 下對(duì)該算法進(jìn)行仿真，從仿真結(jié)果可以看出，改進(jìn)后的評(píng)價(jià)標(biāo)準(zhǔn)在犧牲一定路徑長(zhǎng)度的基礎(chǔ)上減少了節(jié)點(diǎn)的數(shù)量，獲得更優(yōu)的工程應(yīng)用路徑。

表2 路徑規(guī)劃統(tǒng)計(jì)結(jié)果Tab.2 The Results of Path Planning

5 結(jié)論

針對(duì)蟻群算法收斂速度慢，容易陷入局部最優(yōu)的缺點(diǎn)，借鑒A*算法估價(jià)函數(shù)的基本思想和狼群分配原則中“強(qiáng)者生存”的狼群更新機(jī)制改進(jìn)自適應(yīng)啟發(fā)函數(shù)以及信息素更新機(jī)制。根據(jù)橋式起重機(jī)的運(yùn)行特征，研究容易被忽略的路徑工程應(yīng)用問(wèn)題，通過(guò)對(duì)橋式起重機(jī)大小車(chē)啟停和吊物搖擺的運(yùn)動(dòng)動(dòng)力學(xué)分析，抽象出兩個(gè)仿真因子：路徑長(zhǎng)度和節(jié)點(diǎn)數(shù)量，提出以路徑長(zhǎng)度、運(yùn)行時(shí)間和穩(wěn)定性等性能參數(shù)為代價(jià)的新的評(píng)價(jià)標(biāo)準(zhǔn)。柵格環(huán)境下的橋式起重機(jī)路徑規(guī)劃仿真結(jié)果表明，改進(jìn)的蟻群算法提高算法的收斂速度，避免搜索陷入局部最優(yōu)，通過(guò)改進(jìn)的評(píng)價(jià)標(biāo)準(zhǔn)可以得到較優(yōu)的工程應(yīng)用路徑。