基于改進的NSGA-II的多目標魯棒性設備布局研究*

張萍萍，鄭飂默，王詩宇

(1.中國科學院大學，北京 100039；2.中國科學院沈陽計算技術研究所 高檔數(shù)控國家工程研究中心， 沈陽 110168；3.沈陽高精數(shù)控技術有限公司，沈陽 110168)

0 引言

企業(yè)在構建制造系統(tǒng)初期階段，設備布局是首要解決的問題之一。研究表明，合理的設備布局至少可以節(jié)約10%～30%的物料運輸費用[1]。在動態(tài)多變的市場環(huán)境下，靜態(tài)布局(SFL)[2-3]方法已經(jīng)無法滿足生產(chǎn)需求。如果采用中斷生產(chǎn)重新進行設備布局來滿足生產(chǎn)需求，會對企業(yè)造成較大的損失。如何使布局在動態(tài)多變的需求下，表現(xiàn)出良好的柔性和魯棒性，是企業(yè)能否持續(xù)發(fā)展的關鍵之一。

用戶需求的動態(tài)性,導致傳統(tǒng)的靜態(tài)布局無法滿足在連續(xù)的生產(chǎn)過程中后期的生產(chǎn)計劃；同時又因為制造系統(tǒng)的復雜性，不可能在設備布局無法滿足生產(chǎn)計劃時，調(diào)整設備位置或重新布局。因此在制造系統(tǒng)設計初期提供一種布局方案，這種布局方案在動態(tài)的需求下，也能很好的滿足生產(chǎn)任務，“不變應萬變”，即魯棒性設備布局。

1987年，Meir Rosenblatt等[4]首次將魯棒性概念引入到制造業(yè)設備布局領域，使設備布局對動態(tài)的生產(chǎn)任務表現(xiàn)出良好的性能。魯棒性布局是指存在一種布局方案能滿足各階段不同的生產(chǎn)需求，對于其中某個特定階段，它不一定是最優(yōu)方案，但對整個生產(chǎn)周期卻是最優(yōu)的布局方案。Ghorbanali Moslemipour等[5]針對魯棒性布局問題進行了綜述，詳細總結了以往文獻中所采用的優(yōu)化模型及求解算法。劉瓊等[6]則針對設施面積不等的作業(yè)車間作為研究對象，以最小化物流搬運費用和面積費用為優(yōu)化目標，建立魯棒性布局模型，并提出一種改進的蛙跳算法對其進行求解。李愛平等[7]考慮到物流搬運系統(tǒng)的設計對魯棒性布局的影響，提出設備魯棒性布局方案及物料搬運系統(tǒng)協(xié)同優(yōu)化方法。目前魯棒性布局的研究中采用的優(yōu)化算法大都是采用加權系數(shù)將多目標單一化，但是由于加權系數(shù)的值對結果的影響較大，因此采用基于Pareto最優(yōu)前沿的方法在多目標空間內(nèi)直接求解，不再需要將多個目標進行單一化處理。在基于Pareto尋優(yōu)的多目標優(yōu)化算法[8]中，DEB在2002年提出的帶精英策略的非支配排序遺傳算法(Non-dominated Genetic Algorithm II,NSGA-II)是一種有效的算法，已被國內(nèi)外廣泛用來求解多目標優(yōu)化問題。

根據(jù)上述研究現(xiàn)狀，針對魯棒性設備布局問題的多目標多約束的特點，以物料搬運費用、非物流關系和面積費用為優(yōu)化目標建立布局模型，并利用改過的NSGA-II算法對其求得Pareto解集，用戶根據(jù)實際情況擇優(yōu)選取布局方案。最后，通過實例驗證模型和算法的有效性。

1 數(shù)學模型

1.1 問題描述

魯棒性布局問題是連續(xù)P個生產(chǎn)計劃期最穩(wěn)定的布局方案。根據(jù)產(chǎn)品的工藝路線和各個子計劃期設備間的物流矩陣等約束條件的變化，分析整個生產(chǎn)周期，引入魯棒性指標，最后合理確定車間設備的具體位置。

以已知的n臺設備為研究對象，以最小化車間物料搬運費用、非物流關系和面積費用為優(yōu)化目標，建立多目標魯棒性布局模型。

假設條件：①設備均為矩形結構，且長寬已知；② P個階段的生產(chǎn)計劃已定；③各產(chǎn)品的工藝路線已定；④同行設備的中心點位于同一條水平線上；⑤設備間的物料搬運只能走水平和垂直直線。

1.2 優(yōu)化目標

以物流費用，非物流關系及面積費用作為優(yōu)化目標，具體分析如下：

(1) 物流搬運費用最小化。其中：i和j表示車間設備，i,j[1,2,…,n];xi和yi為設備i的坐標值；Cij表示多設備i到設備j的單位距離物料搬運費用；fpij表示p階段從設備i到設備j的物料搬運量。由文獻[5]對魯棒性布局問題的總結，建立車間物料搬運費用的計算公式，如式(1)，其中Dij表示設備i與設備j的距離。

(1)

(2) 非物流關系最大化。根據(jù) LEEK等人的研究，非物流關系可表達為：

(2)

cij為設備之間的非物流密切度值，如表 1 所示，bij是布局方案中設備之間的密切度關聯(lián)因子，它由資源間的實際物流距離dij和最大可能距離dmax決定，如表2所示。

表1 設備關系密切度分類

表2 密切度關聯(lián)因子

非物流關系的值越大，表明非物流關系越密切，為方便利用 NSGA- II 編程解決多目標布局問題，非物流關系目標函數(shù)如式(3)所示。其中M為一個較大的常數(shù)，可根據(jù)實際情況選擇。

(3)

(3) 車間面積費用最小化。采用設備自動換行的布局策略，即在同一行內(nèi)的各設備長度及其設備相互間距之和超過了布局車間的長度，則該行最后一臺設備自動進入下一行。

設備占地總面積簡化為矩形，長度為車間總長度L，寬度為h，h可以表達為：

h=(m-1)×s+s0+0.5×wi-(s0-0.5×wj)

其中，wi為最后一行上的設備的最大寬度，wj為第一行上的設備的最大寬度，s為行間距，s0為第一行設備與車間上邊界之間的最小距離，m為布局行數(shù)。不同布局方式中處于邊界的設備不同，h的取值也會相應地發(fā)生變化；R為單位土地面積費用。

因此，面積費用公式如式(4)所示：

AC=min{R·L·h}

(4)

1.3 約束條件

(1) 邊界約束和空間約束：式(5)保證車間設備不重疊，由于使用自動換行策略，Y方向上的行間距根據(jù)設備尺寸設定，設備之間不會出現(xiàn)重疊放置；式(6)保證一臺設備只能被放置一次，式(7)保證在設備自動換行的布局策略下，設備不超過車間寬度；

(i,j=1,2...,n,i≠j)

(5)

(6)

h≤H

(7)

Xi和Yi表示設備i的長和寬；sij表示設備i與j的X向最小間距；L和H為車間的長和寬；hi0為設備i離車間邊距界的X向和Y向最小間距；zik是0～1決策變量，其中zik=1，表示設備i在k行上，zik=0，表示設備i不在k行上，k為設備所有的行。

Rc≤δ

(8)

(9)

2 優(yōu)化算法設計

為了對上述模型進行化化計算，在NSGA-II的基礎上引入了DE策略[9-10]，從而使獲得的Pareto最優(yōu)解集保持較好的多樣性，加快算法的收斂速度。

2.1 染色體編碼/解碼機制

染色體編碼采用實數(shù)編碼方式，每個染色體由兩部分組成表示一種布局方案，這兩部分分別為設備排列順序和設備間凈間距。

[{Mv,Mr,…,Mu,…,Mz},{Δ1,Δ2,…,Δi,…,Δn}]

其中，Δ1表示設備Mv與車間邊界的最小距離，Δi表示第i臺設備與第i-1臺設備之間的凈間距，取值范圍為[Umin,Umax]。由于采用自動換行的布局策略，當?shù)趇臺設備剛好是某一行的第一臺設備時，Δi表示第i臺設備與車間邊界的最小距離。

染色體的解碼即求解每臺設備中心對應的坐標值，設備坐標的求解公式為：

yk=(t-1)×s+s0

(10)

(i,k=1,2,…,n;t=1,2,…m)

其中，n為設備的數(shù)量，t為該染色體對應的布局行數(shù)。

2.2 遺傳算子

(1) 二元錦標賽選擇算子

通過快速非支配排序以及擁擠度計算之后，種群中的每個個體都得到兩個屬性：非支配序rank和擁擠度nd。利用這兩個屬性，可以區(qū)分種群中任意兩個個體的支配和非支配關系。個體優(yōu)劣比較依據(jù)為：當且僅當irankjd，個體i優(yōu)于個體j。

選用二元錦標賽選擇算子，從種群中隨機選擇兩個個體，根據(jù)非支配排序和擁擠度比較兩個個體，選擇最優(yōu)的個體進入交配池。

(2) 交叉算子

對于染色體的設備排列序列部分采用映射交叉(PMX)算子。

(3) 基于差分進化的進化算子

對于設備凈間距序列部分，引入DE策略進行交叉和變異，提高算法局部搜索能力，在進行精英保留策略選擇子代個體時擁有較高的競爭能力，即在一定程度上保證了個體的多樣性。

在DE中，常見的差分策略是隨機選取兩種群中兩個不同的個體，將其向量差縮放后與待變異個體進行向量合成，即：

Ti=Xr1+F×[Xr2-Xr3]

其中，T為變異目標個體；F為縮放因子；Xr1表示種群中第r1個個體。F[0,1]；r1≠r2≠r3≠i。在進行變異操作時，為了保證解的有效性，要保證各“基因”滿足邊界條件，如果不滿足邊界條件，則隨機重新生成。

對xi及其變異的中間體Ti進行個體間的交叉操作：

其中，Tij為變異個體Ti的第j個變量，j[1,NP]；rij為個體i第j個變量對應的均勻分布的一人隨機變理，rij[0,1]；rnd為均勻分布的整數(shù)，rnd[1,NP]；cr為交叉概率，cr[0, 1]。

2.3 懲罰項

由于采用自動換行的布局策略，因此設備在X方向上不會超出工作區(qū)域。所以只需要判斷在Y方向上最后一行的設備是否會超出車間區(qū)域。Pt為Y方向超出車間區(qū)域的懲罰項，如式(11)，其中m為布局行數(shù)，w最后一行設備的最大寬度，T為正的大數(shù)懲罰項。

(11)

2.4 算法流程

采用改進后的NSGA-II算法求解已建立的優(yōu)化模型，DE-NSGA-II算法過程如圖1所示。首先將第t代產(chǎn)生的新種群Qt與父代Pt合并組成Rt，種群大小為2N，然后對Rt進行非支配排序，產(chǎn)生一系列非支配集Zi并計算擁擠度。由于子代和父代個體都包含在Rt中，則經(jīng)過非支配排序以后的非支配集Z1中包含的個體是Rt中最好的，所以先將Z1放放新的父代種群Pt+1中，依次類推，直到添加Zi時，種群的大小超出N，此時對Zi中的個體使用擁擠度比較，取前(N-num(Pt+1))個元素添加到新的父代種群Pt+1中。對新的父代種群進行選擇、交叉、變異操作，產(chǎn)生新的子代種群。

如此反復迭代直至達到最大迭代次數(shù)，得到pareto最優(yōu)解集。為了使得到的布局方案滿足魯棒性的要求，需要驗證pareto解集中是否存在滿足魯棒性約束的解，若存在這樣的解，則對該解進行解碼，即得到魯棒性布局方案，最后算法可能得到不只一種滿足魯棒性的布局方案，如果沒有一個解滿足魯棒性要求，則重啟算法。

圖1 NSGA-II算法流程

3 實例研究

3.1 實例描述

應用上述算法對某柔性制造單元的布局問題進行求解。該柔性制造單元的長為12m，寬為10m，需對12臺設備進行布局設計，設備的具體尺寸如表3所示。設備間的凈間距?的取值范圍為[0, 1.5]，設備間行間距s為2m，第一行設備與車間邊界距離s0為1.2m。設懲罰值T=500元，土地面積費用R=500元/m2。分析整個生產(chǎn)周期的實際情況以及車間安全性，可得到非物流關系cij，設備間水平最小間距要求hij和設備與車間邊界的最小距離要求hi0；魯棒性指標δ=0.07。

分析該制造單元連續(xù)3個計劃期的工藝路線(表4)和物流信息(表5)，求解每個階段的物流搬運頻率矩陣。

表3 設備尺寸(m×m)

表4 工藝路線

表5 生產(chǎn)計劃

3.2 算法參數(shù)設計與問題求解

DE-NSGA-II算法的相關參數(shù)設置如下：種群規(guī)模pop=100；最大遺傳代數(shù)maxgen=100；交叉概率pc=0.7，以式(1)～式(3)為目標函數(shù)，運行程序，最終得到的Pareto解集如圖2所示。針對提出的魯棒性布局模型分別應用DE-NSGA-II、NSGA-II，SADE對該魯棒性布局模型進行多次求解，結果對比，與NSGA-II及SADE相比，DE-NSGA-II的收斂性和多樣性更好，對比結果見表6。

圖2 pareto解集

在最終的Pareto解集中，剔除相似度比較高的布局方案，得到如表7所示的5種布局方案。方案1的目標1值是所有解集中最小的，但是目標2和目標3的值是最大的；方案5的目標3的值是最小的，但是目標1的值是最大的；方案4的目標2的值是所有解集中最小的，但是目標1和目標3的值均不是最小的。通過多次實驗分析可得，不存在某種方案可以使得3個目標都達到最優(yōu)。

該實例三個目標的最優(yōu)解分別為F1=729698.92，F(xiàn)2=33.8，F(xiàn)3=50040，不存在任何一個個體能使三個目標值同時達到最優(yōu)。企業(yè)決策者可以根據(jù)實際情況，在多種方案中選擇最合適的布局方案。

表6 三種優(yōu)化算法性能對比

表7 部分Pareto解集

4 結束語

針對提出的魯棒性布局模型，利用基于差分進化與NSGA-II的多目標算法驗證了該模型的有效性，克服了使用加權系數(shù)將多目標單一化求解多目標問題的缺點，可以有效地應對復雜多變的市場需求。算法設計的過程中，在NSGA-II算法的基礎上引入DE策略，有效地提高了Pareto解集的多樣性和算法的收斂速度，最終得出符合魯棒性要求的布局方案集。