基于混合灰狼算法實現(xiàn)第Ⅱ類機器人U型裝配線能耗優(yōu)化

張子凱 唐秋華 張利平 李梓響

1.武漢科技大學(xué)冶金裝備及其控制教育部重點實驗室，武漢，430081

2.武漢科技大學(xué)機械傳動與制造工程湖北省重點實驗室，武漢，430081

0 引言

裝配線是一種常用于汽車、電子等行業(yè)的產(chǎn)品制造系統(tǒng)。在裝配線上，產(chǎn)品從入口線的工位依次進入下一工位進行裝配，直到從出口線的工位出來。該過程中，工序的裝配順序需滿足工序間的優(yōu)先關(guān)系，且工位的加工時間應(yīng)小于節(jié)拍。不同于傳統(tǒng)的直線型裝配線，U型裝配線的同一工位既可以包含入口線工序，也可以包含出口線工序，這使得U型裝配線具有更高的生產(chǎn)效率和柔性。如今，自動化技術(shù)已逐漸應(yīng)用到企業(yè)的裝配系統(tǒng)，機器人開始逐漸替代工人在裝配線上進行作業(yè)的裝配。

M ILTENBURC等［1］提出并構(gòu)建了U型裝配線平衡的數(shù)學(xué)模型后，眾多學(xué)者開始研究U型裝配線平衡問題。G?K?EN等［2］采用最短路徑法、OGAN等［3］提出分支定界法來求解簡單U型裝配線平衡問題。LI等［4］提出多規(guī)則啟發(fā)式算法求解第二類U型裝配線平衡問題。RABBBANI等［5］同時考慮混流U型裝配線的工位負(fù)載和線效率，提出了基于規(guī)則編碼的遺傳算法來實現(xiàn)該類問題的求解。張子凱等［6］設(shè)計了基于Bender分解的多目標(biāo)快速非支配遺傳算法來實現(xiàn)多重資源約束下的第一類U型裝配線平衡問題的求解。查靚等［7］運用基于信息素更新的蟻群算法求解第一類U型裝配線問題。劉冉等［8］采用多目標(biāo)克隆免疫協(xié)同進化算法來實現(xiàn)混流U型裝配線平衡與調(diào)度的多目標(biāo)集成優(yōu)化問題的求解。唐秋華等［9］基于隨機機會約束規(guī)劃，通過確定性等價和線性化處理模型，采用GAMS/Cplex實現(xiàn)小規(guī)模U型裝配線的平衡問題的優(yōu)化。

總體來看，上述研究主要是研究半自動化或人工U型裝配線，主要目的是在生產(chǎn)節(jié)拍和優(yōu)先關(guān)系的約束下，將各裝配工序分配到工位。不同于該類裝配線，機器人裝配線不僅要分配工序到工位，還應(yīng)當(dāng)分配機器人到工位。因此為實現(xiàn)機器人U型裝配線工序和機器的協(xié)同優(yōu)化，本文以能耗為優(yōu)化目標(biāo)，提出一種基于隨機鍵編碼的混合灰狼優(yōu)化（hybrid gray w olf optim ization，HG?WO）算法，并將算法與原始灰狼算法進行對比以證明算法的優(yōu)越性。

1 機器人U型裝配線

機器人U型裝配線由若干個工作站組成，每個工作站一般配備一個機器人來完成裝配工序，因此，機器人U型裝配線問題主要涉及兩類問題：工序分配和機器人分配。

U型裝配線中，某一工序的直接前序或直接后序分配到工作站，該工序才能進行分配。為描述這種關(guān)系，URBAN［10］提出了影子優(yōu)先約束關(guān)系（圖1）。基于影子優(yōu)先約束關(guān)系分配工序到工作站時，每個工作站的裝配時間應(yīng)當(dāng)小于或等于預(yù)定的節(jié)拍。

圖1 影子優(yōu)先約束關(guān)系Fig.1 Phantom p recedence relationship

分配機器人到工作站時，一般假設(shè)機器人的數(shù)量等于工作站的數(shù)量，且各工序在不同機器人上的裝配時間不同［11］。由于部分機器人不能裝配所有的工序，故當(dāng)某一機器人無法裝配某一工序時，設(shè)置其裝配時間為一個極大值。圖2展示了機器人U型裝配線。

機器人裝配線平衡問題中，一般以能耗為其主要的優(yōu)化目標(biāo)。裝配線問題中，能耗特指電能耗，主要包含兩部分：裝配能耗和待機能耗。各能耗分別與裝配時間和待機時間成正比［12］，計算公式如下：

式中，P1為裝配能耗；P2為待機能耗；P3為總能耗；n、m、r分別為工序數(shù)、工作站數(shù)和機器數(shù)；Xij(Yij)為1表示工序i分配到工作站j的入口線（出口線）；Zkj為1表示機器人k分配到工作站j；tik為工序i在機器人k上的裝配時間；Ek、Ik分別為機器人k的裝配單元能耗和待機單元能耗；C為節(jié)拍。

2 混合灰狼算法

原始的灰狼算法模擬灰狼尋找獵物的行為來搜索最優(yōu)解。灰狼社會有4種狼：α、β、δ和ω，其中，具有最佳適應(yīng)度的狼稱為α，具有第二、第三最佳適應(yīng)度的狼分別稱為β和δ，其余的狼稱為ω。灰狼算法中，低等級的狼必須服從高等級的狼，所以算法中的狩獵過程（優(yōu)化過程）主要由α、β和δ引導(dǎo)ω包圍獵物，并不斷更新其位置，更新方式如下：

式中，t為當(dāng)前迭代次數(shù)；Xp為獵物位置；X為灰狼的位置；A、C為系數(shù)；r1、r2為服從［0，1］均勻分布的隨機變量；a在迭代過程中，從2到0線性下降。

在α、β和δ引導(dǎo)ω包圍獵物時，由于獵物的位置是未知的，該算法假設(shè)獵物位于α、β和δ之間，所以在α、β和δ引導(dǎo)下，灰狼ω位置更新如下：

其中，Xα、Xβ、Xδ分別為α、β和δ的位置。

上述灰狼算法常用來處理連續(xù)問題，而機器人U型裝配線為一個離散問題。為此，有效的編碼方式和進化機制是實現(xiàn)灰狼算法求解機器人U型裝配線平衡問題的關(guān)鍵。本文提出的混合灰狼算法采用隨機鍵編碼方式對種群個體進行編碼，解碼中，考慮工序間的優(yōu)先關(guān)系約束和節(jié)拍約束，將工序和機器人分配到工位，計算灰狼的適應(yīng)度函數(shù)值（能耗值）。算法基于灰狼個體間的社會等級信息，選擇出3只最優(yōu)狼指引剩余個體進化，防止算法陷入局部最優(yōu)，以實現(xiàn)種群的更新。最后，算法采用交叉算子，以實現(xiàn)種群間的信息交流。

2.1 編碼和解碼

機器人U型裝配線涉及工序和機器人的分配［13?15］，因此，種群初始化時，其編碼主要包含兩部分：工序編碼和機器人編碼。

工序編碼采用隨機鍵編碼方式，以實現(xiàn)連續(xù)問題到離散問題的轉(zhuǎn)換。該編碼包含N個要素，每一個要素為0、1之間的隨機數(shù)，且每一位置的隨機數(shù)表示對應(yīng)工序的權(quán)值。當(dāng)從可選工序集中選擇工序進行分配時，權(quán)值最大的工序被挑選出來。可選工序集包含兩部分：入口線可選工序集和出口線可選工序集。依據(jù)影子優(yōu)先約束關(guān)系，若工序的所有直接前序工序已分配，則該工序進入入口線可選工序集；若工序的所有直接后續(xù)工序已分配，則進入出口線可選工序集。

如圖3所示，某一灰狼的工序權(quán)值編碼為{0.910 1，0.854 2，0.321 5，0.120 3，0.146 5，0.652 4，0.854 1，0.941 2，0.215 3}。由影子優(yōu)先約束關(guān)系圖（圖1）可知，初始入口線可選工序集為{1}，出口線可選工序集為{7，9}，則可選工序集中具有最大權(quán)值0.910 1的工序1被挑選出，存放到工序分配序列第一個位置，且被分配到入口線。由于工序1已被分配，則工序1從可選工序集中剔除，且此時工序2、3、4的所有直接前序工序1已被分配，則工序2、3、4進入入口線可選工序集。更新后，入口線可選工序集為{2，3，4}，出口線可選工序集為{7，9}。第二次選擇時，可選工序集中具有最大權(quán)值0.852 4的工序2存放到工序分配序列第二個位置，且被分配到入口線。以此類推，直到所有的工序存放到工序分配序列。機器人編碼中，編碼長度等于工位的數(shù)量且每一要素表示機器人代號。

上述工序編碼和機器編碼僅僅得到工序分配順序和機器人分配情況，而解碼方式則是進一步獲取工序分配到工位情況以及獲取適應(yīng)度函數(shù)值。具體步驟如下：

（1）初始節(jié)拍值為

令當(dāng)前節(jié)拍C=C0，工作站序號j=1；

（2）按照工序分配序列，將工序i分配到工作站j中，若分配后的工作站裝配時間大于節(jié)拍C，則工作站序號j←j+1，將工序i重新分配到工作站j；

（3）重復(fù)步驟（2），直至工序全部分配；

（4）若工作站數(shù)量大于m，則令C←C+1，轉(zhuǎn)步驟（2）；

（5）計算能耗值。

2.2 進化機制

根據(jù)原始灰狼算法包圍獵物的原理，利用適應(yīng)度函數(shù)最佳的3只灰狼α、β和δ引導(dǎo)其余灰狼ω包圍獵物，實現(xiàn)位置的更新。

2.3 交叉算子

原始灰狼算法只有最佳的3只灰狼α、β、δ與其余灰狼ω存在信息交流，最低等級的灰狼ω之間無信息交流。因此，為增強灰狼間的信息交流，該算法分別針對工序編碼和機器人編碼，提出兩種交叉方式：雙點工序交叉和單點機器人交叉。具體交叉方式如圖4、圖5所示。

圖3 編碼和解碼Fig.3 Encode and decode

圖4 雙點工序交叉Fig.4 Two-point task crossover

圖5 單點機器人交叉Fig.5 Single-poin t robot crossover

混合灰狼算法的流程如圖6所示。

圖6 混合灰狼算法流程Fig.6 Flow chart of hybrid grey wolf op tim ization

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

為驗證HGWO算法的性能，將HGWO算法與GWO算法進行對比。兩種算法都采用C語言進行編程，并在同一臺電腦上運行，電腦配置為：Intel Core i5 CPU，2.80 GHz and 2.00 GB RAM。實驗案例選取大規(guī)模U型裝配線標(biāo)桿案例：A rcus111，Barthol148和Scholl297。3個案例的工序數(shù)n分別為111、148、297。且每個案例分別設(shè)置4種規(guī)模的工作站數(shù)量：A rcus111中，m=9，13，17，22；Barthol148中，m=10，14，21，29；Scholl297中，m=19，29，38，50。機器人的數(shù)量r等于工作站的數(shù)量。案例的優(yōu)先關(guān)系和裝配時間來自專業(yè)裝配線網(wǎng)站https：//assembly?line?balancing.de/。工序在不同機器人上的加工時間在［0.8ti，1.2ti］中隨機生成（ti為工序 i的裝配時間），單元能耗值在［0.2，3.0］中隨機生成［12］。算法終止條件設(shè)置為運行時間n×n×10和n×n×20。

算法對比前，采用M initab中的田口實驗對算法進行參數(shù)校驗，得出最佳參數(shù)組合。HGWO最佳參數(shù)組合為：種群規(guī)模40，交叉概率0.7；GWO最佳參數(shù)組合為：種群規(guī)模40。

對比試驗中，每一個案例運行10次，獲取總能耗的最小值和平均值。表1、表2分別展示了2種終止條件下的對比結(jié)果。

表1 終止條件為n×n×10的對比結(jié)果Tab.1 Com parative resu lts of term inal condition n×n×10

表2 終止條件為n×n×20的對比結(jié)果Tab.1 Com parative results of term inal condition n×n×20）

由表1、表2可知，在不同的案例，兩種終止條件下，HGWO所獲得能耗最小值和平均值基本都要小于GWO獲取的結(jié)果。從而證明了所提出的HGWO算法在求解機器人U型裝配線能耗優(yōu)化問題時具有顯著的優(yōu)越性。

圖7為HGWO算法求解A rcus111問題的收斂圖，即能耗隨迭代次數(shù)的變化曲線。由圖7可知，在算法運行到70代左右時，算法收斂很快；70～308代時，算法收斂變慢，但種群還在持續(xù)進化；308代之后，算法基本不再進化。這表明HGWO算法在求解該問題時具有較好的收斂性。

圖7 HGWO算法收斂圖Fig.7 Convergence of HGWO algorithm

為分析能耗的降低是否會影響裝配線常規(guī)目標(biāo)——節(jié)拍值，本文分析了不同方案的工序分配、機器人分配和目標(biāo)值。表4展示了兩種方案的工序和機器人布局，以及節(jié)拍值和能耗值。所分析的案例為A rcus111標(biāo)桿案例，工序數(shù)為111，工作站和機器人數(shù)為9。方案1為HGWO算法的第一代最優(yōu)解的分配方案，方案2為算法優(yōu)化后，得到的最優(yōu)解的分配方案。由表4可知，由于方案1中工序分配很不均勻，其最終的節(jié)拍值和能耗都很大，分別為755和9 252.28。方案2工序分配比較均勻，每個工作站的工序數(shù)量都在13左右，且節(jié)拍值和能耗都要小于方案1，分別為709和8 756.12。由此可以發(fā)現(xiàn)，在算法優(yōu)化能耗的同時，節(jié)拍值也在逐漸減小，表明能耗的降低也會影響裝配線的傳統(tǒng)目標(biāo)——節(jié)拍。因此，在實際裝配線布局時，企業(yè)可以以能耗為目標(biāo)，來平衡裝配線的生產(chǎn)負(fù)載。這樣既可以達(dá)到負(fù)載均衡的目的，也能降低企業(yè)的生產(chǎn)能耗。

表4 能耗節(jié)能方案對比表Tab.4 Com parative results of the energy consum p tion p lans

4 結(jié)語

針對當(dāng)前逐漸推廣的機器人U型裝配線問題，本文以能耗為優(yōu)化目標(biāo)，介紹了機器人U型裝配線平衡問題，并采用混合灰狼算法求解了該問題。算法采用隨機鍵編碼方式實現(xiàn)工序編碼，將連續(xù)問題離散化。針對問題中的工序分配和機器人分配，引入兩種交叉算子，實現(xiàn)算法中最低等級灰狼之間的信息交流。通過與原始灰狼算法的對比，驗證了混合灰狼算法性能的可行性和有效性。在未來的研究中，可以將生產(chǎn)中的負(fù)載問題與能耗問題進行協(xié)同優(yōu)化。