基于改進多目標平衡優化器算法的點焊機器人路徑規劃

趙云濤，甘鐳，李維剛

(武漢科技大學，冶金自動化與檢測技術教育部工程研究中心，湖北武漢 430081)

0 前言

機器人在車身焊接中應用廣泛，但傳統點焊的路徑規劃多采用手工教學方法。手工教學方法的焊接質量取決于工人的技能和經驗，焊接質量不能保證。因此，需要采用自動、有效的路徑優化方法。規劃合理的焊接路徑、提高生產效率是當前研究的熱點。

點焊機器人的路徑規劃是一個最優化問題。根據給定的焊點，規劃機器人焊槍通過這些符合相應約束條件的焊點運動的最佳路徑。王學武等[1]針對弧焊機器人的路徑長度和能耗比提出了一種自適應鄰域的離散DMOEA/D-ET算法，通過觸發機制選擇全局搜索和局部勘探兩種策略，局部搜索采用MOEA/D算法。高明、陸穎[2]針對汽車引擎蓋焊接的路徑規劃問題，提出一種改進蟻群算法，對原始蟻群算法的信息素更新加入自適應混沌策略，局部信息素根據蟻群密度自適應變化，全局信息素則結合混沌擾動進行更新，信息素的改進提高了多樣性和隨機性。文獻[3]指出對于焊接機器人的規劃，路徑長度和周期時間非常重要，針對焊接機器人建立了路徑和時間模型，并提出一種采用聚類引導的多目標粒子群算法來解決點焊機器人的路徑規劃問題。

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

以高效解決點焊機器人的路徑規劃問題為目標，本文作者提出一種融合改進快速非支配排序的離散多目標平衡優化器算法(Discrete Multi-Objective Non-dominated Equilibrium Optimizer，DMONEO)。結合快速非支配排序策略，針對擁擠度因子不能很好地反映同層次解的密度，通過生存評分來替換擁擠度因子，可以更好地保持種群的多樣性。最后通過精英策略，將當前種群和子代種群合并競爭從而使得表現較好的個體保留。

1 點焊機器人路徑規劃問題

機器人的路徑規劃可以簡化為旅行商問題(Traveling Salesman Problem，TSP)。以一個焊接工件作為路徑規劃的對象，工件中有多個焊點。焊槍的運動代表了旅行銷售員的行走。路徑規劃是為了尋找穿越所有焊點的最短路徑。在實際生產作業中，達到最高效率是優化目的。因此，本文作者針對焊接時間和焊接路徑建立了模型。

1.1 焊接時間模型

在焊接過程中，當機器人在焊接點{γ1，γ2，…，γi，…，γn}之間移動時，它對應于一個時間序列{t1，t2，…，ti，…，tn-1，tn}。ti表示焊點γi與焊點γi+1之間移動所需要的時間。tn為焊接時間，包括工作時間和移動時間。因為焊接所用的工作時間是固定的。為了簡化問題，焊接時間主要考慮了焊點之間的移動時間。焊接時間的定義見式(1)

(1)

1.2 焊接長度模型

(2)

其中：σ5、σ4、σ3、σ2、σ1、σ0為系數；ti為時間。

焊點之間的運動軌跡γiγi+1在關節空間中可以分為等量的p段。根據等式計算軌跡上p個點的角位移θi1、…、θip，通過機器人的運動學分析，得到了p個點對應的笛卡爾坐標值。隨著段數的增加，p段軌跡的和近似為路徑長度qi，i+1

(3)

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

(4)

移動路徑的總長度計算見式(5)

(5)

1.3 多目標路徑規劃模型

將所建立的焊接路徑長度模型和焊接時間模型作為路徑規劃的目標函數，以最大角速度和最大角加速度為約束條件，由此建立點焊機器人路徑規劃的多目標模型，見式(6)(7)

Minimize：f1(x)=L(x)

(6)

Minimize：f2(x)=T(x)

(7)

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

2 平衡優化器算法

平衡優化器算法的思想參考了質量平衡模型[4]，見式(8)

(8)

其中：V代表控制容積；C表示控制容積內的濃度；Q為流進或流出控制容積的容量流速；Ceq表示控制容積內部在平衡時的濃度；G代表控制容積內部的質量生成速率。平衡優化器算法的流程如下：

(1)種群初始化

初始種群是根據種群規模在每個決策變量的上下界范圍內進行隨機初始化，見式(9)

(9)

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

(2)生成平衡狀態池

更新過程中的候選解選自平衡狀態池，見式(10)

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

(10)

其中：Ceq，1、Ceq，2、Ceq，3、Ceq，4分別為當前種群中最好的4個解；Ceq，ave代表這4個解的平衡狀態。更新過程中在平衡狀態池里隨機選取最優解。前4個候選解用于爭取更好的勘探效果，第5個候選解為平衡值可以提高開發水平。

(3)指數項系數

指數項系數記為F，影響更新規則，定義見式(11)—(13)

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

(11)

(12)

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

(13)

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

(4)生成率

生成率記為G，設計如下，見式(14)(16)

G=G0e-λ(t-t0)

(14)

G0=GCP(Ceq-λC)

(15)

(16)

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

(5)更新公式

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

(17)

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

3 離散化多目標平衡優化器算法

3.1 離散編碼方式

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

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

順序交叉算子的操作見圖1，可以分為以下3個步驟：

圖1 交叉算子流程

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

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

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

隨機插入算子的操作見圖2，可以分為以下3個步驟：

圖2 變異算子流程

(1)父代隨機選擇3個點，分別作為插入點、保留領域信息的起點和終點。

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

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

3.2 生存評分策略

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

生存評分計算步驟如下：

(1)歸一化

在迭代過程中，使用非支配排序將種群劃分為不同層次的非支配前沿。然后，對第一個非支配前沿進行標準化和歸一化處理，見式(18)

(18)

(2)計算Lp范數估計前沿集合形狀

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

(19)

(20)

(3)計算生存評分

通過第一個非主導前沿F1的Lp范數，測量f1的多樣性和鄰近性。計算見式(21)(22)

(21)

(22)

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

(23)

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

3.3 算法流程

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

圖3 DMONEO算法流程

4 實驗驗證與分析

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

表1 TSP基準測試函數

實驗所用計算機環境為Intel Corei5-7300HQ@2.50 GHz CPU，16 GB內存，Windows10 64位操作系統。運行環境為MATLAB-R2019b。對比算法基于PlatEMO平臺[15]。

本文作者使用超體積度量(Hypervolume，HV)以及算法的運行時間(Runtime)來衡量DMONEO算法和對比算法的性能。HV計算的是解集與參考點之間的目標空間體積。較大的HV代表著算法的表現更好，更接近真實的帕累托前沿和更好的多樣性。運行時間體現了該算法的計算復雜度。

表2、3分別為DMONEO算法和其他對比算法在測試問題的HV統計結果和運行時間。性能指標平均值和標準方差作為評價標準，運行時間單位為秒(s)。帶下劃線的數據代表該算法在相應測試問題上表現最優。表格底部的數據是通過Wilcoxon符號秩檢驗的結果，以“+/-/=”的形式顯示對應算法的表現優于/差于/接近DMONEO算法。

表2 基準測試實驗HV值

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

表3 基準測試實驗運行時間

將DMONEO應用于實際問題中工件的焊點順序規劃問題。本文作者以47個焊點為例，表4為47個焊點在焊接時的坐標值和姿態值。表5、6分別為DMONEO算法和其他對比算法在47個焊點路徑規劃問題的HV統計結果和運行時間。

表4 47個焊點坐標和姿態值

表5 焊點規劃實驗HV值

表6 焊點規劃實驗運行時間

通過表5、6可得：DMONEO在實際焊接路徑規劃問題中取得了優異的表現，不僅取得了最好的HV指標值，并且運行時間也取得了最優值。

DMONEO算法得到的最優焊接序列為：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測試和實際應用中都取得了較好的效果，說明該算法得到的解的多樣性和效率性都較高。在實際生產中，技術人員可以為兩個目標設定不同的權重，從解集中可以得到與權重相對應的最優焊接路徑。

5 結語

本文作者針對點焊機器人的路徑規劃問題，以工作時間和長度路徑作為優化目標，提出一種結合改進快速非支配排序策略的多目標平衡優化器算法——DMONEO。結合快速非支配排序策略，針對擁擠度因子不能很好地反映同層次解的密度的問題，通過生存評分來替換擁擠度因子，可以更好地保持種群的多樣性。最后通過精英策略，將當前種群和子代種群合并競爭從而使得表現較好的個體保留。

通過TSP基準測試進行算法對比實驗，結果表明本文作者提出的DMONEO算法相對于其他優化算法和改進算法均有較大的優勢。最后，將提出的算法應用于點焊機器人的路徑規劃中，得到了較好的路徑。未來進一步研究可以從以下幾個方面發展：加入其他點焊機器人優化目標如能耗等，對點焊機器人的軌跡優化進行研究。