基于改進遺傳算法的多直角貼裝機器人路徑協(xié)同規(guī)劃

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

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

0 引言

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

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

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

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

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

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

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

.

(1)

約束條件為：

xijk∈{0,1}.

(2)

(3)

(4)

(5)

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

2 改進的遺傳算法

2.1 編碼與生成初始種群

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

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

圖2 柵格地圖

圖3 初始種群三維矩陣

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

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

(6)

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

M=P1∩P2∩P3.

(7)

(8)

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

minf=ui·f1.

(9)

2.3 基于分組進化的選擇算子

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

2.4 部分匹配交叉算子

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

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

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

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

(10)

Gm=Gm0·2t.

(11)

3 仿真實驗與結(jié)果分析

3.1 實驗準備與參數(shù)設(shè)計

根據(jù)本文的算法，采用MATLAB程序?qū)?個直角貼裝機器人進行協(xié)同路徑規(guī)劃仿真實驗。機械硬件采用直線電機組成的直角坐標機器人，速度為2 m/s，加速度為12 m/s2；每個機器人Z軸末端都帶有兩個真空吸盤，復(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 實驗結(jié)果與分析

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

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

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

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

圖6 3個機器人最優(yōu)路徑的時間序列曲線

4 結(jié)論與展望

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