求解PFSP問題的多粒子群協同學習算法

秦志偉，黃友銳，徐善永

(安徽理工大學電氣與信息工程學院，安徽 淮南 232001)

置換流水車間調度問題(Permutation Flow Shop Scheduling Problem，PFSP) 是在流水車間調度的特例，即增加了每臺機器上所有作業(yè)的加工順序都相同這一約束。但當機器數大于等于3時，置換流水車間調度問題還是屬于典型的 NP 問題[1]117。該調度問題被廣泛用于指導實際生產，可以有效提高企業(yè)生產效率與設備利用率。因此研究高效的求解算法具有重要的理論和工程意義。

粒子群算法[2](Particle Swarm Optimization，PSO)因為其通用性好、參數少、易實現等優(yōu)點，被廣泛應用于模式識別、神經網絡、生產調度等領域，PSO求解流水調度問題也成了研究的熱點。文獻[3]設計了一個基于隨機鍵最小位置值(Smallest position value，SPV)的規(guī)則，使得算法中的粒子由連續(xù)空間映射到離散空間。文獻[4]提出了一種混合粒子群算法來求解最小化中間存儲有限的調度問題的makespan，并在初始化中使用了啟發(fā)式規(guī)則，還加入了局部搜索以及模擬退火的思想，通過仿真表明此算法的有效性。文獻[5]將啟發(fā)式信息和激素調節(jié)機制結合，對粒子飛行方程進行改進，為解決PFSP提供了一個新的思路。文獻[6]將粒子群算法與迭代貪心算法混合，用來求解PFSP中的makespan，取得了很好的效果。文獻[7]將假設檢驗、模擬退火結合粒子群，用于解決分布式置換流水車間調度。文獻[8]提出一種基于Taguchi的粒子群算法并將其用于多目標置換車間調度。

針對粒子之間信息交流不足、高維求解困難等的缺點，本文在協同粒子群算法(Cooperative Particle Swarm Optimization，CPSO)[9]的基礎上，將一種多粒子群協同學習算法(MPSO-CL)用于置換流水車間調度。該算法引入了精英策略，通過不同規(guī)模Taillard系列基準實例的仿真分析，驗證該算法在求解PFSP的有效性與可行性。

1 相關問題數學描述

1.1 PFSP數學描述

PFSP的總體目標就是合理地安排工件在每臺機器上的加工順序，使所有工件最大完工時間(Makespan)最短。在研究該類調度問題時經常作以下假設：n個工件以相同的順序在m臺機器上加工；每臺機器上所有工件的順序是一樣的；每個工件在同一時刻只能在一臺機器上進行加工；每臺機器同一時刻只能處理一個工件；工件在上一個機器加工完成后，立即送到下一臺機器加工；每臺機器加工工件的過程不允許中斷[10]。

令π={π1，π2，…，πn}為一個排序，Pπ，j和Cπ，j分別為πi在機器j上的加工時間和完成時間，則PFSP數學描述如下

min∶Cmax(π)

(1)

(2)

式中：Cmax(π)為最大完成時間。

1.2 協同粒子群算法數學描述

(3)

xi=xi+vi

(4)

式中：w(w≥0)為慣性權重，c1和c2為正的學習因子，r1、r2是[0，1]區(qū)間內均勻分布的隨機數。

第j個子群粒子個體最優(yōu)位置更新公式如下

(1≤j≤k) (5)

第j個子群的全局最優(yōu)位置更新公式如下

(1≤i≤s，1≤j≤k) (6)

2 多粒子群協同學習算法

2.1 多粒子群協同學習算法模型

本文在文獻[11]的模型基礎上重新定義了學習交流機制，引入了綜合學習策略和精英策略，提出了一種經驗指導的精英學習策略，其框架如圖1所示。

圖1 多粒子群協同學習算法模型

定義1精英庫種群Z0(t)=(P1Y1，P1Y2，…，PjYi)，PjYi表示第j個子種群的第i個代表。精英庫種群Z0是由按照Pareto 的精英理論中的 80/20 法則從普通種群中篩選組建成的，它保存了各普通種群在進化過程中產生的優(yōu)良基因。利用綜合學習策略使精英庫種群內部個體相互學習，保持其種群多樣性，防止出現早熟收斂現象。

定義2普通種群Z(t)=(P1，P2，…，PI)，其中I∈Z+，其中ZI(t)表示第I個子種群。在進化過程，每一個普通種群中的個體都有概率向精英中的最好個體學習，否則只能學習自己的歷史經驗。同時隔代引進若干個精英庫種群的個體指導普通種群進化，同時淘汰其適應度最差的個體，實現了種群間的信息共享交流。

2.2 改進的綜合學習策略

精英庫種群采用綜合學習粒子群算法(CLPSO)[12]更新，其速度更新公式如下

vid=wvid+c3r3(Pbestfi(d)-xid)

(7)

式中：fi=[fi(1)，fi(2)，…，fi(D)]表示粒子i學習的Pbest向量。通過選擇概率Pc來決定精英是否需要綜合學習，在[0，1]之間產生一個隨機數k1，當k1

CLPSO算法由于速度更新中采用的是較優(yōu)的粒子，算法后期收斂速度變慢，甚至停滯。

所以在速度公式上加入柯西擾動項

vid=wvid+c3r3(Pbestfi(d)-xid)+

(8)

同時設置并設置進化停滯閥值Tn

(9)

每當CLPSO更新最優(yōu)不變，flag就會加1，當達到預設閥值，就會產生一個擾動，使精英庫粒子擺脫停滯狀態(tài)，在新的鄰域里更好地尋優(yōu)。

2.3 經驗指導的精英學習

本文在文獻[13]468的基礎上，提出了一種基于經驗指導的精英學習策略來對普通種群中的每個子群個體極值進行局部搜索。當普通種群每次迭代更新個體極值時， 通過Pe進行決策，當大于Pe時，該子群將由精英庫種群的歷史最優(yōu)pbeste1來指導學習搜索，否則通過每次迭代更新歷史最優(yōu)pbest1、次優(yōu)pbest2的差分來指導個體極值來指導學習搜索。歷史經驗指導的學習公式如下

(10)

式中：r為[-1， 1]之間隨機數，控制局部搜索的方向，d(t)為第t代時的縮放因子，控制局部搜索范圍。

進化前期，pbest1距最優(yōu)解一般比較遠，這時較大的d(t)進行粗粒度局部搜索， 加快收斂速度； 進化后期， pbest1距最優(yōu)解一般比較近， 這時通過較小的d(t)進行細粒度搜索， 可以提高解質量。 d(t)的設置給出一種非線性遞減的取值。

d(t)=d0·exp(-t/(Gennum-t))

(11)

最后對于學習后的結果進行適應度評價，若適應度好于原有的，則替換原有的最優(yōu)極值。

(12)

2.4 隔代精英遷移

普通子種群內部進化過程中，每隔兩代需要進行一次評價，若每一個子群的全局最優(yōu)個體的適應度小于等于精英庫種群的全局最優(yōu)時，則從精英庫種群中隨機引入個體并淘汰該種群中適應度最差個體。

通過隔代精英遷移，普通種群既傳承了精英庫種群優(yōu)良的基因模式，加快了其向最優(yōu)解的收斂性能，又增強了群體的多樣性，提高了尋優(yōu)能力。

2.5 粒子的編碼與解碼

本文采用了 SPV 法[1]118來對工件的加工順序進行提取。粒子的每一維表示一個工件，所得到的隨機數表示粒子每一維的位置，對粒子每一維的位置進行升序排序，然后將粒子排序好的新位置與原來維數進行映射。

3 算法步驟

Step 1 初始化。設置種群規(guī)模psize、迭代次數Gennum、慣性權重w、學習因子c1、c2，綜合學習概率Pc、精英學習概率Pe、縮放因子初值d0。

Step 2 按照spv規(guī)則，獲取每維粒子對應的工件加工序列，并由加工序列對其調度目標進行評價。

Step 3 根據Pareto 的精英理論中的 80/20 法則選擇每個子群的20%個體組建精英庫種群。

Step 4 對于精英庫種群，采用改進綜合學習策略。

Step 5 對于普通種群，采用歷史經驗指導的學習策略。

Step 7 若當前迭代次數為偶數，執(zhí)行精英遷移策略，否則轉到step 8。

Step 8 循環(huán) step 2～step 7，根據式(2)、式(3) 更新普通種群各子群粒子的速率和位置， 根據式(8)、式(3)更新精英庫種群的粒子速率和位置。

Step 9 更新迭代次數Gennum，若還在迭代范圍內，則轉到step 2；否則，停止更新。

Step 10 輸入全局最優(yōu)值和對應調度方案，調度算法運行結束。

4 仿真結果及分析

為了驗證算法的有效性，本文選擇文獻[14]提出的Ta系列的基準問題進行仿真實驗。使用 Matlab2015b 軟件編程實現，參數設置與文獻[13]469相同，分裂因子為5，慣性權重w=0.4，學習因子c1=c2=2，精英庫種群綜合學習概率Pc=0.3，縮放因子初值d0=40，設置普通種群精英學習概率Pe時，分別使用0.1、0.3、0.5、0.7、0.9值求解Ta系列基準算例Ta11、Ta21、T31、Ta41各10次，將平均值作為各算例的運算結果，再獲得所有算例求解結果的平均值并進行比較，結果Pe取0.7較好。種群規(guī)模psize=150，迭代次數Gennum=500。設置好參數后，MPSO-CL與PSO、CPSO進行比較，分別將每種算法運行10次，對每種算例運算所得的最好結果加粗顯示，得到仿真結果如表2所示。

表2中，最佳相對偏差BRE(Best Relative Error)和平均相對偏差ARE(Average Relative Error)的計算公式如下

(13)

(14)

由表1可知， PSO求解PFSP問題結果最差，CPSO運行結果比PSO有所改進，除了Ta51三種算法，MPSO-CL的結果比PSO、CPSO都好，改進效果很好， Ta01、Ta22、Ta35、T61都尋到了最優(yōu)結果。從穩(wěn)定性上可以看出， MPSO-CL的結果相對與其他三個算法比較穩(wěn)定。在處理大規(guī)模調度問題上，PSO與CPSO、MPSO-CL差距很大，說明協同進化算法在解決大規(guī)模調度問題的優(yōu)勢，而改進后MPSO-CL比CPSO在精度、穩(wěn)定性上都有提升。

為了更突出三種算法之間的差異，圖2給出了三種算法在求解Ta21、Ta71調度問題上的進化曲線。

圖2中，三種算法在執(zhí)行的初始階段，PSO收斂速度被遠遠拉下，是由于CPSO和MPSO-CL都采用了“分而治之”[16]的協同思想；由于采用學習策略局部搜索， MPSO-CL的收斂速度有所下降，但不會陷入停滯，而CPSO易陷入“偽極值點”，卻無法跳出。以上說明MPSO-CL求解置換流水車間問題的有效性。

(a) Ta21

(b) Ta71圖2 PSO、CPSO和MPSO-CL進化曲線

5 結論

本文針對置換流水車間調度中求解最小化最大完工時間問題進行了研究，提出一種多粒子群協同學習粒子群算法來進行優(yōu)化。該算法在協同粒子群算法的基礎上，將種群分為精英庫種群和普通種群，精英種群采用綜合學習策略，避免了早熟收斂；普通種群采用一種新的精英學習策略進行局部搜索，提高了解的質量；并且還引入精英遷移策略，增加了種群多樣性。通過不同規(guī)模Taillard系列基準實例與PSO、CPSO進行仿真比較，結果驗證該算法在求解PFSP上的有效性，在大規(guī)模調度上取得了不錯的效果。