基于改進蟻群算法的焊接機器人路徑優化*

孫振博,王明偉,李 姝,張文超

(大連工業大學機械工程與自動化學院,大連 116034)

0 引言

一輛普通汽車的白車身焊點約有4000～5000個,其中一半以上的焊點是由焊接機器人完成焊接任務的,而傳統的機器人焊接路徑通常是依靠人工經驗獲得,這就導致焊接路徑長、焊接質量可靠性低等問題,因此對于焊接機器人路徑自動規劃算法的研究,是汽車智能制造技術重點研究方向[1-2]。針對焊接機器人路徑規劃問題,許多學者在智能優化算法方面進行了大量研究。蟻群算法(ant colony optimization,ACO)是一種基于螞蟻在尋找食物時的行為策略的優化算法,在解決路徑搜索問題中具有較好的性能,但對于解決復雜路徑問題時,存在著容易陷入局部最優解等問題。

為解決蟻群算法存在的問題,圣文順等[3]通過將蟻群算法與遺傳算法融合的方式擴大了蟻群算法的解空間,同時引入貪心策略改進蟻群算法收斂速度。呂文壯等[4]提出利用粒子群算法對蟻群算法隨機產生的解進行交叉與變異,擴大了蟻群算法的搜索空間,改善了算法的收斂準確度。秦東各等[5]提出一種改進的蟻群算法,通過2-opt算子對于蟻群算法中部分螞蟻路徑進行優化,提高收斂速度,并針對蟻群算法信息素揮發因子參數特性提出了一種動態調整信息素揮發因子策略,以避免算法過早收斂。

本文為提高了焊接機器人路徑規劃的效率和精度,針對ACO算法易陷入局部最優且收斂速度慢等問題提出一種改進的蟻群算法(DWAG),通過動態權重策略與排序因子策略改進了蟻群算法的信息素更新方式以改善算法的收斂性能,同時結合遺傳算法中交叉與變異操作以提高算法搜索的廣度與深度。本文將DWAG算法應用于實際焊接機器人的路徑規劃中。白車身后地板總成焊接路徑規劃實例表明,DWAG算法相比于ACO算法,縮短了焊接路徑距離,提升了焊接效率且求解穩定性更佳。

1 焊接機器人的路徑規劃問題描述

焊接路徑規劃可以簡單描述為:假設某工位有n個焊點需要焊接,裝有焊槍的點焊機器人從起始點出發,遍歷所有焊點且每個焊點只遍歷一次后回歸起始點[6-7]。本文以白車身后地板總成點焊工位上的某一臺點焊機器人為研究對象,工位焊點分布如圖1所示。

設n個焊點的集合為C={c1,c2,…,cn},將第m條焊接序列設為cm=(cm1,cm2,…,cmn),其中cm(i)∈C(1≤i,j≤n),焊點之間的距離為d(cmi,cmj)≥0。焊接路徑總距離可表達為:

(1)

在焊接機器人的路徑規劃中,焊接路徑最短距離是重要的評價標準之一,為了提高工作效率,在路徑規劃的過程中需保證Lm盡可能小[8]。

2 基本的蟻群算法

(2)

tabuk(k=1,2,…,m)稱為禁忌表,螞蟻數量設為m,用以記錄螞蟻k當前已經走過的城市。ηij是某種啟發信息,其具體數值為焊點i與焊點j之間距離的倒數,即ηij=1/dij,dij(i,j=1,2,…,n)表示焊點之間的距離,焊點數量為n,τij(t)表示t時刻對應于焊點i、j之間的信息量,其中,α、β體現信息素和啟發信息素對螞蟻決策的影響程度。當前螞蟻遍歷所有焊點完成一次循環后,對每條路徑上對應的信息量進行更新:

τij(t+1)=(1-ρ)τij(t)+Δτij

(3)

式中:ρ∈(0,1)表示信息素的衰減程度,信息素增量Δτij表示螞蟻k在本次循環中在焊點i和焊點j之間所有留下的信息量:

(4)

(5)

式中:Q為常數,Lk表示第k只螞蟻在本次迭代中所走過路徑的長度。

3 改進的蟻群算法以及性能測試

蟻群算法具有全局搜索能力強、能夠處理復雜問題等優點,但也存在缺點。為了改進蟻群算法的缺點,本文將遺傳算法中的交叉和變異操作引入蟻群算法,并結合動態權重與排列因子策略進行優化。

3.1 引入交叉和變異操作

引入交叉和變異操作可以增加蟻群算法的全局搜索能力[9]。從而增加算法在搜索空間中的探索能力,避免算法陷入局部最優解。

本文選擇的交叉算子為Ox(order crossover),Ox交叉算子在遺傳算法中,是一種常用的交叉操作方法之一,用于將兩個父代個體的染色體進行重組生成新的子代個體。

具體來說,Ox交叉操作首先從兩個父代個體中隨機選擇兩個交叉點,r1與r2,這兩個交叉點滿足r1

Aparent=[1 2 3 4 5 6 7 8]
Bparent=[3 5 8 1 7 4 2 6]

在經過Ox交叉算子后,子代child1和子代child2可表示為:

child1=[8 2 3 4 5 1 7 6]
child2=[2 5 8 1 7 3 2 6]

對于變異操作,本文采用交換變異與逆轉變異。當遺傳算法在解決優化問題時,交換變異(swap mutation)是一種常用的變異操作,是指隨機互換染色體中的兩個基因位。對于逆轉變異,常用于改變染色體中的局部排列順序,以便算法更好的探索搜索空間。在逆轉變異中,通常會隨機選擇兩個邊界點,確定一個基因片段,之后翻轉該基因片段。例如父代染色體A通過交換變異得到子代染色體a。

A=[1 2 3 4 5 6 7 8]
a=[1 2 5 4 3 6 7 8]

父代染色體B通過逆轉變異得到子代染色體b,這里兩種變異算子隨機選擇兩個基因點位均為r1=3,r2=5。

B=[1 5 8 7 4 6 3 2]
b=[1 5 4 7 8 6 3 2]

3.2 引入動態權重與排序因子策略

本文通過引入動態權重和排序因子策略以提高算法的性能和魯棒性。如下為基于動態權重與排序因子的信息素更新策略:

τij(t+1)=(1-θ)τij(t)+Δτij·θ

(6)

式中:θ(0.1≤θ≤0.7)為動態權重因子,此處可代表信息素影響權重,θ計算方式為:

(7)

式中:λ(0≤λ≤1)為下降速率因子,控制動態權重因子的變化幅度;t為當前迭代次數,tmax為總的迭代次數。具體來講,采用指數函數計算動態權重因子,根據當前迭代次數和總迭代次數的比例自適應地調整θ[10]。當λ取0.5,動態權重因子θ變化曲線如圖2所示。

圖2 動態權重因子θ變化曲線

Δτij表示該次迭代中邊ij上信息素的增量,即:

(8)

(9)

式中:Lbest為當前迭代最優路徑長度,Lk為第k只螞蟻在本次迭代中所走過路徑的距離,mη為參與信息素更新計算的優秀螞蟻群體,在每次迭代中,根據路徑的長度對于螞蟻群體進行排名(距離短的靠前),只有在螞蟻群體中排名靠前的部分螞蟻即優秀螞蟻群體才允許在路徑上釋放信息素。mη可表示為:

mη= [m*η]

(10)

式中:m為螞蟻總數,η(0.2≤η≤0.7)為百分比調整因子?？杀硎緸?

η=θ

(11)

總的來講,動態權重策略的優點在于在算法的求解過程中對于優秀螞蟻群體所占螞蟻總群體的數量比例以及信息素的蒸發程度隨著算法在求解過程中的需要進行了自適應調整,這就保證算法在求解過程中解空間的相對完整性,同時也提高了算法的收斂速度;排序因子策略是對于動態權重策略獲得的螞蟻群體進行進一步的擇優,根據排名因子策略,對所選擇的優秀螞蟻群體中的螞蟻的影響權重進行線性遞減的方式調整,使路徑長度較短的螞蟻在信息素更新時具有更大的貢獻。這樣,路徑長度較短的螞蟻可以更快地傳播信息素,加速了優秀螞蟻所留下的信息素在搜索空間中的傳播速度,從而加速全局最優解的收斂速度,減少了陷入局部最優解的可能性。

綜上所述,動態權重和排序因子策略可以提高算法的性能和魯棒性,增強算法在全局和局部搜索空間的探索能力,減少陷入局部最優解的風險,提高算法的適應性和效率,這樣的改進有望在實際應用中幫助蟻群算法更好地克服其缺點,提高算法的性能和效果。

3.3 算法流程及性能測試

判斷陷入局部最優的條件為:迭代次數若大于1且全局最優路徑長度與個體最優路徑長度的差的絕對值小于0.01時即算法在求解問題過程中發生停滯。具體的交叉、變異操作:對全局最優與個體最優進行交叉、變異操作。取優操作:從參與交叉、變異操作的所有個體中取一個路徑長度最短個體替代為新的個體最優與全局最優。根據式(10),取優秀螞蟻群體進行信息素更新計算。圖3為DWAG算法流程圖。

圖3 DWAG算法流程圖

本文采用TSPLIB數據集中的st70、rat99和ch130數據集,對比了ACO算法和DWAG算法的性能。表1列出了兩種算法在測試數據集上的最大值、最小值和方差。最小值是用來評估算法求解最優解的能力。方差則表示算法在求解問題時穩定性,當方差越小時,算法的在求解問題時的穩定性越佳。

表1 測試數據集結果比較

從表1的數據可以看出,DWAG算法相比于ACO算法,在求解最優解的能力和在求解問題過程中的穩定性方面都表現優異,優化效果顯著。圖4為兩種算法求解3種案例的收斂結果比較。

(a) st70 (b) rat99

從圖4可以明顯看出,相比于DWAG算法,ACO算法收斂速度差,尋優效果能力不足,易陷入局部最優,而DWAG算法很好的彌補了ACO算法的缺點,且隨著案例規模復雜度的提升,兩者在求解不同問題的性能差距進一步增大。綜合來看,DWAG算法相比于ACO算法具有更好的優化效果和穩定性,是一種更為優秀的算法。

4 改進算法實例應用測試

本文以后地板總成某一點焊機器人工位為研究對象,在MATLAB中,分別對ACO算法與DWAG算法規劃的焊接路徑進行仿真。為保證結果的相對準確性,本文對兩種算法分別運行20次。表2記錄了兩種算法對應用實例仿真結果的最小值、最大值以及方差,可以較為客觀地評價各算法的尋優性能。

表2 仿真結果比較

圖5為DWAG算法的路徑優化效果,最小路徑長度為2 976.782 8 mm,方差為各算法運行20次后統計的最優解方差。

圖5 改進蟻群算法規劃結果

從仿真結果可以看出,DWAG算法方差最小,由此可得DWAG算法優化結果相比于ACO算法更為穩定。

圖6為兩種算法的優化結果比較,可以較為明顯的看出兩種算法在焊接路徑規劃問題上的收斂性能以及優化結果的接近度。

根據仿真結果顯示,在汽車后地板點焊路徑規劃中,DWAG算法表現出明顯優于ACO算法的收斂速度和優化效果。方差分析也表明,DWAG算法得到的結果更加穩定。這表明相對于ACO算法,DWAG算法具有更強的優化能力。因此,DWAG算法可以有效地克服ACO算法易陷入局部最優和收斂速度慢等缺點,為焊接路徑規劃提供前期的焊接順序建議,并為后續具體實現提供參考。

5 結論

針對焊接機器人路徑規劃問題,提出了一種改進的蟻群算法并進行實例應用,得到以下結論:

(1)引入動態權重策略以及排序因子策略加快了ACO算法的收斂速度,引入遺傳算法的交叉和變異操作避免ACO算法在求解問題過程中陷入局部最優解。

(2)從最短焊接路徑距離、尋優穩定性、收斂速度綜合對比了DWAG算法與ACO算法,驗證了DWAG算法在焊接機器人路徑規劃方面性能更佳。