基于改進(jìn)狼群算法的焊接機(jī)器人路徑規(guī)劃*

龔 正，涂福泉，李圣偉

(武漢科技大學(xué) 機(jī)械自動(dòng)化學(xué)院，湖北 武漢 430081)

0 引 言

隨著科學(xué)技術(shù)的發(fā)展，焊接機(jī)器人在汽車(chē)制造業(yè)中的作用越來(lái)越大，以焊接機(jī)器人為核心的生產(chǎn)和技術(shù)改革，成為越來(lái)越多的學(xué)者研究對(duì)象，其中研究重點(diǎn)之一就是白車(chē)身焊接任務(wù)的合理規(guī)劃[1]。白車(chē)身是汽車(chē)設(shè)計(jì)的重要組成部分，擁有著5 000～7 000個(gè)焊接點(diǎn)[2]。如果能有效合理的規(guī)劃出焊接路徑，不僅能大大提高焊接機(jī)器人的工作效率，也可以降低生產(chǎn)中的成本[3]。焊接路徑規(guī)劃所用方法可以分為兩種，傳統(tǒng)算法路徑規(guī)劃和智能算法路徑規(guī)劃。傳統(tǒng)算法計(jì)算速度快，方法也簡(jiǎn)單，但在解決多焊點(diǎn)離散型問(wèn)題上很難找到最優(yōu)解，已不能滿(mǎn)足路徑規(guī)劃需求。因此，越來(lái)越多的學(xué)者開(kāi)始利用智能算法開(kāi)展路徑規(guī)劃研究。王春華等人[4]在蟻群算法中加入局部搜索策略，并引入最大最小螞蟻機(jī)制對(duì)算法進(jìn)行了改進(jìn)，避免算法陷入局部最優(yōu)，但算法選取精英螞蟻比較困難，且對(duì)路徑規(guī)劃結(jié)果影響很大。吳明輝等人[5]提出了一種梯度下降和蟻群的混合算法，通過(guò)算法間的結(jié)合，增加了蟻群算法在尋優(yōu)過(guò)程中的隨機(jī)性，但是算法路徑規(guī)劃所用時(shí)間太長(zhǎng)，不利于提高工作效率。林巨廣等人[6]利用蟻群算法對(duì)焊接路徑進(jìn)行規(guī)劃，通過(guò)引入評(píng)價(jià)函數(shù)來(lái)提升算法的工作效率，但是選取的焊點(diǎn)實(shí)在太少，初始路徑也比較有規(guī)律，不具備普適性。

與上述方法相比，狼群算法(wolf pack algorithm,WPA)具有良好的收斂性和魯棒性，能夠適用于不同的焊接路徑，所以選用了WPA對(duì)焊接路徑進(jìn)行規(guī)劃。但WPA也存在著精度不高、容易陷入局部最優(yōu)且搜索時(shí)間太長(zhǎng)的不足[7,8]，為此，對(duì)WPA進(jìn)行了改進(jìn)，提出了一種基于Logistic混沌初始化的模擬退火WPA。將改進(jìn)WPA應(yīng)用于TSP和焊接路徑規(guī)劃任務(wù)中，利用MATLAB仿真分析驗(yàn)證算法的有效性和可行性。

1 焊接路徑規(guī)劃任務(wù)描述

1.1 車(chē)門(mén)焊接件結(jié)構(gòu)描述

汽車(chē)車(chē)門(mén)是白車(chē)身的重要組成部分，車(chē)門(mén)上焊點(diǎn)分布特征明顯，幾乎在一個(gè)平面上，本文選取上汽榮威IR31白車(chē)身車(chē)門(mén)為示例，忽略焊點(diǎn)高度差，建立二維車(chē)門(mén)焊接任務(wù)模型。如圖1(a)為車(chē)門(mén)結(jié)構(gòu)，從圖中可以明顯的看出，車(chē)門(mén)上的焊點(diǎn)數(shù)量眾多且排列沒(méi)有規(guī)則，現(xiàn)從其中提取出焊點(diǎn)模型，為焊接路徑規(guī)劃做準(zhǔn)備。車(chē)門(mén)焊點(diǎn)模型如圖1(b)。

圖1 車(chē)門(mén)模型

1.2 焊接任務(wù)描述

本文將焊接總路徑距離最短作為目標(biāo)函數(shù)，來(lái)進(jìn)行焊接任務(wù)路徑規(guī)劃，即焊接機(jī)器人從初始位置出發(fā)，在遍歷所有焊點(diǎn)后回到初始位置，尋找出一條焊接路徑總距離最短的路線(xiàn)。焊接路徑規(guī)劃模型如下：

給定N個(gè)焊點(diǎn)，N個(gè)焊點(diǎn)的其集合為C=(c1,c2,…,cn)以及各焊點(diǎn)之間的距離d，目標(biāo)函數(shù)為

(1)

式中L為遍歷焊點(diǎn)的總路徑長(zhǎng)度，d(ci，ci+1)為第i個(gè)焊點(diǎn)ci與第i+1個(gè)焊點(diǎn)ci+1之間的距離，i=1，2，…，n-1，d(cn，c1)為第n個(gè)焊點(diǎn)cn到第一個(gè)焊點(diǎn)c1之間的距離。在整個(gè)路徑規(guī)劃過(guò)程中,怎樣使目標(biāo)函數(shù)L最小，是路徑規(guī)劃的關(guān)鍵。

2 改進(jìn)WPA

2.1 WPA

狼群在捕獵過(guò)程中分工明確，相互協(xié)作，對(duì)捕獲到的獵物按勞分配，弱小的狼自動(dòng)被淘汰。WPA模型[9]如圖2。

圖2 狼群捕獵活動(dòng)

狼群的捕獵空間為N×D，其中,N為狼群的人工狼數(shù)量，D為焊點(diǎn)數(shù)量，人工狼用Xi表示，Xi=(Xi1，Xi2，…，Xid)，Xi即為焊點(diǎn)序列。目標(biāo)函數(shù)：L=F(X)，L為焊接路徑長(zhǎng)度。狼群捕獵規(guī)則如下：

1)頭狼產(chǎn)生：以狼群中目標(biāo)函數(shù)最小的狼為頭狼，頭狼引領(lǐng)整個(gè)狼群，當(dāng)出現(xiàn)目標(biāo)函數(shù)更小的人工狼時(shí)，更新頭狼。即：若人工狼目標(biāo)函數(shù)Li小于頭狼目標(biāo)函數(shù)Llead，則Llead=Li，Xlead=Xi。頭狼不執(zhí)行3種智能行為。

2)游走行為：狼群中探狼負(fù)責(zé)尋找獵物，游走過(guò)程中探狼向t個(gè)不同方向游走，計(jì)算游走前后的目標(biāo)函數(shù)值，選擇目標(biāo)函數(shù)更小的方向前進(jìn)，前進(jìn)后更新探狼位置。之后探狼繼續(xù)游走，直至Li

3)召喚行為：頭狼召喚，其余狼向它靠近奔襲，在奔襲過(guò)程中，猛狼所在位置目標(biāo)函數(shù)Li小于頭狼所在位置目標(biāo)函數(shù)Llead，則更新頭狼，新的頭狼繼續(xù)召喚行為，直到與頭狼Xlead的距離dis小于或等于所要求的判定距離dnear。猛狼與頭狼間的距離采用最長(zhǎng)公共子序列[10，11]來(lái)計(jì)算。判定距離dnear，dnear=1/(D×ω)，ω為距離判定因子。

4)圍攻行為：經(jīng)歷過(guò)召喚行為的狼，已經(jīng)距離獵物非常近，而且狼群中人工狼的距離也非常近，在圍攻的時(shí)候，狼群采用精細(xì)化搜索向獵物靠近，圍攻前后目標(biāo)函數(shù)值變小，則更新人工狼所在位置，如果沒(méi)有，則人工狼位置不變。

5)狼群淘汰機(jī)制：狼群按強(qiáng)者生存法則，淘汰掉狼群中弱小的狼。即將狼群中目標(biāo)函數(shù)值較差的狼從狼群中淘汰出去，重新產(chǎn)生多條新的狼，以此增加整個(gè)種群的多樣性。

2.2 WPA改進(jìn)策略

2.2.1 Logistic混沌初始化

狼群的初始解很大程度影響著狼群最后尋優(yōu)精度和穩(wěn)定性，初始解分布不均勻，也將直接影響算法的尋優(yōu)結(jié)果，為使初始種群中的個(gè)體更好的遍及整個(gè)解空間，減少初始解對(duì)算法的影響，本文采用Logistic混沌初始化方法[12]對(duì)狼群進(jìn)行初始化處理，混沌序列產(chǎn)生公式如下

Zi+1=μZi(1-Zi)，i=0，1，2，…，n，μ=4

(2)

其中，0≤Zi≤4，且Zi≠0.25，0.5，0.75。

2.2.2 2-opt算子

狼群圍攻過(guò)程中，人工狼之間距離已經(jīng)越來(lái)越近，狼群精細(xì)化搜索起到的作用越來(lái)越少，但狼群精細(xì)化搜索所用時(shí)間卻很長(zhǎng)，利用2-opt算子代替狼群圍攻行為，可實(shí)現(xiàn)細(xì)化搜索，提高搜索速度，減少搜索時(shí)長(zhǎng)。2-opt算子示意如圖3所示，選取abcd共4個(gè)焊點(diǎn)，若ab的距離加cd的距離大于ac加bd的距離，則反轉(zhuǎn)cb段編碼。若沒(méi)有,則保留。

圖3 2-opt算子示意

2.2.3 模擬退火算法

WPA在搜索后期存在著正反饋效應(yīng)，頭狼引領(lǐng)著整個(gè)狼群，若頭狼沒(méi)有前進(jìn)，狼群中所有的狼就會(huì)離頭狼越來(lái)越近，狼群中解的種類(lèi)就會(huì)越來(lái)越少，最終就會(huì)出現(xiàn)停滯現(xiàn)象。并且WPA中的淘汰機(jī)制目的即為增加種群多樣性，讓算法擁有一定的概率突破局部最優(yōu)解，但概率實(shí)在太小，到算法尋優(yōu)后期很難找到更好的解。通過(guò)引入模擬退火機(jī)制，不僅能夠有效地增加解的多樣性，而且能避免WPA陷入早熟現(xiàn)象。模擬退火算法的引入，就是在所有狼完成一輪搜索后，讓頭狼作為變換的基礎(chǔ)，以一定的概率進(jìn)行互換、逆轉(zhuǎn)和平移中的一個(gè)操作，以產(chǎn)生新的不同解。若新的解總路徑更短，則重新計(jì)算初始解和新的解偏離度，如果偏離度變小了，則接受新產(chǎn)生的解，如若沒(méi)有，則以一定的概率接受新的解[13]。接受概率為

(3)

式中p為接受新解的概率，ΔD為新舊解的偏離度差值，T為當(dāng)前所處的溫度，在完成模擬退火操作之后，再進(jìn)行目標(biāo)函數(shù)更新和降溫操作，降溫公式為T(mén)=T×a，a為降溫系數(shù)，a∈(0，1)。

3 改進(jìn)WPA流程

改進(jìn)WPA步驟如下：1)初始化：初始化狼群規(guī)模Nwolf，最大游走次數(shù)Smax，退火溫度T，冷卻因子a，最大迭代次數(shù)kmax，距離判定因子ω等參數(shù)，logistic混沌初始化每匹人工狼的位置Xi，計(jì)算目標(biāo)函數(shù)值Li，選出頭狼。執(zhí)行步驟2。2)探狼游走：當(dāng)目標(biāo)函數(shù)值Li≤Llead或者達(dá)到最大游走步數(shù)Smax，轉(zhuǎn)入步驟3，否則，繼續(xù)游走。3)頭狼召喚：若人工狼目標(biāo)函數(shù)Li大于頭狼目標(biāo)函數(shù)Llead，則重復(fù)召喚行為。若Li≤Llead，則更新頭狼，計(jì)算人工狼與頭狼的距離dis，判斷dis與判定距離dnear的大小，若dis≤dnear,則轉(zhuǎn)入步驟4，否則繼續(xù)召喚行為。4)猛狼圍攻：猛狼執(zhí)行圍攻行為，圍攻后轉(zhuǎn)入步驟5。5)模擬退火：狼群執(zhí)行模擬退火操作。6)更新狼群：更新狼群計(jì)算目標(biāo)函數(shù)值。7)降溫操作：根據(jù)式(5)降溫操作，若當(dāng)前溫度T小于最小溫度Tmin，或者達(dá)到循環(huán)次數(shù)kmax則退出循環(huán)，輸出最優(yōu)路徑，否則，轉(zhuǎn)步驟2。

4 仿真試驗(yàn)與分析

4.1 TSP仿真分析

機(jī)器人焊接路徑規(guī)劃可看作TSP，為驗(yàn)證改進(jìn)WPA具有一定普遍性，可以適用不同的路徑情況，現(xiàn)將基本W(wǎng)PA、改進(jìn)WPA、蟻群算法和模擬退火算法分別應(yīng)用于TSP求解，迭代次數(shù)為1 000次，重復(fù)運(yùn)行算法30次，做對(duì)比分析。驗(yàn)證算法的數(shù)據(jù)均來(lái)自TSPLIB標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)。算法的測(cè)試環(huán)境為個(gè)人電腦：Intel?coreTM2.9 GHz，8 GB RAM，在Windows 10系統(tǒng)下的MATLAB R2018a編程測(cè)試，算法的各參數(shù)由經(jīng)驗(yàn)和試算得到。由表1可以看出，在算例Burma14,Oliver30,Eil51和Pr76中，改進(jìn)WPA具有較好的尋優(yōu)能力，相比其他3種算法，改進(jìn)WPA在4個(gè)案例中均尋找到了已知最優(yōu)解，偏差為0，收斂率為100 %，具有明顯優(yōu)越性。

表1 4種算法的尋優(yōu)結(jié)果對(duì)比

仿真試驗(yàn)證明，改進(jìn)WPA具有良好的收斂性能和尋優(yōu)能力，可以適用不同的路徑情況。圖4為改進(jìn)WPA在以上算例上的最優(yōu)解路徑。

圖4 改進(jìn)WPA路徑尋優(yōu)

4.2 車(chē)門(mén)焊點(diǎn)路徑規(guī)劃仿真分析

將改進(jìn)WPA運(yùn)用到車(chē)門(mén)焊接路徑規(guī)劃任務(wù)中，以上汽榮威某車(chē)型車(chē)門(mén)焊接模型為例，分別利用基本W(wǎng)PA和改進(jìn)WPA對(duì)焊接任務(wù)進(jìn)行路徑規(guī)劃，算法迭代次數(shù)250次，重復(fù)運(yùn)行30次，取單次和多次算法尋優(yōu)結(jié)果進(jìn)行對(duì)比分析。圖1(b)為某種車(chē)門(mén)實(shí)物，均勻的取車(chē)門(mén)上的60個(gè)焊點(diǎn)做仿真。圖5(a)為基本W(wǎng)PA規(guī)劃的結(jié)果，最終得到的焊接路徑最短長(zhǎng)度為5 457.130 9 mm，路徑規(guī)劃所用時(shí)間為268 s。圖5(b)為改進(jìn)WPA的機(jī)器人焊接路徑規(guī)劃的結(jié)果，最終得到的最短焊接路徑長(zhǎng)度為4 592.384 5 mm，路徑規(guī)劃所用時(shí)間為28 s。改進(jìn)WPA在MATLAB仿真中，最短焊接路徑為：1—2—3—4—5—6—7—8—9—10—11—12—13—52—53—14—15—51—50—16—17—49—46—47—45—20—21—22—44—43—23—24—25—26—27—28—29—42—41—59—30—31—40—58—33—32—34—35—39—57—36—56—60—55—54—37—38—1。

圖5 2種算法尋優(yōu)路徑

圖6為基本W(wǎng)PA和改進(jìn)WPA在焊接路徑中的單次和多次尋優(yōu)路徑對(duì)比，可以看出，改進(jìn)WPA的收斂速度明顯高于基本W(wǎng)PA，改進(jìn)WPA在迭代50次左右就開(kāi)始收斂，而基本W(wǎng)PA在迭代70次左右才開(kāi)始收斂。在搜索過(guò)程中，改進(jìn)WPA在迭代60～80次時(shí)能很好地跳出局部最優(yōu)解，在迭代100～130次時(shí)就能尋找到最優(yōu)解，而基本W(wǎng)PA并不能有效地跳出局部最優(yōu)，且會(huì)發(fā)生停滯現(xiàn)象。從算法單次尋優(yōu)結(jié)果上看，改進(jìn)WPA最短路徑比基本W(wǎng)PA減少了864.74 mm，總路徑縮短了15.8 %，且在路徑規(guī)劃時(shí)間上減少了4 min，所用時(shí)間縮短了89.5 %。

圖6 單次、平均尋優(yōu)路徑對(duì)比

5 結(jié) 論

本文改進(jìn)的WPA具有很好的普適性，能夠適用于不同的路徑，尋優(yōu)偏差小且收斂率高；從焊點(diǎn)路徑規(guī)劃試驗(yàn)結(jié)果分析，改進(jìn)WPA在路徑規(guī)劃任務(wù)中取得了明顯的效果，解決了基本W(wǎng)PA尋優(yōu)過(guò)程中的不足；通過(guò)引入Logistic混沌初始化、2-opt算子和模擬退火算法對(duì)WPA進(jìn)行的改進(jìn)是有效的，改進(jìn)WPA能夠很好的適用于焊接路徑規(guī)劃任務(wù)中，提出的改進(jìn)策略縮短了算法運(yùn)行時(shí)間，增加了算法精度，成功幫助算法在路徑規(guī)劃中跳出了局部最優(yōu)解，大大提高了算法性能和焊接效率。