快速混合粒子群優(yōu)化算法應用研究

康鯤鵬

（商丘師范學院 計算機與信息技術(shù)學院，河南 商丘 476000）

為了提高生產(chǎn)效率，分配給一個流水車間單元的作業(yè)在不同條件下（如：機器的性能和配置），基于相似需求會被按類分成幾組。這種課題被稱為組調(diào)度（GS）。在組調(diào)度（GS）中，屬于一個組的作業(yè)將會被連續(xù)處理而不會被其他組的作業(yè)打斷。一般來說，每個機器的主要配置是用來在組之間實現(xiàn)處理轉(zhuǎn)換的，當然也需要附帶配置以便實現(xiàn)同組作業(yè)處理間的轉(zhuǎn)換。如果為處理一組作業(yè)而配置各機器的時間依賴于每臺機器對前一個組的處理，那么我們稱這個問題為流水車間序列依賴組調(diào)度（FSDGS）問題。

以往人們研究了FSDGS問題時，他們設(shè)計了幾個最小化最大完工時間（makespan）為性能衡量標準的元啟發(fā)式算法，而且還設(shè)計了一個界定下界的方法來評估這幾個元啟發(fā)式算法的性能。由Kennedy和Eberhart[1]共同提出的一種新型進化技術(shù)—粒子群優(yōu)化（PSO），獲得了較多關(guān)注并被廣泛應用于各個領(lǐng)域，尤其是對于連續(xù)優(yōu)化問題。通過比較，PSO算法比已有的元啟發(fā)式算法具有較大優(yōu)越性。

基于當前FSDGS問題有限的研究成果和PSO算法在常規(guī)調(diào)度問題上具有潛力的性能以及在不同調(diào)度問題領(lǐng)域PSO算法逐漸普及的應用，使得我們?yōu)橐宰钚』偭鲃訒r間為基準的FSDGS問題開發(fā)一種新型的PSO算法具有非凡的意義。

1 流水車間組調(diào)度問題

研究的問題可以借助Pinedo[2]研究結(jié)果中的符號Fm|fm ls，Splk，prmu|∑Cj。 Pinedo 在研究過程中對這些符號的解釋和假設(shè)如下：

1）將g組作業(yè)賦予一個擁有m臺機器的流水車間單元（Fm）。在這項研究中，Gp代表組P。

2）每一組（p=1，2，…，g）包含 bp個作業(yè)（ fm ls）。 研究中，Jpj代表組 p（p=1，2，…，g）中第 j個作業(yè)（ j=1，2，…，bp），組中作業(yè)的個數(shù)可以不同。

3）組（l）在機器（k）上的配置時間依賴于該機器上緊接在前被處理的組（p），即序列依賴于配置時間（Splk）。

4）所有的作業(yè)和組在所有的機器處理序列相同。（置換調(diào)度（prmu））

5）組中的每一個作業(yè)不需要獨立的配置時間。如果需要的話，可以假設(shè)每個作業(yè)的運行時間包含了配置時間。

6）每臺機器只需要在處理第一個組時配置一次。

7）同屬于一個組的作業(yè)處理時不會被其他組的作業(yè)打斷（成組技術(shù)）。

8）每個作業(yè)在每臺機器上的運行時間與其他作業(yè)的運行時間是無關(guān)的。

1.1 解的表達式

解決組調(diào)度問題需要兩個步驟：第一步，為每一組的作業(yè)尋找一個序列。第二步，為所有的組尋找一個序列。研究中，g+1個向量構(gòu)成一個可行性解，前g向量表示組中作業(yè)的序列。最后一個向量對應組的序列。因為這兩中類型的向量相互作用，所以這g+1個向量必須同步考慮。由于每個組中作業(yè)的個數(shù)是不相等的（如：bp≠bq），組調(diào)度問題的解可以用一個偽矩陣來表示。這種矩陣的特點是每行或者每列的元素可以不相等[3]。在偽矩陣中，前g行與各組中作業(yè)的序列有關(guān)，第g+1行（也就是最后一行）對應組的序列。例如，假設(shè)有3個組，每組中分別有3個、兩個和4個作業(yè)，將這3個組逐個分配給擁有3臺機器一個的車間單元來處理，則組中的作業(yè)可表示為：

G3（J33-J32-J34-J31）-G1（J12-J11-J13）-G2（J21-J22）

而組處理的序列所構(gòu)成的偽矩陣可表示成下面的形式：

為了將PSO算法應用于當前問題，應將上面矩陣中的元素轉(zhuǎn)換為整數(shù)。式（2）用來完成這種轉(zhuǎn)換操作：

其中，bp是組 p（p=1，2，…，g）中作業(yè)的個數(shù)且 b0=0。 這種映像形式的轉(zhuǎn)換可將式（1）中的偽矩陣轉(zhuǎn)化為下面的偽矩陣：

基于這個新得到的偽矩陣，上例中每臺機器上作業(yè)處理的順序就變成的下面的形式：

2 標準粒子群優(yōu)化

PSO是一種重在協(xié)作的迭代方法。PSO的整體稱之為群，PSO整體中的每個個體稱為粒子[4-5]。由當前位置及速度來確定的每個粒子，都是PSO中的一個潛在解。粒子在多維搜索空間中飛行從而使位置發(fā)生改變。將一個新位置和新速度值賦予某個粒子從而使其得到一個新位置。在搜索的過程中，每個粒子不斷變換位置。位置值是通過計算位置目標函數(shù)值獲得，上個階段每個粒子獲得的最佳位置被稱為該粒子的最優(yōu)值（p-best）。而所有粒子獲得的最佳位置稱為搜索的全局最優(yōu)值（g-best）。 每個粒子都是基于其以前位置、（p-best）和搜索的（g-best）得到當前新位置值和速度的。

考慮一個d維的搜索空間，假設(shè)初始解（群的大小）的個數(shù)是 S。 此時，第 i（i=1，2，…，S）個粒子的參數(shù)由位置向量 xi=（xi1，xi2，…，xid）和速度向量 vi=（vi1，vi2，…，vid）構(gòu)成。 定義第 i個粒子的 p-best為 yi=（yi1，yi2，…，yid），全局最優(yōu)值 g-best為每個粒子的位置和速度參數(shù)更新可以通過對下面公式（5）和（6）的計算得到：

其中w是慣性權(quán)重，用來控制該粒子以前的速度值對當前的影響，c1和c2稱為置信系數(shù)或者加速系數(shù)，r1和r2是在區(qū)間（0，1）上獨立均勻分布的隨機變量，i=1，2，…，S 且 j=1，2，…，d。

在PSO算法中，等式（5）用來根據(jù)粒子以前的速度和它們當前位置與p-best、g-best的距離計算其新速度。通常，為了控制粒子極端漫游而逸出搜索空間，應為新速度定義一個最大值（vmax）和一個最小值（vmin）。這種情況下，粒子的速度可以被約束在區(qū)間[vmin，vmax]上。根據(jù)等式（6），粒子從一個位置移動到一個新位置，不斷重復這個過程，直到滿足一個事先設(shè)定的停止標準。

在標準PSO算法中，解用向量來表示。本文中，我們把組調(diào)度（GS）問題中的每個可行性解都用一個偽矩陣來表示[6]。因此為了能用PSO算法來解決現(xiàn)在研究的GS問題，須將標準PSO算法作如下擴展：

設(shè)Xi是GS問題的一個可行性解，就像PSO搜索空間的一個粒子。Xi可以用一個（g+1）×h的偽矩陣來表示，前g行表示各組中作業(yè)的序列，最后一行表示組的序列。h的值等于組中作業(yè)的最大數(shù)和組的個數(shù)。則粒子Xi和其速度Vi可以分別用下面的矩陣表示：

與標準PSO相似，粒子的速度的更新可以基于下面的公式計算得到：

其中Yi是第 i個粒子的 p-best的值， 而Y?是 g-best。 k，j和 i的取值范圍分別是 k=1，2，…，h，j=1，2，…，g，i=1，2，…，S，其他操作和標準PSO算法類似。

3 混合PSO算法

PSO算法多用于連續(xù)優(yōu)化問題，而GS是一個離散問題（最優(yōu)解是組的序列，組中作業(yè)調(diào)度其實也是個離散問題），因此需要對標準PSO算法作一些調(diào)整使之適合解決這樣的離散問題。為此，課題組設(shè)計了一個基于排序值（Ranked Order Value，ROV）規(guī)則的新的編碼方案。這個ROV規(guī)則可以將粒子連續(xù)的位置轉(zhuǎn)化為作業(yè)和組序列。課題組還設(shè)計了一種被稱為個體增益（IE）的鄰域搜索策略，它由PSO構(gòu)成，目的是提高了搜索能力并在搜索空間深度和廣度方面做出平衡，這種算法被稱為PSOIE。下面就來介紹這種基于擴展PSO算法，用來解決FSDGS問題的元啟發(fā)式算法。

3.1 排序值規(guī)則

考慮一個流水車間GS問題的可行性解。假設(shè)Xi是一個在某連續(xù)空間中由作業(yè)和組位置的值構(gòu)成的偽矩陣，且Xi對應現(xiàn)階段空間的第 i個粒子。 設(shè) Xi1=（Xi11，Xi12，…，Xi1b1）為偽矩陣中對應第一組作業(yè)序列的第一行。在ROV規(guī)則中，向量Xi1的最小位置值（SPV）首先映射為第一等級。然后，第二SPV值被指定為第二等級。同樣的方法，所有位置上的值會被轉(zhuǎn)化成第一組的一個作業(yè)序列。以此類推，將這種方法應用到偽矩陣Xi的所有行上。

3.2 領(lǐng)域搜索方案

假設(shè)Xi是GS問題的一個解偽矩陣。若與組序列（最后一行）相關(guān)向量中任意兩個組的位置發(fā)生了變化，意味著該GS問題的一個新的解產(chǎn)生了。這個新偽矩陣被稱為鄰域矩陣。如果新解的目標函數(shù)值比當前目標函數(shù)值好，接受當前更新，否則另外選擇兩組[6]。這種方法被稱為個體增益，具體應用如下：

為了標明組順序，設(shè)定最后一行有g(shù)個位置。假設(shè)這些組的初始順序是任意的，可以通過改變 “b1”和“b2”兩個位置上的組順序來產(chǎn)生一個領(lǐng)域矩陣，其中，1≤b1≤b2且b1≤b2≤g。如圖1所示，在這個例子中假設(shè)有4個組，X是問題的一個解。 設(shè)定組的原始序列是 Xg=（1，3，4，2），且解 X 的目標函數(shù)值f=120。解Xg中頭兩個值進行交換，在這種情況下，新序列就表示成 Xnewg=（3，1，4，2）。 假設(shè)新序列的目標函數(shù)值是fnew=112。顯然，新序列的目標函數(shù)比前一個好。因此，新解（Xg=Xnewg且f=fnew）是可以接受的?；谕瑯拥囊?guī)則，選定第一和第三個交換其位置上的值，迭代方式和結(jié)果如圖1中所示。

圖1 個體增益策略Fig.1 Individual enhancement strategy

很明顯鄰域矩陣搜索方案并不是直接應用在連續(xù)偽矩陣上而是應用在了離散偽矩陣的組序列上。為了做到這一點，連續(xù)偽矩陣中，使用個體增益策略交換組中元素位置的組值也應該作相應修正。因此，當鄰域矩陣搜索結(jié)束時，為得到新連續(xù)位置值應該對其加以更新以保證ROV規(guī)則生成的序列結(jié)果和鄰域矩陣搜索得到的結(jié)果相同[7]。

為了更利于研究當前的調(diào)度問題，本文在個體增益算法和粒子群優(yōu)化算法的基礎(chǔ)上，開發(fā)了一種混合算法。在每一個階段，當PSO產(chǎn)生一個新解，個體增益算法會改進這個解并把它傳遞到下一階段的PSO算法中進行處理。

3.3 PSO參數(shù)

本文的研究中，在等式（5）上我們設(shè)計的3個動態(tài)系數(shù)和，是經(jīng)過深思熟慮的，在進化過程中它們呈現(xiàn)非線性的變化趨勢[14]。在每個階段，這3個系數(shù)的值可以通過下面幾個等式計算得出：

其中ωmax和ωmin分別表示w的最大值和最小值。同樣地，cmax1和cmin1分別表示c1的最大值和最小值，cmax2和cmin2分別表示c2的最大值和最小值。參數(shù)α是一個常量。I表示當前迭代次數(shù)，而max I表示總迭代次數(shù)。

初始粒子總數(shù)由下面的公式（11）為PSO算法隨機生成：

其中Xmin和Xmax分別是連續(xù)搜索空間中位置的上下限。公式中的rand是區(qū)間（0，1）上的一個隨機變量。類似的，粒子的初始速度由下面的公式（12）生成：

其中vmin和vmax和上面的解釋類似，而rand是區(qū)間（0，1）上的隨機變量。

表1 PSOIE算法和Salm asi給定下限的蟻群算法的平均百分比誤差對比Tab.1 The average percentage error for the PSOIE algorithm and ant colony algorithm

4 結(jié)果和比較

本文將該PSO算法的性能與參考文獻上提到的已知性能最好的元啟發(fā)式搜索算法做了對比，如Salmasi等人提出的ACO算法。比較是基于Salmasi等人設(shè)計的流水車間測試問題進行的。這些測試問題產(chǎn)生自3個不同的集合，這3個集合的特點是：一個流水車間單元分別具有2個、3個和6個機器。共有2到16個組，每個組有2到10個作業(yè)。

為了比較算法的性能，在本文的PSO算法效果和ACO算法效果間進行了一次由Salmasi等人開發(fā)的t-測試。對比分別在2臺、3臺和6臺機器問題間進行，并把每種問題的總流水時間的最小化值作為基準。附件B中是比較的統(tǒng)計結(jié)果。2臺、3臺和6臺機器問題下兩種算法比較的P-值參數(shù)很接近于零（分別是0.001，0.000和0.022）。因此可以推斷，基于2臺、3臺和6臺機器問題下兩種算法的結(jié)果區(qū)別明顯。就實驗的3種問題來說，因為PSO算法的平均目標函數(shù)值都小于ACO算法的平均目標函數(shù)值，可以得出這樣的結(jié)論，對于我們要研究的問題，PSO算法的解更加高效。為了做進一步的對比，針對實驗問題，表2展示了由Salmasi提出的兩種算法基于下限的百分比誤差。這個下限可以用下面一個簡單的公式計算得到：

（啟發(fā)式算法的解-下限）/下限

如表2中所示，該PSO算法的百分比誤差比ACO算法的百分比誤差在3種情況下都低。為了對兩種算法性能的做出更貼切的評估，圖2展示了該PSO算法最優(yōu)解所需時間柱狀圖，圖3展示了ACO算法最優(yōu)解所需時間最優(yōu)解柱狀圖。兩張圖比較顯示PSO算法比ACO算法能在更短的時間內(nèi)趨于最優(yōu)解。

圖2 粒子群優(yōu)化算法運行時間百分比柱狀圖Fig.2 Runtime percentage histogram for the particle swarm optimization algorithm

圖3 蟻群優(yōu)化算法運行時間百分比柱狀Fig.3 Runtime percentage histogram for the ant colony optimization

5 結(jié) 論

文中開發(fā)了一種基于PSO的元啟發(fā)式算法，用來解決Fmlfmls，Splk，Prmu|∑Cj問題。 然后將這種 PSO算法的性能與ACO算法的做了對比，ACO算法是已知文獻上提到的最好的元啟發(fā)式算法。結(jié)果表明，成對t-測試時該PSO算法的性能優(yōu)于ACO算法，并且能夠在較短的時間內(nèi)找到最優(yōu)解。這種PSO算法可以用來解決帶有不同目標函數(shù)的FSDGS問題。如果能找到一個更好的鄰域矩陣搜索機制的話，我們的算法還有改進的空間。后面的工作我們將致力于此。

[1]Kennedy J，Eberhart R.Particle swarm optimization[C]//Proceeding of IEEE International Conference on Neural Network， 4， Australia，1995:1942-1948.

[2]Schaller G E，Gupta JN D，Vakharia A.Scheduling a flow line manufacturing cell with sequence dependent family setup time[J].European Journal of Operational Research，2000，125（2）:324-329.

[3]Franca P M，Gupta JN D，Mendes P M，et al.Evolutionary algorithms for scheduling a flow shopmanufacturing cellwith sequence dependent family setups [J].Computers and Industrial Engineering，2005，48（3）：491-506.

[4]王江榮.基于粒子群優(yōu)化算法的直線擬合及應用[J].工業(yè)儀表與自動化裝置，2013（4）：73-75.WANG Jiang-rong.Straight line fitting based on particle swarm optimization algorithm and application[J].Industrial Instrumentation&Automation,2013（4）：73-75.

[5]楊柳春.基于粒子群優(yōu)化算法的AR模型參數(shù)估計[J].工業(yè)儀表與自動化裝置，2013（5）：67-69,95.YANG Liu-chun.AR model parameter estimation based on particle swarm optimization algorithm [J]. Industrial Instrumentation&Automation,2013（5）：67-69,95.

[6]Lin SW，Gupta J N D，Ying K C，et al.Using simulated annealing to schedule a flowshop manufacturing cell with sequencedependent family setup times[J]. International Journal of Production Research， 2009，47（12）：3205-3217.

[7]齊學梅，羅永龍.求解流水車間調(diào)度問題的混合粒子群算法[J].計算機工程與應用，2012，48（9）:33-39.QI Xue-mei，LUO Yong-long. Hybrid particle swarm optimization algorithm for flow shop scheduling problem[J].Computer Engineering and Application，2012，48（9）:33-9.