基于差分量子粒子群優化算法的作業車間調度

黃宇， 顧智勇， 張中印， 王東風

(華北電力大學自動化系， 保定 071003)

以提高工作效率為目標的工業流水線問題研究一直是工業界普遍關注的領域，而群體智能算法具有很強的優化搜索能力，是求解流水線問題的有效手段，受到人們的廣泛研究[1-2]。然而作業車間調度問題(job-shop scheduling problem，JSP)的求解復雜程度高，并隨著調度規模的增加影響求解的精度和速度，導致流水線上的工作效率降低，因此提出有效、合理的智能優化算法并應用于求解JSP具有重要的理論與現實意義[3-4]。

文獻[5]提出一種新的混合整數規劃模型用于求解JSP，雖然這種模型的調度方法表達清晰、易于理解，但是存在搜索效率低、難以求解較大規模JSP的缺點。文獻[6]研究了基于異構并行遺傳算法并應用于JSP，但是其不足之處在于對種群初始化依賴程度較大。文獻[7]設計出一種有效種群初始化于方法用于提高遺傳算法求解JSP的性能，但是其不足之處在于局部搜索能力較弱，并且容易出現早熟收斂。文獻[8]介紹了混合遺傳算法和帶有變量鄰域搜索的帝國主義競爭算法來求解JSP，提高了求解速度，但仍存在局部收斂問題。文獻[9]采用染色體思想進行局部搜索并結合遺傳算法進行求解JSP，此方法將最優隨機個體添加到初始種群中，雖然這種方法可以獲得高質量的初始個體，但它增加了計算時間并降低了種群多樣性。文獻[10]提出了一種可變鄰域搜索方法，然而，大多數鄰域結構都是隨機生成的，這使得搜索變得盲目。因此，隨著JSP問題規模的增加，搜索效率降低。文獻[11]研究了基于混合蟻群算法的柔性JSP，并將遺傳算子與尋優蟻群有機結合，提高了獲得JSP最優解的概率。文獻[12-13]分別將離散粒子群算法、遺傳算法應用于求解JSP并得到了不錯的搜索效果。文獻[14]利用自適應學習策略改進了細菌覓食算法，采用在多鄰域結構下按貢獻選擇搜索方式，改善了原始算法在求解JSP出現的早熟問題。

現有求解JSP算法大部分是單一群體智能算法，存在著收斂時間慢、求解精度差等不足之處，導致難以有效地解決工業流水線上的調度問題。為此，現提出一種基于差分特性的量子粒子群優化算法。量子粒子群算法運用量子疊加原理克服了粒子群算法的粒子聚集性低且粒子搜索范圍有限的問題，具有更好的全局收斂性，但在搜索后期存在粒子早熟問題。而差分進化算法可通過變異交叉策略提高種群粒子多樣性，提升局部搜索性能，但在收斂后期速度變慢。所提算法結合二者的優勢，應用差分進化思想改善量子粒子群算法迭代過程粒子多樣性不足問題，具有很好的全局收斂性和優化性能。最后通過FT和LA兩類JSP經典算例對所提方法的求解效果進行驗證。

1 JSP數學模型

每個工件包含多道加工工序，每道工序所需時間固定且由對應的機器完成。每個制造的工件都是在預定的機器上按照預定的操作順序生產的。要求各工件選擇滿足工藝約束條件的機器，確定最佳操作順序以達到加工性能最優[15]。

設機器j加工工件k的時間為tki,j，機器j加工工件k的第i個操作的完成時間為T(ki,j)，q=(k1,k2,…,kn)是所有工件的排序，Q為所有排序集合。機器j完成操作ki的兩個條件：一是機器j完成操作ki-1，二是上一個機器j-1的操作已經完成。數學描述為

T(ki,j)=max{T(ki-1,j),T(ki,j-1)}+tki,j，

i=1,2,…,n，j=2,3,…，m

(1)

則完成所有工件操作的最大加工時間為

Tmax(q)=T(kn,m)

(2)

尋求最大完成時間的最小值的調度方案為

minf=min[Tmax(q)] ?q∈Q

(3)

式中：n為總工件數；m為機器總數。

JSP調度解的編碼具有多樣且復雜的特點，其數量也會隨著調度規模劇烈增長，形成一個巨大的解空間，其空間解的極小值分布并無特殊規律，且調度指標計算耗時較長。為此，提出一種基于差分進化的量子粒子群優化算法并應用于求解JSP中。

2 差分量子粒子群算法

2.1 量子粒子群優化算法

量子粒子群優化(quantum particle swarm optimization, QPSO)算法引入了量子模型的概念，是粒子群算法(particle swarm optimization,PSO)的發展。QPSO中粒子的狀態由概率函數而不是速度、位置來描述，該理論認為粒子在由可行解構成的勢場中運動，其運動軌跡符合特定的概率分布，可通過概率密度函數學習粒子出現在位置x的概率。QPSO的進化方程為

(4)

P=αPbest(i)+(1-α)Gbest

(5)

(6)

式中：F[x(t+1)]為粒子的分布函數；L(t)為分布的標準偏差；σ(t)為勢場中心；P為局部中心點；Pbest(i)為第i個粒子當前達到的最佳值；Gbest為當前所有粒子的最佳值；β為收縮擴張系數，一般情況下β的值從1至0.5線性遞減；u和a為均勻分布在0～1的隨機數；mbest為平均最佳值，定義為總體所有最佳位置的平均值，其計算公式為

(7)

式(7)中：M為粒子維度數。

QPSO運用量子疊加基本原理及其量子分布特征,解決了PSO算法中粒子聚集特性較低且粒子搜索范圍有限的問題。不過,在量子粒子集群計算過程中收斂后期仍會存在大量粒子早熟的現象,從而導致整個種群的復雜性大大下降,并因此面臨著局部問題優化求解。難以有效地解決解空間巨大，且具有組合優化特性的車間作業調度問題。為此，將差分進化引入量子粒子群，采取面向JSP的編碼和操作算子，將其運用于離散空間；利用差分進化(differential evolution，DE)中的變異操作方式，提高了群體突變的可能性，從而避免個體陷入局部最優；并且使用DE中的交叉方法提升對個體極值信息的使用水平。從而可以實現較短時間求取JSP問題的最優解，提高算法的搜索精度和計算速度。

2.2 差分進化算法

差分進化是一種高效的并行搜索算法，交叉、變異和選擇是DE算法的3個核心操作。

(1)變異操作目的是在種群迭代過程中構建變異個體Vi。對于每個目標個體，選擇3個隨機且不同的個體對其進行差分求和操作即產生變異個體。變異操作的計算公式為

Vi(t+1)=Xr1(t)+F[Xr2(t)-Xr3(t)]

(8)

式(8)中：r1、r2、r3分別為從區間[1，MP]中選取的不同隨機整數，MP為最大種群數；Vi(t+1)為當前迭代過程的變異個體；Xi(t)為選取的基向量與差分向量；F為縮放因子，一般情況下F∈[0.5,1]。

(2)在變異操作后引入交叉操作以保持種群多樣性。該過程根據交叉概率從變異個體或目標個體中選擇元素來構建測試種群，交叉操作方程為

Ui,j(t+1)=

(9)

式(9)中：CR為交叉概率，一般取CR∈[0.8,1]；jrand為隨機數。

(3)選擇操作中，根據適應度函數選取當前種群和測試種群中表現更好的個體，進而生成新的種群。選擇操作表達式為

Xi(t+1)=

(10)

針對QPSO存在的粒子更新方式造成的搜索精度不足問題[16-18]，將DE算法引入QPSO，采用差分量子粒子群算法(differential evolution quantum particle swarm optimization， DEQPSO)以解決JSP。

2.3 DEQPSO粒子搜索策略

DEQPSO算法粒子更新策略是QPSO和DE兩種算法粒子更新策略的結合，QPSO引入量子機制克服了PSO算法在全局收斂性上的不足，DE算法的變異操作可提升群體突變可能性，防止個體收斂到局部極值，并使用交叉、選擇方法融合入QPSO中進行粒子更新，增強粒子全局和局部搜索能力，直至得到全局最優解。改進的公式為

(11)

式(11)中：r為生成的隨機序列，其取值代表種群數量；c為生成的隨機系數。

對于迭代過程中產生的最優個體，通常它們包含最有價值的信息，因此采用多鄰域搜索局部搜索方法對這些最優值個體進行局部搜索，以提高算法的尋優速度，改善搜索質量。

自適應學習的多鄰域搜索局部搜索步驟如下。

步驟 2鄰域選擇操作。若某鄰域選擇概率大于給定值，選定其作為移動鄰域，否則改變搜索區域。篩選opt′的所有鄰域，獲得最優個體點bs；若f(opt′)>f(bs)，則opt′=bs；若f(opt′)≤f(bs) ，則重新進行鄰域選擇。

步驟3鄰域獎勵值更新操作。若f(opt)

圖1 DEQPSO算法粒子搜索步驟

DEQPSO偽代碼如表1所示。

表1 DEQPSO偽代碼

2.4 DEQPSO計算復雜度分析

算法計算復雜度是影響算法執行效率的關鍵因素，可用于評判算法性能。將所提算法從空間復雜度和時間復雜度兩方面進行分析。

空間復雜度是指算法運行所需的計算機存儲空間大小。相比于QPSO，DEQPSO增加了差分進化和多鄰域搜索操作，故空間復雜度有所增加，但對于求解JSP，增加程度是線性階的，對存儲空間影響較小。

算法的時間復雜度是指運行算法所需的時間長短，主要反映于算法執行次數。對于某個JSP問題，假設問題規模為D=n×m(n為工件數，m為機器數)，種群規模數為M。對于標準QPSO算法，時間復雜度為ο(D×M)。DEQPSO增加了差分進化算法的變異、交叉、選擇操作以及多鄰域搜索策略，而標準QPSO算法中也存在選擇操作，所以變異、交叉操作的時間復雜度為ο(D×M)；對于多鄰域局部搜索策略尋求最優值的時間復雜度為ο(D)。因此應用DEQPSO進行求解JSP的時間復雜度仍為ο(D×M)，整體時間復雜度不變。

2.5 DEQPSO實驗性能測試

選取6種已被廣泛應用于測試優化算法性能的標準測試函數[12]對所提出DEQPSO算法性能進行驗證。表2展示了所采用的測試函數方程、變量的搜索范圍以及最優解。

表2所列的6種測試函數中，前4種是維度為n的高維測試函數，f5、f6為低維測試函數，f1、f2和f3為單極值點標準測試函數，f4、f5和f6為多極值點標準測試函數。對于相同的給定條件，使用不同算法對測試函數進行尋優得到的最優解與理論值差別越小，說明算法尋優性能越好，求解精度越高。

表2 基準測試函數

將DEQPSO與引力搜索算法(gravitational search algorithm, GSA)、PSO、QPSO、差分進化算法(differential evolution algorithm，DE)以及正弦余弦算法(sine cosine algorithm，SCA)進行性能比較。將測試函數f1、f2、f3以及f4的維數n設置為32，各算法的種群規模均設置為80，最大迭代次數設置為1 200。其余參數設置信息如下。

DEQPSO參數：縮放因子為0.56，交叉概率為0.8；GSA參數：引力初值為100，學習因子為0.75；PSO和QPSO參數：加速常數c1、c2分別為3、2，慣性因子為0.6；DE參數：縮放因子為0.5，交叉概率為0.9；SCA參數：比例因子a為2，轉化概率r∈[0,1]。

表3展示了30次獨立重復實驗下各算法對各測試函數的求解情況，統計數據中的最優結果已重點標出，其中PSO與GSA的計算結果參見文獻[19]。

從表3的尋優結果可以看出，在6種基準函數測試條件下，除DE算法所得f4函數的最好值精度略優于所提算法外，本文算法求解所得結果的平均值、中值、標準差、最優值精度均遠高于PSO、GSA、QPSO、DE以及SCA。其中，在絕對誤差小于1×10-2范圍內，本文算法得到了6種測試函數的理論最優解，而其余5種算法在誤差范圍內得到理論最優解函數的個數分別為3、4、5、5、1，且誤差均大于所提算法，結果表明DEQPSO具有更好的收斂性能。對于函數f5，所提算法與DE算法得到了理論最優值0，而其余4種算法均存在一定的誤差；對于函數低維函數f6，6種算法取得了相近的結果，且尋優結果誤差均小于1×10-2。綜合以上分析可得，相比于PSO、GSA、QPSO、DE以及SCA算法，DEQPSO具有更好的尋優性能以及適用性。

表3 6種算法的實驗結果比較

3 仿真與實驗

為了驗證本文算法求解作業車間調度問題的性能，使用兩類經典的JSP算例進行測試。第一種是FISHER與THOMPSON提出的FT類，由FT06、FT10和FT20組成；第二種是LA類，選取不同規模的8種典型問題，并與典型離散粒子群算法[12]、遺傳算法[13]和細菌覓食優化算法[14]進行對比。以MATLAB為開發環境，利用CPU主頻為3.4 GHz和內存為4.0 GB的計算機進行仿真。算法運行相關參數設置如下每個JSP問題實例的初始種群規模M=500，迭代次數T=200，交叉概率CR=0.75；終止條件：最大迭代數200。選擇完成所有工件操作的最大加工時間作為評價指標。各算例均進行10次獨立運算，記錄10次實驗的運行時間以及求解結果平均值，對照情況如表4所示。

從表4可以看出，對于FT、LA兩類JSP算例，相比于其他3種算法，本文算法都能以較快的收斂速度得到其最優解；采用本文算法在求解較為困難的FT20、LA21算例時仍取得了較好的尋優結果，其中，FT20算例在10次獨立實驗中有6次得到了1 165的最優解。DEQPSO在求解難度較大的LA36問題時誤差較大，但相較于其他參考算法，DEQPSO仍表現出較強的搜索能力。

表4 DEQPSO與典型離散粒子群算法、遺傳算法以及細菌覓食算法的性能比較

為測試算法的收斂性能，并與其他3這種參考算法進行比較，僅給出FT10和LA36算例分別如圖2、圖3所示，其中對于FT10、DEQPSO在迭代到48代時，搜索到的工作時長已經接近最優值930，典型離散而粒子群算法為953，遺傳算法為965，細菌覓食算法為973，由此可見DEQPSO算法的收斂性能優于其他3種算法；對于LA36，本文算法迭代到100次時，其搜索解為1 268，而其他3種算法均在1 400以上，其他算例情況相似，可知本文算法對于空間搜索更加充分，更容易獲得空間最優解。圖4為求得的LA16算例調度甘特圖，方框中數字代表工件序號，從左到右依次表示該工件的加工次序。如圖4中灰色方框代表了工件J1的各道工序。

圖2 FT10收斂性能比較

圖3 LA36收斂性能比較

圖4 LA16算例的調度甘特圖(加工周期為945 h)

4 結論

以作業車間調度問題為研究對象，通過對原始QPSO優化機理分析，引入差分進化思想，提出一種差分量子粒子群優化算法。對所提DEQPSO算法求解性能進行驗證，得出以下結論。

(1)對6種標準測試函數進行最優值求解，DEPQSO算法求解結果的平均值、中值、標準差、以及最好值精度均優于PSO、GSA、QPSO、DE、SCA等算法，其中DEQPSO在絕對誤差小于1×10-2范圍內得到了6種函數的理論最優解，而其他算法未能全部收斂于理論值，所提算法具有更好的收斂性能以及適用性。

(2)對FT、LA兩類JSP算例進行求解，將所提算法與離散粒子群算法、遺傳算法以及細菌覓食算法進行對比。其中，LA36算例的理論最優解1 268，4種算法所得結果分別為1 294.6、1 457.4、1 374.3以及1 398，且所提算法收斂時間最短。仿真結果表明，相比于其他算法，DEPQSO算法尋優速度和精度都有了明顯提升。

(3) 所提出的差分量子粒子群算法可以較好地改善車間調度問題加工周期，為實際工業流水線作業問題提供了理論依據。