基于改進(jìn)粒子群-禁忌搜索算法的FMS布局優(yōu)化*

彭正超，胡曉兵，周韶武，殷 鳴，李彥儒

(1.四川大學(xué)機(jī)械工程學(xué)院，成都 610065；2.中國核動(dòng)力研究設(shè)計(jì)院，成都 610213)

0 引言

柔性制造系統(tǒng)(Flexible Manufacturing System, FMS)是典型機(jī)電液組成的復(fù)雜大系統(tǒng)，其中設(shè)備的布局是FMS設(shè)計(jì)過程中最重要的設(shè)計(jì)決策環(huán)節(jié)，設(shè)備布局的優(yōu)良直接決定了FMS機(jī)床利用率的高低和投資回收周期的長短。設(shè)備的布局通?？紤]待加工零件(族)加工過程的物流成本。傳統(tǒng)柔性制造系統(tǒng)的設(shè)計(jì)過程往往依賴于經(jīng)驗(yàn)，存在設(shè)計(jì)周期長、無法保證方案最優(yōu)等問題，因此這類復(fù)雜系統(tǒng)的快速、高效設(shè)計(jì)是數(shù)字化設(shè)計(jì)領(lǐng)域的技術(shù)難點(diǎn)與發(fā)展方向。

對(duì)于FMS布局優(yōu)化設(shè)計(jì)的研究，Yang T等[1]研究了單回路定向物流模式FMS的開放場地式布局設(shè)計(jì)；Qudeiri J A等[2]利用遺傳算法和神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)了動(dòng)態(tài)環(huán)境下FMS的布局優(yōu)化設(shè)計(jì)；對(duì)于一般的生產(chǎn)線布局問題，以總物流量最小為優(yōu)化目標(biāo)，李建榮等[3]使用粒子群算法(PSO)求解單行布局；王明超等[4]和Hu B等[5]使用改進(jìn)的遺傳算法(GA)和粒子群算法求解多行布局問題。鄧兵等[6]和黃淇等[7]將遺傳算法與系統(tǒng)布置設(shè)計(jì)法(SLP)結(jié)合求解布局問題。文獻(xiàn)[8-10]分別采用吸收了遺傳算法中交叉操作算子的改進(jìn)粒子群算法、模擬退火算法(SA)改進(jìn)的粒子群算法、動(dòng)態(tài)改變慣性因子和粒子飛行情況的粒子群算法求解布局問題。房殿軍等[11]將設(shè)施規(guī)劃與生產(chǎn)調(diào)度并行進(jìn)行，對(duì)多行設(shè)施布局和混流生產(chǎn)線分別建模，利用路徑系數(shù)對(duì)物料流向進(jìn)行優(yōu)化，物流距離與物流量數(shù)據(jù)相互傳遞與迭代。Benderbal H H等[12]求解機(jī)器布局時(shí)采用多目標(biāo)模擬退火(AMOSA)，將機(jī)器平均使用量的最大化也作為優(yōu)化目標(biāo)。以上研究對(duì)于多行生產(chǎn)線與FMS布局研究較少，且采用的啟發(fā)式算法的性能有待改進(jìn)。

針對(duì)待加工零件(族)的工藝特性已知，且加工設(shè)備型號(hào)與數(shù)量選定的FMS的多行布局優(yōu)化問題，本文提出了一種改進(jìn)的粒子群-禁忌搜索算法算法，引入自適應(yīng)變異算子對(duì)粒子的位置進(jìn)行隨機(jī)變異，并將得到的優(yōu)化結(jié)果進(jìn)行禁忌搜索，提高算法的局部搜索能力和尋優(yōu)質(zhì)量。

1 FMS布局優(yōu)化問題描述和數(shù)學(xué)建模

1.1 問題描述

FMS的設(shè)計(jì)過程中，確定各制造單元的位置布局，以保證在加工過程中物料的運(yùn)輸物流成本最低很關(guān)鍵。常見的FMS的設(shè)備布局有4種方式：單行直線布局、環(huán)形布局、階梯形布局(多行直線布局)、開放場地布局[1]。為考慮布局問題的一般性，擬以多行直線布局為主要研究對(duì)象。作出如下假定：

①用長和寬已知的矩形來抽象化制造單元的具體形狀；

②同一行的制造單元的中心位于同一條直線上，行與行間距固定；

③各制造單元的長邊與水平方向平行，短邊與豎直方向平行；

④各制造單元間保持固定間隔，位于布局場地四周的制造單元與場地外圍的水平方向和豎直方向保持固定間隔。

FMS多行直線布局的拓?fù)淠Ｐ腿鐖D1所示。以FMS設(shè)備間物流成本最小為優(yōu)化目標(biāo)，優(yōu)化各制造單元的布局，是典型的NP hard問題。

圖1 FMS多行直線布局的拓?fù)淠Ｐ?/p>

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

定義布局場地的長和寬分別為L和H，m個(gè)待加工零件構(gòu)成待加工零件集合p={p1,p2, …,pm}，其中n個(gè)制造單元構(gòu)成制造單元集合M={M1,M2, …,Mn}。制造單元長度和寬度集合分別為l={l1,l2, …,ln}和h={h1,h2, …,hn}，制造單元i中心坐標(biāo)為(xmi,ymi)。

設(shè)多行直線布局的行數(shù)為r，每個(gè)單元所在的行數(shù)為α(α=1, 2, …,r)，每行允許排列最大單元數(shù)為K，第一行的豎直坐標(biāo)為y1，行與行間的距離為d0，制造單元間的最小距離為Δ，制造單元在水平方向和豎直方向與布局場地外圍的最小距離分別為Δx和Δy。排列在第α行第i個(gè)位置的制造單元對(duì)應(yīng)的長度和寬度為lmi∈l、hmi∈h，其中心坐標(biāo)計(jì)算公式為：

(1)

(2)

任意兩個(gè)制造單元i與j間的物流距離可以表達(dá)為：

dij=|xmi-xmj|+|ymi-ymj|

(3)

單位距離制造單元i到j(luò)間總物流系數(shù)可以表達(dá)為：

(4)

為了最小化制造單元間物料搬運(yùn)的總成本，布局問題的目標(biāo)函數(shù)如下：

(5)

約束條件：

(1)制造單元位置不超過布局場地外圍

(6)

由于各制造單元在豎直方向的坐標(biāo)yi在確定每行的位置時(shí)已經(jīng)確定，可不再考慮，故約束條件式(6)可簡化為：

(7)

(2)制造單元間不干涉

(8)

其中，zij用于表征制造單元i和j是否布局在同一行，當(dāng)yi=yj時(shí)取1，否則取0。

2 改進(jìn)粒子群-禁忌搜索算法

2.1 標(biāo)準(zhǔn)粒子群算法

由于粒子群算法具有較快的計(jì)算速度和較好的全局搜索能力，與進(jìn)化算法相比避免了復(fù)雜的遺傳操作，因此作為FMS布局優(yōu)化的基本算法。

n維目標(biāo)搜索空間中，N個(gè)粒子組成一個(gè)群，第i個(gè)粒子的位置記為Xi=(xi1,xi2, …,xin)，速度記為Vi=(vi1,vi2, …,vin)，迄今搜索到的個(gè)體極值記為pbest=(pi1,pi2, …,pin)，整個(gè)粒子群迄今搜索到的全局極值記為gbest=(g1,g2, …,gN)。粒子通過迭代尋優(yōu)，每一次迭代中跟蹤個(gè)體極值pbest和全局極值gbest來更新空間位置和飛行速度:

vij(t+1)=wvij(t)+c1rand1( )[pij(t)-xij(t)]+
c2rand2( )[gj(t)-xij(t)]

(9)

xij(t+1)=xij(t)+vij(t+1)

(10)

(11)

式中，c1和c2為學(xué)習(xí)因子；rand1( )和rand2( )是[0,1]內(nèi)的均勻隨機(jī)數(shù)；w為慣性權(quán)重，在搜索過程中根據(jù)式(11)動(dòng)態(tài)調(diào)整；t為當(dāng)前迭代次數(shù)；T為最大迭代次數(shù)。

2.2 改進(jìn)算法設(shè)計(jì)

由于粒子群算法具有早熟收斂、局部搜索能力弱容易陷入局部最優(yōu)等缺點(diǎn)，對(duì)粒子群算法進(jìn)行改進(jìn)，提出一種新的基于自適應(yīng)變異的改進(jìn)粒子群-禁忌搜索算法(AMPSO-TS)。改進(jìn)如下：一是借鑒其他啟發(fā)式算法[13]引入變異操作，在粒子群算法進(jìn)化過程中對(duì)得到的每個(gè)粒子的位置以一定概率進(jìn)行變異操作，提高粒子種群的多樣性；二是引入禁忌搜索算法，將粒子群算法得到的收斂的全局極值gbest使用禁忌搜索進(jìn)行鄰域解搜索，提高算法跳出局部最優(yōu)解的能力。

改進(jìn)算法流程圖如圖2所示，步驟如下：

步驟1：初始化算法參數(shù)，隨機(jī)生成粒子的初始位置和速度；

步驟2：計(jì)算每個(gè)粒子的適應(yīng)度值fit[i]；

步驟3：對(duì)每個(gè)粒子，比較fit[i]和個(gè)體極值pbest(i)。如果fit[i]

步驟4：對(duì)每個(gè)粒子，判斷是否符合變異條件，如果符合進(jìn)入步驟5；

步驟5：對(duì)pbest(i)進(jìn)行變異操作，如果變異后的粒子適應(yīng)度值更優(yōu)則保留變異，否則取消當(dāng)前變異；

步驟6：將所有粒子的最優(yōu)值中最優(yōu)的個(gè)體存儲(chǔ)在全局最優(yōu)gbest中；

步驟7：更新每個(gè)粒子的位置和速度；

步驟8：進(jìn)行邊界條件處理；

步驟9:判斷是否滿足粒子群迭代終止條件：若是，則結(jié)束粒子群算法迭代進(jìn)入下一步；否則返回步驟2；

步驟10:將得到的最佳微粒解碼，進(jìn)行禁忌搜索；

步驟11:禁忌搜索操作結(jié)束，輸出結(jié)果。

圖2 改進(jìn)粒子群禁忌搜索算法(AMPSO-TS)流程圖

針對(duì)FMS布局優(yōu)化問題，在粒子群編碼時(shí)將離散的布局問題進(jìn)行連續(xù)化處理。制造單元數(shù)量為D，粒子的搜索空間為D維，粒子的位置Xi=(xi1,xi2, …,xiD)初始化時(shí)隨機(jī)生成在某個(gè)范圍內(nèi)的實(shí)數(shù)。用隨機(jī)生成的實(shí)數(shù)的排序后其原來的位置映射制造單元的序號(hào)。采用自動(dòng)換行原則[8]，當(dāng)某一行制造單元排滿后，自動(dòng)換行排列到下一行。如某粒子的位置為(6.2295、5.9421、5.1011、8.5432、7.4442、9.5082、5.3451、5.5942、0.4734、7.3808)，按數(shù)值從小到大排序后的元素在原編碼中的位置 (9, 3, 7, 8, 2, 1, 10, 5, 4, 6)作為解碼，每個(gè)數(shù)字對(duì)應(yīng)加工單元的編號(hào)。當(dāng)所需排列的單元數(shù)小于行數(shù)×每行最大制造單元數(shù)時(shí)，在解碼后隨機(jī)填充空位數(shù)個(gè)0表示該位置空缺，計(jì)算中心坐標(biāo)和適應(yīng)度值時(shí)跳過空位。

引入變異操作來提高粒子種群的多樣性，避免算法早熟和陷入局部收斂[14]。為了提高算法效率，保證變異操作盡可能發(fā)生在收斂前，引入自適應(yīng)變異因子來約束變異的發(fā)生。自適應(yīng)變異因子為：

(12)

式中,t為當(dāng)前迭代次數(shù)，T為總迭代次數(shù)；λ為調(diào)節(jié)系數(shù)常量，用于調(diào)節(jié)δ的取值位于[0, 1]間，可取λ=1/e。變異發(fā)生在前若干次迭代且以一定的概率變異的條件可以歸納為：

(13)

式中,δ0為允許變異因子常量，只有當(dāng)變異因子δ<δ0時(shí)才允許變異；pm為變異概率。變異操作采用柯西變異(Cauchy mutation)，柯西變異是基于柯西密度函數(shù)的，關(guān)于原點(diǎn)對(duì)稱的一維柯西密度函數(shù)為：

(14)

變異操作采用對(duì)粒子個(gè)體的位置進(jìn)行變異，避免對(duì)個(gè)體極值變異使算法得到小于真實(shí)最小值的解，變異按如下式進(jìn)行[15]：

x'ij(i)=xij(i)+scCi

(15)

(16)

式中,Ci是柯西隨機(jī)變量；sc為變異步長；rand(+,-)表示隨機(jī)取正負(fù)號(hào)；ωc是[0,fcauchy(0)]中均勻產(chǎn)生的隨機(jī)數(shù)。

禁忌搜索操作流程如圖3所示。將粒子群迭代得到的最優(yōu)解微粒的解碼后的序列作為禁忌搜索的初始解。定義鄰域映射為2-opt (2-Optimization) 形式，即初始解中兩個(gè)單元排列位置進(jìn)行對(duì)換。產(chǎn)生Ca個(gè)候選解，并保留前Ca/2個(gè)最好候選解。每一次迭代都會(huì)進(jìn)行2-opt操作，某次搜索的其迭代過程中2-opt操作如圖4所示。

圖3 禁忌搜索流程圖

圖4 禁忌搜索2-opt操作產(chǎn)生候選解過程

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

(17)

將算法運(yùn)行10次，得到10組最優(yōu)的布局方案如表1所示，對(duì)應(yīng)記錄算法進(jìn)行禁忌搜索前得到的最優(yōu)解如表2所示。表中的1-1表示第一行第1個(gè)位置，以此類推。

表1 AMPSO-TS得到的最優(yōu)布局方案

表2 禁忌搜索前得到的最優(yōu)解

表1中除實(shí)驗(yàn)(1)外其余9次均收斂到了適應(yīng)度最小值19 972。對(duì)比分析表1和表2中對(duì)應(yīng)適應(yīng)度值：實(shí)驗(yàn)(1)粒子群階段(前120次迭代)收斂并進(jìn)行禁忌搜索得到了更小的適應(yīng)度值，但最終的收斂值大于適應(yīng)度的最小值，其適應(yīng)度進(jìn)化曲線如圖5a所示；實(shí)驗(yàn)(2)、(3)、(5)、(8)在進(jìn)行禁忌搜索前(前120次迭代)算法已收斂到適應(yīng)度最小值，其中實(shí)驗(yàn)(5)的適應(yīng)度進(jìn)化曲線如圖5b所示。實(shí)驗(yàn)(4)、(6)、(7)、(9)、(10)在進(jìn)行禁忌搜索前(前120次迭代)雖然已收斂但未收斂到適應(yīng)度最小值，在進(jìn)行禁忌搜索后得到了適應(yīng)度最小值，其中實(shí)驗(yàn)(9)、(10)的適應(yīng)度進(jìn)化曲線如圖5c、圖5d所示。結(jié)果表明， 60%的情況下禁忌搜索對(duì)算法得到更優(yōu)的適應(yīng)度值起到積極作用。

進(jìn)入禁忌搜索前(前120次迭代)，圖5a和圖5c中，粒子群階段很快收斂，圖5b和圖5d中適應(yīng)度值隨著迭代保持短暫穩(wěn)定后突變，是由于變異操作帶來的，避免了算法進(jìn)入局部收斂，得到了更優(yōu)的適應(yīng)度值。

(a) 實(shí)驗(yàn)(1) (b) 實(shí)驗(yàn)(5)

(c) 實(shí)驗(yàn)(9)(d) 實(shí)驗(yàn)(10)圖5 適應(yīng)度進(jìn)化曲線

為了驗(yàn)證AMPSO-TS算法的性能提升，將本文算法與標(biāo)準(zhǔn)PSO進(jìn)行對(duì)比，適應(yīng)度進(jìn)化曲線如圖6所示。算法的收斂速度的差異較小，標(biāo)準(zhǔn)PSO得到的最優(yōu)解適應(yīng)度為20 114，AMPSO-TS得到的最優(yōu)解適應(yīng)度值為19 972，得到了更優(yōu)的適應(yīng)度值。

圖6 AMPSO-TS與標(biāo)準(zhǔn)PSO對(duì)比

對(duì)表1中的最優(yōu)布局進(jìn)行修正，選取出現(xiàn)概率最大的設(shè)備為該位置的設(shè)備。當(dāng)出現(xiàn)概率相同時(shí)，跳過該位置選定其它位置后再確定該位置；若出現(xiàn)兩個(gè)位置兩種設(shè)備出現(xiàn)的概率相同時(shí)則隨機(jī)選取。修正后的布局方案序列為(1、2、3、9、6、4、8、5、10、7)，記為最終布局方案，如圖7所示。

圖7 最終布局方案

4 結(jié)論

(1)改進(jìn)粒子群-禁忌搜索算法，引入了自適應(yīng)變異操作和禁忌搜索策略，提高了粒子的多樣性，避免了粒子“早熟”快速收斂陷入局部最優(yōu)，同時(shí)增加鄰域搜索策略來提高粒子群算法的局部搜索能力，使得算法精度和尋優(yōu)質(zhì)量有所提高。

(2)以某機(jī)床箱體類零件FMS為計(jì)算實(shí)例，使用改進(jìn)粒子群-禁忌算法求解FMS布局優(yōu)化問題，解決了在待加工零件(族)及其工藝路線已知且FMS中制造單元數(shù)量和種類選定后，對(duì)FMS布局優(yōu)化的實(shí)際工程問題，快速準(zhǔn)確得到可靠的多行優(yōu)化布局方案，降低了FMS總物流成本。