陳 寶，田 斌，周占偉，陳 靜，陳雪婷，李經(jīng)民

(1.大連理工大學(xué) 遼寧省微納米技術(shù)及系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，遼寧 大連 116024；2.北京衛(wèi)星制造廠有限公司，北京 100048)

0 引言

復(fù)合結(jié)構(gòu)板的尺寸較大，若采用傳統(tǒng)單機(jī)器人帶多貼片頭的方式進(jìn)行貼片，將產(chǎn)生過多往復(fù)取片的空行程，大大降低機(jī)器人貼片效率[1，2]；若采用多直角貼裝機(jī)器人協(xié)同貼片雖能滿足需求，但需采用遺傳算法進(jìn)行協(xié)同路徑規(guī)劃。

采用傳統(tǒng)遺傳算法進(jìn)行協(xié)同路徑規(guī)劃存在易陷入局部最優(yōu)解和早熟的問題，目前雖然一些學(xué)者針對(duì)遺傳算法存在的問題進(jìn)行了改進(jìn)與優(yōu)化，如引入局部算子[3]、最小準(zhǔn)則[4]、災(zāi)變算子[5]、自適應(yīng)交叉和變異算子[6]等，但是針對(duì)多直角貼裝機(jī)器人共用X軸且貼裝環(huán)境復(fù)雜的情況，以上算子在編碼、避免碰撞、收斂速度等方面仍有提高空間。

本文充分考慮多機(jī)器人碰撞的問題，建立多直角貼裝機(jī)器人協(xié)同貼片的數(shù)學(xué)模型，引入碰撞懲罰、分組進(jìn)化、部分匹配交叉、自適應(yīng)變異算子對(duì)遺傳算法進(jìn)行改進(jìn)，并采用MATLAB對(duì)3個(gè)直角機(jī)器人協(xié)同路徑規(guī)劃問題進(jìn)行仿真實(shí)驗(yàn)。

1 多直角貼裝機(jī)器人協(xié)同貼片數(shù)學(xué)模型建立

圖1為3個(gè)直角貼裝機(jī)器人在復(fù)合結(jié)構(gòu)板上的分布情況，并以此建立數(shù)學(xué)模型。

圖1 3個(gè)直角貼裝機(jī)器人在復(fù)合結(jié)構(gòu)板上的分布

將直角貼裝機(jī)器人看做是多旅行商問題中的旅行商，復(fù)合結(jié)構(gòu)板上的貼片點(diǎn)看做是城市集合。定義如下：總共有3個(gè)直角貼裝機(jī)器人，N個(gè)待貼片點(diǎn)，每個(gè)貼片點(diǎn)有被貼片且只被貼一次。由于貼裝效率的高低取決于所有直角貼裝機(jī)器人走的路徑總長(zhǎng)度，因而本文的優(yōu)化目標(biāo)是使得機(jī)器人走的路徑總長(zhǎng)度D最短，建立的數(shù)學(xué)模型為：

.

(1)

約束條件為：

xijk∈{0,1}.

(2)

(3)

(4)

(5)

式(3)確保每一個(gè)需貼片點(diǎn)都被貼上料片；式(4)和式(5)確保每個(gè)貼片點(diǎn)只被貼一次。

2 改進(jìn)的遺傳算法

2.1 編碼與生成初始種群

由于復(fù)合結(jié)構(gòu)板上的貼裝區(qū)域類似于柵格地圖，因而可以將貼裝區(qū)域用柵格地圖表示，如圖2所示。

圖2中,白色區(qū)域表示貼片區(qū)域，黑色區(qū)域表示障礙物，每1格代表貼1片40 mm×40 mm料片，半格為貼1片40 mm×20 mm料片，并將貼片點(diǎn)按順序以數(shù)字集E=1,2,3,…，N編號(hào)。將貼片點(diǎn)編號(hào)隨機(jī)分配給3個(gè)機(jī)器人，以此生成一條染色體。重復(fù)此過程，生成種群池所需數(shù)量的染色體，以這些染色體組成初始種群，存儲(chǔ)到三維矩陣中，如圖3所示。

圖2 柵格地圖

圖3 初始種群三維矩陣

2.2 基于時(shí)間序列的碰撞懲罰適應(yīng)度函數(shù)

本文是選用3個(gè)機(jī)器人進(jìn)行協(xié)同貼片，采用遺傳算法優(yōu)化路徑，并且路徑不可產(chǎn)生碰撞，否則將造成設(shè)備的損壞。因而選取直角貼裝機(jī)器人總路徑長(zhǎng)度D的倒數(shù)作為適應(yīng)度函數(shù)的一個(gè)分量f1：

(6)

可通過加速度函數(shù)反計(jì)算得到某個(gè)直角坐標(biāo)機(jī)器人在任意時(shí)刻的位置集合Pk={Pk1,Pk2,…Pkn}，重復(fù)此過程，可得到各機(jī)器人的時(shí)間序列總集合{P1,P2,P3}。如果3個(gè)機(jī)器人的時(shí)間序列交集M為空集，則碰撞懲罰系數(shù)ui為1，否則為0，將其作為適應(yīng)度函數(shù)的另一個(gè)分量：

M=P1∩P2∩P3.

(7)

(8)

綜合式(6)和式(8)，本文遺傳算法所構(gòu)造的適應(yīng)度函數(shù)為：

minf=ui·f1.

(9)

2.3 基于分組進(jìn)化的選擇算子

本文在傳統(tǒng)遺傳算法基礎(chǔ)上引入分組的思想，將總種群分為精英組、優(yōu)質(zhì)解組以及劣質(zhì)解組進(jìn)行分組進(jìn)化。首先對(duì)初始種群按照適應(yīng)度值進(jìn)行排序，選出適應(yīng)度值最靠前的幾個(gè)解放入精英組，不參與后續(xù)遺傳操作直接放入下一代新種群；選出適應(yīng)度值排名前半部分(除去精英組成員)的解放入優(yōu)質(zhì)解組，后續(xù)采用單點(diǎn)交叉和單點(diǎn)變異；剩余的解則放入劣質(zhì)解組，后續(xù)采用單點(diǎn)交叉和多點(diǎn)變異。

2.4 部分匹配交叉算子

結(jié)構(gòu)板上每個(gè)貼片點(diǎn)必須保證有且只有一次訪問，因而需采用部分匹配交叉算子來保證這一約束條件。部分匹配交叉算子類似于單點(diǎn)交叉算子，隨機(jī)生成一個(gè)交叉點(diǎn)，將交叉點(diǎn)之后的交叉區(qū)域進(jìn)行交換。此時(shí)，生成的兩條染色體一般存在重復(fù)和缺失的基因，為了修復(fù)染色體需要在交叉區(qū)域內(nèi)建立基因的映射關(guān)系，根據(jù)此關(guān)系消除重復(fù)基因和增加缺失基因，操作過程如圖4所示。

圖4 部分匹配交叉算子操作過程

2.5 自適應(yīng)變異算子

遺傳算法前期主要通過交叉算子產(chǎn)生新的優(yōu)良染色體，需要采用低的變異概率來保持，從而實(shí)現(xiàn)優(yōu)良個(gè)體的快速積累；到算法后期由于種群全是類似的染色體，如若還是采用靜態(tài)變異概率，則算法易陷入局部最優(yōu)解。因而，本文采用一種自適應(yīng)變異算子，隨著當(dāng)前進(jìn)化代數(shù)g從1增大到最大進(jìn)化代數(shù)gmax，變量t逐步從0增大到1，與此同時(shí)變異概率Gm也逐步增大到初始變異概率Gm0的2倍，從而產(chǎn)生更多新個(gè)體，提高種群豐富度，避免陷入局部最優(yōu)解，即：

(10)

Gm=Gm0·2t.

(11)

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)準(zhǔn)備與參數(shù)設(shè)計(jì)

根據(jù)本文的算法，采用MATLAB程序?qū)?個(gè)直角貼裝機(jī)器人進(jìn)行協(xié)同路徑規(guī)劃仿真實(shí)驗(yàn)。機(jī)械硬件采用直線電機(jī)組成的直角坐標(biāo)機(jī)器人，速度為2 m/s，加速度為12 m/s2；每個(gè)機(jī)器人Z軸末端都帶有兩個(gè)真空吸盤，復(fù)合結(jié)構(gòu)板如圖2所示。

電腦開發(fā)環(huán)境為Win11和MATLAB2020a。仿真設(shè)定的種群規(guī)模為500，最大迭代次數(shù)為600；精英解組選擇概率為0.01；優(yōu)質(zhì)解組的交叉概率為0.8，初始變異概率為0.1；劣質(zhì)解組交叉概率為0.9，初始變異概率為0.2。

3.2 實(shí)驗(yàn)結(jié)果與分析

采用傳統(tǒng)遺傳算法和本文改進(jìn)遺傳算法得到的路徑優(yōu)化曲線如圖5所示。

圖5 遺傳算法優(yōu)化曲線

由圖5可知，采用本文的改進(jìn)遺傳算法在389代得到長(zhǎng)118 196 mm的最優(yōu)路徑，而采用傳統(tǒng)遺傳算法在526代得到局部最優(yōu)解，路徑長(zhǎng)度為124 383 mm。本文遺傳算法較傳統(tǒng)平均分配貼片區(qū)域的路徑長(zhǎng)度152 771 mm優(yōu)化了22.6%，較傳統(tǒng)遺傳算法路徑長(zhǎng)度優(yōu)化了4.9%，收斂速度加快26.1%。

圖6為3個(gè)機(jī)器人最優(yōu)路徑的時(shí)間序列曲線,可以看出，任意時(shí)刻的3條曲線都沒有交點(diǎn)，表明3個(gè)機(jī)器人在協(xié)同貼裝結(jié)構(gòu)板的過程中不會(huì)發(fā)生碰撞。

圖6 3個(gè)機(jī)器人最優(yōu)路徑的時(shí)間序列曲線

4 結(jié)論與展望

本文針對(duì)多直角貼片機(jī)器人協(xié)同路徑規(guī)劃的問題，提出了適合本問題的帶有碰撞懲罰、分組進(jìn)化、部分匹配交叉和自適應(yīng)變異的改進(jìn)遺傳算法。經(jīng)3個(gè)直角貼裝機(jī)器人仿真實(shí)驗(yàn)得到，本算法相對(duì)平均分配貼片區(qū)域，降低了路徑長(zhǎng)度；相對(duì)傳統(tǒng)遺傳算法，加快收斂速度，不易陷入局部最優(yōu)解。接下來將著重于研究加入其他交叉算子和變異算子，以進(jìn)一步提高算法的收斂速度和穩(wěn)定性；或者研究本算法在其他種類貼片機(jī)器人協(xié)同路徑規(guī)劃中的應(yīng)用。