趙云濤，甘鐳，李維剛

(武漢科技大學(xué)，冶金自動(dòng)化與檢測(cè)技術(shù)教育部工程研究中心，湖北武漢 430081)

0 前言

機(jī)器人在車(chē)身焊接中應(yīng)用廣泛，但傳統(tǒng)點(diǎn)焊的路徑規(guī)劃多采用手工教學(xué)方法。手工教學(xué)方法的焊接質(zhì)量取決于工人的技能和經(jīng)驗(yàn)，焊接質(zhì)量不能保證。因此，需要采用自動(dòng)、有效的路徑優(yōu)化方法。規(guī)劃合理的焊接路徑、提高生產(chǎn)效率是當(dāng)前研究的熱點(diǎn)。

點(diǎn)焊機(jī)器人的路徑規(guī)劃是一個(gè)最優(yōu)化問(wèn)題。根據(jù)給定的焊點(diǎn)，規(guī)劃?rùn)C(jī)器人焊槍通過(guò)這些符合相應(yīng)約束條件的焊點(diǎn)運(yùn)動(dòng)的最佳路徑。王學(xué)武等[1]針對(duì)弧焊機(jī)器人的路徑長(zhǎng)度和能耗比提出了一種自適應(yīng)鄰域的離散DMOEA/D-ET算法，通過(guò)觸發(fā)機(jī)制選擇全局搜索和局部勘探兩種策略，局部搜索采用MOEA/D算法。高明、陸穎[2]針對(duì)汽車(chē)引擎蓋焊接的路徑規(guī)劃問(wèn)題，提出一種改進(jìn)蟻群算法，對(duì)原始蟻群算法的信息素更新加入自適應(yīng)混沌策略，局部信息素根據(jù)蟻群密度自適應(yīng)變化，全局信息素則結(jié)合混沌擾動(dòng)進(jìn)行更新，信息素的改進(jìn)提高了多樣性和隨機(jī)性。文獻(xiàn)[3]指出對(duì)于焊接機(jī)器人的規(guī)劃，路徑長(zhǎng)度和周期時(shí)間非常重要，針對(duì)焊接機(jī)器人建立了路徑和時(shí)間模型，并提出一種采用聚類引導(dǎo)的多目標(biāo)粒子群算法來(lái)解決點(diǎn)焊機(jī)器人的路徑規(guī)劃問(wèn)題。

平衡優(yōu)化器算法(Equilibrium Optimizer，EO)是FARAMARZI等[4]受控制容積質(zhì)量平衡的物理現(xiàn)象啟發(fā)于2020年提出的一種新型優(yōu)化算法。和傳統(tǒng)的啟發(fā)式算法相比，平衡優(yōu)化器算法具有尋優(yōu)能力強(qiáng)、精度高等特點(diǎn)；但EO算法也存在著易陷入局部最優(yōu)、收斂精度低等問(wèn)題。針對(duì)這些問(wèn)題，已有許多學(xué)者對(duì)平衡優(yōu)化算法進(jìn)行了改進(jìn)。例如：TANG等[5]結(jié)合多種群策略并采用高斯分布估計(jì)策略和萊維飛行策略進(jìn)行更新，提高了種群的多樣性。MOUSA等[6]在平衡優(yōu)化算法中加入混沌搜索策略，增強(qiáng)了算法的局部搜索能力。周鵬等人[7]融合了Tent混沌映射改進(jìn)初始化種群，并且在迭代過(guò)程中加入透鏡成像策略得到反向解進(jìn)行更新，提高了算法跳出局部最優(yōu)的能力。以上改進(jìn)的平衡優(yōu)化算法取得了較好的效果，但都是基于單目標(biāo)問(wèn)題的改進(jìn)優(yōu)化。在多目標(biāo)優(yōu)化問(wèn)題中，PREMKUMAR等[8]將非支配排序和平衡優(yōu)化器算法進(jìn)行結(jié)合并且加入了存檔集機(jī)制。目前沒(méi)有平衡優(yōu)化算法應(yīng)用于處理離散問(wèn)題的研究。

以高效解決點(diǎn)焊機(jī)器人的路徑規(guī)劃問(wèn)題為目標(biāo)，本文作者提出一種融合改進(jìn)快速非支配排序的離散多目標(biāo)平衡優(yōu)化器算法(Discrete Multi-Objective Non-dominated Equilibrium Optimizer，DMONEO)。結(jié)合快速非支配排序策略，針對(duì)擁擠度因子不能很好地反映同層次解的密度，通過(guò)生存評(píng)分來(lái)替換擁擠度因子，可以更好地保持種群的多樣性。最后通過(guò)精英策略，將當(dāng)前種群和子代種群合并競(jìng)爭(zhēng)從而使得表現(xiàn)較好的個(gè)體保留。

1 點(diǎn)焊機(jī)器人路徑規(guī)劃問(wèn)題

機(jī)器人的路徑規(guī)劃可以簡(jiǎn)化為旅行商問(wèn)題(Traveling Salesman Problem，TSP)。以一個(gè)焊接工件作為路徑規(guī)劃的對(duì)象，工件中有多個(gè)焊點(diǎn)。焊槍的運(yùn)動(dòng)代表了旅行銷售員的行走。路徑規(guī)劃是為了尋找穿越所有焊點(diǎn)的最短路徑。在實(shí)際生產(chǎn)作業(yè)中，達(dá)到最高效率是優(yōu)化目的。因此，本文作者針對(duì)焊接時(shí)間和焊接路徑建立了模型。

1.1 焊接時(shí)間模型

在焊接過(guò)程中，當(dāng)機(jī)器人在焊接點(diǎn){γ1，γ2，…，γi，…，γn}之間移動(dòng)時(shí)，它對(duì)應(yīng)于一個(gè)時(shí)間序列{t1，t2，…，ti，…，tn-1，tn}。ti表示焊點(diǎn)γi與焊點(diǎn)γi+1之間移動(dòng)所需要的時(shí)間。tn為焊接時(shí)間，包括工作時(shí)間和移動(dòng)時(shí)間。因?yàn)楹附铀玫墓ぷ鲿r(shí)間是固定的。為了簡(jiǎn)化問(wèn)題，焊接時(shí)間主要考慮了焊點(diǎn)之間的移動(dòng)時(shí)間。焊接時(shí)間的定義見(jiàn)式(1)

(1)

1.2 焊接長(zhǎng)度模型

(2)

其中：σ5、σ4、σ3、σ2、σ1、σ0為系數(shù)；ti為時(shí)間。

焊點(diǎn)之間的運(yùn)動(dòng)軌跡γiγi+1在關(guān)節(jié)空間中可以分為等量的p段。根據(jù)等式計(jì)算軌跡上p個(gè)點(diǎn)的角位移θi1、…、θip，通過(guò)機(jī)器人的運(yùn)動(dòng)學(xué)分析，得到了p個(gè)點(diǎn)對(duì)應(yīng)的笛卡爾坐標(biāo)值。隨著段數(shù)的增加，p段軌跡的和近似為路徑長(zhǎng)度qi，i+1

(3)

dj，j+1是p段軌跡中相鄰點(diǎn)(aj,bj,cj)和(aj+1,bj+1,cj+1)之間的歐氏距離，定義見(jiàn)式(4)

(4)

移動(dòng)路徑的總長(zhǎng)度計(jì)算見(jiàn)式(5)

(5)

1.3 多目標(biāo)路徑規(guī)劃模型

將所建立的焊接路徑長(zhǎng)度模型和焊接時(shí)間模型作為路徑規(guī)劃的目標(biāo)函數(shù)，以最大角速度和最大角加速度為約束條件，由此建立點(diǎn)焊機(jī)器人路徑規(guī)劃的多目標(biāo)模型，見(jiàn)式(6)(7)

Minimize：f1(x)=L(x)

(6)

Minimize：f2(x)=T(x)

(7)

其中：x∈{x1,x2,…,xi,…,xΔ}是所有焊點(diǎn)順序的集合。

2 平衡優(yōu)化器算法

平衡優(yōu)化器算法的思想?yún)⒖剂速|(zhì)量平衡模型[4]，見(jiàn)式(8)

(8)

其中：V代表控制容積；C表示控制容積內(nèi)的濃度；Q為流進(jìn)或流出控制容積的容量流速；Ceq表示控制容積內(nèi)部在平衡時(shí)的濃度；G代表控制容積內(nèi)部的質(zhì)量生成速率。平衡優(yōu)化器算法的流程如下：

(1)種群初始化

初始種群是根據(jù)種群規(guī)模在每個(gè)決策變量的上下界范圍內(nèi)進(jìn)行隨機(jī)初始化，見(jiàn)式(9)

(9)

其中：Cub、Clb分別為決策變量的上限和下限；ri為[0，1]之間的隨機(jī)數(shù)向量，其維度跟空間維度一致。

(2)生成平衡狀態(tài)池

更新過(guò)程中的候選解選自平衡狀態(tài)池，見(jiàn)式(10)

Ceq,pool={Ceq,1,Ceq,2,Ceq,3,Ceq,4,Ceq,ave}

(10)

其中：Ceq，1、Ceq，2、Ceq，3、Ceq，4分別為當(dāng)前種群中最好的4個(gè)解；Ceq，ave代表這4個(gè)解的平衡狀態(tài)。更新過(guò)程中在平衡狀態(tài)池里隨機(jī)選取最優(yōu)解。前4個(gè)候選解用于爭(zhēng)取更好的勘探效果，第5個(gè)候選解為平衡值可以提高開(kāi)發(fā)水平。

(3)指數(shù)項(xiàng)系數(shù)

指數(shù)項(xiàng)系數(shù)記為F，影響更新規(guī)則，定義見(jiàn)式(11)—(13)

F=exp[-λ(t-t0)]

(11)

(12)

t=(1-n/nmax)(a2n/nmax)

(13)

其中：a1、a2分別為全局勘探和局部開(kāi)發(fā)的權(quán)重系數(shù)，一般分別取2和1；λ為[0，1]之間的隨機(jī)數(shù)；n和nmax分別為目前迭代次數(shù)和終止迭代條件。

(4)生成率

生成率記為G，設(shè)計(jì)如下，見(jiàn)式(14)(16)

G=G0e-λ(t-t0)

(14)

G0=GCP(Ceq-λC)

(15)

(16)

其中：GCP為生成率控制參數(shù)，用于對(duì)迭代過(guò)程中的生成率進(jìn)行控制；r1、r2和λ為[0，1]隨機(jī)數(shù)向量，其維度跟優(yōu)化空間維度一致；G0為生成率的初始值；GP為生成概率，一般取0.5。

(5)更新公式

C=Ceq+(C0-Ceq)F+G(1-F)/λV

(17)

平衡優(yōu)化器算法主要基于式(17)展開(kāi)迭代尋優(yōu)。等式左邊的濃度C代表新產(chǎn)生的解，C0代表上一次迭代得到的解，Ceq為從平衡狀態(tài)池中隨機(jī)選取的解，V一般取1。

3 離散化多目標(biāo)平衡優(yōu)化器算法

3.1 離散編碼方式

TSP問(wèn)題的解通常用路徑編碼來(lái)描述，即最終經(jīng)過(guò)所有城市的排序。針對(duì)路徑編碼的信息更新，參考遺傳的思想，即染色體的交叉變異進(jìn)行信息的互換。交叉算子是產(chǎn)生新個(gè)體的主要方法，通過(guò)交換兩個(gè)父代之間的部分信息得到兩個(gè)新的子代。變異算子是對(duì)個(gè)體的某些序列上的信息進(jìn)行改變，這種操作不需要進(jìn)行信息交換。

在TSP問(wèn)題中，鄰域信息具有十分重要的作用。為了較好地保留領(lǐng)域信息以及更好地進(jìn)行迭代更新，本文作者采用了順序交叉算子和隨機(jī)插入算子。

順序交叉算子的操作見(jiàn)圖1，可以分為以下3個(gè)步驟：

圖1 交叉算子流程

(1)隨機(jī)選擇兩個(gè)個(gè)體P1、P2作為父代以及兩個(gè)隨機(jī)點(diǎn)作為互換信息的起始點(diǎn)和終點(diǎn)。

(2)將P1、P2中兩點(diǎn)之間信息提取出來(lái)，放在子代O1、O2的相同位置。

(3)將另一個(gè)父代按序刪除已有的基因后將該序列填入O1。同理對(duì)O2進(jìn)行操作。

隨機(jī)插入算子的操作見(jiàn)圖2，可以分為以下3個(gè)步驟：

圖2 變異算子流程

(1)父代隨機(jī)選擇3個(gè)點(diǎn)，分別作為插入點(diǎn)、保留領(lǐng)域信息的起點(diǎn)和終點(diǎn)。

(2)將起點(diǎn)和終點(diǎn)之間信息提取出來(lái)，從子代插入點(diǎn)的位置插入。

(3)將父代按序刪除已有的基因后將該序列填入子代。

3.2 生存評(píng)分策略

文獻(xiàn)[8]所提出的算法結(jié)合了非支配排序的策略。但文獻(xiàn)[9]中提出的NSGA-II算法中通過(guò)擁堵因子并不能客觀反映同層次中個(gè)體之間的真實(shí)擁擠程度。當(dāng)兩個(gè)或多個(gè)解具有同樣的適應(yīng)度時(shí)，計(jì)算出的擁擠距離值可能為0或者由個(gè)體在帕累托前序列中的位置所決定。針對(duì)這個(gè)缺點(diǎn)，本文作者采用了一種快速估計(jì)非支配前沿幾何形狀的策略[10]，使用一個(gè)結(jié)合非支配前沿多樣性和鄰近性的生存分?jǐn)?shù)取代了擁擠距離。

生存評(píng)分計(jì)算步驟如下：

(1)歸一化

在迭代過(guò)程中，使用非支配排序?qū)⒎N群劃分為不同層次的非支配前沿。然后，對(duì)第一個(gè)非支配前沿進(jìn)行標(biāo)準(zhǔn)化和歸一化處理，見(jiàn)式(18)

(18)

(2)計(jì)算Lp范數(shù)估計(jì)前沿集合形狀

Lp范數(shù)用于計(jì)算接近度和多樣性的距離。指數(shù)p是依據(jù)每代中第一個(gè)非支配前沿的幾何形狀所計(jì)算的，通過(guò)式(19)求指數(shù)p的值。

(19)

(20)

(3)計(jì)算生存評(píng)分

通過(guò)第一個(gè)非主導(dǎo)前沿F1的Lp范數(shù)，測(cè)量f1的多樣性和鄰近性。計(jì)算見(jiàn)式(21)(22)

(21)

(22)

一般解S∈F1的接近度得分為其目標(biāo)向量fn(S)到理想點(diǎn)的距離，多樣性得分為與前沿F1中其他解的最小距離。生存評(píng)分結(jié)合了多樣性和鄰近性，見(jiàn)式(23)

(23)

非支配前沿Fd>1中的解的生存得分為它們的近度得分的倒數(shù)。

3.3 算法流程

DMONEO算法的流程如圖3所示。

圖3 DMONEO算法流程

4 實(shí)驗(yàn)驗(yàn)證與分析

為了驗(yàn)證所提出算法的性能，采用了TSP30、TSP50、TSP100這3個(gè)Mo-TSP問(wèn)題進(jìn)行測(cè)試，測(cè)試信息見(jiàn)表1。對(duì)比算法選取了NSGA-II[11]、SPEA2SDE[12]、IBEA[13]和MOEADD[14]。所有算法均采用相同的參數(shù)設(shè)置：種群規(guī)模N=200，最大迭代次數(shù)nmax=30 000；算法的其他參數(shù)設(shè)置均參考原文獻(xiàn)。每個(gè)算法對(duì)每個(gè)測(cè)試問(wèn)題獨(dú)立運(yùn)行30次。

表1 TSP基準(zhǔn)測(cè)試函數(shù)

實(shí)驗(yàn)所用計(jì)算機(jī)環(huán)境為Intel Corei5-7300HQ@2.50 GHz CPU，16 GB內(nèi)存，Windows10 64位操作系統(tǒng)。運(yùn)行環(huán)境為MATLAB-R2019b。對(duì)比算法基于PlatEMO平臺(tái)[15]。

本文作者使用超體積度量(Hypervolume，HV)以及算法的運(yùn)行時(shí)間(Runtime)來(lái)衡量DMONEO算法和對(duì)比算法的性能。HV計(jì)算的是解集與參考點(diǎn)之間的目標(biāo)空間體積。較大的HV代表著算法的表現(xiàn)更好，更接近真實(shí)的帕累托前沿和更好的多樣性。運(yùn)行時(shí)間體現(xiàn)了該算法的計(jì)算復(fù)雜度。

表2、3分別為DMONEO算法和其他對(duì)比算法在測(cè)試問(wèn)題的HV統(tǒng)計(jì)結(jié)果和運(yùn)行時(shí)間。性能指標(biāo)平均值和標(biāo)準(zhǔn)方差作為評(píng)價(jià)標(biāo)準(zhǔn)，運(yùn)行時(shí)間單位為秒(s)。帶下劃線的數(shù)據(jù)代表該算法在相應(yīng)測(cè)試問(wèn)題上表現(xiàn)最優(yōu)。表格底部的數(shù)據(jù)是通過(guò)Wilcoxon符號(hào)秩檢驗(yàn)的結(jié)果，以“+/-/=”的形式顯示對(duì)應(yīng)算法的表現(xiàn)優(yōu)于/差于/接近DMONEO算法。

表2 基準(zhǔn)測(cè)試實(shí)驗(yàn)HV值

根據(jù)表2所示的HV指標(biāo)結(jié)果可得：DMONEO在Mo-TSP測(cè)試問(wèn)題中均取得了最優(yōu)的效果，MOEADD取得了兩個(gè)次優(yōu)值，NSGAII取得了一個(gè)次優(yōu)值。平衡優(yōu)化算法的平衡狀態(tài)池可以視為算法的選擇算子，對(duì)當(dāng)前4個(gè)最優(yōu)解以及平衡狀態(tài)解的選擇提高了算法的搜索能力。生存評(píng)分策略使算法在迭代過(guò)程中更好地保持多樣性。表3所示的運(yùn)行時(shí)間數(shù)據(jù)中，NSGAII取得了3個(gè)最優(yōu)值，DMONEO取得了3個(gè)次優(yōu)值。說(shuō)明DMONEO算法融合了快速非支配排序策略，復(fù)雜度略大于NSGAII，但運(yùn)行效率仍高于其他幾個(gè)對(duì)比算法。綜合表2、3的數(shù)據(jù)，DMONEO算法在Mo-TSP問(wèn)題中得到的解接近真實(shí)的帕累托前沿，具有較高的多樣性和效率性。

表3 基準(zhǔn)測(cè)試實(shí)驗(yàn)運(yùn)行時(shí)間

將DMONEO應(yīng)用于實(shí)際問(wèn)題中工件的焊點(diǎn)順序規(guī)劃問(wèn)題。本文作者以47個(gè)焊點(diǎn)為例，表4為47個(gè)焊點(diǎn)在焊接時(shí)的坐標(biāo)值和姿態(tài)值。表5、6分別為DMONEO算法和其他對(duì)比算法在47個(gè)焊點(diǎn)路徑規(guī)劃問(wèn)題的HV統(tǒng)計(jì)結(jié)果和運(yùn)行時(shí)間。

表4 47個(gè)焊點(diǎn)坐標(biāo)和姿態(tài)值

表5 焊點(diǎn)規(guī)劃實(shí)驗(yàn)HV值

表6 焊點(diǎn)規(guī)劃實(shí)驗(yàn)運(yùn)行時(shí)間

通過(guò)表5、6可得：DMONEO在實(shí)際焊接路徑規(guī)劃問(wèn)題中取得了優(yōu)異的表現(xiàn)，不僅取得了最好的HV指標(biāo)值，并且運(yùn)行時(shí)間也取得了最優(yōu)值。

DMONEO算法得到的最優(yōu)焊接序列為：17→34→16→20→12→25→27→11→5→24→6→38→40→42→35→41→31→30→2→3→39→1→32→22→36→26→14→29→15→4→43→21→8→9→33→7→13→28→44→45→46→47→18→19→37→23→10。

DMONEO算法在Mo-TSP測(cè)試和實(shí)際應(yīng)用中都取得了較好的效果，說(shuō)明該算法得到的解的多樣性和效率性都較高。在實(shí)際生產(chǎn)中，技術(shù)人員可以為兩個(gè)目標(biāo)設(shè)定不同的權(quán)重，從解集中可以得到與權(quán)重相對(duì)應(yīng)的最優(yōu)焊接路徑。

5 結(jié)語(yǔ)

本文作者針對(duì)點(diǎn)焊機(jī)器人的路徑規(guī)劃問(wèn)題，以工作時(shí)間和長(zhǎng)度路徑作為優(yōu)化目標(biāo)，提出一種結(jié)合改進(jìn)快速非支配排序策略的多目標(biāo)平衡優(yōu)化器算法——DMONEO。結(jié)合快速非支配排序策略，針對(duì)擁擠度因子不能很好地反映同層次解的密度的問(wèn)題，通過(guò)生存評(píng)分來(lái)替換擁擠度因子，可以更好地保持種群的多樣性。最后通過(guò)精英策略，將當(dāng)前種群和子代種群合并競(jìng)爭(zhēng)從而使得表現(xiàn)較好的個(gè)體保留。

通過(guò)TSP基準(zhǔn)測(cè)試進(jìn)行算法對(duì)比實(shí)驗(yàn)，結(jié)果表明本文作者提出的DMONEO算法相對(duì)于其他優(yōu)化算法和改進(jìn)算法均有較大的優(yōu)勢(shì)。最后，將提出的算法應(yīng)用于點(diǎn)焊機(jī)器人的路徑規(guī)劃中，得到了較好的路徑。未來(lái)進(jìn)一步研究可以從以下幾個(gè)方面發(fā)展：加入其他點(diǎn)焊機(jī)器人優(yōu)化目標(biāo)如能耗等，對(duì)點(diǎn)焊機(jī)器人的軌跡優(yōu)化進(jìn)行研究。