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

康鯤鵬

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

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

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

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

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

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

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

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

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

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

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

6）每臺(tái)機(jī)器只需要在處理第一個(gè)組時(shí)配置一次。

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

8）每個(gè)作業(yè)在每臺(tái)機(jī)器上的運(yùn)行時(shí)間與其他作業(yè)的運(yùn)行時(shí)間是無關(guān)的。

1.1 解的表達(dá)式

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

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

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

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

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

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

2 標(biāo)準(zhǔn)粒子群優(yōu)化

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

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

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

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

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

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

與標(biāo)準(zhǔn)PSO相似，粒子的速度的更新可以基于下面的公式計(jì)算得到：

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

3 混合PSO算法

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

3.1 排序值規(guī)則

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

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

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

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

圖1 個(gè)體增益策略Fig.1 Individual enhancement strategy

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

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

3.3 PSO參數(shù)

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

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

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

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

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

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

4 結(jié)果和比較

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

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

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

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

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

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

5 結(jié) 論

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

[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)化算法的直線擬合及應(yīng)用[J].工業(yè)儀表與自動(dòng)化裝置，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ì)[J].工業(yè)儀表與自動(dòng)化裝置，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]齊學(xué)梅，羅永龍.求解流水車間調(diào)度問題的混合粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用，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.