張 屹，盧 超，張 虎，方子帆

（三峽大學(xué) 水電機(jī)械設(shè)備設(shè)計與維護(hù)湖北省重點實驗室，湖北 宜昌 443002）

0 引言

設(shè)備布局優(yōu)化設(shè)計是現(xiàn)代制造業(yè)面臨的重要且復(fù)雜的問題之一。一般來說，設(shè)備布局問題（Facility Layout Problem，F(xiàn)LP）指將一組設(shè)備合理地布置在特定布局空間內(nèi)，使設(shè)計目標(biāo)集盡可能地優(yōu)化，并且滿足給定的空間或性能約束條件［1］。車間設(shè)備布局是否科學(xué)、合理，將直接影響企業(yè)的生產(chǎn)效率。隨著社會經(jīng)濟(jì)的快速發(fā)展，越來越多的企業(yè)開始意識到合理的車間布局不僅可以降低運輸成本，還可以提高設(shè)備的使用壽命、廠房的利用率等。因此，科學(xué)合理的車間設(shè)備布局對企業(yè)來說尤為重要。

目前，大多數(shù)學(xué)者對車間布局的研究主要集中在減少車間設(shè)備間物料搬運費用的單目標(biāo)布局優(yōu)化方面。然而在實際車間布局設(shè)計過程中，當(dāng)物料傳輸費用成本下降時，往往會使車間設(shè)備的其他性能有所降低，如產(chǎn)品質(zhì)量降低、占地利用率減少等。因此，不能盲目追求物料傳輸費用最小，要統(tǒng)籌兼顧車間設(shè)備布局的整體規(guī)劃。實際上，面積利用率這項指標(biāo)直接影響車間布局的美觀和投資成本，應(yīng)在評估最佳布局方案時予以考慮。因此，應(yīng)該綜合考慮搬運費用成本和車間占地面積利用率這兩項指標(biāo)，建立車間設(shè)備布局多目標(biāo)優(yōu)化模型，以設(shè)計出更科學(xué)合理的布局方案。在解決多目標(biāo)優(yōu)化問題時，國際上涌現(xiàn)出許多經(jīng)典的多目標(biāo)進(jìn)化算法，如非支配排序遺傳算法（Non－dominated Sorting Genetic Algorithm Ⅱ，NSGAⅡ）［2］、強(qiáng)度Pareto進(jìn)化算法2（Strength Pareto Evolutionary Algorithm Ⅱ，SPEA2）［3］等。近年來，Nebro等又提出了經(jīng)典元胞多目標(biāo)遺傳算法和 MOCell［4］，總體而言，MOCell在多樣性和收斂性方面均表現(xiàn)出比NSGAⅡ和PESAⅡ更為優(yōu)越的性能，并在工程中得到很好的應(yīng)用［5－9］。但是對于解決 FLP 這樣非線性、高維的NP－h(huán)ard問題，MOCell的收斂性依然不盡如人意。2005年，Kukkonen S提出的 GDE3［10］在解決高維、非線性的復(fù)雜問題時，其收斂性相比其他算法有明顯提高。本文針對這些問題，結(jié)合MOCell良好的多樣性和GDE3良好的收斂性，在MOCell算法中引入差分演化（Differential Evolution，DE）策略［11］，并采用換位變異算子，形成一種混合算法DECell，以達(dá)到高效求出FLP的Pareto最優(yōu)解集的目的。

1 車間設(shè)備布局優(yōu)化模型

1．1 目標(biāo)函數(shù)的建立

因為車間布局問題可分為環(huán)型布局、U型布局等問題，所以以多行線性車間設(shè)備布局問題為例；又因為該問題較為復(fù)雜，所以需要對其模型進(jìn)行簡化。假定各設(shè)備為矩形塊狀結(jié)構(gòu)，長和寬已知，同一行中設(shè)備的中心位置處于同一水平線上，兩設(shè)備之間的物流運輸方向只能平行于相應(yīng)的參考線。多行線性車間布局示意圖如圖1所示。

圖1中，X和Y軸分別表示車間的長度和寬度方向，H和W 分別為車間的長度和寬度。xi和xj為設(shè)備i和j與垂直參考線之間的水平距離；yi和yj為設(shè)備i和j與水平參考線之間的垂直距離。該模型主要考慮下述兩個布局優(yōu)化設(shè)計目標(biāo)：①車間里總的物料搬運費用最小；②車間占地面積利用率最大，一是充分利用現(xiàn)有給定的空間，二是防止工作時車間之間噪音干擾，因此在指定的范圍內(nèi)占地面積越大越好。這兩個目標(biāo)一方面使物料搬運費用最小，另一方面要使占地面積利用率盡可能的高，因此它是一個典型的多目標(biāo)問題。由于多目標(biāo)優(yōu)化問題一般是求解目標(biāo)的最小值，可將面積函數(shù)轉(zhuǎn)化為A＝Z－f（s）形式。其中：Z為給定的常值；f（s）為車間實際占地面積，即f（s）＝a×b，且Z＞f（s）。綜上所述，多行線性車間設(shè)備布局問題的目標(biāo)函數(shù)可以表示為

式中：n為布局的設(shè)備的數(shù)目；C為總物流費用；A為車間的占地轉(zhuǎn)化面積；fij為設(shè)備i和j之間的搬運頻率；pij為設(shè)備i和j之間物料搬運一次單位距離的搬運費用（令pij＝pji）；dij為設(shè)備i和j之間的距離

1．2 約束條件的確定

由于各設(shè)備在車間中需占一定的面積，設(shè)備間還需為操作人員留出一定的活動空間，在多行線性車間布局設(shè)計中還需考慮各種約束條件。dxmin為相鄰設(shè)備i和j的邊界在水平方向（X方向）應(yīng)保證的最小間距，dymin為相鄰兩行設(shè)備i和j的邊界在垂直方向（Y方向）應(yīng)保證的最小間距。Si和Li分別為設(shè)備i在X方向和Y方向的尺寸?？紤]到多行布局的約束情況，引進(jìn)決策變量Zik，i＝1，…，n，k＝1，2，…，m，其中m為設(shè)備被排布的總行數(shù)。

因此，實現(xiàn)多行線性車間設(shè)備布局的優(yōu)化設(shè)計的約束條件包括：

（1）一臺設(shè)備只能被布置在一行，且每一行最多只能布置n臺設(shè)備。

式中tk表示第k行排布的設(shè)備數(shù)。

（2）邊界約束，即每一臺設(shè)備都應(yīng)處于車間之內(nèi)。

（3）同一行中設(shè)備的y坐標(biāo)相同。

（4）同一行中的設(shè)備不能重疊，且設(shè)備邊界之間的最小間距需要大于水平方向上應(yīng)保證的最小間距，邊界間的最大距離要小于布局車間的長度。

（5）處于不同行的任意兩臺設(shè)備在垂直方向上設(shè)備邊界之間的最小間距，要大于垂直方向上應(yīng)保證的最小間距；邊界間的最大距離要小于布局車間的寬度。

2 差分元胞遺傳算法設(shè)計及性能測試

為了對上述FLP多目標(biāo)優(yōu)化模型進(jìn)行優(yōu)化計算，提出一種差分元胞遺傳算法DECell。DECell是在MOCell的基礎(chǔ)上引入DE策略的算法，該算法采用換位變異算子。為了對上述FLP多目標(biāo)優(yōu)化模型進(jìn)行優(yōu)化計算，提出一種差分元胞遺傳算法DECell。DECell是在MOCell的基礎(chǔ)上改進(jìn)的一種算法，它引入了DE策略，并采用換位變異算子，從而使獲得的Pareto前端的解集能在保持良好均勻性和分布廣度的同時，朝著最優(yōu)前端不斷逼近。

2．1 差分演化策略原理

DE策略利用群體中個體之間的距離和方向信息，具有全局并行直接搜索的特點，適于求解高維、非線性的多目標(biāo)問題，且實施起來相對較容易［12］。具體操作過程是：

對于每個個體xi，D，i∈［0，N－1］，N 為種群大小，定義操作［13］

式中：D 為個體的決策變量個數(shù)，xr1，D，xr2，D和xr3，D為選擇出來的三個父本向量，r1，r2和r3為三個父本的索引位置，F(xiàn)為縮放因子。式（10）表示隨機(jī)取出兩個父本向量xr2，D和xr3，D，取兩者的差值，將其縮放后的結(jié)果加到第三個父本向量xr1，D上，最終得到交叉后的個體向量vi，D＝［vi，1，…，vi，j，…，vi，D］。而對于處于第i索引位置的父本向量xi，D＝［xi，1，…，xi，j，…，xi，D］中的每一分量xi，j，隨機(jī)產(chǎn)生一個數(shù)randj∈［0，1］，比較randj與交叉因子CR 或j與K 的大小，判斷是否用vi，，j來替換xi，j，隨機(jī)產(chǎn)生一個數(shù)randj∈［0，1］，比較randj與交叉因子CR或j與K（K∈［0，D－1］之間的整數(shù)）的大小，從而利用式（11）判斷是否用vi，，j來替換xi，j，判斷操作完成以后，得到新個體ui，D＝［ui，1，…，ui，j，…，ui，D］，其中

若交叉后的新個體ui，D優(yōu)于父代個體xi，D，則用新個體替換父代個體，否則保持不變。

2．2 DECell算法原理

DECell算法具體原理如圖2所示。首先將種群個體安排在二維的環(huán)形網(wǎng)格中，從每個當(dāng)前個體周圍鄰居中隨機(jī)選出兩個較優(yōu)秀的個體，與當(dāng)前個體共同構(gòu)成三個父本個體；然后對這三個父本進(jìn)行DE策略的交叉操作；最后進(jìn)行變異操作，產(chǎn)生子代。如果子代支配當(dāng)前個體，或者子代和當(dāng)前個體都處于非支配地位，且子代的擁擠距離比當(dāng)前個體的擁擠距離大，則子代個體代替當(dāng)前個體，同時將該非支配的個體存放到外部文檔中，并對這些外部文檔存放好的個體按擁擠距離進(jìn)行排序，若其非支配個體超過了規(guī)定的容量，則將其中擁擠距離最小的個體刪除。最后，在每代結(jié)束時，從外部文檔中選一些個體代替相同數(shù)量的原始種群中的個體，使種群不斷進(jìn)行更新操作，最終使外部文檔中的非支配個體在保持多樣性的同時，能朝著Pareto最優(yōu)前端的方向不斷逼近。其主要偽代碼如下：

2．3 DECell算法性能測試及結(jié)果分析

為驗證算法DECell的性能，選用一個多約束、多變量的雙目標(biāo)測試函數(shù)Osyczka2［14］和一個高維多 目 標(biāo) 函 數(shù) DTLZ2［15］。 分 別 利 用 DECell，NSGAⅡ及MOCell對上述測試函數(shù)進(jìn)行計算，并分析相同評價體系下三種算法的性能。

2．3．1 算法性能評價指標(biāo)

這里采用世代距離［16］、分布指標(biāo)［3］和超體積［17］三個性能指標(biāo)進(jìn)行度量。

（1）世代距離

世代距離是用來評價所得的Pareto前端與最優(yōu)Pareto前端之間的間隔距離，計算公式為

式中：n為所得Pareto前端個體的數(shù)目，di為目標(biāo)空間中的第i個解與Pareto最優(yōu)前端中最近解之間的歐氏距離。顯然，當(dāng)GD＝0時，所得的Pareto解集就是Pareto最優(yōu)解。因此，GD 越小，表明收斂到最優(yōu)Pareto解的程度越好。

（2）分布指標(biāo)

Deb提出的分布指標(biāo)是衡量所得的Pareto前端解集的分布情況，計算公式為

式中：di為所得Pareto前端上每兩個連續(xù)解點的歐氏距離，為這些歐氏距離的平均距離，df和dl分別為所得Pareto前端的邊界點與Pareto最優(yōu)邊界點的歐氏距離，n為所得Pareto前端個體的數(shù)目。對于分布均勻的解來說，該指標(biāo)取0。因此，該指標(biāo)的值越小表明分布程度越均勻。

（3）超體積

超體積是用來計算獲得的Pareto解集個體在目標(biāo)域所覆蓋的體積，計算公式為

式中Q為所獲得的Pareto前端的個數(shù)。對于該P(yáng)areto前端中的每一個體i，vi是由參考點W ＝ （0，…，0）和成員i所形成的超體積，該指標(biāo)越大表明所得的Pareto解集能越寬廣地覆蓋在其前端上。

2．3．2 算法性能優(yōu)化結(jié)果及分析

Osyczka2與DTLZ2基準(zhǔn)測試函數(shù)的定義如表1所示。

表1 基準(zhǔn)測試函數(shù)

NSGAⅡ，MOCell和DECell算法的參數(shù)設(shè)置為：均采用實數(shù)制進(jìn)行編碼，多項式變異；NSGAⅡ和MOCell采用模擬二進(jìn)制交叉（Simulation Binary Crossover，SBX）［18］算子，DECell使用DE交叉操作算子；種群規(guī)模為100，最大評價次數(shù)為25 000，交叉概率為0．8，變異概率為1／len，len為變量維數(shù)；在此取CF＝0．6，CR＝0．5。這三種算法分別對測試函數(shù)進(jìn)行10次獨立運行計算。圖3是三種算法所獲得到Pareto前端的對比圖之一。

從定性的角度分析圖4可知：NSGAⅡ收斂性好，但分布性能較差；MOCell的分布性能較好，但其收斂性和覆蓋性能較差；采用DE策略的DECell所求的Pareto前端解集，在分布性、覆蓋廣度和收斂性方面均比NSGAⅡ和MOCell好。

表2記錄了三種算法在Osyczka2和DTLZ2函數(shù)上的收斂性、分布性和覆蓋范圍。每種性能指標(biāo)的第一列為性能均值，第二列為性能標(biāo)準(zhǔn)差，加粗?jǐn)?shù)據(jù)為最優(yōu)值。分析表2可以發(fā)現(xiàn)，在解決DTLZ2和Osycka2時，DECell在收斂性方面和覆蓋范圍方面要比NSGAⅡ和MOCell更好一些。雖然在解決Osyczka2時DECell的分布性能比MOCell的差，但DECell的穩(wěn)定性比MOCell好。DECell之所以表現(xiàn)出優(yōu)良的性能，其原因在于它結(jié)合了MOCell和DE兩種算法的優(yōu)點。由實驗數(shù)據(jù)可知，DECell的確提高了解集的收斂性能，有效地保持了種群的多樣性，增大了解集的覆蓋范圍。因此，通過以上算例結(jié)果分析可知，在解決多約束、多變量、高維的多目標(biāo)問題時，DECell比NSGAⅡ和MOCell具有良好的優(yōu)勢。

表2 算法性能結(jié)果對比

3 DECell算法在設(shè)備布局問題中的應(yīng)用設(shè)計

采用DECell對FLP模型進(jìn)行計算，基本步驟如下：

（1）隨機(jī)生成初始種群 采用實數(shù)制編碼生成初始種群，根據(jù)車間布局問題的實際要求，將編碼設(shè)計為 ［（m1，…，mn），（x1，…，xn），（y1，…，yn）］。其中mn表示第n臺設(shè)備編號，xn和yn為第n臺設(shè)備的坐標(biāo)，（m1，…，mn）是n臺設(shè)備的一個全排列。

（2）選擇操作 采用錦標(biāo)賽法，該選擇方法是基于個體的秩和擁擠距離對種群父本進(jìn)行選擇，因此步驟為：選出當(dāng)前個體的鄰居個體，首先比較鄰居個體的秩，秩越小個體的性能越優(yōu)秀，因此處于較小秩的個體被保留下來。若鄰居個體的秩相等，則比較它們的擁擠距離，擁擠距離較大的個體被保留下來。最終選出鄰居中較優(yōu)秀的兩個個體。

（3）交叉操作 其作用是產(chǎn)生更多的新個體，增大搜索空間的能力。為保障交叉后的解集可行，只對 （x1，…，xn）區(qū)域進(jìn)行交叉操作，并對 （y1，…，yn）進(jìn)行重新移動，調(diào)整設(shè)備的行距。在交叉操作中引入DE策略，其交叉過程如式（10）和式（11）所示。該操作中要使用到交叉系數(shù)CR和縮放因子F兩個參數(shù)，在這里CR＝0．8，F(xiàn)＝0．5，具體參數(shù)設(shè)置詳見參考文獻(xiàn)［19］。DECell算法中的交叉代碼流程如下：

（4）變異操作 為使個體逃離局部收斂，且盡可能保障產(chǎn)生的子代是可行解，此處對 （m1，…，mn）區(qū)域進(jìn)行換位變異操作。具體步驟如圖5所示。

4 實例求解

在一個長×寬，即17m×14m的車間放置9臺設(shè)備，這些設(shè)備分3行放置在車間內(nèi)，每行3臺，設(shè)備的尺寸如表3所示，設(shè)備之間的搬運頻率如表4所示，單位距離的搬運費用如表5所示，設(shè)備之間應(yīng)保證水平方向和垂直方向的安全距離，其最小距離分別為dxmin＝1m，dymin＝1 m，設(shè)常數(shù)Z＝500。

表3 設(shè)備尺寸

表4 設(shè)備之間的搬運頻率fij

表5 單位距離的搬運費用pij

依然采用DECell，MOCell和NSGAⅡ三種算法分別對車間設(shè)備布局進(jìn)行優(yōu)化計算。三種算法的參數(shù)設(shè)置為：種群數(shù)量M＝25，文檔大小N＝100，反饋數(shù)目C＝5，終止評價次數(shù)G＝25 000，交叉概率pc＝0．8，變異概率pm＝0．2。求出這三種算法所產(chǎn)生的Pareto前端，如圖6所示。

由于問題的復(fù)雜性，很難找到最優(yōu)解集，這里將最后得到的非支配解集當(dāng)作最優(yōu)Pareto解集。從圖6可以看出，位于左上方的Pareto前端的點具有較大的轉(zhuǎn)換區(qū)域面積和較低的物料運輸費用，即物料運輸費用越低，車間設(shè)備占地面積利用率越小。而位于右下方的Pareto前端的點具有較小的轉(zhuǎn)換區(qū)域面積和較大的物料運輸費用，意味著車間設(shè)備占地面積利用率越大，其物料運輸費用就越高。在目標(biāo)空間中，這些算法為決策者提供了各自的Pareto前端解集，以便決策者根據(jù)自己的偏好選擇出合適的解。由圖6可以看出，DECell的Pareto前端的解集的分布性和收斂性比NSGAⅡ和MOCell好。為進(jìn)一步說明DECell算法在車間布局優(yōu)化設(shè)計上的應(yīng)用較其他算法具有一定的優(yōu)勢，本文用上述三種算法對車間設(shè)備布局各自進(jìn)行了10次獨立運算，計算結(jié)果如表6所示。

表6 三種算法準(zhǔn)確率比較 %

綜上所述，與MOCell和NSGAⅡ相比，DECell表現(xiàn)出了一定的優(yōu)勢，因此選擇采用DECell算法求解得到FLP的Pareto前端，并從中選出A和B兩點所對應(yīng)的Pareto解集解，A和B兩點如圖6所示，結(jié)果如表7所示。

表7 DECell算法得到的部分Pareto解集

5 結(jié)束語

本文針對車間FLP建立了一個同時考慮物料搬運費用和車間占地面積利用率的多目標(biāo)優(yōu)化模型，基于MOCell良好的多樣性，以及GDE3良好的收斂性和分布廣度的優(yōu)點，結(jié)合這兩種算法的特點，互補(bǔ)長短，在MOCell算法中引入DE策略，并采用換位變異算子，形成一種混合算法DECell，以使獲得的Pareto前端的解集在保持均勻性和覆蓋性能的同時，其解集能朝著最優(yōu)前端不斷逼近。最后將DECell與MOCell和NSGAⅡ進(jìn)行了性能對比，驗證了DECell的有效性和可行性，并將三種算法分別對車間設(shè)備布局進(jìn)行優(yōu)化設(shè)計。通過實例對比分析可知，該算法比其他兩種算法的效果有所改善，為解決多行車間布局問題提供了一種新的方法。未來工作將進(jìn)一步改善該算法的性能，并將此算法推廣到其他類型的車間布局實際問題中。

［1］CAGAN J，SHIMADA K，YIN S．A survey of computational approaches to three－dimensional layout problems［J］．Computer－Aided Design，2002，34（8）：597－611．

［2］DEB K，PRATAB A，AGARWAL S，et al．A fast and elitist multiobjective genetic algorithm：NSGA－Ⅱ［J］．IEEE Transactions on Evolutionary Computation，2002，6（2）：182－197．

［3］CORNE D W，JERRAN N R，KNOWLES J D，et al．PESA－Ⅱ：region－based selection in evolutionary multi－objective optimization［EB／OL］．［2011－11－15］．http：／／www．macs．hw．a(chǎn)c．uk／～dwcorne／pesall．pdf．

［4］NEBRO A J，DURILLO J J，LUNA F，et al．MOCell：a cellular genetic algorithm for multiobjective optimization［J］．International Journal of Intelligent Systems，2009，24（7）：726－746．

［5］BRUDARU O，POPOVICI D，COPACEANU C．Cellular genetic algorithm with communicating grids for assembly line balancing problems［J］．Advances in Electrical and Computer Engineering，2010，10（2）：87－93．

［6］ALBA E，MOLINA G．Location discovery in wireless sensor network using metaheuristics［J］．Applied Soft Computing，2011，11（1）：1223－1240．

［7］CANYURT O E，HAJELA P．Cellular genetic algorithm technique for the multicriterion design optimization［J］．Structural and Multidisciplinary Optimization，2010，40（1－6）：201－214．

［8］LI Xunbo，WANG Zhenlin．Cellular genetic algorithms for optimizing the area covering of wireless sensor networks［J］．Chinese Journal of Electronics，2011，20（2）：352－356．

［9］WU Feng，ZHOU Hao，REN Tao，et al．Combining support vector regression and cellular genetic algorithm for multi－objective optimization of coal－fired utility boilers［J］．Fuel，2009，88（10）：1864－1870．

［10］KUKKONEN S，LAMPINEN J．GDE3：the third evolution step of generalized differential evolution［C］／／Proceedings of the 2005IEEE Congress on Evolutionary Computation．Washington，D．C．，USA：IEEE，2005：443－450．

［11］STORN R，PRICE K．Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces［J］．Journal of Global Optimization，1997，11（4）：341－359．

［12］SHI Yanjun．The cooperative co－evolutionary differential evolution and its applications for complex layout optimization［D］．Dalian：Dalian University of Technology，2005（in Chinese）．［史彥軍．復(fù)雜布局的協(xié)同差異演化方法與應(yīng)用研究［D］．大連：大連理工大學(xué)，2005．］

［13］DURILLO J J，NEBRO A J，LUNA F，et al．Solving threeobjective optimization problems using a new hybrid cellular genetic algorithm［J］．Lecture Notes in Computer Science，2008，5199：661－670．

［14］OSYCZKA A，KUNDO S．A new method to solve generalized multicriteria optimization problems using a simple genetic algorithm［J］．Structural and Multidisciplinary Optimization，1995，10（2）：94－99．

［15］DEB K，THIELE L，LAUMANNS M，et al．Scalable test problems for evolutionary multi－objective optimization［C］／／Proceeding of 2002Congress on Evolutionary Computation．Berlin，Germany：Springer－Verlag，2002：852－890．

［16］VAN VELDHUIZEN D A，LAMONT G B．On measuring multiobjective evolutionary algorithm performance［C］／／Proceedings of the 2000Congress on Evolutionary Computation．Washington，D．C．，USA：IEEE，2000：204－211．

［17］ZITZLER E，THIELE L．Multiobjctive evolutionary algorithms：a comparative case study and the strength Pareto approach［J］．IEEE Transactions on Evolutionary Computation，1999，3（4）：257－271．

［18］DEB K，AGRAWAL R B．Simulated binary crossover for continuous search space［J］．Complex Systems，1995，9（2）：115－148．

［19］ZIELINSKI K，WEITKEMPER P，LAUR R，el at．Parameter study for differential evolution using apower allocation problem including interference cancellation［C］／／Proceedings of the IEEE Congress on Evolutionary Computation．Washington，D．C．，USA：IEEE，2006：1857－1864．