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

嚴坤妹

(福建商學院 基礎部，福建 福州，350012)

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

嚴坤妹

(福建商學院 基礎部，福建 福州，350012)

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

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

0、引言

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

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

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

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

設在有向圖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對應的頂點i，j之間就有從i到j的邊相連，即有向邊ei，j＝＜i，j＞存在，且令ei，j＝1，否則ei，j＝0。W＝(wi，j)n×n是權矩陣，其中wi，j表示加工工件i后接著加工產品j所需要的設備調整時間，是邊ei，j＝＜i，j＞上的權；wj，i表示加工工件j后接著加工工件i所需要的設備調整時間，是邊ej，i＝＜j，i＞上的權，一般wj，i≠wi，j。如果有向圖中任意兩個頂點間都有弧，那么可以得到一個相應的競賽圖，由于每個競賽圖都有有向Hamiiton路，而有向Hamiiton路實際上就是一棵有向樹(或根樹)。設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)，則排序問題可以轉化為度約束最小生成樹問題，對應的DCMST問題的數(shù)學模型如下所示:

2.排序問題的求解策略

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Step2:將Q中的頂點標號數(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:重復以上過程，直到P，Q中都無數(shù)字。于是形成n－1條邊的有向樹(根樹)。

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

在求解DCMST問題的模糊離散粒子群優(yōu)化算法中，如何產生prüfer數(shù)是很重要的環(huán)節(jié)。文獻[3]的算法中用模糊矩陣R＝(rij)m×n來產生無向圖的生成樹的prüfer數(shù)，其中n是頂點數(shù)目，m＝n－2是prüfer數(shù)的總位數(shù)。為了產生根樹的prüfer數(shù)，與文獻[3]一樣，也是通過構造模糊矩陣來產生的。設根樹的頂點有n個，則根樹對應的prüfer數(shù)的總位數(shù)為m＝n－1。用[1，n]中的整數(shù)來表示一個有向圖D的頂點，用X1，X2，…，Xn－1序列表示一棵有向樹(根樹)對應的prüfer數(shù)的各位數(shù)字。設X＝{X1，X2，…，Xn－1}表示prüfer數(shù)的各位數(shù)字的集合，Y＝{1，2，…，n}表示圖的頂點的集合，構造一個(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(最大數(shù)法)。另外算法中的每個粒子位置和速度也都表示為一個(n－1)×n階矩陣，即:

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

3.3適應度函數(shù)和度的改進

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

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

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

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

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

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

[4]紀震，廖惠連，吳青華.粒子群算法及應用[M].北京:科學出版社，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

(責任編輯:楊成平)

2017－03－10

福建省教育廳科技項目“度約束最小生成樹拓撲結構的粒子群算法研究”(JB10221)。

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