嚴(yán)坤妹

(福建商學(xué)院 基礎(chǔ)部，福建 福州，350012)

粒子群優(yōu)化算法在工件排序問題中的應(yīng)用

嚴(yán)坤妹

(福建商學(xué)院 基礎(chǔ)部，福建 福州，350012)

排序問題的求解和DCMST問題一樣，一般是NP－h(huán)ard的。度約束最小生成樹(DCMST)問題按權(quán)矩陣W＝(wij)n×n中wij是否等于wji可以分成兩類，權(quán)矩陣是對稱矩陣的DCMST問題已有很多啟發(fā)式算法求解，其中有研究者提出了一種有效求解DCMST問題的模糊粒子群優(yōu)化算法。針對工件排序問題，提出了應(yīng)用粒子群優(yōu)化算法求解排序問題的策略，并通過重新設(shè)計根樹的prüfer數(shù)編碼和初始粒子群的產(chǎn)生方法，使得基于prüfer數(shù)的模糊離散粒子群優(yōu)化算法也能應(yīng)用于權(quán)矩陣不是對稱矩陣的DCMST問題的求解。

排序問題；根樹；Prüfer數(shù)編碼；粒子群優(yōu)化算法；Hamilton路

0、引言

度約束最小生成樹問題(Degree－Constrained Minimum Spanning Tree，DCMST)在實際應(yīng)用中具有廣泛的代表性，它是一個經(jīng)典的NP－h(huán)ard問題且難于用傳統(tǒng)方法進(jìn)行求解。DCMST問題的兩個重要參數(shù)是:頂點個數(shù)和兩個頂點之間的邊代表的某種屬性(權(quán))。DCMST問題可以分成兩類:權(quán)矩陣是對稱矩陣的DCMST問題和權(quán)矩陣不是對稱矩陣的DCMST問題。針對權(quán)矩陣是對稱矩陣的DCMST，已有很多學(xué)者進(jìn)行研究并提出了各種啟發(fā)式算法。其中有學(xué)者研究了用遺傳算法求解DCMST問題[1－2]，也有學(xué)者詳細(xì)討論了用粒子群優(yōu)化算法求解DCMST，并提出了一種有效的基于prüfer數(shù)求解DCMST的模糊離散粒子群優(yōu)化算法[3]。本文在文獻(xiàn)[3]算法的基礎(chǔ)上，進(jìn)一步研究權(quán)矩陣不是對稱矩陣的DCMST的特點，重新設(shè)計粒子編碼和修改初始種群的prüfer數(shù)的產(chǎn)生方法，使得基于prüfer數(shù)的模糊離散粒子群優(yōu)化算法也能用于求解權(quán)矩陣不是對稱矩陣的DCMST。針對工件排序問題，提出了應(yīng)用粒子群優(yōu)化算法求解排序問題的策略。

1.排序問題的數(shù)學(xué)模型

當(dāng)不同型號的產(chǎn)品在某部機(jī)床上進(jìn)行機(jī)械加工，若機(jī)床對某種型號產(chǎn)品加工完畢而要對另一種型號的產(chǎn)品進(jìn)行加工時，通常工藝裝備需要更換，即需要花費一定的工藝裝備更換時間。產(chǎn)品的加工順序不同，所花費的工藝裝備更換時間的總和也就不同。因此，這個排序問題是要找一個不同類型產(chǎn)品的最優(yōu)加工排序，使工藝裝備更換時間的總和最少。例如某臺機(jī)器必須加工多種工件J1，J2，…，Jn，在一種工件加工完畢之后，為了加工下一個工件，機(jī)器必須進(jìn)行調(diào)整。不同工件的排序會影響調(diào)整時間，當(dāng)工件的排序設(shè)定之后，在設(shè)備上就按此順序進(jìn)行加工。

對于工件排序問題，可以建立網(wǎng)絡(luò)圖，把不同型號的工件看作頂點，分別用1，2，3，…，n自然數(shù)表示，把不同工件間的調(diào)整時間看作兩頂點之間連線的一種屬性(權(quán))，并用正數(shù)wi，j表示。則排序問題可以轉(zhuǎn)化為在對應(yīng)的有向圖中求一條權(quán)總數(shù)最小的有向哈密爾頓路(Hamiiton路)。

設(shè)在有向圖G＝(V，E，W)中，V＝{1，2，…，n)}表示工件的集合，代表圖G的頂點；而E＝{e1，2，e1，3，…，e2，1，e2，3，…，ei，j，…，en，1，…，en，n－1}代表圖G的邊集合，ei，j≠ej，i，邊ei，j表示工件i，j是否相繼加工，若加工工件i后接著加工工件j，則圖G對應(yīng)的頂點i，j之間就有從i到j(luò)的邊相連，即有向邊ei，j＝＜i，j＞存在，且令ei，j＝1，否則ei，j＝0。W＝(wi，j)n×n是權(quán)矩陣，其中wi，j表示加工工件i后接著加工產(chǎn)品j所需要的設(shè)備調(diào)整時間，是邊ei，j＝＜i，j＞上的權(quán)；wj，i表示加工工件j后接著加工工件i所需要的設(shè)備調(diào)整時間，是邊ej，i＝＜j，i＞上的權(quán)，一般wj，i≠wi，j。如果有向圖中任意兩個頂點間都有弧，那么可以得到一個相應(yīng)的競賽圖，由于每個競賽圖都有有向Hamiiton路，而有向Hamiiton路實際上就是一棵有向樹(或根樹)。設(shè)y＝(y1，2，y1，3，…，yi，j，…，yn，1，…，yn，n－1)表示圖G的一棵生成樹(可以理解為有向樹)，其中如果邊ei，j＝1且被選中，則yi，j＝1，否則yi，j＝0(i＝1，2，…，n；j＝1， 2，…，n，i≠j)。因為一種工件加工完緊接著加工另一種工件，所以各個頂點的度約束不會大于2，即bi≤2(i＝1，2，…，n)，則排序問題可以轉(zhuǎn)化為度約束最小生成樹問題，對應(yīng)的DCMST問題的數(shù)學(xué)模型如下所示:

2.排序問題的求解策略

排序問題的求解，現(xiàn)在還沒有十分有效的方法。若排序問題中的產(chǎn)品(如工件)個數(shù)與加工不同產(chǎn)品間的工藝裝備更換時間是已知的，可以用整數(shù)規(guī)劃的算法、最近鄰居啟發(fā)式算法等算法求解，但是計算量大。特別是當(dāng)產(chǎn)品的種類較多時，這些算法的過程非常繁瑣，甚至不能求解。所以希望有一個方法能得到一個相當(dāng)好的解，但不一定是最優(yōu)解。文獻(xiàn)[3]提出的基于prüfer數(shù)的模糊離散粒子群優(yōu)化算法用于求解權(quán)矩陣是對稱的DCMST問題是有效的，且當(dāng)DCMST問題中的頂點的度約束d≤2時，DCMST就是一棵線性樹，對應(yīng)的頂點排列就體現(xiàn)了順序關(guān)系。而排序問題的網(wǎng)絡(luò)圖的權(quán)矩陣一般不是對稱的，不能直接應(yīng)用文獻(xiàn)[3]提出的算法求解，需要對該粒子群優(yōu)化算法進(jìn)行適當(dāng)修改。

對于一個實際的排序問題(如工件的排序)，可以采用以下的策略解決:

第一步，把排序問題轉(zhuǎn)化成有向圖的有向hamilton路。構(gòu)造具有頂點1，2，…，n(或v1，v2，…，vn)的有向圖D＝(V，E，W)，其中有向邊ei，j＝＜vi，vj＞∈E，ej，i＝＜vj，vi＞∈E，邊上的權(quán)可以不相等，即wj，i≠wi，j。則D中必有有向hamilton路，而且不只一條，這些有向hamilton路實際上就是包含所有頂點的有方向的生成樹，稱為根樹。

第二步，求D中的權(quán)數(shù)之和最小的有向hamilton路。利用求解權(quán)矩陣不是對稱矩陣的DCMST的粒子群優(yōu)化算法求出頂點的度約束為d≤2的根樹，即權(quán)和最小的有向hamilton路，于是頂點的排序也就可知了。

3.權(quán)矩陣不是對稱矩陣的DCMST的粒子群優(yōu)化算法設(shè)計

文獻(xiàn)[3]提出的基于prüfer數(shù)的模糊離散粒子群優(yōu)化算法中，prüfer數(shù)編碼是針對無向圖G的權(quán)矩陣是對稱矩陣的情形，選到的邊與頂點順序無關(guān)。如果權(quán)矩陣不是對稱矩陣，選到的邊就與頂點順序有關(guān)，為了使該算法能求解權(quán)矩陣不是對稱的DCMST問題(比如工件排序問題)，需要重新設(shè)計根樹的prüfer數(shù)編碼和解碼，并重新修改粒子群優(yōu)化算法中初始粒子種群prüfer數(shù)的產(chǎn)生方法，而算法的具體設(shè)計流程與文獻(xiàn)[3]一樣，不再贅述。

3.1根樹的prüfer數(shù)編碼設(shè)計:

根樹的prüfer數(shù)是指一棵有n個頂點的根樹可以用n－1個數(shù)字的排列來表示，其中每個數(shù)字都是1和n之間的整數(shù)。

在一棵有n個頂點的根樹中，用自然數(shù)1，2，…，n對頂點進(jìn)行標(biāo)號。

編碼過程:將一棵根樹(有序樹))轉(zhuǎn)化為一個Prüfer數(shù)

Step1:令j為根樹T中入度是1，出度是0的頂點(即葉子頂點)中標(biāo)號最大的頂點，i為j的關(guān)聯(lián)頂點，即i是有向邊eij＝＜i，j＞的始頂點。則i為Prüfer數(shù)編碼P的第一個數(shù)字，編碼順序從左到右。

Step2:刪除根樹T中的頂點j及邊＜i，j＞。

Step3:重復(fù)上述步驟，直到剩下根頂點。于是得到一個由n－1個介于1和n之間的數(shù)字組成的數(shù)字排列，即為根樹的Prüfer數(shù)。

解碼過程:將一個Prüfer數(shù)轉(zhuǎn)化為一棵根樹

Step1:令P為原始Prüfer數(shù)，Q為所有不包含在P中的頂點的集合。

Step2:將Q中的頂點標(biāo)號數(shù)字從左到右降序排列，保證Q的最左邊的數(shù)字為最大數(shù)字。令i為P中的最左邊的數(shù)字，j為Q中的最左邊的數(shù)字(即最大數(shù)字)。將有向邊＜i，j＞添加到樹上，將i從P中除去，j從Q中除去。若i在P的剩余部分中不再出現(xiàn)，將i加入到Q中，始終保證Q中的數(shù)字按降序排列。

Step3:重復(fù)以上過程，直到P，Q中都無數(shù)字。于是形成n－1條邊的有向樹(根樹)。

3.2初始種群prüfer數(shù)的產(chǎn)生方法

在求解DCMST問題的模糊離散粒子群優(yōu)化算法中，如何產(chǎn)生prüfer數(shù)是很重要的環(huán)節(jié)。文獻(xiàn)[3]的算法中用模糊矩陣R＝(rij)m×n來產(chǎn)生無向圖的生成樹的prüfer數(shù)，其中n是頂點數(shù)目，m＝n－2是prüfer數(shù)的總位數(shù)。為了產(chǎn)生根樹的prüfer數(shù)，與文獻(xiàn)[3]一樣，也是通過構(gòu)造模糊矩陣來產(chǎn)生的。設(shè)根樹的頂點有n個，則根樹對應(yīng)的prüfer數(shù)的總位數(shù)為m＝n－1。用[1，n]中的整數(shù)來表示一個有向圖D的頂點，用X1，X2，…，Xn－1序列表示一棵有向樹(根樹)對應(yīng)的prüfer數(shù)的各位數(shù)字。設(shè)X＝{X1，X2，…，Xn－1}表示prüfer數(shù)的各位數(shù)字的集合，Y＝{1，2，…，n}表示圖的頂點的集合，構(gòu)造一個(n－1)×n階模糊矩陣R＝(ri，j)(n－1)×n，rij∈[0，1]，其中位于第i行第j列的元素ri，j，就代表prüfer數(shù)中第i位數(shù)Xi對于頂點j的隸屬程度，采用最大數(shù)法得到prüfer數(shù)中第i位數(shù)字j，即若ri，j＝max{Xi，1，Xi，1，…，Xi，n}，則Xi＝j(luò)(最大數(shù)法)。另外算法中的每個粒子位置和速度也都表示為一個(n－1)×n階矩陣，即:

位置矩陣中行數(shù)表示粒子對應(yīng)的prüfer數(shù)的總位數(shù)，列數(shù)代表圖的頂點個數(shù)，prüfer數(shù)中的第i位數(shù)字Xi與頂點j的關(guān)系由元素xi，j決定。初始粒子種群由位置矩陣產(chǎn)生，初始化時位置矩陣中的元素按滿足這兩個條件隨機(jī)產(chǎn)生；速度矩陣中的元素按滿足這個條件隨機(jī)產(chǎn)生。對位置矩陣的每一行按照最大數(shù)法進(jìn)行解模糊就得到n－1個數(shù)字，即為初始粒子種群中粒子對應(yīng)的prüfer數(shù)中的各位數(shù)字。

3.3適應(yīng)度函數(shù)和度的改進(jìn)

由于對粒子的位置矩陣進(jìn)行解模糊后，得到的prüfer數(shù)表示的粒子可能有不滿足度約束的粒子存在，另外，在迭代更新后的新一代粒子中也會出現(xiàn)不滿足度約束的粒子，因此需要對粒子進(jìn)行檢驗，看粒子是否可行，并對那些不滿足度約束的粒子進(jìn)行改進(jìn)。如果頂點在prüfer數(shù)中出現(xiàn)的次數(shù)再加上1得到的數(shù)就是對應(yīng)頂點的度數(shù)，若頂點沒有在prüfer數(shù)中出現(xiàn)，則該頂點的度為1。因此把“頂點的度數(shù)不超過其規(guī)定的度的上限d”作為檢驗粒子是否可行的依據(jù)。如果某個頂點的度超過上限d，表示違反了度約束條件，那么將prüfer數(shù)中違反度約束的頂點隨機(jī)替換為未在編碼prüfer數(shù)中出現(xiàn)的頂點；如果粒子是可行的，則對prüfer數(shù)進(jìn)行解碼，便可得到一棵滿足度約束的根樹。經(jīng)過這樣修改后的模糊離散粒子群優(yōu)化算法就可以解決有關(guān)排序問題。

4.粒子群優(yōu)化算法求解排序問題的優(yōu)點

粒子群優(yōu)化算法因其概念簡單、實現(xiàn)容易而引起學(xué)術(shù)界的廣泛重視，一經(jīng)提出便在短短的幾年內(nèi)出現(xiàn)了大量的研究成果。粒子群優(yōu)化算法是非線性連續(xù)優(yōu)化問題、組合優(yōu)化問題和混合整數(shù)非線性優(yōu)化問題的有效優(yōu)化工具，是一種有效的全局搜索方法，目前已被應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制、多目標(biāo)優(yōu)化及其他遺傳算法的應(yīng)用領(lǐng)域[4]。因此，當(dāng)排序問題中產(chǎn)品的種類較多，即圖的頂點個數(shù)較多、邊數(shù)也較多時，可以把排序問題轉(zhuǎn)化為DCMST問題，再用粒子群優(yōu)化算法求解，不但可以縮短計算時間，而且能得到滿意的最優(yōu)解。

[1]牧云志，周根貴.基于prüfer數(shù)的遺傳算法求解度約束最小樹問題[J]，計算機(jī)工程與應(yīng)用，2008(12):53－56.

[2]宋海洲.求解度約束最小生成樹的單親遺傳算法[J].系統(tǒng)工程理論與實踐，2005(4):62－67.

[3]嚴(yán)坤妹，王鐫，林娟，等.求解DCMST問題的模糊離散粒子群優(yōu)化算法[J].莆田學(xué)院學(xué)報，2011(5):59－63.

[4]紀(jì)震，廖惠連，吳青華.粒子群算法及應(yīng)用[M].北京:科學(xué)出版社，2009.

The Application of Particle Swarm Optimization Algorithm in Workpiece Sorting

YAN Kun－mei
(Foundation Department，F(xiàn)ujian Commercial College，F(xiàn)uzhou 350012，China)

The solution of the sort problem，is similar to DCMST，which is generally NP－h(huán)ard.The niche minimum spanning tree problem can be divided into two categories，the weight matrix has many heuristic algorithms for DCMST problem of symmetric matrix.Some researchers have proposed an effective fuzzy particle swarm optimization algorithm for DCMST problem.This paper proposes a strategy to solve the sorting problem by using particle swarm optimization algorithm，and then uses Prüfer number coding and primitive particle group generation method to apply to the solution of DCMST，which is weight matrix not symmetric matrix.

sorting problem；root tree；Prüfer number coding；particle swarm optimization algorithm；Hamilton path

O29

A

2096－3300(2017)02－0096－05

(責(zé)任編輯:楊成平)

2017－03－10

福建省教育廳科技項目“度約束最小生成樹拓?fù)浣Y(jié)構(gòu)的粒子群算法研究”(JB10221)。

嚴(yán)坤妹(1966－)，女，福建莆田人，副教授，碩士。研究方向:應(yīng)用數(shù)學(xué)、計算智能及其應(yīng)用。