基于廣義粒子群優(yōu)化模型的工藝規(guī)劃方法研究

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

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

0 引言

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

近年來，越來越多的智能優(yōu)化算法被應用于解決現(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)化問題，隨著研究的深入，許多學者對傳統(tǒng)的PSO進行改進，將其廣泛應用于諸多復雜的組合優(yōu)化問題中，如旅行商問題[7]、作業(yè)車間調(diào)度問題等[8-9].其中，高海兵等[7]提出的廣義粒子群優(yōu)化(general PSO, GPSO)模型建立了一種將PSO應用于組合優(yōu)化問題的通用思路，在應用GPSO模型求解工藝規(guī)劃問題時，值得進一步去探索更加有效的粒子全局更新策略和局部搜索策略.

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

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

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

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

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

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

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

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

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

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

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

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

MinPT=OT+TT，

(1)

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

(2)

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

(3)

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

(4)

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

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

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

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

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

2.2 粒子的編碼與解碼

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

圖2 粒子對應的編碼方案Fig.2 Corresponding encoding scheme for a particle

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

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

2.4 粒子的全局更新策略

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

2.5 粒子的局部搜索策略

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

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

步驟2隨機挑選一種鄰域結構，產(chǎn)生當前粒子Pcurr的鄰域解P1.

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

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

步驟5令k=1，k代表當前使用的鄰域結構編號.

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

步驟7令l=l+1, 跳轉到步驟4.

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

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

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

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

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

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

3 計算結果及分析

3.1 算例及計算結果

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

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

表2 IGPSO計算結果及與其他算法的對比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次獨立運行中每次均都能夠找到最優(yōu)解.在最好值上，針對零件1，IGPSO算法的計算結果優(yōu)于SA和GA，與MPSO的計算結果相同.針對零件2、零件3、零件4和零件5，4種算法在最好值上的計算結果相同，但是與SA、GA和MPSO算法相比，筆者提出的IGPSO算法的平均收斂代數(shù)較少.針對零件6，筆者提出的IGPSO在最好值、平均值和平均收斂代數(shù)上均優(yōu)于其他3種算法.

3.2 計算結果分析

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

4 結束語

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

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