文笑雨， 羅國富， 李 浩， 肖艷秋， 喬東平， 李曉科

(鄭州輕工業(yè)學(xué)院 河南省機(jī)械裝備智能制造重點(diǎn)實驗室，河南 鄭州 450002)

0 引言

工藝規(guī)劃的輸入是產(chǎn)品的設(shè)計數(shù)據(jù)，輸出為產(chǎn)品具體的制造信息，它對制造系統(tǒng)的性能有著重要的影響[1].由于柔性制造系統(tǒng)和數(shù)控加工中心的廣泛應(yīng)用，許多零件在生產(chǎn)加工時，存在大量的柔性工藝可供選擇，同時，每道加工工序還有眾多可選的加工資源，這使得工藝規(guī)劃問題成為一個典型的NP(non-deterministic polynomial)-Complete 問題，傳統(tǒng)的方法很難有效地解決該問題[1].

近年來，越來越多的智能優(yōu)化算法被應(yīng)用于解決現(xiàn)代制造系統(tǒng)中的工藝規(guī)劃問題，如粒子群優(yōu)化(particle swarm optimization， PSO)[1]、殖民競爭算法[2]、蟻群算法[3-4]、蝙蝠算法[5]、遺傳算法[6](GA)、禁忌搜索[6](TS)和模擬退火算法[6](SA)等.在上述方法中，PSO算法是一種基于群體智能理論的優(yōu)化算法.傳統(tǒng)的PSO適合于處理連續(xù)優(yōu)化問題，隨著研究的深入，許多學(xué)者對傳統(tǒng)的PSO進(jìn)行改進(jìn)，將其廣泛應(yīng)用于諸多復(fù)雜的組合優(yōu)化問題中，如旅行商問題[7]、作業(yè)車間調(diào)度問題等[8-9].其中，高海兵等[7]提出的廣義粒子群優(yōu)化(general PSO, GPSO)模型建立了一種將PSO應(yīng)用于組合優(yōu)化問題的通用思路，在應(yīng)用GPSO模型求解工藝規(guī)劃問題時，值得進(jìn)一步去探索更加有效的粒子全局更新策略和局部搜索策略.

筆者在廣義粒子群優(yōu)化模型基礎(chǔ)上，結(jié)合工藝規(guī)劃問題的特性，設(shè)計了基于個體極值庫和種群極值庫的粒子全局更新策略，引入變鄰域搜索算法作為粒子的局部搜索策略，提出了求解工藝規(guī)劃問題的改進(jìn)GPSO(improved GPSO， IGPSO)算法，并使用已有工藝規(guī)劃文獻(xiàn)中的6個典型零件對提出的算法進(jìn)行了測試，驗證了提出算法的有效性.

1 工藝規(guī)劃問題描述

本文研究的工藝規(guī)劃問題可被描述為：某待加工零件具有多種加工特征，每種加工特征具有不同的可選加工工藝，每一種可選加工工藝可能包含多道加工工序，每道加工工序可以在若干臺可選機(jī)器上進(jìn)行加工，被加工零件的不同特征之間具有一定的次序約束關(guān)系.工藝規(guī)劃的目的是在已有加工資源和加工約束的情況下，確定被加工零件的工藝路線，從而使得某項指標(biāo)達(dá)到最優(yōu).在本文中，選擇待加工零件的加工時間作為優(yōu)化目標(biāo)，并進(jìn)行如下假設(shè)：

(1)同一零件的不同工序不能被同時加工；

(2)在0時刻，所有的機(jī)器都是可用的；

(3)每道工序的加工時間被定義為常數(shù)；

(4)一個零件在一臺機(jī)器上加工完成之后，它被立刻傳送至工藝路線中的下一臺機(jī)器，零件在不同機(jī)器之間的傳輸時間被定義為常數(shù)；

(5)機(jī)器加工每道工序的準(zhǔn)備時間和工序加工順序是相互獨(dú)立的，并被包含在每道工序的加工時間中.

為了形象地描述所研究的問題，針對某待加工零件詳細(xì)說明如何進(jìn)行工藝規(guī)劃操作.表1給出了某零件的加工工藝信息表.

該零件包含有9個加工特征，有5臺機(jī)器可供選擇對零件不同的工序進(jìn)行加工.確定該零件的工藝路線需要經(jīng)過三個步驟：第一，確定不同加工特征的順序，該順序必須滿足不同特征之間的次序約束關(guān)系；第二，確定每種加工特征具體的加工工藝；第三，對具有可選加工機(jī)器的工序確定具體的加工機(jī)器.

表1 某零件的加工工藝信息表Tab.1 Machining process information of a part

當(dāng)該零件的工藝路線確定之后，可以計算出該零件的總加工時間.基于上述問題描述，本文研究的工藝規(guī)劃問題優(yōu)化目標(biāo)為零件的總加工時間(processing time，PT)最短，具體計算方法如下所示：

MinPT=OT+TT，

(1)

式中:OT為零件的工序加工時間;TT為零件在不同機(jī)器之間的傳輸時間.

(2)

式中:OTi為工藝路線中第i道工序的加工時間；n為零件的工藝路線中包含的工序數(shù)目.

(3)

如果零件相鄰的兩道工序在不同的機(jī)器上進(jìn)行加工，則需要一定的機(jī)器傳輸時間，TTMi,Mi+1為從工藝路線中第i道工序的加工機(jī)器Mi轉(zhuǎn)換到第i+1道工序的加工機(jī)器Mi+1所需要的傳輸時間.

(4)

當(dāng)相鄰兩道工序在相同的機(jī)器上加工時，式(4)為0；當(dāng)相鄰兩道工序在不同的機(jī)器上加工時，式(4)為1.

2 IGPSO求解工藝規(guī)劃問題

2.1 廣義粒子群優(yōu)化算法模型

高海兵等[7]通過對傳統(tǒng)PSO核心優(yōu)化機(jī)理的分析，忽略粒子的具體更新策略，總結(jié)出了GPSO模型，其基本流程如圖1所示.筆者在GPSO模型下設(shè)計求解工藝規(guī)劃問題的IGPSO算法，接下來將分別介紹基于IGPSO算法的工藝規(guī)劃方法主要組成部分以及算法流程.

圖1 廣義粒子群優(yōu)化模型[7]Fig.1 General particle swarm optimization model

2.2 粒子的編碼與解碼

每一個粒子代表零件的一條具體的工藝路線，筆者采用文獻(xiàn)[1]中的編碼與解碼方法對粒子進(jìn)行編碼與解碼操作.每一個粒子包含三段長度不同的序列:第一段為特征序列；第二段為可選工藝序列，這兩段序列的長度均等于零件的總特征數(shù)；第三段為可選機(jī)器序列，該序列的長度等于零件的總工序數(shù).以表1中的零件為例，一種可行的粒子編碼方案如圖2所示.特征序列代表的含義為該零件特征加工順序為：F4-F1-F8-F7-F5-F9-F2-F3-F6.

圖2 粒子對應(yīng)的編碼方案Fig.2 Corresponding encoding scheme for a particle

可選工藝序列的第i個位置的數(shù)字k，代表了第i個特征選擇第k種可選加工工藝進(jìn)行加工，如圖2中可選工藝序列中第二個位置為2，則代表特征2從它的可選工藝集{O4-O5，O6-O7-O8}中選擇第2種加工工藝，即O6-O7-O8進(jìn)行加工.可選機(jī)器序列中第i個位置的數(shù)字k，代表了零件的第i道工序從可選加工機(jī)器集當(dāng)中選擇第k個加工機(jī)器，如圖2中可選機(jī)器序列第1個位置為2，則代表工序1從它的可選加工機(jī)器集{M1,M2}中選擇了第二個機(jī)器，即M2進(jìn)行加工.

該編碼方案經(jīng)解碼后代表所確定的零件工藝路線為:O12(M4)-O1(M2)-O17(M2)-O16(M3)-O13(M3)-O18(M3)-O6(M3)-O7(M3)-O8(M4)-O9(M4)-O14(M4)-O15(M4).

2.3 初始化粒子種群

粒子種群中的每一個粒子代表零件的一種工藝規(guī)劃方案.按照編碼操作，每一個粒子包含三段序列，均采用隨機(jī)初始化的方法進(jìn)行初始化操作.每個粒子隨機(jī)初始化編碼之后，利用文獻(xiàn)[10]的約束調(diào)整方法調(diào)整編碼方案，然后使用解碼操作對其進(jìn)行解碼，獲得具體該粒子所代表的零件工藝路線；根據(jù)具體的工藝路線，計算該工藝路線下零件的總加工時間，將染色體所對應(yīng)工藝路線的總加工時間直接作為適應(yīng)度值.

2.4 粒子的全局更新策略

IGPSO中粒子的全局更新采用文獻(xiàn)[1]中的交叉操作來實現(xiàn).為了避免進(jìn)行無效的交叉操作，設(shè)定個體極值庫，保存粒子在搜索過程中發(fā)現(xiàn)的最好的若干個解(一般取2～3個)[11].為了避免算法過早收斂，設(shè)定種群極值庫保存整個搜索過程中發(fā)現(xiàn)的最好的若干個解(一般取整個種群的20%～30%).當(dāng)前粒子通過與個體極值庫和種群極值庫中不同的粒子進(jìn)行交叉操作，獲取更新信息.

2.5 粒子的局部搜索策略

采用變鄰域搜索算法作為粒子的局部搜索策略,詳細(xì)步驟如下:

步驟1根據(jù)粒子的編碼方案，定義3種鄰域結(jié)構(gòu)N1、N2、N3.其中，N1為交換操作，即隨機(jī)選擇粒子中特征序列上不同的兩個位置，將這兩個位置上的數(shù)值進(jìn)行交換；N2為插入操作，隨機(jī)選擇粒子中特征序列的一個位置，將這個位置上的數(shù)值插入到該序列的任意其他位置之前；N3為變異操作，隨機(jī)選擇粒子中可選工藝序列、可選加工機(jī)器序列中的一個位置，根據(jù)其可選加工資源情況，選擇另外一種加工資源.設(shè)定外循環(huán)最大迭代次數(shù)MaxIterOut，內(nèi)循環(huán)最大迭代次數(shù)MaxIterIn.令i=0,l=0.i代表當(dāng)前內(nèi)循環(huán)次數(shù)，l代表當(dāng)前外循環(huán)次數(shù).

步驟2隨機(jī)挑選一種鄰域結(jié)構(gòu)，產(chǎn)生當(dāng)前粒子Pcurr的鄰域解P1.

步驟3當(dāng)i大于MaxIterOut時，輸出Pcurr；否則，順序執(zhí)行.

步驟4當(dāng)l大于MaxIterIn時，令i=i+1, 若P1的適應(yīng)度值小于Pcurr，則令Pcurr=P1,跳轉(zhuǎn)到步驟3；當(dāng)l小于或等于MaxIterIn時，順序執(zhí)行.

步驟5令k=1，k代表當(dāng)前使用的鄰域結(jié)構(gòu)編號.

步驟6根據(jù)Nk隨機(jī)產(chǎn)生P1鄰域解P2.如果P2的適應(yīng)度值小于P1，則令P1=P2，k=1，跳轉(zhuǎn)到步驟6(繼續(xù)按照當(dāng)前鄰域結(jié)構(gòu)進(jìn)行搜索)；如果P2的適應(yīng)度值大于P1，則令k=k+1,如果k小于等于3，跳轉(zhuǎn)到步驟6(繼續(xù)搜索下一個鄰域).如果k大于3，順序執(zhí)行.

步驟7令l=l+1, 跳轉(zhuǎn)到步驟4.

2.6 IGPSO求解工藝規(guī)劃的總流程

步驟1設(shè)定算法參數(shù)：種群規(guī)模PopSize；種群極值庫規(guī)模GlobSize；個體極值庫規(guī)模SelfSize；最大迭代次數(shù)MaxGen；粒子全局搜索的概率GlobProb；粒子局部搜索的概率LocalProb；變鄰域搜索中外循環(huán)最大迭代次數(shù)MaxIterOut；內(nèi)循環(huán)最大迭代次數(shù)MaxIterIn.

步驟2隨機(jī)初始化種群和個體極值庫，挑選種群中適應(yīng)度值最好的20%個粒子存入種群極值庫.

步驟3依據(jù)粒子全局搜索的概率，依次對種群中的粒子進(jìn)行全局搜索，更新個體極值庫和種群極值庫.

步驟4依據(jù)粒子局部搜索的概率，依次對種群中的粒子進(jìn)行局部搜索，更新個體極值庫和種群極值庫.

步驟5如果循環(huán)達(dá)到最大迭代次數(shù)，則輸出種群極值庫中最好的個體作為優(yōu)化結(jié)果；如果循環(huán)沒有達(dá)到最大迭代次數(shù)，則跳轉(zhuǎn)到步驟3.

3 計算結(jié)果及分析

3.1 算例及計算結(jié)果

上述提出的IGPSO算法用C++語言編程實現(xiàn).本文的測試實例包含對6個不同的零件進(jìn)行工藝規(guī)劃，以驗證提出算法的有效性.零件1包含14個加工特征20道可選加工工序；零件2包含15個加工特征16 道可選加工工序；零件3包含11個加工特征14道可選加工工序；零件4包含13個加工特征13道可選加工工序；零件5包含7個加工特征9道可選加工工序；零件6包含14個加工特征18道可選加工工序.零件圖和具體的加工信息表見文獻(xiàn)[1].筆者假定在車間中有5臺機(jī)器用于零件加工，零件在不同機(jī)器之間的傳輸時間見文獻(xiàn)[1].算法參數(shù)設(shè)置如下：種群規(guī)模設(shè)定為200, 種群極值庫規(guī)模設(shè)定為40，個體極值庫規(guī)模設(shè)定為3，最大迭代次數(shù)設(shè)定為100，粒子全局搜索的概率設(shè)定為0.8，粒子局部搜索的概率設(shè)定為0.3，變鄰域搜索中外循環(huán)最大迭代次數(shù)設(shè)定為20，內(nèi)循環(huán)最大迭代次數(shù)設(shè)定為20.

使用筆者提出的IGPSO算法針對6個零件獨(dú)立計算20次，統(tǒng)計了20次運(yùn)行中獲得零件工藝路線對應(yīng)加工時間的最好值、平均值以及平均收斂代數(shù)，具體計算結(jié)果以及與其他算法的對比如表2所示，其中，SA、GA和MPSO(改進(jìn)PSO)算法的計算結(jié)果均來自文獻(xiàn)[1].筆者提出的IGPSO獲得的最優(yōu)工藝路線如表3所示.

表2 IGPSO計算結(jié)果及與其他算法的對比Tab.2 Results obtained by IGPSO and the comparisons with other algorithms

表3 IGPSO獲得的最優(yōu)工藝路線Tab.3 Optimal process plans obtained by IGPSO

從表2可以看出，針對零件1～零件5，使用本文提出的IGPSO算法在20次獨(dú)立運(yùn)行中每次均都能夠找到最優(yōu)解.在最好值上，針對零件1，IGPSO算法的計算結(jié)果優(yōu)于SA和GA，與MPSO的計算結(jié)果相同.針對零件2、零件3、零件4和零件5，4種算法在最好值上的計算結(jié)果相同，但是與SA、GA和MPSO算法相比，筆者提出的IGPSO算法的平均收斂代數(shù)較少.針對零件6，筆者提出的IGPSO在最好值、平均值和平均收斂代數(shù)上均優(yōu)于其他3種算法.

3.2 計算結(jié)果分析

整體來說，4種算法在本文的測試實例中顯示的性能從優(yōu)到劣順序為：IGPSO>MPSO>GA>SA.雖然在零件1～零件5的測試中，SA算法獲得了最優(yōu)解，但是與其他3種算法相比，它所獲得的平均值比較大，平均收斂代數(shù)也比較大.這是因為SA是一種局部搜索算法，計算結(jié)果比較依賴于初始解.相比SA，全局搜索能力比較好的GA獲得的計算結(jié)果更加穩(wěn)定，平均收斂次數(shù)低于SA，在零件6的測試中，獲取了比SA更好的解.在零件1～零件5的測試中，MPSO獲得的最好值與GA相同，平均值小于或等于GA獲得的結(jié)果，平均收斂代數(shù)均優(yōu)于GA.在零件6的測試中，MPSO獲得了更小的最優(yōu)解.這是因為，與GA的并行全局搜索策略相比，MPSO在粒子的全局更新策略上有所不同，當(dāng)前粒子通過與個體極值和種群極值庫中的粒子進(jìn)行交叉操作，迅速向解空間中較好的區(qū)域進(jìn)行移動，因此，MPSO平均收斂代數(shù)小于GA. 在零件1～零件5的測試中，IGPSO取得了與MPSO相同的最好值，在平均值上略優(yōu)于MPSO獲得的計算結(jié)果，平均收斂次數(shù)優(yōu)于MPSO.在對零件6的測試中，IGPSO獲得了新的最優(yōu)解，平均值與平均收斂次數(shù)也優(yōu)于MPSO獲得的結(jié)果.與MPSO相比，筆者提出的IGPSO在算法的局部搜索策略上引入了變鄰域搜索算法，增強(qiáng)了粒子的局部搜索能力，因此算法的平均收斂次數(shù)較少，且在零件6的測試中發(fā)現(xiàn)了新的最優(yōu)解.通過不同測試實例的計算結(jié)果可以證明，筆者提出的算法IGPSO在求解工藝規(guī)劃問題上具有一定優(yōu)勢.

4 結(jié)束語

筆者設(shè)計了一種IGPSO算法求解柔性工藝規(guī)劃問題，計算結(jié)果顯示，與其他算法相比，筆者提出的IGPSO算法在求解工藝規(guī)劃問題時具有更高的求解效率和更好的穩(wěn)定性.

在今后的研究工作中，可以從工藝規(guī)劃問題建模和求解算法設(shè)計兩個方向進(jìn)一步深入研究.在工藝規(guī)劃問題建模上，考慮進(jìn)一步研究面向綠色制造模式的工藝規(guī)劃問題建模方法;在求解算法設(shè)計上，筆者設(shè)計的IGPSO算法，是通過改變GPSO算法的操作算子，對算法的收斂和發(fā)散進(jìn)行控制.近年來，涌現(xiàn)出了一些新型的群體智能優(yōu)化算法，能夠?qū)?shù)據(jù)挖掘的思想融入群體智能優(yōu)化算法設(shè)計中，如頭腦風(fēng)暴優(yōu)化算法[12]，為算法的設(shè)計提供了一種新思路.因此，考慮在今后的研究工作中，對基于頭腦風(fēng)暴算法的柔性工藝規(guī)劃方法進(jìn)行進(jìn)一步的研究.