求解機(jī)器人雙邊裝配線平衡的萊維-灰狼優(yōu)化算法研究

王惠敏,蘇瑩瑩

(沈陽大學(xué)機(jī)械工程學(xué)院,遼寧 沈陽 110044)

0 引言

裝配線廣泛應(yīng)用于制造業(yè)。如何利用有效的方法平衡和優(yōu)化裝配線,一直是制造業(yè)和學(xué)術(shù)界關(guān)注的焦點(diǎn)。求解裝配線平衡問題的目的是減少不平衡工時(shí)、降低工時(shí)損失、有效提高設(shè)備利用率、減少在制品,從而提高裝配線的生產(chǎn)效率、提升企業(yè)效益。裝配線按照自動(dòng)化程度可以分為人工裝配線、人-機(jī)裝配線以及機(jī)器人裝配線。

隨著機(jī)器人越來越廣泛地應(yīng)用在裝配線上,產(chǎn)品的裝配效率也越來越高,在一定程度上提高了企業(yè)的效益。然而,機(jī)器人在運(yùn)轉(zhuǎn)工作的時(shí)候,也會(huì)帶來一定的能源消耗,以及投入的機(jī)器人成本。因此,在對(duì)機(jī)器人裝配線平衡問題進(jìn)行優(yōu)化時(shí),如何在節(jié)拍最小化、降低機(jī)器人能耗以及機(jī)器人成本之間尋找一個(gè)契合點(diǎn),已成為科研工作者工作的重心。

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

現(xiàn)階段的研究主要是對(duì)機(jī)器人裝配線進(jìn)行單一目標(biāo)或雙目標(biāo)優(yōu)化,而未對(duì)其節(jié)拍、能耗和成本組成的多目標(biāo)集合進(jìn)行優(yōu)化。在機(jī)器人裝配線上,不僅節(jié)拍是主要的影響因素,能耗和機(jī)器人投入成本更是直接決定了投資成本。

1 問題描述

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

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

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

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

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

式(1)為優(yōu)化目標(biāo)。式(2)為最小化生產(chǎn)節(jié)拍。式(3)為最小化總能耗。式(4)為最小化機(jī)器人成本。式(5)為操作分配約束,要求每個(gè)工序必須成對(duì)分配到工作站的一側(cè)。式(6)為優(yōu)先關(guān)系約束,要求操作工序的前一工序必須被分配到靠前或者相同的成對(duì)工作站。式(7)為生產(chǎn)節(jié)拍約束,要求每個(gè)工序的完成時(shí)間須得小于或等于節(jié)拍時(shí)間。式(8)為成對(duì)工位操作內(nèi)的優(yōu)先關(guān)系約束。式(9)要求每個(gè)工作站必須分配有一個(gè)機(jī)器人。式(10)要求每個(gè)機(jī)器人必須被分配到一個(gè)工作站。

2 萊維飛行和灰狼優(yōu)化算法

2.1 萊維飛行簡介

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

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

式中:μ、v服從標(biāo)準(zhǔn)正態(tài)分布;β=1.5。

φ的數(shù)學(xué)定義為:

2.2 灰狼優(yōu)化算法

灰狼優(yōu)化(grey wolf optimizer,GWO)算法是受灰狼群體捕食行為啟發(fā),所研究出的一種群智能優(yōu)化算法。該算法收斂性強(qiáng)、參數(shù)少、易于實(shí)現(xiàn)[14]。

2.2.1 灰狼算法基本原理

灰狼是群居生活的動(dòng)物,在食物鏈中處于頂端。灰狼群體嚴(yán)格遵守等級(jí)關(guān)系。狼群的組織結(jié)構(gòu)根據(jù)領(lǐng)導(dǎo)權(quán)力進(jìn)行分級(jí),主要分為4 個(gè)等級(jí):α、β、δ、ω。低等級(jí)的狼服從于高等級(jí)的。

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

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

2.2.2 灰狼行為

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

①搜索。

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

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

當(dāng)|A|>1 時(shí),灰狼盡可能地分散在不同的區(qū)域,尋找獵物;當(dāng)|A|<1 時(shí),灰狼將會(huì)聚集在同一個(gè)或多個(gè)區(qū)域?qū)ふ耀C物。

②包圍獵物。

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

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

在整個(gè)迭代計(jì)算過程中,a從2 線性降到0。

③襲擊獵物。

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

2.3 基于萊維飛行的灰狼優(yōu)化算法

2.3.1 基本原理

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

式中:X(t)為第t代時(shí)灰狼個(gè)體α狼的位置;⊕為點(diǎn)對(duì)點(diǎn)乘法;a為α狼位置的隨機(jī)數(shù),由式(20)決定;Levy(β)為隨機(jī)搜索路徑,由式(21)決定。

2.3.2 算法流程

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

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

算法流程如下。

①輸入。輸入裝配線平衡問題數(shù)據(jù)。

②數(shù)值初始化。初始化灰狼種群、灰狼個(gè)體的位置和目標(biāo)函數(shù)值。

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

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

⑤計(jì)算每只狼在新位置的適應(yīng)度值。若新個(gè)體的適應(yīng)度值優(yōu)于舊個(gè)體,則更新新一代個(gè)體,由新個(gè)體替換原來的位置,并更新適應(yīng)度值。反之,保留舊個(gè)體,原來的適應(yīng)度值保持不變。

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

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

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

GWO 算法具有局部搜索能力強(qiáng)、收斂速度快、易于編程實(shí)現(xiàn)等特點(diǎn),但存在全局搜索能力較弱、易陷入局部收斂早熟等不足。在算法中,引入萊維飛行對(duì)群體中α 狼展開全局搜索,擴(kuò)大搜索范圍。

3.1 編碼

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

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

表1 任務(wù)隨機(jī)數(shù)Tab.1 Task random number

3.2 解碼

解碼中,考慮工序優(yōu)先關(guān)系、節(jié)拍約束、位置關(guān)系以及工序內(nèi)的優(yōu)先關(guān)系。

解碼方式可進(jìn)一步得到工作站的供需分布和適應(yīng)度函數(shù)值。具體步驟如下。

①初始節(jié)拍值為:

令當(dāng)前的節(jié)拍C=C0,工作站序號(hào)j=1。

②根據(jù)操作序列分配順序,將操作i分配給工作站j。如果分配的工作站的裝配時(shí)間大于節(jié)拍C,則工作站編號(hào)j←j+1 。

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

④如果工作站的數(shù)量大于m,則令C←C+1,轉(zhuǎn)步驟②。

⑤計(jì)算節(jié)拍、能耗以及機(jī)器人成本。

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

4 實(shí)例應(yīng)用及分析

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

表2 節(jié)拍優(yōu)化結(jié)果Tab.2 Beat optimization results

表3 能耗優(yōu)化結(jié)果Tab.3 Energy consumption optimization results

表4 成本優(yōu)化結(jié)果Tab.4 Cost optimization results

圖4 節(jié)拍優(yōu)化曲線Fig.4 Beat optimization curve

圖5 能耗優(yōu)化曲線Fig.5 Energy consumption optimization curve

圖6 成本優(yōu)化曲線Fig.6 Cost optimization curve

由求解所得各目標(biāo)函數(shù)的解和優(yōu)化結(jié)果可知,通過灰狼算法結(jié)合萊維飛行進(jìn)行求解之后,節(jié)拍優(yōu)化了39 s,能耗優(yōu)化了106 kW·h,機(jī)器人投入成本優(yōu)化了39 萬元。經(jīng)過優(yōu)化,在縮短節(jié)拍、提高生產(chǎn)效率的同時(shí),也減少了能耗投入和建線時(shí)的機(jī)器人成本投入,一定程度地降低了企業(yè)的生產(chǎn)成本。

5 結(jié)論

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