蟻獅算法在第二類多目標(biāo)裝配線平衡問題中的應(yīng)用*

陳 帥，晁永生，江 韓

(新疆大學(xué)機(jī)械工程學(xué)院，烏魯木齊 830047)

0 引言

裝配線平衡研究主要被分為兩大類：一種是給定生產(chǎn)線節(jié)拍，以最小工作站數(shù)目為優(yōu)化目標(biāo)的第一類裝配線平衡問題[1]；另一種是給定裝配線工作站數(shù)，以最小生產(chǎn)節(jié)拍為優(yōu)化目標(biāo)的第二類裝配線平衡問題[2]。第一類裝配線平衡問題只產(chǎn)生在設(shè)計(jì)一條新的裝配線時，而每當(dāng)現(xiàn)有的裝配線做出調(diào)整需要重新達(dá)到平衡時，第二類裝配線平衡問題就會隨之產(chǎn)生[3]，而且隨著企業(yè)裝配環(huán)境的復(fù)雜化，往往需要對第二類裝配線平衡問題的多個目標(biāo)進(jìn)行優(yōu)化。

在實(shí)際裝配生產(chǎn)中、每個任務(wù)完成裝配所需的零部件存儲在對應(yīng)工位的零部件放置區(qū)，由于不同任務(wù)所需的零部件尺寸范圍跨度大，造成不同工位的占地面積具有很大差異，不便于物流運(yùn)輸與人員行走，導(dǎo)致物流運(yùn)輸效率低下增加不必要的時間成本，因此應(yīng)考慮任務(wù)所需的占地面積，合理分配任務(wù)到工位上使得每個工位的占地面積相對均勻。同時在重新規(guī)劃裝配線時，某些工位會增加新的任務(wù)因此工人需要學(xué)習(xí)如何裝配新的任務(wù)，而不同的任務(wù)，裝配難度是不同的，因此對應(yīng)所需要花費(fèi)的學(xué)習(xí)成本也不同，所以當(dāng)工位增加新的任務(wù)時會帶來學(xué)習(xí)成本的增加，為了降低企業(yè)重新調(diào)整裝配線的總成本，在優(yōu)化其他目標(biāo)的同時應(yīng)該盡可能最小化學(xué)習(xí)成本。因此面臨特定的裝配環(huán)境時需要考慮對多個目標(biāo)同時進(jìn)行優(yōu)化以保證求解結(jié)果滿足實(shí)際的生產(chǎn)需求。

蟻獅算法[4](Ant Lion Algorithm,ALA)是一種新型智能群算法，具有尋優(yōu)效率高，全局搜索尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn)，目前已在多個領(lǐng)域[5-7]內(nèi)得到了應(yīng)用，并且取得了不錯的效果，本文在單目標(biāo)蟻獅算法的基礎(chǔ)上提出一種多目標(biāo)蟻獅算法(Multi-objective Ant Lion Algorithm,MOALA)，運(yùn)用于第二類多目標(biāo)裝配線平衡問題的求解。通過對實(shí)例算例求解并與改進(jìn)多目標(biāo)粒子群算法對比分析，驗(yàn)證該算法的有效性和優(yōu)越性。

1 第二類多目標(biāo)裝配線平衡問題的數(shù)學(xué)模型

1.1 問題描述

為了簡化問題,只考慮任務(wù)分配過程中所需的零部件占地面積不同，合理分配任務(wù)到工位上使得各工位的占地面積相對均衡，同時最小化工位的生產(chǎn)節(jié)拍以提高生產(chǎn)效率，并且盡可能降低調(diào)整后的裝配分配方案帶來的學(xué)習(xí)成本。

某企業(yè)實(shí)例裝配作業(yè)任務(wù)的任務(wù)信息和調(diào)整前后的裝配方案如表1所示，給定的工位數(shù)目為3。調(diào)整前后裝配方案的節(jié)拍分別為17，15，每個工位所需占地面積分別為[48.2,46.7,12.8]，[37.2,27.3,43.2]，可知調(diào)整后的裝配方案較調(diào)整前在節(jié)拍和占地面積均衡性上都要好，但是由于工位2和工位3增加了新的任務(wù)，所以也帶來了學(xué)習(xí)成本，新增加的任務(wù)為任務(wù)6與任務(wù)3,4，所以學(xué)習(xí)成本的累積和是17。

表1 任務(wù)信息與調(diào)整前后的裝配方案

本文以最小化生產(chǎn)節(jié)拍、學(xué)習(xí)成本，占地面積均衡指標(biāo)為目標(biāo)建立第二類多目標(biāo)裝配線平衡問題的優(yōu)化模型，假設(shè)：①每個任務(wù)都有穩(wěn)定的任務(wù)時間且學(xué)習(xí)成本和所需的占地面積都是固定的；②必須將所有的任務(wù)都分配到工位中；③工位個數(shù)是確定的；④任務(wù)的分配不能違反優(yōu)先關(guān)系約束。

1.2 數(shù)學(xué)模型

變量及其含義定義如下：n為任務(wù)數(shù)；m為工位數(shù)；I為任務(wù)矩陣，I=(1,2,…,n)為行向量，由所有任務(wù)序號構(gòu)成；t(i)為任務(wù)i的操作時間，Cost(i)為任務(wù)i的學(xué)習(xí)成本，Area(i)為任務(wù)i所需要的占地面積，i為I內(nèi)任務(wù)；Pdn×n為優(yōu)先關(guān)系矩陣，如果任務(wù)i1是i2的優(yōu)先任務(wù)，Pd(i2,i1)=1，否則為0；J為工位矩陣，J=(1,2,…,m)由所有I中的元素構(gòu)成；j為J內(nèi)元素；ST(j)為工位j的裝配時間；Sq(j)表示工位j所分配到的任務(wù)集合。

CT為裝配線節(jié)拍：

CT=max{ST(1),ST(2),…,ST(m)}

(1)

CtTheory為裝配線節(jié)拍的理論值：

(2)

WArea(j)為工位j的占地面積：

WArea(j)=∑(Area(Sq(j)))

(3)

其中，MArea為所有工位當(dāng)中最大的占地面積：

MArea=max(WArea(1),…,WArea(m))

(4)

(5)

決策變量：

xij，0-1變量，當(dāng)任務(wù)i被分配到第j個工位時，xij=1，否則xij=0。

目標(biāo)函數(shù)：

Z={Z1,Z2,Z3}

(6)

Z1=minCT

(7)

(8)

(9)

約束條件：

(10)

ST(j)≤CT

(11)

(12)

模型說明：式(6)表示同時優(yōu)化3個目標(biāo)值；其中優(yōu)化目標(biāo)Z1如式(7)所示最小化工位的生產(chǎn)節(jié)拍；優(yōu)化目標(biāo)Z2如式(8)所示，最小化由每個工位新增加的操作任務(wù)帶來的學(xué)習(xí)成本；優(yōu)化目標(biāo)Z3如式(9)所示最小化工位占地面積均衡指標(biāo)使得空間面積得到合理化的應(yīng)用。式(10)表示每個任務(wù)只能與一個工作站相匹配，不能進(jìn)行重復(fù)分配；式(11)表示生產(chǎn)節(jié)拍約束，每個工位的操作時間都應(yīng)小于或等于生產(chǎn)節(jié)拍；式(12)表示優(yōu)先關(guān)系約束。其中式(10)～式(12)對應(yīng)的3種約束被稱為裝配線平衡的基本約束。

2 求解第二類多目標(biāo)裝配線平衡問題的蟻獅

算法

求解第二類多目標(biāo)裝配線平衡優(yōu)化問題，難點(diǎn)在于確保最優(yōu)解集的均勻性和多樣性，本文在單目標(biāo)蟻獅算法的基礎(chǔ)上提出一種多目標(biāo)蟻獅算法用于求解該問題，通過引入解碼和基于牛頓二分法的解碼裝配任務(wù)分配規(guī)則，使得每個個體均滿足裝配線平衡的基本約束；引入Pareto支配規(guī)則，確保得到的精英蟻獅群為最優(yōu)解集，為了保證最優(yōu)解集的均勻性和多樣性，去除單目標(biāo)蟻獅算法中的蟻獅捕食規(guī)則而是將螞蟻和蟻獅種群合并成新種群并且引入基于非支配排序和擁擠度的精英保留策略更新蟻獅種群的位置。多目標(biāo)蟻獅算法的流程如圖1所示。

圖1 多目標(biāo)蟻獅算法流程圖

2.1 解碼和基于牛頓二分法的解碼裝配任務(wù)分配

假設(shè)個體的位置為向量PosList，輸出的任務(wù)序列矩陣為TaskList，對于PosList的解碼采用文獻(xiàn)[8]中基于位置優(yōu)先權(quán)重的解碼方法，通過結(jié)合位置向量和優(yōu)先關(guān)系矩陣將個體的位置解碼為對應(yīng)的任務(wù)序列矩陣。為求解任務(wù)序列矩陣TaskList的最優(yōu)分配節(jié)拍，利用牛頓二分法的思想不斷將節(jié)拍搜索區(qū)間一分為二從而快速將任務(wù)分配到工位上，得出最優(yōu)分配節(jié)拍CT和任務(wù)分配集合Sq，解碼裝配任務(wù)分配流程如圖2所示。

圖2 解碼裝配任務(wù)分配流程圖

2.2 Pareto支配規(guī)則和精英保留策略

在多目標(biāo)優(yōu)化問題中，往往存在多個目標(biāo)之間構(gòu)成相互沖突的關(guān)系，通常不可能找到一個最優(yōu)解使得每個目標(biāo)函數(shù)都達(dá)到最優(yōu)，因此解的優(yōu)劣性采用文獻(xiàn)[9]中的Pareto支配規(guī)則來衡量,對于無法執(zhí)行任務(wù)分配的個體直接設(shè)置為最劣個體，由Pareto支配規(guī)則選擇蟻獅種群中的最優(yōu)解集為精英蟻獅群。采用文獻(xiàn)[10]中基于非支配排序和擁擠度的精英保留策略選擇出新的蟻獅群，種群數(shù)量均為P的螞蟻種群Pt和蟻獅種群Qt合并成種群數(shù)量為2P的Rt，先對Rt中的個體非支配排序分層，分層完畢之后，對每一層的個體計(jì)算擁擠度，最后根據(jù)每個個體的優(yōu)劣程度從種群Rt中選出前P個個體形成新的蟻獅種群。

3 實(shí)例驗(yàn)證

為驗(yàn)證算法的性能，以某企業(yè)的實(shí)際問題為例優(yōu)化求解，給定工位數(shù)目m=3，任務(wù)信息如表1所示。并與改進(jìn)的多目標(biāo)粒子群算法[11](Multi-objective Improved Particle Swarm Algorithm,MIPSA)對比分析，使用以下指標(biāo)對算法進(jìn)行綜合衡量：

(1)非劣解數(shù)目：表示算法搜索Pareto最優(yōu)解的能力。

(2)世代距離[12]：表示所求的Pareto最優(yōu)解距真實(shí)Pareto最優(yōu)解的運(yùn)近程度。

(3)間隔[13]：表示所求的Pareto最優(yōu)解中各個解的均布程度。

(4)運(yùn)行時間：表示算法運(yùn)行一次所需的時間。

由于問題的可行解空間規(guī)模巨大，難以得到真實(shí)的最優(yōu)解集，因此取各算法求出的最優(yōu)解集作為所求問題的真實(shí)最優(yōu)解集。經(jīng)過算法的靈敏性實(shí)驗(yàn)，設(shè)置算法相關(guān)參數(shù)：種群數(shù)目P=300，最大迭代次數(shù)tmax=300；初始搜索步長dt=10，節(jié)拍搜索精度CTaccuracy=0.01。為消除隨機(jī)因素的影響，各算法取100次的平均結(jié)果對4個指標(biāo)對比說明。

由表2可知多目蟻獅算法在4個指標(biāo)上均比改進(jìn)多目標(biāo)粒子群算法更優(yōu)，表明在單目標(biāo)蟻獅算法中去除蟻獅捕食規(guī)則的基礎(chǔ)上加入Pareto支配規(guī)則與基于非支配排序和擁擠度的精英保留策略之后，多目標(biāo)蟻獅算法不僅在搜索Pareto最優(yōu)解的能力上相比于改進(jìn)多目標(biāo)粒子群算法更強(qiáng)而且所求得的最優(yōu)解集不僅更靠近于真實(shí)的最優(yōu)解集而且在均布程度上也比其他兩種算法更優(yōu)，在運(yùn)行時間上由于多目標(biāo)蟻獅算法的迭代更新機(jī)制比改進(jìn)多目標(biāo)粒子群算法的復(fù)雜度更低，所以用更短的時間即可求出更優(yōu)的Pareto解集。

表2 4種指標(biāo)比較

在表3中列出了100次求解結(jié)果中兩種算法求解出的各目標(biāo)函數(shù)最小值，并且列出了多目標(biāo)蟻獅算法中3個目標(biāo)函數(shù)最小值的求解方案進(jìn)行說明，可知多目標(biāo)蟻獅算法搜索出的3個目標(biāo)函數(shù)最小值均比改進(jìn)多目標(biāo)粒子群算法搜索出的值都要小，再次表明多目標(biāo)蟻獅算法搜索出的最優(yōu)解集更接近于真實(shí)的最優(yōu)解集。結(jié)合表2和表3可知多目標(biāo)蟻獅算法能在更短時間內(nèi)為企業(yè)提供更多且更優(yōu)的裝配方案。

表3 求解結(jié)果

4 結(jié)論

通過對實(shí)際問題的求解，并與改進(jìn)多目標(biāo)粒子群算法對比分析，表明多目標(biāo)蟻獅算法在搜索Pareto最優(yōu)解的能力上相比于改進(jìn)多目標(biāo)粒子群算法更強(qiáng)；所求得的最優(yōu)解集不僅更靠近于真實(shí)的最優(yōu)解集而且在均布程度上也比改進(jìn)多目標(biāo)粒子群算法更優(yōu)，在運(yùn)行時間上也更短。從而說明了多目標(biāo)蟻獅算法在求解第二類多目標(biāo)裝配線平衡優(yōu)化問題的適用性和優(yōu)越性。