陳 勇 程子文 姜樅聰 王亞良 王 成 酈仕云

浙江工業(yè)大學(xué)機(jī)械工程學(xué)院，杭州，310014

0 引言

制造業(yè)的市場需求有著持續(xù)性、關(guān)聯(lián)性、多變性等特點(diǎn)，客戶需求多樣化和訂單動(dòng)態(tài)波動(dòng)的趨勢日益突顯，企業(yè)需要更加合理的車間布局來滿足生產(chǎn)高柔性、制造低碳化、布局高穩(wěn)定性等要求。復(fù)雜性作業(yè)車間的布局問題近年來的研究主要集中于面積利用率、物流成本、搬運(yùn)距離、設(shè)備利用率、魯棒性和柔性等多目標(biāo)對布局系統(tǒng)的影響。 朱琳等[1]為解決多品種混合裝配車間的布局問題，以工人平均取料路徑最短為目標(biāo)，以物料擺放位置為決策變量，建立了數(shù)學(xué)模型，采用只允許最優(yōu)解釋放信息素的蟻群算法求解目標(biāo)函數(shù)；劉瓊等[2]針對動(dòng)態(tài)環(huán)境下頻繁的布局優(yōu)化，以物料搬運(yùn)費(fèi)用和面積費(fèi)用最小化為目標(biāo)，建立了魯棒性布局優(yōu)化模型，利用改進(jìn)的蛙跳算法求解具有較高魯棒性的布局方案；馬淑梅等[3]考慮產(chǎn)品不確定性隨時(shí)間變化的特性，構(gòu)建了基于柔性區(qū)域結(jié)構(gòu)的不確定需求動(dòng)態(tài)布局模型，并提出一種結(jié)合模糊理論與改進(jìn)遺傳算法的動(dòng)態(tài)布局方法；劉瓊等[4]以制造過程總碳排量和調(diào)度完工時(shí)間最小為雙目標(biāo)，建立了車間布局與調(diào)度集成優(yōu)化模型；陳勇等[5]針對一類多態(tài)性作業(yè)車間，利用成組技術(shù)與分層思想構(gòu)建低熵布局模型，提出了低熵化布局評價(jià)指標(biāo)；GONZALEZCRUZ等[6]以多產(chǎn)品工藝順序作為設(shè)備間物流紊亂度指標(biāo)，采用熵優(yōu)化算法求解了混合生產(chǎn)車間低紊亂度布局問題；KAVEH等[7]通過建立期望值、機(jī)會(huì)約束規(guī)劃、相關(guān)機(jī)會(huì)規(guī)劃模型來解決模糊約束條件下的動(dòng)態(tài)車間布局問題；GARCIAHERNANDEZ等[8]針對物流量最小和穩(wěn)定性最高的多目標(biāo)，設(shè)計(jì)了融合專家定性評判與聚類遺傳算法的混合優(yōu)化算法；RAZAVIALAVI等[9]同時(shí)考慮設(shè)備位置、物流成本以及動(dòng)態(tài)物料配送，建立了多目標(biāo)布局模型，采用遺傳算法與仿真軟件的交互式運(yùn)算解決了多態(tài)性車間布局問題；LENO等[10]以單元間設(shè)備布局、物料進(jìn)出口最佳位置和物料移動(dòng)距離為目標(biāo)建立基于混合整數(shù)規(guī)劃的數(shù)學(xué)模型，通過最小化處理成本來評估布局的質(zhì)量，設(shè)計(jì)融合模擬退火算法與遺傳算法的混合進(jìn)化算法來求解目標(biāo)。

在解決多目標(biāo)問題時(shí)，多目標(biāo)優(yōu)化算法求解Pareto解集是主要趨勢。如非支配解排序遺傳算法(non-dominated sorting genetic algorithmⅡ,NSGAⅡ)[11]、強(qiáng)度Pareto進(jìn)化算法(strength pareto evolutionary algorithm,SPEA)[12]等。近年來，又相繼出現(xiàn)了在NSGA基礎(chǔ)上改進(jìn)的多目標(biāo)粒子群算法(multi-objective particle swarm optimization,MPSO)[13]、多目標(biāo)果蠅優(yōu)化算法(multiobjective optimization algorithm for drosophila melanogaster，MOADM)、多目標(biāo)差分元胞遺傳算法(multiobjective differential cellular genetic algorithm，MDCGA)[14]?？傮w而言，這些算法在一定程度上能夠很好地求得Pareto解，但也存在一些問題。如NSGAⅡ、SPEA會(huì)出現(xiàn)解集分布不均勻、收斂性不足等問題。改進(jìn)的多目標(biāo)算法整體上表現(xiàn)出良好的性能，但在非線性、高維度的NP-Hard問題上依然不能滿足要求。

本文提出以單位面積布置成本、單位產(chǎn)品物流成本以及布局熵為指標(biāo)，設(shè)計(jì)多目標(biāo)的布局模型，實(shí)現(xiàn)一類多態(tài)性車間低成本、高穩(wěn)健性布局。設(shè)計(jì)基于Pareto優(yōu)化的模糊聚類并行多目標(biāo)遺傳算法以提高Pareto解集分布的多樣性與均勻性；提出改進(jìn)的多元胞差分進(jìn)化重插入操作以避免算法陷入局部最優(yōu)。提出的算法能夠有效地保證整個(gè)Pareto曲面解集的均勻分布，保證種群的多樣性，提高進(jìn)化效率與解的質(zhì)量。

1 一類多態(tài)性作業(yè)車間布局目標(biāo)

1.1 一類多態(tài)性作業(yè)車間問題描述

一類多態(tài)性作業(yè)車間是指大規(guī)模定制和產(chǎn)業(yè)集群下代工企業(yè)為滿足多品種、小批量的市場需求，以單元群制造模式為基礎(chǔ)，實(shí)現(xiàn)多產(chǎn)品、多工藝、多功能區(qū)域一體化的生產(chǎn)車間[15]。其生產(chǎn)過程在訂單、設(shè)備、工藝、批量、瓶頸等層次上越來越凸顯出形態(tài)和狀態(tài)的多樣性，加工批量和運(yùn)轉(zhuǎn)批量呈現(xiàn)動(dòng)態(tài)性，布局高穩(wěn)健性需求逐步增強(qiáng)。

多態(tài)性作業(yè)車間布局問題描述如下：n種產(chǎn)品需要在m個(gè)功能單元內(nèi)加工裝配，每種產(chǎn)品具有不同的加工路線，受到功能區(qū)域緊前關(guān)系約束，需要完整地在必須經(jīng)過的功能單元上完成相應(yīng)的過程。布局過程受單元形狀、物流成本、產(chǎn)品工藝、布局穩(wěn)定性等多條件約束，需尋求車間布局整體最優(yōu)化。

1.2 車間布局多目標(biāo)

企業(yè)希望通過提高車間面積利用率，降低產(chǎn)品物流成本，同時(shí)保證車間的穩(wěn)定性，實(shí)現(xiàn)車間的有效布局。參考文獻(xiàn)[16]給出的布局關(guān)鍵目標(biāo)建議，提出以下3個(gè)布局目標(biāo)。

(1)單位面積布置成本T。傳統(tǒng)意義上的車間面積利用率是需求面積與車間總面積之比，僅表示車間面積被占用情況，無法表征土地利用價(jià)值。筆者認(rèn)為在有限的土地資源中，單位面積布置成本能夠更加直觀地體現(xiàn)車間面積的有效利用價(jià)值。單位面積布置成本越小，表明面積的利用價(jià)值越高，布局更合理高效。

考慮不同的設(shè)備布局方式會(huì)帶來單元形狀變化，進(jìn)而引起布置成本變動(dòng)，因此研究中考慮單元形狀不固定的情況，引入單元縱橫比的概念，即

(1)

式中，li、hi為單元i的長度和寬度。

對任意單元而言，恰當(dāng)?shù)目v橫比表征合理的單元形狀，不易引起額外的布置成本，否則易造成布置成本增加。將縱橫比與設(shè)備成本耦合，定義布置成本：

(2)

s.t.

Δx=max|xi-xj|

Δy=max|yi-yj|

i,j=1,2,…,m

式中，m為單元數(shù)；Mi為單元i的設(shè)備數(shù)；qM為設(shè)備M的成本；F(ηi)為單元縱橫比ηi模糊評價(jià)函數(shù)，參考文獻(xiàn)[17]，文中引用圖1所示的最簡單的評價(jià)函數(shù)；ηi,max、ηi,opt為單元i縱橫比上限和最優(yōu)值，可根據(jù)實(shí)際情況定義；Δx、Δy分別為單元i、j沿x軸和y軸方向的間距；ΔxΔy為車間包含所有單元的最小面積；xi、xj、yi、yj分別為單元i、j的橫縱坐標(biāo)。

(2)單位產(chǎn)品物流成本Z。最小化物流搬運(yùn)耗費(fèi)是傳統(tǒng)的布局評價(jià)目標(biāo)。產(chǎn)品物流流向的復(fù)雜性與功能單元的不確定性導(dǎo)致常規(guī)的物流量距模型只能模糊地描述車間物流對布局的約束。多品種多工藝生產(chǎn)的路線較多、交叉頻繁，需根據(jù)不同產(chǎn)品組合選擇合理的生產(chǎn)工藝路線，以減少其交叉。同時(shí)考慮搬運(yùn)距離，以達(dá)到總物流量距最小。筆者提出以單位產(chǎn)品的有效物流量距成本與路線交叉懲罰成本衡量物流對布局的約束，有

(3)

s.t.

dij=|xi-xj|+|yi-yj|

式中，n為產(chǎn)品總數(shù)量；fijp為產(chǎn)品p在單元i至單元j間的物流量；cijp為產(chǎn)品p在單元i和j之間的單位運(yùn)輸成本；Cpk為產(chǎn)品p與產(chǎn)品k的路線交叉懲罰成本；dij為單元i和單元j間的距離，考慮車間內(nèi)物料搬運(yùn)無法沿兩點(diǎn)間直線搬運(yùn)，故視為單元間折線距離。

(3)布局熵E。多態(tài)性作業(yè)車間需要一個(gè)較為穩(wěn)定的生產(chǎn)環(huán)境，穩(wěn)定性的獲得不僅依賴于布局系統(tǒng)的可靠運(yùn)行，同樣依賴于布局系統(tǒng)單元間各種關(guān)聯(lián)關(guān)系的相對穩(wěn)定性。本文引入熱力學(xué)中象征系統(tǒng)紊亂度的物理熵概念，根據(jù)熵的含義，布局自然發(fā)展的過程為在自組織作用下熵值不斷增大的過程，即系統(tǒng)紊亂度增加。由于熵值的增大導(dǎo)致布局系統(tǒng)復(fù)雜性增加，從而降低了效率，因此需要給出低熵化、引導(dǎo)性的布局約束?；诖嗳跣猿橄蟮牟季朱啬Ｐ鸵晕锢盱貫檐囬g穩(wěn)健優(yōu)化度量指標(biāo)，能很好地滿足系統(tǒng)高穩(wěn)定性、持續(xù)改善的要求。

根據(jù)文獻(xiàn)[18-19]所述，由某種相似粒子組成的系統(tǒng)，N和Es分別表示系統(tǒng)中粒子的數(shù)量和其所擁有的能量，系統(tǒng)某一時(shí)刻處在微觀狀態(tài)(N，Es)的概率為

(4)

式中，a、b為歸一化系數(shù)。

由物理熵表達(dá)公式可知系統(tǒng)的熵值表達(dá)式：

(5)

研究過程中將車間視為一個(gè)無序的開放系統(tǒng)，單元設(shè)備、物料等視為系統(tǒng)粒子。衡量布局熵的關(guān)鍵在于如何定義概率P，根據(jù)物理熵公式的含義及其單調(diào)性可知，概率P越大，熵值越小，系統(tǒng)越穩(wěn)定?？紤]車間布局實(shí)際情況，將P定義為車間某種狀態(tài)可能崩潰情況的映射概率。布局魯棒性能差則無法應(yīng)對車間機(jī)器故障等不確定性因素，柔性程度低則無法及時(shí)應(yīng)對多生產(chǎn)工藝路線更改等擾動(dòng)因素，兩種情況都有可能導(dǎo)致車間停產(chǎn)崩潰。因此將各種引起崩潰的情況綜合為魯棒性與柔性兩種，建立概率P與魯棒性(R)和柔性(F)的映射關(guān)系，以布局熵反映車間紊亂度，能夠很好地表征布局系統(tǒng)的穩(wěn)定程度。

對布局層面而言，產(chǎn)品工藝魯棒性體現(xiàn)在加工距離差異性上。不同產(chǎn)品的工藝路線與加工距離各不相同，保證加工距離的一致性能夠保證生產(chǎn)穩(wěn)定性，即

(6)

s.t.

式中，Lp為產(chǎn)品p經(jīng)過完整工藝路線的加工距離；wp為產(chǎn)品p的工序集合；I(J)表示第I(J)道工序。

布局柔性體現(xiàn)布局系統(tǒng)自身調(diào)節(jié)能力，主要影響因素有生產(chǎn)路徑、物流量、可變單元數(shù)、單元負(fù)載量等。布局柔性定義為

(7)

建立概率P與魯棒性R和柔性F的映射模型：

(8)

(9)

其中，Rmax、Rmin、Fmax、Fmin分別為理論上魯棒性和柔性的最大值、最小值；考慮到布局實(shí)際與概率映射模型，崩潰概率P∈(e-1,1)，魯棒值R越大，則車間穩(wěn)健性能越好，崩潰概率P1越小；柔性程度越高，則車間容納性能越好，崩潰概率P2越小。

在式(8)、式(9)基礎(chǔ)上建立表征車間布局穩(wěn)定程度的布局熵模型：

E=e·(P1lnP1+P2lnP2)+1

(10)

由式(10)的單調(diào)性可知，崩潰概率越小，熵值E越小，車間穩(wěn)定性能越好。為了將E映射至(0,1)區(qū)間，參考文獻(xiàn)[5]，取E∈[0.2,0.8]，認(rèn)為在此區(qū)間布局系統(tǒng)的熵值合理。

1.3 車間布局多目標(biāo)優(yōu)化模型

筆者提出的單位面積布置成本、單位物流成本以及布局熵3個(gè)目標(biāo)之間存在著相互競爭的關(guān)系：單位面積布置成本越高，單元分布越緊湊，物流量距越小，工藝路線交叉越頻繁，直接引起車間布局熵增加。因此建立多目標(biāo)優(yōu)化模型，利用改進(jìn)的多目標(biāo)求解算法求解Pareto解集，模型如下：

(11)

(12)

f3=min(e·(P1lnP1+P2lnP2)+1)

(13)

1.4 約束條件

將車間看作一個(gè)二維矩形平面，各功能單元為矩形，平面內(nèi)以車間左下角為原點(diǎn)建立長寬方向的坐標(biāo)系，如圖2所示。因本文編碼方式存在邊界約束性，因此只需建立位置約束：

(14)

圖2 車間坐標(biāo)示意圖Fig.2 Workshop coordinate diagram

(15)

式中，dxmin、dymin為沿x軸和y軸方向的最小間距，用來保證任何兩個(gè)單元不會(huì)重疊布置。

2 算法設(shè)計(jì)

針對多目標(biāo)車間布局問題，提出基于Pareto優(yōu)化的聚類并行多目標(biāo)遺傳算法(cluster parallel multi-objective genetic algorithms，CPMGAs)，在每一代進(jìn)化過程中得到的當(dāng)前種群中引入模糊C-均值聚類算法，依據(jù)布局模型的多個(gè)優(yōu)化目標(biāo)將種群分成n類元胞種群，元胞種群存在組內(nèi)染色體相似度最高、組間染色體差異性最大的特征，該進(jìn)化過程可以提高Pareto解集分布的多樣性與均勻性；提出改進(jìn)的多元胞差分進(jìn)化重插入操作，并采用“移民策略”避免算法陷入局部最優(yōu)[20-21]。提出的算法能夠有效地保證整個(gè)Pareto曲面解集的均勻分布，保證種群的多樣性。改進(jìn)的多元胞差分進(jìn)化重插入操作與移民策略能起導(dǎo)向進(jìn)化作用，保證優(yōu)質(zhì)解的有效遺傳，提高進(jìn)化效率。

2.1 CPMGAs基本框架

引入模糊C-均值聚類算法，依據(jù)各目標(biāo)將種群劃分為若干元胞種群，并組成環(huán)狀拓?fù)浣Y(jié)構(gòu)進(jìn)行協(xié)作進(jìn)化，以增強(qiáng)種群的導(dǎo)向性進(jìn)化，基本框架如圖3所示。

圖3 CPMGAs模型框架Fig.3 Framework model of CPMGAs

2.2 染色體編碼策略

根據(jù)布局模型，染色體需要包含三類信息：單元坐標(biāo)、形狀和組合分布情況。為避免編碼冗長,采用FBS(flexible bay structure)編碼方式：每條染色體由單元排序編碼與單元分割點(diǎn)編碼兩部分組成。單元排序編碼由n個(gè)單元組成，表示車間由左至右，從上至下排列順序；分割點(diǎn)編碼由n-1個(gè)0/1二進(jìn)制編碼組成，0表示單元處于同一縱列，1表示單元為某縱列最后單元。

為方便編碼與計(jì)算，對車間單元和編碼環(huán)境作如下簡化：

(1)研究的單元是包括機(jī)器群、通道、緩沖區(qū)等組成的綜合單元模塊，單元面積確定，形狀可變。

(2)FBS編碼前，總面積的長與寬已知，即各單元填充排布的總區(qū)域是確定的，如圖4所示，即

LH=SA+SB+SC+SD+SE+SF

其中，L、H為已知單元填充區(qū)域的長與寬；SA為單元A的面積，其余解釋同SA。

圖4 FBS編碼方式示意圖Fig.4 FBS encoding scheme diagram

FBS編碼過程確定了各單元間的相對位置，接下來根據(jù)L、H及各單元面積確定精確位置坐標(biāo)。由FBS編碼規(guī)則可知，單元A的左下角為直角坐標(biāo)系原點(diǎn)處，具體求解步驟如下(以圖4為例)。

(1) 單元A的寬度已知，即hA=H，長lA=SA/hA，則單元A的坐標(biāo)(xA，yA)=(SA/(2hA)，H/2)。

(2)計(jì)算第二列單元坐標(biāo)。由于lB=lC=lD，SB/lB+SC/lC+SD/lD=H，因此lB=lC=lD=(SB+SC+SD)/H，hB=SBH/(SB+SC+SD)，hC=SCH/(SB+SC+SD)，hD=SDH/(SB+SC+SD)。則第二列各單元坐標(biāo)：(xD，yD)=(lA+(SB+SC+SD)/(2H)，hD/2),(xC，yC)=(lA+(SB+SC+SD)/(2H)，hD+hC/2),(xB，yB)=(lA+(SB+SC+SD)/(2H)，hD+hC+hB/2)。

(3)依次計(jì)算剩余單元的坐標(biāo)。

(4)根據(jù)式(14)、式(15)，排除不符合約束的染色體，如兩長度足夠小且相鄰的單元，其單元間距有可能不滿足位置約束。

在FBS編碼前提下計(jì)算精確位置，能夠最大限度地減少不滿足間距約束的染色體生成，提高編碼的效率與有效性。

2.3 模糊聚類操作

與傳統(tǒng)聚類算法對數(shù)據(jù)的硬劃分不同，模糊聚類是依據(jù)多個(gè)聚類特征的綜合隸屬度進(jìn)行聚類，是一種分類界限模糊化處理的軟劃分[22]。由于布局問題復(fù)雜多變，故允許同一布局方案(染色體)同時(shí)處于多個(gè)分類，避免算法陷入局部最優(yōu)陷阱。參考GARCIAHERNANDEZ等[8]提出的聚類方法，引入模糊C-均值聚類算法，算法模型如下：

(16)

s.t.

(17)

(18)

(19)

式中,FC為聚類目標(biāo)函數(shù)，用來衡量聚類特征綜合相異程度；V為數(shù)據(jù)個(gè)數(shù);K為聚類中心的個(gè)數(shù);g為聚類特征類別;z為聚類特征;vr為第r個(gè)數(shù)據(jù);ch為模糊組h的聚類中心;urh(v)為隸屬度函數(shù)，表示第r個(gè)數(shù)據(jù)點(diǎn)隸屬于第h個(gè)聚類中心的程度;vrg為以特征g為分類指標(biāo)時(shí)的第r個(gè)數(shù)據(jù);chg為以特征g為分類指標(biāo)時(shí)模糊組h的聚類中心；z為聚類特征個(gè)數(shù)，以單位面積布置成本、單位產(chǎn)品物流成本、布局熵為聚類特征，即z=3；f為大于1的模糊參數(shù)，取值為2。

圖5為初始種群模糊聚類為若干元胞種群示意圖。通過各染色體的單位面積布置成本、單位物流成本以及布局熵的值計(jì)算染色體隸屬度，并做劃分處理，得到的各種群存在內(nèi)部相似性最大，種群間差異性最大的特點(diǎn)。

圖5 初始化種群元胞組合示意圖Fig.5 Initialized population cell assembly schematic

2.4 進(jìn)化算子

選擇、交叉、變異的操作過程是同時(shí)在各自元胞種群中獨(dú)立完成的，這三步操作環(huán)境相對封閉，既能最大程度地保證各組特征的遺傳，也為元胞種群間的協(xié)作進(jìn)化奠定基礎(chǔ)。

(1)選擇算子。選擇過程既要保證各自元胞種群特征的遺傳，也需要引導(dǎo)種群向最優(yōu)Pareto解進(jìn)化。本文采用錦標(biāo)賽法，該方法是基于個(gè)體的秩與隸屬度對父代種群進(jìn)行選擇的。步驟為：①根據(jù)個(gè)體的支配關(guān)系，對種群分層，確定個(gè)體的秩，第一層秩為1，依次遞增；②選出當(dāng)前個(gè)體的鄰居個(gè)體，比較鄰居個(gè)體的秩，秩越小則個(gè)體性能越優(yōu)秀，保留下來；③若與鄰居個(gè)體的秩相等，則比較它們的種群隸屬度，隸屬度越大的個(gè)體表明與中心個(gè)體性能越接近，保留。由①、②、③三步確定出優(yōu)秀個(gè)體。

(2)交叉算子。根據(jù)編碼方式的特殊性，采用兩種不同的交叉算子進(jìn)行交叉。針對單元排序部分，采用部分映射交叉算子可以有效地避免交叉后設(shè)備的重復(fù)性。針對單元分割點(diǎn)部分，采用多點(diǎn)交叉算子交換片段。

(3)變異算子。針對單元排序部分，為了避免變異后的單元排序中有重復(fù)單元編號，采用單元交換法：任意選取同一染色體兩個(gè)單元位，交換單元位置。針對單元分割點(diǎn)部分，采用基因位0-1轉(zhuǎn)換法：依據(jù)概率任意選擇基因位，將0轉(zhuǎn)換為1，將1轉(zhuǎn)換為0。

2.5 多元胞差分重插入操作

為保證子代染色體數(shù)量保持不變和種群多樣性，每一輪進(jìn)化完成后需補(bǔ)充若干新個(gè)體進(jìn)入種群池。多元胞差分利用各元胞中個(gè)體的距離與方向的優(yōu)勢信息，具有全局并行搜索的優(yōu)點(diǎn)。具體操作如下。

在第G+1代重插入開始之前，首先從3組元胞種群中各隨機(jī)選擇一個(gè)個(gè)體作為父代個(gè)體，記作f1，i(G)、f2，i(G)、f3，i(G)，i=1，2，…，f1，i(G)表示第i次重插入時(shí)從第G代種群的第1個(gè)元胞中隨機(jī)選擇的父代個(gè)體。判斷是否存在全局支配解。

(1)如存在全局支配解則將其定義為fbest，變異按下式規(guī)則操作：

fi(G+1)=αfbest+(1-α)(f1，i(G)+
F(f2，i(G)-f3，i(G)))

(20)

(2)若不存在全局支配解，則變異按下式規(guī)則操作：

fi(G+1)=f1，i(G)+s(f2，i(G)-f3，i(G))

(21)

式(20)表示取父代個(gè)體f2，i(G)、f3，i(G)的差值，將其縮放的結(jié)果直接加到個(gè)體f1，i(G)上獲得新個(gè)體，再將其與全局支配解進(jìn)行交叉，獲得變異后的個(gè)體。α為貪婪因子(α∈(0,1))，α值越大，表示保留全局支配解的基因片段越多；s表示縮放因子，為一個(gè)確定的常數(shù)，s∈[0,1]；fi(G+1)表示第(G+1)代第i個(gè)變異個(gè)體。式(21)表示取父代個(gè)體f2，i(G)、f3，i(G)的差值，將其縮放的結(jié)果直接加到父代個(gè)體f1，i(G)上獲得新個(gè)體。

經(jīng)測試，改進(jìn)后的多元胞差分重插入操作充分利用了各優(yōu)勢種群的全局非支配解集，確保優(yōu)勢基因的遺傳，提高了解的質(zhì)量。圖6為多元胞差分重插入操作示意圖。

圖6 重插入操作示意圖Fig.6 Reinsertion operation schematic

2.6 移民策略

各元胞之間存在最大差異性，且各元胞內(nèi)均有屬于自己的Pareto解，為使這些“精英染色體”得到最大程度的遺傳并對種群起到導(dǎo)向進(jìn)化的作用，需在下一代進(jìn)化開始之前，進(jìn)行優(yōu)秀個(gè)體的移民操作。具體如下：隨機(jī)排列元胞種群并連接組成環(huán)狀拓?fù)浣Y(jié)構(gòu)，為元胞間指定某種遷移拓?fù)洌_定個(gè)體交換的方式。移民路徑如圖7所示，圖中,k1、k2、k3表示按比例從各組元胞種群中復(fù)制的優(yōu)秀個(gè)體數(shù)量。

圖7 染色體移民示意圖Fig.7 Chromosome migration diagram

2.7 循環(huán)終止條件

循環(huán)執(zhí)行模糊聚類、選擇、交叉、變異、移民等操作，算法迭代niter次或在迭代過程中連續(xù)mopt次產(chǎn)生PN條Pareto解集，則進(jìn)化結(jié)束。

3 算法步驟與流程

算法流程如圖8所示。

(1)利用FBS編碼隨機(jī)產(chǎn)生一定規(guī)模的種群。

(2)計(jì)算所有染色體的f1、f2、f3的目標(biāo)值，運(yùn)用模糊C-均值聚類算法，對所有染色體聚類，分為PC組種群元胞，文中取PC=3。

(3)各元胞同時(shí)進(jìn)行獨(dú)立的選擇、交叉、變異。

(4)重插入操作。按照多元胞差分操作規(guī)則，生成一定數(shù)量的新個(gè)體平均分配給各元胞。

(5)將各元胞組成環(huán)狀拓?fù)浣Y(jié)構(gòu)，對環(huán)狀鄰域種群元胞進(jìn)行精英個(gè)體的移民操作。

(6)如果算法迭代niter次或在迭代過程中連續(xù)mopt次產(chǎn)生PN條Pareto解集則結(jié)束計(jì)算，輸出Pareto解集，否則返回步驟(2)，進(jìn)行下一輪進(jìn)化。

圖8 算法流程Fig.8 Algorithm flow

4 算法性能分析與算例驗(yàn)證

為驗(yàn)證本文算法的性能，選用一個(gè)多約束、多變量的雙目標(biāo)測試函數(shù)ZDT3和一個(gè)高維多目標(biāo)函數(shù)DTLZ2[23]，分別利用文獻(xiàn)[13]的MOPSO、文獻(xiàn)[14]的NSGAⅡ以及本文的CPMGAs對上述測試函數(shù)進(jìn)行計(jì)算，并分析相同評價(jià)體系下三種算法的性能。

4.1 算法性能評價(jià)指標(biāo)

采用分布指標(biāo)[23]、世代距離和超體積指標(biāo)對算法性能進(jìn)行評價(jià)[24]。

(1)分布指標(biāo)TD。分布指標(biāo)用來衡量獲得的Pareto前沿的分布情況，該指標(biāo)的值越小，表明Pareto前沿分布越均勻，且

(22)

(2)世代距離GD。世代距離用來計(jì)算所得的Pareto前沿收斂到最優(yōu) Pareto前沿的程度，GD越小，解的收斂性越好,且

(23)

式中，n為近似Pareto前沿中個(gè)體的數(shù)目；di為第i個(gè)解的目標(biāo)函數(shù)構(gòu)成的向量與Pareto最優(yōu)前沿之間的最近距離。

(3)超體積。超體積(HV)用來計(jì)算獲得的Pareto前沿在目標(biāo)空間所覆蓋的體積。超體積越大，說明獲得的Pareto前沿的多樣性、收斂性越好，有

(24)

在三維目標(biāo)空間中，Q表示所有Pareto解的個(gè)數(shù)，Vi是由參考點(diǎn)W與解i的目標(biāo)向量作為對角點(diǎn)所形成的長方體的體積。為方便處理，將最差的分目標(biāo)值構(gòu)成的一個(gè)向量作為參考點(diǎn)W，合并所有Vi得到HV。

4.2 算法測試結(jié)果及性能分析

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

表1 ZDT3與DTLZ2基準(zhǔn)測試函數(shù)Tab.1 ZDT3 and DTLZ2 benchmark functions

NSGA Ⅱ、MPSO、CPMGAs算法參數(shù)設(shè)置如下：均采用實(shí)數(shù)編碼，多項(xiàng)式變異；采用模擬二進(jìn)制交叉；MPSO算法的學(xué)習(xí)因子均取0.8；CPMGAs的元胞種群分組取PC=3，移民率為各元胞的5%；交叉概率取0.8，變異概率取0.3，種群規(guī)模取100，進(jìn)化代數(shù)為50。三種算法對測試函數(shù)ZDT3和DTLZ2均進(jìn)行20次測試，表2表示三種性能指標(biāo)統(tǒng)計(jì)結(jié)果均值。圖9、圖10分別表示測試函數(shù)ZDT3和DTLZ2的Pareto解前沿分布。

表2 算法有效性分析表Tab.2 Algorithm validity analysis table

(a)NSGAⅡ算法Pareto解集前沿

(b)MPSO算法Pareto解集前沿

(c)CPMGAs算法Pareto解集前沿圖9 NSGAⅡ、MPSO、CPMGAs算法在ZDT3上的Pareto前沿對比圖Fig.9 Pareto frontier contrast diagram of NSGA Ⅱ、 MPSO、CPMGAs algorithm on ZDT3

(a)NSGAⅡ算法Pareto解集前沿

(b)MPSO算法Pareto解集前沿

(c)CPMGAs算法Pareto解集前沿圖10 NSGAⅡ、MPSO、CPMGAs算法在DTLZ2上的Pareto前沿對比圖Fig.10 Pareto frontier contrast diagram of NSGA Ⅱ、MPSO、CPMGAs algorithm on DTLZ2

由圖9、圖10定性分析三種算法性能的對比結(jié)果可知：NSGAⅡ算法的收斂性最差，解集多樣性好，但分布不均；MPSO算法的收斂性較好且解集的分布均勻性能好；本文提出的CPMGAs的收斂性比NSGAⅡ算法好，與MPSO算法具有相同的收斂性，但解集的均勻分布性與覆蓋廣度較MPSO算法要好。

表2記錄了三種算法在測試函數(shù)ZDT3和DTLZ2上的三種性能指標(biāo)。由指標(biāo)性能的含義可知，在求解ZDT3和DTLZ2函數(shù)時(shí)，CPMGAs算法在收斂性(GD)和分布均勻性(TD)上比其他兩種算法更優(yōu)，雖然在求解ZDT3函數(shù)上，MPSO算法也表現(xiàn)了較好的收斂性(GD)，但CPMGAs的標(biāo)準(zhǔn)差更小，說明在收斂性上表現(xiàn)更加穩(wěn)定。在分布均勻性(TD)上，MPSO算法在ZDT3函數(shù)上表現(xiàn)最佳，而CPMGAs算法在DTLZ2函數(shù)上表現(xiàn)最佳，說明二者在解集分布均勻性上均有良好性能但不夠穩(wěn)定。CPMGAs算法在覆蓋范圍(HV)上表現(xiàn)出最佳性能，是因?yàn)樵谀：垲惒僮髦?，各元胞種群間存在最大差異性，且多元胞差分進(jìn)化重插入與移民操作保證了種群的多樣性與分布均勻性。因此本文的CPMGAs算法總體上能夠滿足求解多目標(biāo)、多維度非線性問題，且具有良好的性能。

4.3 算例驗(yàn)證

為進(jìn)一步驗(yàn)證算法的有效性，本文選用國際上公布的旅行商問題(traveling salesman problem,TSP)標(biāo)準(zhǔn)測試庫(TSPLIB)中的8組算例(oliver30，eil51，rand100，rand300，kroab100，kroac100，krobc100，kroab200)進(jìn)行算例驗(yàn)證，并與文獻(xiàn)[25]提出的混合遺傳算法(hybrid genetic algorithm,HGA)進(jìn)行結(jié)果的對比與驗(yàn)證。

參考文獻(xiàn)[25]，算例中的目標(biāo)1為最小化總距離，目標(biāo)2為最小化總成本。針對算例oliver30、eil51、rand100、rand300，與目標(biāo)1相關(guān)任意兩點(diǎn)坐標(biāo)值由標(biāo)準(zhǔn)庫所給，與目標(biāo)2相關(guān)的任意兩點(diǎn)成本值隨機(jī)生成[25]。采用超體積(HV)、計(jì)算時(shí)間(t)、相對誤差(e)三個(gè)指標(biāo)驗(yàn)證本文算法解的質(zhì)量。指標(biāo)e的定義如下：

其中，f1為只考慮單目標(biāo)TSP問題時(shí)目標(biāo)1的最優(yōu)值(由TSPLIB給出)，f2為考慮雙目標(biāo)TSP問題時(shí)目標(biāo)1的最優(yōu)值，由算法計(jì)算所得。測試過程中，HGA算法的參數(shù)設(shè)置與文獻(xiàn)[25]一致，本文算法參數(shù)與4.1.2節(jié)一致。種群規(guī)模取50，針對算例oliver30、eil50,迭代次數(shù)取200，其余算例取500。每個(gè)算例各單獨(dú)測試10次，取指標(biāo)均值，測試結(jié)果如表3所示。

表3 算例驗(yàn)證結(jié)果對比表Tab.3 Examples comparison of verification results

由表3可知，本文算法CPMGAs在超體積(HV)指標(biāo)上的值比文獻(xiàn)[25]的HGA更高，說明解的空間范圍更廣，驗(yàn)證了本文算法在計(jì)算結(jié)果的多樣性與收斂性方面更好；在計(jì)算時(shí)間上，因?yàn)榇嬖诰垲?、移民等多步操作，CPMGAs所耗費(fèi)的計(jì)算時(shí)間更長。在相對誤差e上，CPMGAs的值普遍更小，進(jìn)一步論證了本文算法在多樣性與收斂性上具有一定的優(yōu)勢。因此CPMGAs算法以相對較長的計(jì)算時(shí)長為代價(jià)，換來計(jì)算多樣性與收斂性上的相對優(yōu)勢，能較好地滿足離散組合優(yōu)化問題的需求。

5 企業(yè)應(yīng)用分析

將多目標(biāo)布局模型應(yīng)用于企業(yè)布局中，研究模型的實(shí)用性。 A公司目前的生產(chǎn)裝配車間仍是以大規(guī)模重復(fù)的生產(chǎn)作業(yè)方式來滿足客戶的訂單需求。車間的總面積為100×100 m2，包括15個(gè)功能單元區(qū)域。車間物流量關(guān)系如表4所示，車間功能單元約束如表5所示，其中，S1、S2、…、S5表示5類產(chǎn)品編號。Y表示Yes，N表示No。車間布局現(xiàn)狀如圖11所示，其中，F(xiàn)1、F2、…、F5表示單元內(nèi)的設(shè)備編號。

表4 車間單元間物流量關(guān)系Tab.4 Relationship of material flow among units in workshop (104元·件/m)

表5 產(chǎn)品功能單元約束Tab.6 The constraint of functional unit

圖11 車間布局現(xiàn)狀圖Fig.11 Workshop layout map

利用本文模型與算法進(jìn)行布局優(yōu)化，參數(shù)選取：種群規(guī)模M=1 000，聚類數(shù)p=3，交叉概率Pc=0.75，變異概率Pm=0.001，移民率Y=5%，課題組在企業(yè)實(shí)地調(diào)研后，取ηopt=4/3，ηmax=5，迭代次數(shù)niter=100，用MATLAB2010a仿真計(jì)算。由于布局問題的復(fù)雜性，以算法產(chǎn)生的Pareto解作為最優(yōu)解集，如圖12所示。

圖12 布局多目標(biāo)Pareto解集前沿Fig.12 Layout multi-objective pareto solution frontier

因進(jìn)化過程中的低熵化引導(dǎo)，所產(chǎn)生的布局方案的布局熵均在[0.2,0.8]的合理區(qū)間范圍內(nèi)，說明布局方案均有較高的穩(wěn)定性。圖13表示子目標(biāo)f1與f2的解集前沿，可以看出，左上方的解具有較低的單元布置成本與較高的物流成本；右下角的解具有較高的單元布置成本與較低的物流成本。目標(biāo)空間的解集能為決策者根據(jù)自己偏好提供有效布局解。解碼，得到部分布局解。

圖13 布局子目標(biāo)f1與f2的Pareto解集前沿Fig.13 The Pareto solution frontier of layout subtargets f1 and f2

表6提供了部分Pareto解，選擇序號1為實(shí)例布局解進(jìn)行解碼，考慮車間運(yùn)輸工具等原因，規(guī)定車間長度方向、寬度方向最小間距分別是4.5 m和2.5 m，邊界間距均為5 m，解碼得到實(shí)際布局如圖14所示。

表6 Pareto解集Tab.6 Pareto solution sets

圖14 優(yōu)化后的車間實(shí)際布局Fig.14 Optimized workshop layout

6 結(jié)語

隨著制造業(yè)的發(fā)展，企業(yè)不僅需要面對復(fù)雜多樣的需求波動(dòng)，也需要低成本、高穩(wěn)健發(fā)展以滿足可持續(xù)性。提出單位面積布置成本、單位產(chǎn)品物流成本與布局熵為目標(biāo)的車間布局優(yōu)化模型，設(shè)計(jì)聚類并行多目標(biāo)遺傳算法，進(jìn)行算例論證和實(shí)例驗(yàn)證，有效降低了布置成本、物流成本，提高了布局穩(wěn)定性，表明算法和模型的有效性和可靠性。但本文的布局過程中并沒有與產(chǎn)品的動(dòng)態(tài)調(diào)度相結(jié)合，同時(shí)也假設(shè)了單元的規(guī)則性，在一定程度上限制了應(yīng)用，在今后研究中，可以注重這一方面的研究。