求解機器人雙邊裝配線平衡的萊維-灰狼優化算法研究

王惠敏,蘇瑩瑩

(沈陽大學機械工程學院,遼寧 沈陽 110044)

0 引言

裝配線廣泛應用于制造業。如何利用有效的方法平衡和優化裝配線,一直是制造業和學術界關注的焦點。求解裝配線平衡問題的目的是減少不平衡工時、降低工時損失、有效提高設備利用率、減少在制品,從而提高裝配線的生產效率、提升企業效益。裝配線按照自動化程度可以分為人工裝配線、人-機裝配線以及機器人裝配線。

隨著機器人越來越廣泛地應用在裝配線上,產品的裝配效率也越來越高,在一定程度上提高了企業的效益。然而,機器人在運轉工作的時候,也會帶來一定的能源消耗,以及投入的機器人成本。因此,在對機器人裝配線平衡問題進行優化時,如何在節拍最小化、降低機器人能耗以及機器人成本之間尋找一個契合點,已成為科研工作者工作的重心。

吳意等[1]針對雙邊裝配線平衡問題考慮了多種約束條件,并構造了一種改進的萬有引力搜索算法,以解決問題。詹慧文等[2]建立了雙邊裝配線平衡的多目標優化模型,提出了拓撲排序矩陣編碼方法、面向位置約束的解碼方法、變鄰域搜索策略,與標準蝙蝠算法相結合,對標桿算例進行求解。Zhong[3]以優化循環時間為目標,建立了混合整數線性規劃模型,并考慮順序相關和機器人的裝配時間。周炳海等[4]提出了最小化工作站數量和工作站占用空間的目標模型,并以改進的多目標免疫克隆算法求解。Zhong 等[5]建立了以最小化裝配成本和最小化工作站數量為目標的數學模型,并提出了一種離散人工魚群算法來求解。CIL 等[6]研究了混合模型RALBP-Ⅱ,提出了一種優化所有模型總節拍的波束搜索算法。Zhang 等[7]針對裝配線平衡和能源消耗,建立了考慮能耗和平衡率的雙目標優化數學模型;在對模型求解時,采用了一種結合細胞策略和局部搜索的多目標智能優化算法。蒙凱等[8]建立了以能耗最小為優化目標的數學模型,考慮了工序間的優先關系約束、節拍約束,并用灰狼算法來求解。Fysikopoulos 等[9]指出,在汽車制造過程中,能源成本占總成本的9%～12%,其中主要能源成本是機器人在裝配任務中所消耗的能源成本,而發電所產生的二氧化碳排放量占工廠總排放量的20%。Li 等[10]針對機器人雙邊裝配線建立了總能耗和節拍最小的雙目標模型,并用模擬退火算法求解。Nilakantan 等[11]提出了裝配線最小總碳足跡和最大裝配線效率的數學優化模型。

現階段的研究主要是對機器人裝配線進行單一目標或雙目標優化,而未對其節拍、能耗和成本組成的多目標集合進行優化。在機器人裝配線上,不僅節拍是主要的影響因素,能耗和機器人投入成本更是直接決定了投資成本。

1 問題描述

雙邊裝配線的特點是:裝配線長度較短,可以有效地縮短線上產品的生產時間;設備利用率高,可以減少投入的設備成本,從而應用于汽車、卡車、摩托車等制造業。雙邊裝配線除一些基本約束外,還包括位置約束、區域約束、同步約束等。

雙邊裝配線的工位布局如圖1 所示。

圖1 雙邊裝配線的工位布局圖Fig.1 Station layout of two-sided assembly line

建立機器人雙邊裝配線平衡的數學模型,需要對以下條件作假設:產品的裝配工序時間已經確定,工序邏輯優先級關系已知;所有操作都只分配到其中一個工作站;工作站的數量已經確定;每個工作站之間由傳送帶連接,傳送速度是一定的,可以忽略傳送時間,每相隔固定的節拍時間放置一個待裝配的零件。加工能耗是單位時間加工能耗與加工時間的乘積。待機能耗是單位時間待機能耗與待機時間的乘積。建立模型如下:

式中:r為機器類型;Nr為機器數量;R為機器類型集合,R={1,2,…,r,…,nr};rtir為操作i在機器r上的加工時間;Yrjk為PCr為機器r單位時間內的加工能耗;SPCr為機器r單位時間內的待機能耗;ECjk為工位(j,k)的能耗;TE為裝配線的總能耗;Hr為機器人r的成本。

式(1)為優化目標。式(2)為最小化生產節拍。式(3)為最小化總能耗。式(4)為最小化機器人成本。式(5)為操作分配約束,要求每個工序必須成對分配到工作站的一側。式(6)為優先關系約束,要求操作工序的前一工序必須被分配到靠前或者相同的成對工作站。式(7)為生產節拍約束,要求每個工序的完成時間須得小于或等于節拍時間。式(8)為成對工位操作內的優先關系約束。式(9)要求每個工作站必須分配有一個機器人。式(10)要求每個機器人必須被分配到一個工作站。

2 萊維飛行和灰狼優化算法

2.1 萊維飛行簡介

萊維(Levy)飛行[12]是一種理想的捕食方式,其特點是長時間短距離運動和偶爾長距離運動,以確保游動不會停留在某一局部區域。因此,一部分解在當前最優值的附近進行搜索,加快了局部搜索速度;另一個部分解在距離當前最優值足夠遠的空間中搜索,避免系統陷入局部搜索。在布谷鳥搜索算法中,Yang[13]利用Levy分布特征函數,經過變換得到如下概率密度函數:

在布谷鳥搜索算法中,通常使用式(12)計算萊維隨機數:

式中:μ、v服從標準正態分布;β=1.5。

φ的數學定義為:

2.2 灰狼優化算法

灰狼優化(grey wolf optimizer,GWO)算法是受灰狼群體捕食行為啟發,所研究出的一種群智能優化算法。該算法收斂性強、參數少、易于實現[14]。

2.2.1 灰狼算法基本原理

灰狼是群居生活的動物,在食物鏈中處于頂端。灰狼群體嚴格遵守等級關系。狼群的組織結構根據領導權力進行分級,主要分為4 個等級:α、β、δ、ω。低等級的狼服從于高等級的。

在狩獵過程中,主要尋優過程是由ω狼分散包圍獵物,其他3 個等級的狼根據收集到的信息指揮ω狼的移動方向,并決定是否更新自己的位置;當滿足終止條件以后,輸出最優解[15-16]。圖2 為灰狼種群層級金字塔圖。

圖2 灰狼種群層級金字塔圖Fig.2 Hierarchical pyramid of gray wolf population

2.2.2 灰狼行為

在灰狼算法中,灰狼的行為主要包括以下3 種。

①搜索。

狼群搜索獵物的過程主要由灰狼α、β、δ的指引來實現。在模擬此行為時,假定α、β、δ能識別隱藏獵物的位置。因此,每次進行迭代計算,保留當前種群中最好的3 個灰狼(α、β、δ),而后依據它們的位置更新其他灰狼的位置[17-18]。該行為的數學模型表示如下:

式中:Xα、Xβ、Xδ分別為當前種群中α、β、δ的位置;X為灰狼的位置;Dα、Dβ、Dδ分別為目前ω狼與α、β、δ狼之間的距離。

當|A|>1 時,灰狼盡可能地分散在不同的區域,尋找獵物;當|A|<1 時,灰狼將會聚集在同一個或多個區域尋找獵物。

②包圍獵物。

在包圍的過程中,獵物與灰狼個體的位置可以表示為:

式中:t為迭代次數;xp為獵物的位置;X為灰狼的位置;A、C為向量的系數;r1和r2為數值在 [0 1 ]之中的隨機向量[19]。

在整個迭代計算過程中,a從2 線性降到0。

③襲擊獵物。

在建立此行為模型的過程中,當獵物停止移動時,灰狼群開始襲擊獵物,灰狼群的狩獵行為結束。在算法進行到后期時,可以通過將收斂因子a從2 線性地減少到0 來模擬此過程。當|A|≤1 時,灰狼群體開始襲擊獵物?；依侨后w的襲擊行為仿真使灰狼算法具有良好的局部精細搜索能力[19-20]。

2.3 基于萊維飛行的灰狼優化算法

2.3.1 基本原理

優化算法在原灰狼優化算法中,最優解即為α狼的位置。由于存在精英保存策略,在GWO 算法后期,群體中所有的灰狼個體都接近最優個體α狼,從而喪失了種群的多樣性,使算法陷入局部收斂。針對這些不足之處,本文研究基于萊維飛行的灰狼優化(Levy-GWO)算法,采用萊維飛行來全局搜索群體中的灰狼個體α狼。萊維飛行屬于隨機行走,是一種很好的搜索策略。它可以擴大搜索范圍,飛行步長滿足穩定分布。在萊維飛行中,新一代α狼的計算公式如下:

式中:X(t)為第t代時灰狼個體α狼的位置;⊕為點對點乘法;a為α狼位置的隨機數,由式(20)決定;Levy(β)為隨機搜索路徑,由式(21)決定。

2.3.2 算法流程

Levy-GWO 算法的算法流程如圖3 所示。

圖3 Levy-GWO 算法流程圖Fig.3 Levy-GWO algorithm flowchart

算法流程如下。

①輸入。輸入裝配線平衡問題數據。

②數值初始化。初始化灰狼種群、灰狼個體的位置和目標函數值。

③選出頭狼α狼。遍歷灰狼群的所有個體,計算出狼群個體的適應度值。選取最優值為α狼(即頭狼),β狼為次優,其余為δ狼和ω狼。

④更新狼群位置。根據式(1)更新α狼位置,同時利用萊維飛行和灰狼算法結合得出的式(20)～式(22)全局搜索α狼;計算出每次迭代所得的a、A、C等參數值。

⑤計算每只狼在新位置的適應度值。若新個體的適應度值優于舊個體,則更新新一代個體,由新個體替換原來的位置,并更新適應度值。反之,保留舊個體,原來的適應度值保持不變。

⑥包圍獵物。按照式(5)～式(11)更新參與圍攻行為的α狼、β狼、δ狼位置,對獵物實施圍攻行為。當|A|≤1 時,進行下一步襲擊獵物行為。

⑦如果達到迭代終止條件,則輸出頭狼的位置;反之,轉步驟③。

3 基于Levy-GWO 算法的機器人雙邊裝配線平衡

GWO 算法具有局部搜索能力強、收斂速度快、易于編程實現等特點,但存在全局搜索能力較弱、易陷入局部收斂早熟等不足。在算法中,引入萊維飛行對群體中α 狼展開全局搜索,擴大搜索范圍。

3.1 編碼

機器人雙邊裝配線涉及工序和機器人的作業分配。因此,需要在種群初始化時,完成工序編碼和機器人編碼工作。

雙邊裝配線平衡問題屬于離散問題。GWO 算法多用于求解連續性問題。因此,工序編碼采用隨機數編碼方式,以實現連續問題轉換為離散問題。此編碼包含N個要素,每個元素都是[0～1]之間的隨機數,每個位置的隨機數表示相應操作的權重。N代表搜索空間維度,即任務數。假設任務的隨機數越低,則優先級越高,并按照由高至低的順序排序任務的優先級。例如,任務8的隨機數0.25 具有最高的最小優先級,因此它在操作序列中排名第一。以此類推,可以獲得操作序列(8、2、10、3、6、9、7、1、4、5)。任務隨機數如表1 所示 。

表1 任務隨機數Tab.1 Task random number

3.2 解碼

解碼中,考慮工序優先關系、節拍約束、位置關系以及工序內的優先關系。

解碼方式可進一步得到工作站的供需分布和適應度函數值。具體步驟如下。

①初始節拍值為:

令當前的節拍C=C0,工作站序號j=1。

②根據操作序列分配順序,將操作i分配給工作站j。如果分配的工作站的裝配時間大于節拍C,則工作站編號j←j+1 。

③重復步驟②,直至所有操作分配完成。

④如果工作站的數量大于m,則令C←C+1,轉步驟②。

⑤計算節拍、能耗以及機器人成本。

萊維飛行:根據灰狼算法的原理,利用3 只適應度最好的灰狼(α、β、δ) 來引導其余灰狼ω包圍獵物并更新位置。

4 實例應用及分析

X 汽車公司作為汽車生產行業的佼佼者,其車身車間裝配線大多采用機器人裝配線。為驗證算法的可行性,從X 公司汽車車身裝配線上截取5 個成對工位,共40 個任務;每個工位上有1 個機器人,共10 個機器人;每個成對工位的初始節拍為149 s。機器人的能耗主要為電力消耗,機器人每工作1 h,其能耗(包括工作能耗和待機能耗)為406 kW·h,機器人總成本為210 萬元。用MATLAB 2018 軟件編寫程序,進行求解尋優,所得結果如表2～表4 所示,優化曲線如圖4～圖6 所示。

表2 節拍優化結果Tab.2 Beat optimization results

表3 能耗優化結果Tab.3 Energy consumption optimization results

表4 成本優化結果Tab.4 Cost optimization results

圖4 節拍優化曲線Fig.4 Beat optimization curve

圖5 能耗優化曲線Fig.5 Energy consumption optimization curve

圖6 成本優化曲線Fig.6 Cost optimization curve

由求解所得各目標函數的解和優化結果可知,通過灰狼算法結合萊維飛行進行求解之后,節拍優化了39 s,能耗優化了106 kW·h,機器人投入成本優化了39 萬元。經過優化,在縮短節拍、提高生產效率的同時,也減少了能耗投入和建線時的機器人成本投入,一定程度地降低了企業的生產成本。

5 結論

綜合上述分析可知,案例的結果進一步驗證了Levy-GWO 算法的可行性與有效性。操作分配約束、作業優先約束、位置約束增加了機器人雙邊裝配線問題的復雜性,將萊維飛行與灰狼算法結合,可以有效提高算法的全局搜索能力。在更新狼群位置的過程中,萊維飛行可以保證搜索范圍的全局性,提高了灰狼算法的全局搜索尋優能力。該研究為企業提高生產效率、減少成本投入提供了新思路和新方法。