汽車門板焊接路徑的多種群自適應融合蟻群優(yōu)化

李 斌，李康滿，梅陽寒

（1.東莞職業(yè)技術學院，廣東東莞 523808；2.衡陽師范學院，湖南衡陽 421002）

1 引言

汽車車身由白車身、內(nèi)外飾件、電氣附件等組成，其中白車身由形狀各異的薄板沖壓件構成，其中的焊點數(shù)量多達4000～6000個，如何安排焊點的焊接順序、規(guī)劃焊接路徑對焊接效率和生產(chǎn)節(jié)拍影響較大[1]，因此研究白車身焊點的路徑規(guī)劃問題具有重要意義。

焊接路徑規(guī)劃是指根據(jù)設置的焊點位置，規(guī)劃出一條遍歷所有焊點的焊接路徑，在滿足焊接機器人運動約束的前提下，實現(xiàn)設定目標的最優(yōu)化，設置的優(yōu)化目標包括焊接路徑最短、路徑最平穩(wěn)等[2]。

對于焊接路徑規(guī)劃算法的研究，可以分為非進化類規(guī)劃算法和進化類規(guī)劃算法兩大類。其中非進化類規(guī)劃算法是指不具備進化能力的算法，包括模擬退火法、人工勢場法、A*算法、動態(tài)規(guī)劃法、分支界定法等。文獻[3]使用模擬退火算法對無人機山地作業(yè)路徑進行了規(guī)劃，實現(xiàn)了無人機的能耗降低，但是由于模擬退火算法是隨機近似算法，最終解未必是最優(yōu)解。文獻[4]在人工勢場法中引入了逃離策略、穿越策略和距離調(diào)節(jié)因子，解決了局部極值和目標不可達問題，實現(xiàn)了動態(tài)環(huán)境下的避障。進化類規(guī)劃算法是指算法模擬生物群體的智能性，使算法具有較強的進化能力，包括蟻群算法、粒子群算法和遺傳算法等。文獻[5]將粒子群算法和細菌覓食算法進行混合，規(guī)劃了無人機在三維空間的軌跡，減小了路徑長度和碰撞風險。文獻[6]對蟻群算法進行改進，采用無限步長擴展螞蟻視野，并引入了新的信息素更新規(guī)則，改進蟻群算法明顯提高了算法在柵格環(huán)境中的路徑搜索效率。進化算法在路徑規(guī)劃中的應用是當前的研究熱點，路徑規(guī)劃的優(yōu)劣主要取決于算法的尋優(yōu)性能或優(yōu)化能力，因此進化算法在路徑規(guī)劃中的研究本質(zhì)上是提高算法優(yōu)化能力的研究。

這里以汽車前后車門內(nèi)飾焊接路徑優(yōu)化為研究課題，建立了車門焊接路徑的優(yōu)化模型，提出了多種群信息素自適應融合蟻群算法，該算法有效平衡了路徑多樣性和算法收斂性。將多種群信息素自適應融合蟻群算法應用于車門焊接路徑規(guī)劃，達到了減少焊接路徑長度的目的。

2 焊接路徑規(guī)劃建模

2.1 焊點信息與問題描述

這里以某型車前后門的內(nèi)飾門板焊接過程為研究對象，汽車的內(nèi)外飾件為塑料制品，因此本文研究的焊接過程為非金屬品的焊接過程。前后門板內(nèi)飾的焊點，如圖1、圖2所示。其中前門板共51個焊點，后門板共62個焊點。

圖1 門板的焊點分布Fig.1 Solder Joint Distribution of Car Door

車門內(nèi)飾焊接路徑規(guī)劃描述為：對于圖1給出的前后車門板焊點，規(guī)劃出一條焊接路徑，在滿足焊接機器人運動約束前提下，實現(xiàn)焊接路徑最短，達到提高焊接工作效率的目的。

2.2 超聲波焊接技術簡介

這里對汽車門板上的焊點進行電焊，根據(jù)焊接能量來源的不同，點焊包括超聲波焊接、激光焊接、氣體焰焊接等，其中超聲波焊接具有節(jié)能、高效、強度高、耗時少等諸多優(yōu)點，因此本文使用超聲波焊接方式。

超聲波焊接系統(tǒng)的組成，如圖2所示。主要包括電源、超聲波振蕩器、換能器、底砧等，其工作原理為：超聲波振蕩器將50Hz的市電轉化為20kHz的高頻電流，換能器將高頻電流轉化為高頻振動，并通過焊接頭傳遞給焊接物，焊接物因高頻摩擦而產(chǎn)生巨大熱量使接觸面熔化，而后停止振動并對焊點施壓，冷卻后得到融合的焊點。

圖2 超聲波焊接原理圖Fig.2 Principal Diagram of Ultrasonic Welding

2.3 焊接路徑優(yōu)化建模

將內(nèi)飾門板的焊接問題等效為旅行商問題（Travel Salesman Problem，TSP）。在內(nèi)飾門板焊接中，焊點為離散分布的，類似于TSP問題中的城市；在內(nèi)飾門板焊接中，焊接頭需將所有焊點遍歷一次，類似于旅行商遍歷所有城市。因此，可以將內(nèi)飾門板焊接的路徑規(guī)劃問題完全等效為旅行商問題。

將完全無向賦權圖記為G=(V，E，D)［7］，V=(v1，v2，…vN)—焊點集合，vi(i=1，2，…，N)—第i個焊點，N—焊點總數(shù)；E={eij}為邊集，eij—焊點i與焊點j之間的路徑；D={dij}—任意兩個焊點之間的距離矩陣，dij—焊點i與焊點j之間的距離。

將路徑標識參數(shù)記為xij，當焊接路徑中包含路徑eij時xij=1，當焊接路徑中不包含路徑eij時xij=0。焊接路徑規(guī)劃以路徑最短為優(yōu)化目標，要求每個焊接點均遍歷且只遍歷一次。則焊接路徑的優(yōu)化模型為：

式中：Z—焊接路徑長度，約束條件1和約束條件2保證所有焊接均經(jīng)過且只經(jīng)過一次。

3 多種群自適應融合蟻群算法

信息素是蟻群之間進行信息交流的媒介，通過不同蟻群之間信息素的融合與交互，可以實現(xiàn)不同蟻群之間的信息交流。這里基于蟻群的路徑多樣性、蟻群間路徑的差異性，構造了多種群信息素自適應融合的蟻群算法。

3.1 子群構成

這里所謂的多種群蟻群由基本蟻群、蟻群系統(tǒng)、最大最小螞蟻系統(tǒng)組成。在此對基本蟻群與蟻群系統(tǒng)的區(qū)別進行明確，最大最小螞蟻系統(tǒng)的工作原理可參考文獻[8]，這里不再介紹。

基本蟻群算法使用局部信息素更新策略，即螞蟻每選擇一個城市則進行信息素更新，包括信息素的揮發(fā)和殘留，為：

式中：ξ—信息素揮發(fā)系數(shù)—螞蟻k殘留的信息素濃度。

蟻群系統(tǒng)與基本蟻群算法的區(qū)別主要體現(xiàn)在兩個方面：

（1）在基本蟻群算法中，基于概率(t)使用輪盤賭策略確定最終選擇的城市；而在蟻群系統(tǒng)中使用偽隨機策略選擇下一城市。

（2）基本蟻群算法中使用局部信息素更新策略，而蟻群系統(tǒng)同時使用局部信息素更新策略和全局信息素更新策略。蟻群系統(tǒng)的偽隨機策略描述為[10]：

式中：j—螞蟻選擇的下一城市；q0—一概率閾值，q∈[0,1]—隨機變量；J—使用式（3）輪盤賭策略選擇的城市。

蟻群系統(tǒng)使用的全局信息素更新策略為：算法每迭代一次，則在最優(yōu)路徑上實施信息素正反饋更新，即：

3.2 基于信息熵的路徑多樣性度量方法

蟻群算法的信息素分布可以反應算法的搜索狀態(tài)，當信息素分布相對集中時說明算法已經(jīng)相對收斂，路徑多樣性較差；信息素分布較為均勻時說明算法處于大范圍搜索狀態(tài)，路徑多樣性較好。這里使用信息素分布濃度的信息熵衡量信息素分布的無序性，從而對算法搜索狀態(tài)的路徑多樣性進行度量，為：

式中：Ls(p(t))—迭代t次時信息素分布的信息熵，也即路徑多樣新度量參數(shù)；p(t)—迭代t次時信息素濃度比例矩陣；pij(t)—城市ij間信息素與總信息素的比值，即：

式中：τij(t)—城市ij間的信息素濃度。

3.3 基于相對熵的蟻群差異性度量方法

相對熵可以衡量兩個分布之間的差異性，因此這里借助相對熵對不同子群的信息素分布相似程度進行衡量，為：

式中：Gs(pk，ph)—子群k和子群h之間的差異性度量值；pk—子群k的信息素濃度比例矩陣；ph—子群h的信息素濃度比例矩陣—子群k的城市ij間信息素與總信息素的比值—子群h的城市ij間信息素與總信息素的比值。

使用Gs(pk，ph)度量不同蟻群之間的差異性，當Gs(pk，ph)較小時說明兩個子群之間的差異性較小，也即兩個子群之間的信息素分布極為相似，兩個子群進行交互作用的效果極為有限。

當Gs(pk，ph)較大時說明兩個子群之間的差異性較大，也即兩個子群之間的信息素分布差別較大，兩個子群進行交互作用的效果較好。

根據(jù)以上分析，與子群k進行交互的子群g選擇方法為：

式中：C—所有子群的集合。

3.4 多種群信息素自適應融合

多種群信息素融合的目的是將多個子群算法的優(yōu)勢進行結合，實現(xiàn)算法多樣性和收斂性的平衡。

基于前文給出的路徑多樣性度量方法和蟻群差異性度量方法，這里提出了一種多種群信息素的自適應融合方法，為：

式中：λ—融合率—子群k的信息素分布信息熵—信息素分布信息熵的閾值；子群g—與子群k的交互蟻群。

式（10）可解釋為：當小于閾值時，說明子群k的信息素分布過于集中，路徑多樣性較差，此時根據(jù)子群間差異，選擇與子群k差異最大的子群g與其交互，從而增加子群k的路徑多樣性；

當大于閾值時，說明子群k的信息素分布較為分散，路徑多樣性較好，此時不進行信息素的融合與交互，各子群按照各自的工作原理進行路徑規(guī)劃。

由以上分析可知，式（10）是一種根據(jù)子群路徑多樣性自適應進行信息素融合的過程，同時參加融合的子群也是根據(jù)差異性自適應選擇，因此該方法命名為多種群信息素自適應融合。

3.5 算法流程

根據(jù)多種群信息素自適應融合蟻群算法的構造原理，制定算法流程如下。

（1）將所有螞蟻放置于起點位置，基本蟻群算法、蟻群系統(tǒng)、最大最小螞蟻系統(tǒng)三種蟻群算法按照各自的工作原理進行迭代；

（2）每完成一次迭代，計算各子群信息素分布的信息熵，對各子群的路徑多樣性進行度量；

（3）若所有子群的路徑多樣性均較好，則繼續(xù)迭代并判斷各子群路徑多樣性；

（4）若某子群的路徑多樣性較差，按照式（9）選擇與該子群差異性最大的蟻群，兩者進行信息素融合；

（5）重復執(zhí)行（2）～（4），直至算法達到最大迭代次數(shù)，輸出最優(yōu)路徑，算法停止。

4 實驗驗證與分析

本節(jié)首先對多種群信息素自適應融合蟻群算法的性能進行驗證，而后使用該算法求解汽車門板焊接的路徑規(guī)劃問題。

4.1 算法性能測試

為了對多種群信息素自適應融合蟻群算法的性能進行測試，從常用測試集TSPLIB 中隨機選擇3 個樣本進行測試，分別為ei151、kroA200和lin318，其中ei151為小規(guī)模測試集，kroA200為中等規(guī)模測試集，lin318為大規(guī)模測試集。

各子群的參數(shù)設置按照性能最優(yōu)原則設置，基本蟻群算法參數(shù)設置為：α=2、β=3、ρ=0.3；蟻群系統(tǒng)參數(shù)設置為：α=1、β=3、ρ=0.3；最大最小螞蟻系統(tǒng)參數(shù)設置為：α=1、β=2、ρ=0.4。為了保證算法進行充分的搜索，在性能測試中算法最大迭代次數(shù)設置為2000。為了對比算法的搜索性能，使用基本蟻群（Basic Ant Colony，BAC）、蟻群系統(tǒng)（Ant Colony System，ACS）、最大最小螞蟻系統(tǒng)（Max?Min Ant Colony System，MMAS）和多種群自適應蟻群算法（Multi?Population Adaptive Ant Colony，MAAC）分別對3 種測試樣本進行規(guī)劃，每種算法獨立進行實驗10次，統(tǒng)計所得路徑長度的最優(yōu)值、平均值、標準差和迭代次數(shù)，結果，如表1所示。

表1 路徑規(guī)劃結果Tab.1 Path Planning Result

由表1可以看出，在ei151、kroA200和lin318等3個測試樣本中，多種群信息素自適應融合蟻群算法規(guī)劃路徑的最優(yōu)值、平均值、標準差和迭代次數(shù)均小于其余3種蟻群算法，說明多種群自適應蟻群算法規(guī)劃的路徑質(zhì)量和算法平穩(wěn)性均好于3種子種群算法，且算法收斂的規(guī)劃次數(shù)較少。這是因為多種群信息素自適應融合算法中給出了算法的多樣性度量方案和子群差異性度量方法，依據(jù)子群差異性自適應確定信息素融合對象，依據(jù)算法路徑多樣性確定信息素融合時機，因此多種群信息素自適應融合蟻群算法的規(guī)劃性能優(yōu)于3種子種群算法?；诙喾N群信息素自適應融合蟻群算法對3個測試樣本的規(guī)劃結果，如圖3所示。

圖3 3種測試樣本的規(guī)劃結果Fig.3 Planning Result of the 3 Testing Sample

4.2 汽車門板焊點路徑規(guī)劃

本節(jié)使用多種群信息素自適應融合蟻群算法對2.1節(jié)描述的汽車門板焊接路徑規(guī)劃問題進行求解，同時與文獻[11]的自適應蟻群算法（Adaptive Ant Colony Algorithm，AAC）規(guī)劃結果進行對比。2.1節(jié)圖1中的焊點3維信息數(shù)據(jù)較大，這里不再給出。

焊接過程為：焊接機器人從初始位置Home點出發(fā)，遍歷所有焊點后回到Home點，完成焊接過程。對于汽車的前后門板焊接路徑，使用這里的多種群信息素自適應融合蟻群算法和文獻[11]的自適應蟻群算法各自獨立運行10次，統(tǒng)計10次規(guī)劃結果的最優(yōu)值、最差值、平均值和規(guī)劃耗時，結果，如表2、表3所示。

表2 前門板的規(guī)劃結果Tab.2 Planning Result of the Front Door

表3 后門板的規(guī)劃結果Tab.3 Planning Result of the Back Door

基于多種群信息素自適應融合算法規(guī)劃的前后門板焊接路徑，如圖4所示。

圖4 前后門焊接路徑規(guī)劃結果Fig.4 Welding Path Planning Result of Front and Back Door

結合表2、表3和圖4可知，在汽車前門和后門的焊接路徑規(guī)劃中，這里提出所的多種群信息素自適應融合蟻群算法規(guī)劃的焊接路徑最優(yōu)值、平均值均小于文獻[11]的自適應蟻群算法，且規(guī)劃耗時也略短于自適應蟻群算法，這說明多種群信息素自適應融合蟻群算法的優(yōu)化能力和優(yōu)化效率好于文獻[11]的自適應蟻群算法。這是因為文獻[11]只是在蟻群算法基礎上對參數(shù)初值確定方法進行了改進，同時依據(jù)迭代次數(shù)調(diào)整信息素濃度，是較為淺顯的改進方法。這里所提算法給出了路徑多樣性度量方法、子群差異性度量方法，基于路徑多樣性自適應確定子群交流的時機，基于子群差異性自適應確定子群的交流對象，這是一種更深層次的從工作原理上的優(yōu)化，因此這里所提算法的優(yōu)化能力更好、優(yōu)化效率更高。

5 結論

這里研究了汽車們班的焊接路徑優(yōu)化問題，建立了門板焊接路徑的優(yōu)化模型，提出了多種群信息素自適應融合算法，經(jīng)驗證，得出以下結論：（1）多種群信息素自適應融合蟻群算法能夠有效平衡算法的多樣性和收斂性，其優(yōu)化能力好于基本蟻群、蟻群系統(tǒng)、最大最小蟻群系統(tǒng)等算法；（2）將多種群信息素自適應融合蟻群算法應用于車門焊接路徑規(guī)劃，得到了較優(yōu)的焊接路徑。