張瑞星，李秀娟，高 喚

(河南工業(yè)大學(xué) 電氣工程學(xué)院，鄭州 450000)

0 引言

焊接是汽車生產(chǎn)的主要工藝之一，其質(zhì)量的高低會(huì)直接影響車身的性能。白車身作為汽車其它零件的載體[1]共有上千個(gè)焊點(diǎn)，單機(jī)器人系統(tǒng)已經(jīng)無(wú)法快速的完成如此復(fù)雜的焊接任務(wù)，因此雙機(jī)器人系統(tǒng)得以迅猛發(fā)展。文獻(xiàn)[2]針對(duì)雙機(jī)同步焊接問(wèn)題，引入虛擬焊點(diǎn)將多個(gè)旅行商問(wèn)題(Multiple Traveling Salesman Problem，MTSP)轉(zhuǎn)換為旅行商問(wèn)題(Traveling Saleman Problem，TSP)，建立雙機(jī)同步焊接模型；文獻(xiàn)[3]針對(duì)白車身雙機(jī)同步焊接路徑規(guī)劃問(wèn)題，采用柵格法建立同步焊接模型。文獻(xiàn)[4]通過(guò)對(duì)機(jī)器人動(dòng)作節(jié)拍的設(shè)計(jì)優(yōu)化以及雙機(jī)的互索設(shè)計(jì)，完成了雙機(jī)協(xié)同控制。文獻(xiàn)[5]以雙機(jī)對(duì)稱焊接為例，提出了雙機(jī)協(xié)調(diào)鏡像運(yùn)動(dòng)的協(xié)調(diào)軌跡方法。

傳統(tǒng)焊接路徑規(guī)劃大都是基于技術(shù)人員的示教操作，這種方法不僅周期長(zhǎng)且很難得出最優(yōu)路徑。隨著人工智能的迅猛發(fā)展，目前已經(jīng)提出了許多智能算法并將其應(yīng)用到焊接機(jī)器人的路徑規(guī)劃中。文獻(xiàn)[6]以生產(chǎn)節(jié)拍為約束條件，采用遺傳算法(Genetic Algorithm，GA)進(jìn)行焊接路徑規(guī)劃。文獻(xiàn)[7]提出了一種結(jié)合萊維飛行的粒子群算法(Particle Swarm Optimization，PSO)來(lái)求解焊接任務(wù)。文獻(xiàn)[8]以最短無(wú)碰撞為焊接約束條件，提出遺傳粒子群優(yōu)化算法解決焊接機(jī)器人的路徑規(guī)劃問(wèn)題。文獻(xiàn)[9]以時(shí)間最短為約束條件，提出了遺傳混沌粒子群優(yōu)化算法來(lái)解決焊接機(jī)器人路徑規(guī)劃問(wèn)題，能夠快速的得到全局最優(yōu)解。

蟻群算法(Ant Colony Optimization，ACO)是Marco Dorigo[10]提出的一種具有正反饋調(diào)節(jié)能力的啟發(fā)式算法。針對(duì)該算法的存在的問(wèn)題，學(xué)者們提出了很多改進(jìn)方法。文獻(xiàn)[11]提出了對(duì)傳統(tǒng)蟻群算從概率計(jì)算、最優(yōu)路徑二次優(yōu)化等方面進(jìn)行改進(jìn)，增強(qiáng)了算法的魯棒性與快速收斂性。文獻(xiàn)[12]在蟻群算法的啟發(fā)函數(shù)中引入人工勢(shì)場(chǎng)思想的引力系數(shù)和避障系數(shù)，提高了算法的收斂速度。文獻(xiàn)[13]引入約束因子，改進(jìn)信息素的更新規(guī)則，加強(qiáng)了算法的全局搜索能力。文獻(xiàn)[14]提出一種基于蟻群的并行協(xié)同算法，通過(guò)使用3-opt算法避免陷入局部最優(yōu)，增強(qiáng)了算法的全局搜索能力。文獻(xiàn)[15]提出了一種新的增強(qiáng)信息素更新機(jī)制，增強(qiáng)了未使用過(guò)的信息素，利用動(dòng)態(tài)信息進(jìn)行路徑優(yōu)化，提高了全局搜索能力。

由上述分析可知，解決雙機(jī)協(xié)同焊接的核心就是正確建立協(xié)同焊接模型，本文選擇MTSP作為焊接的數(shù)學(xué)模型。改進(jìn)ACO算法的主要方式是提升算法的收斂速度和全局搜索能力。本文針對(duì)ACO算法和PSO算法進(jìn)行分析，提出了一種基于蟻群粒子群的融合算法求解MTSP問(wèn)題。實(shí)驗(yàn)結(jié)果表明該算法對(duì)于求解組合優(yōu)化問(wèn)題能夠得到更優(yōu)解。

1 問(wèn)題描述

對(duì)于多機(jī)協(xié)同作業(yè)，在不考慮焊接工藝的前提下，可將其抽象為MTSP問(wèn)題。MTSP問(wèn)題是指給定N個(gè)城市的集合，M個(gè)商人分別從各自所在的城市出發(fā)，每一個(gè)商人走一條線路，使得每一個(gè)城市有且只有一個(gè)商人訪問(wèn)過(guò)，最后商人們返回出發(fā)的城市，要求商人所走的路徑之和最短。解決MTSP問(wèn)題的核心思想是對(duì)待優(yōu)化問(wèn)題進(jìn)行帶約束條件的分組，令MTSP問(wèn)題轉(zhuǎn)化為一般的TSP問(wèn)題。本文構(gòu)建的TSP模型為：

(1)

其中，Ld為路徑長(zhǎng)度；di,i+1為城市間的距離。

2 融合算法

2.1 蟻群算法的原理與改進(jìn)

2.1.1 基本蟻群算法

(2)

其中，ηij(t)=1/dij為啟發(fā)函數(shù)；allowk為螞蟻k未訪問(wèn)城市的集合；α為信息度濃度重要因子；β為啟發(fā)函數(shù)重要程度因子。當(dāng)蟻群完成一次循環(huán)后，城市之間的信息素將會(huì)更新，更新公式為：

(3)

(4)

其中，Q為常數(shù)；Lk為本倫循環(huán)最短路徑。

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

由于未對(duì)信息素濃度閾值進(jìn)行設(shè)定，當(dāng)多次循環(huán)后，信息素會(huì)聚集在幾條相對(duì)較短的路徑上，這些路徑不一定是全局最優(yōu)，有可能是局部最優(yōu)解。為避免上述問(wèn)題的發(fā)生，本文針對(duì)蟻群算法的缺點(diǎn)，提出了一種基于災(zāi)變策略的最大最小螞蟻算法(Catastrophe Max Min Ant，CMMA)，具體實(shí)現(xiàn)如下：

(1)增加信息素濃度的閾值。在初始時(shí)，設(shè)置信息素濃度的上限max_ph與下限min_ph；設(shè)置信息素的初始濃度τ0=max_ph。

(2)更改狀態(tài)轉(zhuǎn)移規(guī)則。設(shè)常數(shù)p0,若rand>p0則按照公式(3)更新，若rand

(5)

(3)加入精英蟻群思想。將上次循環(huán)中的最優(yōu)路徑替換掉本次循環(huán)中的最劣路徑，使得優(yōu)秀信息可以保留。

(4)改變信息素更新規(guī)則。每次循環(huán)只允許最優(yōu)路徑參與信息素更新，令當(dāng)前最優(yōu)與歷史最優(yōu)路徑交叉參與，完成信息素的一次更新，新的信息素增量公式為：

(6)

其中，Lk_best為歷史最短路徑；N為當(dāng)前迭代次數(shù)。本次循環(huán)找出最優(yōu)路徑的螞蟻為第i只，以信息素矩陣的第i行為藍(lán)本進(jìn)行信息素閾值更新，通過(guò)閾值完成信息素二次更新，信息素閾值的更新公式：

(7)

(5)災(zāi)變操作。若連續(xù)C次歷史最短路徑未發(fā)生變化，則進(jìn)行災(zāi)變操作，將信息素矩陣重置。

(6)若達(dá)到結(jié)束條件則停止循環(huán)，否則重復(fù)上述過(guò)程。

2.2 粒子群算法的原理與改進(jìn)

2.2.1 基本粒子群算法

在M維的空間里，n個(gè)粒子組成粒子群X，X=(X1,X2,...,Xn),第i個(gè)粒子為一個(gè)M維的向量Xi，Xi=(x1,x2,...,xM),表示粒子在M維空間中的位置，即一個(gè)待優(yōu)化問(wèn)題的可行解。粒子X(jué)i的速度為Vi；其個(gè)體極值為Pi,表示第i個(gè)粒子的歷史最優(yōu)值；粒子群的群體極值為Pg,表示當(dāng)前粒子群中的最優(yōu)值。

粒子群算法的核心思想是在每次循環(huán)過(guò)程中，通過(guò)個(gè)體極值與群體極值跟蹤粒子的速度與位置，使粒子的位置不斷向最優(yōu)解靠近，計(jì)算公式：

(8)

其中，ω為慣性權(quán)值，決定當(dāng)前粒子速度對(duì)下次粒子速度的影響程度；k為當(dāng)前的迭代次數(shù)；c1、c2為屬于[0,1]的常數(shù)，分別決定了當(dāng)前個(gè)體極值與群體極值對(duì)下次粒子速度的影響程度。

2.2.2 粒子群算法的改進(jìn)

粒子群算法與其他智能算法相比，有著收斂迅速這一鮮明特點(diǎn)，但是粒子算法有著諸多不足，其中最為突出的是無(wú)法解決離散問(wèn)題與易“早熟”。為解決上述問(wèn)題本文提出一種混沌粒子群遺傳算法(Chaos Particle Swarm Genetic，CHPG)。

(1)生成混沌種群

常見(jiàn)的混沌映射有一維logistic映射、二維Henon映射、三維Lorenz映射等。其中l(wèi)ogistic映射被廣泛的使用，本文使用的就是logistic混沌映射，logistic混沌映射的更新公式：

Xn+1=Xnμ(1-Xn)

(9)

其中，X為(0,1)的隨機(jī)數(shù)；μ為[0,4]的隨機(jī)數(shù)?；煦绶N群的產(chǎn)生過(guò)程如下所示：

1)設(shè)問(wèn)題規(guī)模n,隨機(jī)生成一個(gè)可行解X，X=(x1,x2,...,xn)；

2)將X歸一化，使結(jié)果映射到[0,1]之間，轉(zhuǎn)換公式如下所示，其中ε為常數(shù)：

(10)

3)根據(jù)公式(9)，生成序列Z對(duì)應(yīng)的混沌序列ZCH。將混沌序列中的元素按從大到小排序，此時(shí)混沌元素對(duì)應(yīng)的標(biāo)簽組成的元素就是一個(gè)混沌粒子；

4)根據(jù)種群規(guī)模重復(fù)上述過(guò)程m次，即可得到種群規(guī)模為m的混沌種群。

(2)交叉、變異的融合

引入遺傳算法的交叉、變異策略克服粒子群算法無(wú)法解決離散問(wèn)題的缺點(diǎn)；引入混沌種群，通過(guò)多種群信息交換，克服粒子群算法“早熟”的缺點(diǎn)。具體實(shí)現(xiàn)過(guò)程如下所示：

1)種群交叉：設(shè)粒子群為pop1，混沌種群為pop2，將兩個(gè)種群交叉生成新的種群child1、child2。若子代優(yōu)秀則更新父代；

2)群體極值交叉：pop1、pop2分別與各自的群體極值交叉，生成新的種群child1、child2。若子代優(yōu)秀則更新父代；

3)一次變異：對(duì)于pop1、pop2中的每個(gè)粒子，分別選擇兩個(gè)交叉位，交換交叉位上的元素，生成新的種群child1、child2，若子代優(yōu)秀則更新父代；

4)二次變異：對(duì)于pop1，pop2中的每個(gè)粒子，分別選擇兩個(gè)交叉位，翻轉(zhuǎn)兩個(gè)交叉位之間的元素，生成新的種群child1、child2。若子代優(yōu)秀則更新父代；

5)找出最短路徑。找出上述child1、child2的群體極值，進(jìn)行比較找出最短路徑；

6)災(zāi)變操作。若連續(xù)C次歷史最短路徑未發(fā)生變化時(shí)，則進(jìn)行災(zāi)變操作，即重新生成pop1、pop2兩個(gè)種群；

7)若達(dá)到結(jié)束條件則停止循環(huán)，否則重復(fù)上述過(guò)程。

2.3 融合算法思想

融合算法(Chaos Ant Particle Genetic，CHAPG)的核心思想就是充分的利用蟻群算法的正反饋調(diào)節(jié)機(jī)制。令經(jīng)過(guò)優(yōu)化的路徑參與信息素的更新，在正反饋調(diào)節(jié)的作用下，指導(dǎo)蟻群在下一次循環(huán)中建立優(yōu)秀的可行解空間，具體的操作如下：

(1)初始化算法參數(shù)；

(2)在改進(jìn)后的狀態(tài)轉(zhuǎn)移規(guī)則的指導(dǎo)下構(gòu)建解空間pop1，依據(jù)上述混沌種群的生成規(guī)則，構(gòu)建解空間pop2；

(3)分別計(jì)算pop1、pop2的群體極值；

(4)進(jìn)行種群交叉、群體極值交叉、一次變異操作、二次變異操作；

(5)計(jì)算經(jīng)過(guò)優(yōu)化后的兩個(gè)種群的群體極值，并找出最優(yōu)解；

(6)對(duì)pop1進(jìn)行精英操作，將上次循環(huán)中pop1的最優(yōu)路徑代替本次循環(huán)中pop1中的最劣路徑；

(7)判斷是否滿足災(zāi)變條件，若滿足則初始化信息素與pop2；否則，令經(jīng)優(yōu)化過(guò)的路徑參與信息素的更新，在改進(jìn)后的信息素增量規(guī)則的指導(dǎo)下更新信息素，完成信息素一次更新，更新信息素的閾值，利用閾值再次更新信息素，完成信息素二次更新；

(8)若達(dá)到結(jié)束條件則停止循環(huán)，否則返回到步驟(2)繼續(xù)循環(huán)。

3 算法的設(shè)計(jì)與仿真

3.1 算法設(shè)計(jì)

根據(jù)上述算法的工作原理，本文所提出的算法流程圖如圖1所示。

圖1 CHAPG算法流程圖

3.2 MATLAB 仿真與分析

為驗(yàn)證本文所提出CHAPG算法的有效性，在TSPLIB標(biāo)準(zhǔn)庫(kù)中選擇不同樣本進(jìn)行驗(yàn)證，與ACO、CMMA、CHPG算法的結(jié)果進(jìn)行對(duì)比，得到的驗(yàn)證結(jié)果如表1～表3所示。

表1 Eil51試驗(yàn)結(jié)果

表2 Eli101試驗(yàn)結(jié)果

表3 Ch150實(shí)驗(yàn)結(jié)果

圖4 雙機(jī)器人焊接工作站

上表中分別列出了4種算法在不同樣本集下運(yùn)行10次結(jié)果。在不同樣本試驗(yàn)中，ACO算法與其他3種算法相比，均陷入了局部最優(yōu)，無(wú)法進(jìn)行全局搜索；CMMA算法取得了較好全局最優(yōu)解，但是搜索時(shí)間過(guò)長(zhǎng)；CHPG在最優(yōu)解與搜索時(shí)間上取得了較好的結(jié)果，但是算法的魯棒性較差；CHAPG算法在5種指標(biāo)中均取得了較好的結(jié)果，體現(xiàn)出了CHAPG算法良好的性能。試驗(yàn)表明CHAPG算法在處理不同規(guī)模數(shù)據(jù)時(shí)均擁有良好的全局搜索能力與快速收斂能力。

4 雙機(jī)協(xié)同

對(duì)于雙焊接機(jī)器人系統(tǒng)，不僅需要最短路徑為準(zhǔn)則，還需要增加一些約束條件，確保焊接的同步性，具體做法如下所示。

圖5 焊點(diǎn)可達(dá)性分析

(1)根據(jù)焊點(diǎn)數(shù)據(jù)與機(jī)器人TCP之間的歐氏距離的大小進(jìn)行焊點(diǎn)的初次分配。S1、S2分別為焊點(diǎn)到與機(jī)器TCP距離的集合，若S1

(2)分別計(jì)算出R1、R2對(duì)應(yīng)的焊接距離L1、L2，計(jì)算L1與L2之間的差值，若小于常數(shù)D則跳出循環(huán)，否則繼續(xù)。

圖2 協(xié)同算法流程圖

圖6 干涉性檢查

(3)S12為R1的TCP到n2的距離由小到大的集合，S21為R2的TCP到n1的距離由小到大的集合。若L1>L2，則將S21中最小值對(duì)應(yīng)的焊點(diǎn)添加到n2中；若L2>L1，則將S12中最小值對(duì)應(yīng)的焊點(diǎn)添加到n1中，完成焊點(diǎn)的更新，否則，跳轉(zhuǎn)到(2)繼續(xù)循環(huán)。

根據(jù)上述算法的工作原理，本文所提出的協(xié)同算法的流程圖如圖2所示。

5 ROBCAD仿真

5.1 雙機(jī)器人路徑規(guī)劃

以某汽車白車身一側(cè)為例，共192個(gè)焊點(diǎn)；CHAPG算法的參數(shù)設(shè)置如下：m=192，n=50，α=1，β=5，θ=0.1，設(shè)置迭代次數(shù)為200，在MATLAB中進(jìn)行仿真實(shí)驗(yàn)，得到的路徑如圖3所示。

圖3 雙機(jī)器人路徑規(guī)劃(mm)

5.2 建立三維模型

將在CATIA中建立的白車身數(shù)模，導(dǎo)入ROBCAD中；將焊點(diǎn)數(shù)據(jù)導(dǎo)入在白車身上；在ROBCAD中建立雙機(jī)器人工作站，如圖4所示。

5.3 焊點(diǎn)可達(dá)性分析

將導(dǎo)入的焊點(diǎn)映射到白車身這一過(guò)程中，焊點(diǎn)自身的坐標(biāo)系是隨機(jī)生成的，標(biāo)準(zhǔn)的焊點(diǎn)坐標(biāo)系是z軸垂直向上，x軸是向著焊槍的方向。對(duì)于點(diǎn)焊機(jī)器人來(lái)說(shuō)，由于關(guān)節(jié)角的限制，機(jī)器人都有著自己的工作空間，因此必須通過(guò)ROBCAD的Spot模塊進(jìn)行可達(dá)性分析，如圖5所示，當(dāng)焊點(diǎn)坐標(biāo)的x軸在藍(lán)色區(qū)域則表明該機(jī)器人可以到達(dá)該焊點(diǎn)，當(dāng)在紅色區(qū)域時(shí)，則表示無(wú)法到達(dá)該焊點(diǎn)。依次調(diào)整焊點(diǎn)坐標(biāo)系，確保每一個(gè)焊點(diǎn)都在對(duì)應(yīng)機(jī)器人的工作空間。

5.4 機(jī)器人干涉檢查

對(duì)于多機(jī)器人協(xié)同路徑規(guī)劃，一般都會(huì)存在干涉情況，因此需要通過(guò)使用ROBCAD中的Collision Setup模塊進(jìn)行干涉檢查，找出發(fā)生干涉的位置。對(duì)于大多數(shù)發(fā)生干涉的位置，只需要通過(guò)調(diào)整焊點(diǎn)的坐標(biāo)系或者機(jī)器人的姿態(tài)就可以。如圖6所示，x軸的方向朝向車身，當(dāng)焊槍進(jìn)行焊接時(shí)會(huì)與車身發(fā)生干涉，旋轉(zhuǎn)焊點(diǎn)坐標(biāo)系，使焊點(diǎn)的x軸離開(kāi)車身。對(duì)于一些特殊情況，不能通過(guò)上述方法進(jìn)行調(diào)解時(shí)，可以通過(guò)增加過(guò)度焊點(diǎn)的方法解決。適當(dāng)?shù)脑黾舆^(guò)渡焊點(diǎn)，可以使焊槍避開(kāi)工件或夾具。

6 結(jié)論

利用焊點(diǎn)與機(jī)器人TCP之間的歐式距離關(guān)系將焊點(diǎn)進(jìn)行分配，將MTSP問(wèn)題轉(zhuǎn)換為T(mén)SP問(wèn)題，依靠焊接路徑之間的關(guān)系不斷更新焊點(diǎn)，確保多機(jī)器人協(xié)同工作的同步性；在ACO算法中加入精英思想，改變狀態(tài)轉(zhuǎn)移規(guī)則與信息素更新方式，增加了算法的全局收縮能力；引入混沌總?cè)?，加入GA算法的進(jìn)化思想，提高了算法的快速收斂能力。通過(guò)MATLAB的實(shí)驗(yàn)驗(yàn)證，本文所提出的CHAPG算法在求解組合優(yōu)化問(wèn)題時(shí)比ACO算法、CMMA算法、CHPG算法、CHPG算法具有更佳的效果。在ROBCAD平臺(tái)上進(jìn)行雙機(jī)器人協(xié)同焊接仿真實(shí)驗(yàn)，解決了可達(dá)性與干涉性等在實(shí)際應(yīng)用中存在的問(wèn)題，提高了焊接效率。