李 斌，李康滿，梅陽寒

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

1 引言

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

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

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

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

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)焊接路徑最短，達(dá)到提高焊接工作效率的目的。

2.2 超聲波焊接技術(shù)簡介

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

超聲波焊接系統(tǒng)的組成，如圖2所示。主要包括電源、超聲波振蕩器、換能器、底砧等，其工作原理為：超聲波振蕩器將50Hz的市電轉(zhuǎn)化為20kHz的高頻電流，換能器將高頻電流轉(zhuǎn)化為高頻振動，并通過焊接頭傳遞給焊接物，焊接物因高頻摩擦而產(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ī)劃問題完全等效為旅行商問題。

將完全無向賦權(quán)圖記為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之間的距離。

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

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

3 多種群自適應(yīng)融合蟻群算法

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

3.1 子群構(gòu)成

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

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

式中：ξ—信息素?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 基于信息熵的路徑多樣性度量方法

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

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

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

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

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

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

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

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

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

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

3.4 多種群信息素自適應(yīng)融合

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

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

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

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

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

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

3.5 算法流程

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

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

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

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

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

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

4 實驗驗證與分析

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

4.1 算法性能測試

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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