基于改進(jìn)鯨魚優(yōu)化算法的裝配線再平衡方法*

郭 宏,閆炳南,羅 雷,冒 源,原 超,徐 壯

(1.太原科技大學(xué)機械工程學(xué)院,太原 030024;2.山西平陽重工機械有限責(zé)任公司,侯馬 043003)

0 引言

裝配線平衡問題(assembly line balancing problem,ALBP)主要是研究在滿足各類約束的前提下,將各裝配任務(wù)分配到工作站,來實現(xiàn)減少成本和提升效率的目的[1]。

當(dāng)前,已有許多學(xué)者對裝配線平衡問題進(jìn)行了較深入地研究。ALBUS等[2]采用一種基于混合整數(shù)規(guī)劃的線性優(yōu)化方法來解決裝配線的動態(tài)資源分配問題。KATIRAEE等[3]提出了一個雙目標(biāo)線性規(guī)劃模型來解決裝配線平衡問題。黃輝等[4]提出一種混合算法來解決多目標(biāo)雙邊裝配線平衡問題。趙聯(lián)鵬等[5]提出了一種新的搜索算法去求解裝配線平衡問題,以提高裝配線效率。

現(xiàn)有的大多數(shù)模型都建立在確定需求的情況下,雖然一些模型考慮了需求的變化,但很少考慮再平衡成本的問題。李金霖等[6]使用多能工應(yīng)對需求變化的混裝線平衡問題,以最小化人工成本并滿足不同情境的需求。CHICA等[7]提出了一個用于裝配線平衡的多目標(biāo)模型,并使用自適應(yīng)進(jìn)化算法提高效率。張于賢等[8]為了解決算法的最優(yōu)解存在著達(dá)不到裝配線平衡最優(yōu)準(zhǔn)則且無法對瓶頸工序進(jìn)行操作分析的情形,提出了算法和IE技術(shù)兩階段組合求解法,求出了一個能滿足生產(chǎn)需要的有效可行解。

針對不確定需求下的再平衡問題,本文采用只改變工作站數(shù)量以及重新規(guī)劃邊界的方式來建立裝配線模型,并提出了一種改進(jìn)多目標(biāo)鯨魚的優(yōu)化算法來求解該模型。最后,與其他多目標(biāo)算法進(jìn)行對比驗證了此算法的可行性。

1 問題描述與數(shù)學(xué)建模

1.1 可調(diào)整產(chǎn)能裝配線平衡問題描述

當(dāng)訂單需求改變時,裝配線的生產(chǎn)周期也需要隨之變化。此時,有必要重新平衡裝配線。但為了減少成本,設(shè)施布局應(yīng)避免改動。在不改變裝配線上工位設(shè)備順序的前提下,可以通過增加或減少工作臺的數(shù)量以及重新規(guī)劃工作臺的邊界來實現(xiàn)不同的任務(wù)分配。如圖1所示,分為兩種情境,生產(chǎn)周期C=30和生產(chǎn)周期C=50,已知每個設(shè)備所分配任務(wù)時間,要求每個工作站所有設(shè)備任務(wù)時間之和不大于周期時間。當(dāng)生產(chǎn)周期較小時(圖中舉例為C=30),設(shè)備1和2分配給工作站1 的工人,設(shè)備3,4,5分配給工作站2的工人;當(dāng)需求減少時,生產(chǎn)周期增加(圖中示例為C=50),工作站1的工人操作設(shè)備1和2仍有余力,此時將設(shè)備3也交給此工人操作。

本文所述的裝配線平衡問題可描述為:在已知兩個或多個不同需求情境的條件下,如何完成任務(wù)分配,以最小化多個需求下平均工作站數(shù)量和平均時間均衡指數(shù)。

為有效描述該問題,做以下基本假設(shè):①裝配圖已給定且其中不存在回路;②為了減少成本,同一個任務(wù)只能分配給同一個設(shè)備;③每個任務(wù)都對應(yīng)一個設(shè)備;④可調(diào)整產(chǎn)能裝配線全部使用多能工進(jìn)行裝配;⑤普通工人的每天工作時間為T小時,多能工每天可用裝配時間設(shè)為T/2小時,多能工每天的工資水平是普通工人的2倍。

1.2 符號說明

N為裝配順序圖中任務(wù)的數(shù)量,N*為所有任務(wù)所組成的集合,S*為所有需求情境組成的集合,Ps為需求情境s發(fā)生的比例,Ds為情境s下每天的需求數(shù)量(單位:件/天),T為1個工人1天可使用的工作時間,Cs為需求情境s的生產(chǎn)節(jié)拍,Cs=T/Ds;Tsj為需求情境s下第j個工作站的總體任務(wù)時間,Lsj為情境s下第j個工作站的時間均衡指數(shù),Lsj=(Cs-Tsj)/Cs;H*為已使用設(shè)備所組成的集合,xih為任務(wù)i被分到第h個設(shè)備,則為1,否則為0;yhjs為設(shè)備h在情境s被分到第j個工作臺,則為1,否則為0。

1.3 建立數(shù)學(xué)模型

建立變產(chǎn)能裝配線數(shù)學(xué)模型,其目標(biāo)函數(shù)為:

minF={f1,f2}

(1)

式中:

(2)

(3)

約束條件如下:

(4)

(5)

(6)

(7)

(8)

(9)

xih∈(0,1),?i∈N*,?h∈H*

(10)

yhjs∈(0,1),?h∈H*,?s∈S*

(11)

式(1)～式(3)表示最小化每個場景中使用的工作站數(shù)量的平均值,以及每個場景下每個工作站的時間平衡指數(shù)。式(4)表示每個任務(wù)都對應(yīng)一個設(shè)備。式(5)表示每個站點上都只有一個設(shè)備。式(6)表示任務(wù)優(yōu)先順序約束,每個任務(wù)在生產(chǎn)線上的工位必須在它所有前置任務(wù)完成之后。式(7)表示在給定情境下每個位置只能分配到一個工作站,不同的工作站之間不能共享同一個設(shè)備。式8)表示每個工作站的所包含的區(qū)域必須是連續(xù)。式(9)表示生產(chǎn)節(jié)拍約束,這意味著必須完成每種情況下所需的任務(wù)。式(10)和式(11)分別表示xij和yhjs的值范圍。

2 算法構(gòu)建

本文研究的裝配線平衡問題屬于NP難問題,而群智能算法很適合解決這一問題。鯨魚優(yōu)化算法(WOA)是一種群智能算法,具有結(jié)構(gòu)簡單、計算方便的優(yōu)點,在工程領(lǐng)域已廣泛應(yīng)用[9]。

為更好地求解變產(chǎn)能裝配線模型,本文提出了一種改進(jìn)多目標(biāo)鯨魚優(yōu)化算法。首先,使用混沌映射初始化種群;其次,在位置更新時對搜索步長進(jìn)行動態(tài)調(diào)整來提高算法的效率,并使用新的頭鯨選擇方式來避免局部最優(yōu);最后,采用改進(jìn)擁擠距離來更新外部檔案以得到最優(yōu)解集。

2.1 鯨魚優(yōu)化算法(WOA)

鯨魚優(yōu)化算法(WOA)是一種新的元啟發(fā)式優(yōu)化算法,WOA的主要靈感來自座頭鯨的特殊捕食行為。鯨魚在獵物周圍以螺旋形移動,在覓食時使用縮小的圓圈向獵物移動,這種行為被稱為泡泡網(wǎng)覓食。

2.1.1 包圍捕食階段

WOA通過在螺旋模型和收縮包圍獵物之間進(jìn)行50%的選擇概率來模擬這種狩獵機制,以生成當(dāng)前鯨魚的新位置。通常,包圍機制的數(shù)學(xué)表達(dá)式為:

D=|C·X*(t)-X(t)|

(12)

X(t+1)=X*(t)-A·D

(13)

A=2a×r-a

(14)

C=2×r

(15)

(16)

式中:X為位置矢量,X*(t)為一個向量,包含迄今為止找到的最佳位置;t為當(dāng)前迭代次數(shù),||為絕對值運算,·為逐個元素相乘,A和C為系數(shù)變量,a為一個隨著迭代從2不斷線性減小到0的參數(shù),r為[0,1]范圍內(nèi)隨機生成的數(shù)。

2.1.2 螺旋捕食階段

WOA試圖用螺旋模型來模擬鯨魚的螺旋形運動,以得出獵物和鯨魚之間的位置。螺旋形狀的數(shù)學(xué)表達(dá)式為:

D=|X*(t)-X(t)|

(17)

X(t+1)=D*·ebl·cos(2πl(wèi))+X*(t)

(18)

式中:b為一個常數(shù),用來描述對數(shù)螺旋運動;l為一個1和-1范圍內(nèi)的隨機數(shù)。

2.1.3 隨機搜索階段

為了使WOA能夠探索優(yōu)化問題搜索空間內(nèi)的大部分區(qū)域,它從當(dāng)前種群中隨機選擇一個個體,將當(dāng)前的鯨魚移向它。如果|A|>1,則當(dāng)前鯨魚將移向從種群中隨機選擇的鯨魚。該階段的數(shù)學(xué)公式為:

X(t+1)=X*(t)-A·D

(19)

D=|C·Xr(t)-X(t)|

(20)

式中:Xr(t)為從當(dāng)前種群中隨機選擇的個體。

2.2 頭鯨選擇方式

在WOA的進(jìn)化過程中,頭鯨在逃離局部最優(yōu)解方面發(fā)揮著重要作用。所以本文通過提出一種成對競爭機制來選擇更好的頭鯨,以其來指導(dǎo)鯨魚種群的更新。

在成對競爭機制中,鯨魚個體通過競爭機制更新,而不是使用全局和單個最優(yōu)個體,從而大大提高了種群的多樣性,避免過早收斂。具體來說,在成對競爭機制中,從當(dāng)前種群中隨機配對選擇個體進(jìn)行競爭,并通過向優(yōu)勝者學(xué)習(xí)來更新競爭中的失敗者,而優(yōu)勝者則直接傳遞給下一代種群。

假設(shè)種群P(t)中有N個個體,每個個體都有一個n維位置Xi(t)=(xi,1(t),xi,2(t),…,xi,n(t))和n維速度向量Vi(t)=(vi,1(t),vi,2(t),…,vi,n(t))。在第k輪比賽中,勝利者和失敗者的位置和速度分別表示為Xw,k(t)、Xl,k(t)、Vw,k(t)和Vl,k(t),其中k=1,2,…,N/2。在第k輪比賽后,失敗者的速度將使用以下策略進(jìn)行更新:

(21)

而失敗者的位置可以根據(jù)新的速度更新:

Xl,k(t+1)=Xl,k(t)+Vl,k(t+1)

(22)

在創(chuàng)建精英種群之后,將在其中的鯨魚個體之間進(jìn)行成對競爭,獲勝者將被用來指導(dǎo)當(dāng)前種群中鯨魚個體的移動方向。對于每一次競爭,給定要更新的種群中的一個鯨魚個體p,從精英種群中隨機選擇兩個精英鯨魚個體a和b。分別計算a、b和p之間的角度,角度較小的精英個體獲勝,這樣鯨魚個體p將從更接近其收斂方向的精英個體學(xué)習(xí)。具體示例如圖2所示。

圖2 成對競爭機制示例

圖2中Xi是要更新的解決方案;X1和X2是從精英列表中隨機選擇的精英個體;θ1是X1和Xi之間的角度;θ2是X2和Xi之間的角度。因為θ2<θ1;X2是獲勝者,被選為領(lǐng)導(dǎo)者。

2.3 外部檔案更新策略

外部歸檔是多目標(biāo)鯨魚算法(MOWOA)中常用的模塊,在更新外部檔案的策略方面,有許多選擇,如網(wǎng)格選擇、非支配排序、高效非支配排序(ENS)和擁擠距離法等。

由于擁擠距離法可以更好地維持種群中個體的多樣性,所以本文使用擁擠距離法更新外部檔案。然而,使用傳統(tǒng)的擁擠距離來反映密度在某種程度上是有缺陷的,所以本文采用一種新的方法來計算距離。其具體方法如圖3所示。

圖3 擁擠距離

圖3中有3種解決方案,用x1,x2,x3表示;目標(biāo)數(shù)為2。解x2的傳統(tǒng)擁擠距離為CD(x2)=R1+R2+S1+S2。事實上,只要x2位于邊界框中,其中x1和x3是對角頂點,CD(x2)的值就不會改變。為了解決這個問題,本文使用一種改進(jìn)的擁擠距離,其表達(dá)式定義為[10]:

(23)

式中:M為目標(biāo)數(shù),Si和Ri為圖3所示的距離。

2.4 多策略改進(jìn)多目標(biāo)鯨魚優(yōu)化算法

原始WOA算法通常使用隨機生成初始種群的方法。然而根據(jù)現(xiàn)有研究,初始種群將直接影響算法的計算效率。因為混沌序列有較強的隨機性以及整體穩(wěn)定的特性,所以本文使用混沌序列初始化。其中,Tent映射公式為:

(24)

式中:X(t)∈[0,1]。

在WOA中,因子a是一個距離控制參數(shù),從2線性減少到0。因子a隨固定步長變化,因此當(dāng)?shù)螖?shù)較大時,大多數(shù)迭代將在找到最佳解之前結(jié)束,否則將消耗大量迭代次數(shù)而沒有任何進(jìn)展。所以,本文設(shè)計了新的動態(tài)控制系數(shù),使其與迭代次數(shù)成比例減少。其數(shù)學(xué)表達(dá)式如下:

(25)

(26)

式中:r是一個介于0和1之間的隨機數(shù)。在前面的方程中,我們試圖控制距離控制參數(shù)a以值2開始,該值隨著迭代逐漸減小,并乘以0和1之間的隨機數(shù)r,直到達(dá)到標(biāo)準(zhǔn)參數(shù)無法達(dá)到的區(qū)域。

步驟1:初始化。首先初始化外部檔案,設(shè)置初始容量為C,并在滿足優(yōu)先關(guān)系前提下使用式(24)生成N個初始個體X1,X2,…,XN;

步驟2:確定非支配解集。對每一個鯨魚個體位置Pi計算適應(yīng)度函數(shù),并對其進(jìn)行Pareto非支配排序,得到非支配解集;

步驟3:更新外部檔案。使用式(23)計算前C個個體,并將其加入外部檔案;

步驟4:頭鯨選擇。使用競爭機制進(jìn)行頭鯨選擇, 首先,根據(jù)擁擠距離排序從外部檔案中選擇出前10個個體并組成集合E,從E中隨機選擇兩個個體X1和X2;然后,從當(dāng)前種群中取出一個個體Xi,計算X1和Xi之間的角度θ1以及X2和Xi之間的角度θ2,如果θ1<θ2,X1為領(lǐng)導(dǎo)者X*,否則,X2為領(lǐng)導(dǎo)者X*;之后,將X*代入到式(13)或式(18)或式(19)中得到X(t+1),并將其添加到集合X′,最后,判斷集合X是否為空,為空則重新從E中隨機選擇兩個個體循環(huán)執(zhí)行,否則返回新種群X′;

步驟5:鯨魚位置更新。根據(jù)式(25)和式(26)更新參數(shù)a和C,并相應(yīng)地更新算法中A、l和r等相關(guān)參數(shù)。然后根據(jù)p和|A|的大小來選擇相應(yīng)的更新方案,并使用步驟4選出的頭鯨來指導(dǎo)更新。

MIMOWOA算法流程圖如圖4所示。

圖4 MIMOWOA算法流程圖

3 仿真實驗分析

3.1 參數(shù)分析

使用python實現(xiàn)上述算法程序,并在CPU為CMD 6-Core,內(nèi)存為8 GB的PC上進(jìn)行。實驗參數(shù)設(shè)定為種群規(guī)模30,迭代次數(shù)1000。實驗選用SALBP-1標(biāo)準(zhǔn)算例庫中的9個不同規(guī)模的數(shù)據(jù)進(jìn)行實驗。

3.2 實驗對比

為了驗證此算法的優(yōu)越性,將它與原有的多目標(biāo)鯨魚優(yōu)化算法進(jìn)行比較,求解結(jié)果如表1所示。

表1 不同問題規(guī)模下的結(jié)果對比

表1中分為小,中,大3種不同任務(wù)數(shù)量的任務(wù),給定相應(yīng)的周期時間,對比MOWOA和MIMOWOA 兩種算法對同一問題的計算結(jié)果。從表中可以明顯看出,MIMOWOA算法得出的站點數(shù)量和均衡指數(shù)都低于MOWOA算法。如圖5所示,為了更加直觀地體現(xiàn)出優(yōu)越性,對比任務(wù)數(shù)量為101的帕累托前沿。其中,MIMOWOA在兩個目標(biāo)函數(shù)方向都能實現(xiàn)帕累托最優(yōu)。這主要由于MIMOWOA采用動態(tài)距離控制系數(shù)以及成對競爭機制后,在一定程度上提高了裝配線的均衡性。

圖5 任務(wù)數(shù)量為101的帕累托前沿

為了進(jìn)一步驗證算法的有效性,將改進(jìn)算法與其他多目標(biāo)優(yōu)化算法進(jìn)行比較。其中將算法性能的評價指標(biāo)設(shè)定為帕累托解的個數(shù)(NF)、解的均勻性(ES)和非支配解的最優(yōu)度(DPS)[11]。各項評價指標(biāo)計算為:

(1)非支配解的數(shù)量:

NF=|Np|

(27)

式中:NF為算法得到的帕累托解的數(shù)量,NF值越大,算法越優(yōu)。

(2)非支配解最優(yōu)度:

(28)

(3)解的均勻性指標(biāo):

(29)

(30)

式中:Di為xi與其他相鄰解的距離。ES越小,說明解越分散。

實驗包含3種不同規(guī)模的任務(wù)數(shù)量,每個任務(wù)重復(fù)15次,選取平均值作為最終結(jié)果如表2所示。MW為改進(jìn)多目標(biāo)鯨魚算法,NS為遺傳算法,MP為粒子群算法,加粗字體表示不同問題規(guī)模下各項評價指標(biāo)的最優(yōu)值。

表2 3種算法的數(shù)值結(jié)果對比

分析表2可得:

(1)分析評價性能NF的值可知,MIMOWOA得到的帕累托解的數(shù)量明顯更多。

(2)分析評價性能DPS的值可知,MIMOWOA得到的DPS值較其余算法更大一些,表明MIMOWOA的全局搜索性更好。

(3)分析評價性能ES的值可知,MIMOWOA得出的解的分布與其他算法相比較均勻。這是因為MIMWOA采用了擁擠距離排序的外部檔案更新策略,使解的分布更均勻。

總而言之,MIMOWOA算法在解的數(shù)量或者質(zhì)量方面都明顯優(yōu)于其余兩個算法,這也驗證說明了其求解ALBP問題時的可行性。

4 結(jié)束語

本文研究了可調(diào)整產(chǎn)能裝配線平衡問題,采用只改變工作站數(shù)量以及重新規(guī)劃邊界的方式來建立裝配線模型,降低了裝配線再平衡成本。并針對該模型構(gòu)建了一種改進(jìn)多目標(biāo)鯨魚優(yōu)化算法,在原始鯨魚算法中使用混沌映射初始化種群,并在鯨魚搜索過程中引入動態(tài)距離控制系數(shù)和成對競爭機制來提高算法的收斂速度。最后用實驗驗證了所提出的算法在解決可調(diào)整產(chǎn)能裝配線平衡問題上的可行性和有效性。

當(dāng)然本文只考慮了在兩種周期下進(jìn)行轉(zhuǎn)換的裝配線方案,后續(xù)可以進(jìn)一步開展多周期轉(zhuǎn)換的研究。