指針網絡與遺傳算法求解置換流水車間調度問題

蔡國帥，金 淳，華順剛

（1.大連理工大學機械工程學院，遼寧大連 116024；2.大連理工大學經濟管理學院，遼寧大連 116024）

0 引言

置換流水車間調度問題（Permutation Flow-shop Scheduling problem，PFSP）作為典型的生產調度問題，是許多實際生產調度問題的簡化模型，在運輸、物流、車間生產等領域有著大量的應用[1]，已被證明3臺機器以上的PFSP問題屬于NP-Hard難題[2]。因此，研究該問題的優化算法具有重要的理論意義和工程價值。

求解PFSP的方法主要分為3類，精確算法、啟發式算法和智能優化算法。精確算法主要有分支定界法、整數規劃和動態規劃等方法，由于其計算復雜度大，僅用于求解小規模問題。啟發式算法有CDS（Campbell Dudek Smith）算法、Palmer算法以及NEH（Nawaz Enscore Ham）算法，啟發式算法具有求解速度快的優勢，但是其求得的解的質量較差。由于精確算法和啟發式算法存在不足，目前對PFSP的研究多集中于智能優化算法。常用的智能優化算法有粒子群優化算法、遺傳算法、蟻群算法和差分進化算法等。盡管許多智能優化算法在PFSP上取得了不錯的效果，但是其迭代過程通常比較耗時，因此很多文獻中利用不同的算法生成群智能優化算法的初始種群，以提高初始種群的質量，提升算法的性能。如Zhang等[3]將NEH算法與遺傳算法結合，并融合模擬退火算法，以提升算法性能。秦旋等[4]將NEH算法和共生生物搜索算法相結合，設計了一種混合生物共生算法，并獲得了良好的性能。王凌等[5]利用訓練好的指針網絡輸出初始解，設計一種帶反饋機制的迭代貪婪算法。

由此可見，種群初始化是群智能優化算法的第一個階段，也是影響算法性能的一個重要因素。而深度強化學習技術求解組合優化問題具有求解速度快、泛化能力強的優點，并且可以利用訓練好的網絡直接輸出問題的解。因此適合用來對群智能優化算法的初始種群進行初始化，以提高初始種群質量，提升算法性能。近年來，在組合優化領域出現了多個深度強化學習的新方法[6]，如指針網絡、圖神經網絡。Vinyals等[7]提出了一種名為指針網絡的神經架構來學習輸出序列的條件概率，并用于求解旅行商問題。Bello等[8]提出了一個使用神經網絡和強化學習來解決組合優化問題的框架，在100個城市規模旅行商問題上接近最優解。

因此本文將指針網絡和遺傳算法相結合，利用指針網絡來生成PFSP問題的初始序列，并用于遺傳算法初始種群的構造，然后利用結合重啟機制和局部搜索技術的遺傳算法來獲得最終的解。通過仿真實驗測試Reeves標準數據集，驗證了算法的有效性。

1 置換流水車間調度問題描述

PFSP問題通常描述為n個工件J={1,…,n}在m臺機器M={1,…,m}上加工，每個工件在各機器上加工順序相同而且每臺機器加工的各工件順序也相同，給定工件i(i∈J)在機器j(j∈M)上的處理時間pij，目標是求得一個工件加工順序使得某個調度目標達到最優，常用的調度目標是最大完工時間Cmax。

PFSP問題的假設如下：（1）所有工件在零時刻均可加工；（2）工件在不同機器間的運輸時間和設置時間包含在處理時間中；（3）每臺機器在同一時刻只能處理一個工件；（4）不允許作業搶占，即在每臺機器上工件一旦開始加工則不能中斷；（5）機器之間的緩沖區容量無限大。

令π=(π1,…,πn)代表所有工件一個加工序列，其中πi∈J。Cπi,j和pπi,j分別表示工件πi在機器j上的完成時間和加工時間。最大完工時間Cmax的計算過程如下：

置換流水車間調度的目標是求得一個最優工件加工順序π=(π1,…,πn)，使得Cmax最小。

2 指針網絡與遺傳算法求解流程

指針網絡改進遺傳算法框架如圖1所示。

圖1 PN-HGA算法框架

2.1 指針網絡與參數優化

2.1.1 數據預處理

傳統的指針網絡是用來求解TSP問題，編碼網絡的輸入為二維向量，而PFSP問題的輸入維度則是機器的數量m，因問題不同而不同，這導致指針網絡不能直接應用于PFSP問題。

因此本文對PFSP問題的數據進行預處理，考慮到標準算例（Carlier、Reeves、Taillard）的最大機器數為20，因此可以在算例數據后面增加（20-m）個所有工件加工時間都為0的機器，其最終的最大完工時間和原算例相同，并不會影響調度結果。因此對于一個n個工件，m(m≤20)個機器的調度問題，經過預處理操作后轉化為一個n個工件，20個機器的調度問題。因此對于不同的調度問題，其機器維度固定為20，然后可以通過指針網絡進行求解。

2.1.2 編碼與解碼

指針網絡包括兩個循環神經網絡（RNN）模塊，編碼網絡和解碼網絡，如圖2所示。

圖2 指針網絡結構

這兩個模塊都由長短期記憶（LSTM）網絡組成。編碼網絡讀取實例是由工件i在每臺機器上的處理時間組成的向量。每次讀取一個工件，并將其轉化為一系列的隱藏狀態。在第i步時：

式中：Whp、Whh、h0為待訓練的網絡參數；sigmod()為激活函數；q()表示c是h1,…,h n線性組合；c為編碼網絡的最終輸出，是一個存儲了輸入序列信息的語義向量。

解碼網絡對語義向量c進行解碼。在第一步解碼過程中，即t=0時，解碼網絡讀入語義向量c，輸出當前的隱藏狀態s0，利用Ateention機制跟據s0和編碼器得到的各個工件的隱藏狀態計算選擇各個工件的概率，此時可選擇概率最大的節點作為第一步選擇的工件；在接下來的解碼過程中，即t=1,2,…,n時，解碼網絡讀入上一步的隱藏狀態和上一步選擇工件的特征向量，輸出當前的隱藏狀態st。根據st和各個工件的隱藏狀態計算選擇各個工件的概率。繼續選擇具有最大概率值且沒有被選擇過的節點添加到解當中，按照該方式不斷選擇工件，直至構造一個完整的解。計算公式如下：

式中：v T、W1、W2、y0、Why、Whs為待訓練的網絡參數；s0=c；y t∈o。

2.1.3 策略梯度優化參數

由于采用監督式的訓練方式往往依賴高質量的標簽，而對于PFSP問題，獲得高質量標簽是很困難的。因此采用基于策略的強化學習來優化指針網絡的參數。訓練目標是預期的完工時間，在給定實例o的情況下，該完工時間的期望如下：

假設實例o的加工時間服從分布O，則訓練的目標函數為：

采用策略梯度法優化參數，上式的梯度是使用眾所周知的REINFORCE算法[9]來計算的：

式中：b(s)為不依賴于π的基線函數，并估計預期完工時間以減小梯度的方差。

在訓練過程中，每次從分布S采樣M個實例，并對每個實例oi采樣一個加工序列πi～pθ(.|o i)，上式中的梯度用Monte Carlo采樣近似如下：

然后采用ADAM優化器進行參數優化參數：

2.2 改進的遺傳算法

現有遺傳算法求解PFSP問題通常使用NEH算法來生成一個解，然后隨機生成來初始化種群，而且在迭代后期通常由于種群多樣性降低而停滯在局部最優值附近。因此本文通過訓練的指針網絡與NEH算法相結合來初始化種群，以提高初始種群的質量，并利用重啟機制，在算法陷入局部最優的時候對種群進行調整，來提高算法性能。

2.2.1 編碼與種群初始化

PFSP最常用的編碼是工件的簡單排列，排列中工件的相對順序表示車間機器對工件的加工順序。如一個個體為（2，1，3）表示工件2最先加工，然后加工工件1，最后加工工件3。

為了更好地理解本文初始化過程，簡要描述NEH過程[10]，該過程基于這樣的思想，即所有機器上總加工時間最長的工件應該盡可能早地被調度。這種啟發式方法可以分為3個簡單的步驟如下。

（1）m臺機器上作業的總加工時間計算如下:

（2）工件按Pi的降序排序。然后，獲取前兩個工件（具有較高Pi的兩個工件），這兩個工件有兩種可能的加工序列，計算這兩個加工序列的完工時間，選擇完工時間較小的那個序列。

（3）繼續選擇第i個工件（Pi排第i的工件），并通過將其放置在已調度工件序列中所有可能的i位置來找到最佳調度序列。假如i=3，分別將其插入步驟（2）中選擇序列的頭部、中間和尾部生成3個序列，將選擇3個中的最佳序列用于下一次迭代。

初始化過程基于這個NEH算法和這個算法的修改，初始化種群采用兩種方法：第一種在步驟（2）中對工件進行排序后，只需從有序列表中選擇兩個隨機工件，并用它們來交換前兩個工件，然后繼續步驟2和3的剩余部分來生成部分個體；第二種則在在步驟（2）中工件的序列為訓練好的指針網絡生成的序列，之后和第一種方法一樣生成部分個體。

2.2.2 選擇與種群迭代方案

常用的選擇方案為輪盤賭選擇和錦標賽選擇。本文選擇錦標賽選擇，在整個種群中隨機抽取n個個體，選擇其中的最優的個體作為父代個體。

種群迭代方案有子代取代種群中最差個體和子代直接取代父代的兩種方法。本文采用子代取代種群中最差個體的方法，即子代個體適應度大于種群中最差個體的適應度，并且子代并不存在與種群中的時候子代取代種群中最差個體。

2.2.3 交叉

遺傳交叉算子通過組合父代來產生新的子代。目標是產生“更好的”子代，即在與父母雜交后創造更好的序列。常用的交叉算子有單點順序交叉（OP）、兩點順序交叉（TP）、部分匹配交叉（PMX）等。本文采取一種相似塊序兩點交叉（SBOX）的算子，該算子首先考慮至少兩個連續相同作業的塊，只有那些在父代中占據相同位置的相同塊才被直接復制到子代，然后再保留相同塊的基礎上采用單點順序交叉的方法對父代進行交叉，具體過程如圖3所示。

圖3 SBOX算子

2.2.4 變異

遺傳算法中的變異算子主要是為了避免收斂到局部最優，并在種群中重新引入丟失的基因。變異算子主要有互換突變、位置突變和移碼突變。本文采用移碼突變，即隨機選擇一個工件插入到另一個隨機的位置上去，具體過程如圖4所示。

圖4 移碼突變

2.2.5 重啟機制

在遺傳算法中，種群經過多次迭代之后，種群的多樣性降低，使其停滯在局部最優值附近。因此在遺傳算法中加入重啟機制：在每次迭代，存儲種群的最小完工時間mak i；如果mak i=maki-1則count mark+=1，否則countmark=0；如果countmar k＞Gr，則重新調整種群：首先將種群按照Cmax升序排序，將最小的20%加入新得種群，然后通過對最佳20%個體進行移碼突變產生新的20%的個體加入新得種群，之后通過初始化種群的兩種方法分別生成20%的個體加入新得種群，剩余20%個體則隨機產生。

利用重啟機制，每當種群中最小的最大完工時間超過Gr代不變時，重啟機制將替換種群中除20%以外的所有最佳個體，希望重新引入種群多樣性并脫離局部最優。

2.2.6 局部搜索

局部搜索從個體中隨機提取所有工件，并將其重新插入所有可能的位置，當找到更好的個體時，它將被保留，并且該過程將繼續，直到檢查完所有工件。對每一代中的所有個體應用局部搜索會消耗很多時間，因此通常設置一個局部搜索概率Penh來控制個體是否進行局部搜索。本文在變異之后以Penh的概率對子代進行局部搜索，并且在每一代之后對種群中的最優個體以2Penh的概率進行局部搜索，以提高個體質量。

3 實驗結果與分析

3.1 實驗設計和參數設置

指針網絡訓練階段相關參數設置如下：指針網絡每次采樣數（Batchsize）設為512，RNN采用長短時記憶網絡（LSTM），網絡隱藏層維數設為128，參數優化采用Adam算法，學習率設為1×10-4，學習率衰減速率每5 000步0.96。網絡初始參數為[-0.08，0.08]之間均勻分布的隨機數。訓練數據隨機生成1 024 000個數據，其中規模n_m=（30_5，30_10，30_15，30_20）的訓練數據各占1/4，工件在各個機器上的加工時間為[0，1]均勻分布的隨機數，經過預處理操作后進行訓練。

在遺傳算法迭代搜索環節相關參數設置如下：迭代次數為4 000，重啟參數Gr=25，種群規模Psize=20。遺傳算法中3個關鍵參數交叉概率Pc、變異概率Pm、局部搜索概率Penh的取值會影響算法的性能，因此采用Rec19算例進行正交試驗，每個參數設置4個水平值，數值如表1所示。

表1 參數水平

利用正交表L16進行實驗，在每組參數組合下獨立運行算法10次，采用10次所得的完工時間平均值（AVG）作為響應值，結果如表2所示。

表2 實驗方案與實驗結果

各參數響應值如表3所示。由表3可知，Penh對算法性能的影響最大，Pc其次，Pm對性能的影響最小。根據試驗結果的對比，最佳參數組合為：Pc=0.4，Pm=0.015，Penh=0.075。

表3 各參數響應值

算法性能評價標準采用最優相對誤差（Best Relative Error，BRE）和平均相對誤差（Average Relative Error，ARE），計算公式如下：

式中：Cmax為運行10次中的最優值；為運行10次的平均值；C*為當前算例的最優解。

本文使用Python 3.7編程，進行測試的平臺的參數如下：CPU為Intel（R）Core（TM）i5-8300H CPU@2.30 GHz，內存16 GB，操作系統為Windows 10。

3.2 指針網絡效果檢驗

為了驗證指針網絡生成初始解的有效性，將指針網絡生成的解與NEH算法生成的解進行比較。選擇PFSP問題常用的Rec測試算例，指針網絡獨立運行10次，取最優相對誤差進行比較。比較結果如表4所示。從表中可以看出，指針網絡生成的解有13算例結果優于NEH算法，因此采用指針網絡與NEH算法結合來初始化遺傳算法能夠提高初始種群的質量。雖然21個算例的平均值指針網絡結果比NEH算法差，主要是由于訓練網絡的數據最大為30個工件，而最后3個算例（Rec37、Rec39、Rec41）的工件數達到75個，因此在這幾個算例上指針網絡表現很差，拉高了指針網絡的最優相對誤差的平均值。

表4 指針網絡與NEH算法結果

3.3 PT-HGA算法結果

為了驗證PN-HGA算法求解PFSP問題的性能，選擇PFSP問題常用的Rec測試算例，并將PN-HGA與求解PFSP的混合遺傳算法（HGA）[3]、變參數量子進化算法（VP-QEA）[11]、混合差分進化算法（L-HDE）[12]、混合共生生物搜索算法（HSOS）[4]的求解結果進行比較，比較結果如表5所示。從表5可以看出，PN-HGA算法求解的21個算例有19個算例的最優相對誤差和15個算例的平均相對誤差等于或優于所比較的幾種算法。而從整體上來看，PN-HGA的最優相對誤差的平均值為0.375，平均相對誤差的平均值為0.630，均優于其他4種算法，證明了PN-HGA算法的有效性。

表5 測試結果比較

4 結束語

本文提出了求解置換流水車間調度問題的一種指針網絡與遺傳算法結合的框架，創新之處：首先，根據PFSP問題與指針網絡的特點對算例進行預處理，使得訓練的指針網絡可以適用于不同規模的算例，通過與NEH算法比較，驗證了指針網絡的性能；其次，將指針網絡生成的解并結合NEH算法用來初始化遺傳算法的初始種群，以提高種群質量，提升算法性能，并利用重啟機制來提高算法的全局搜索能力。通過對Reeves標準測試集進行仿真測試，并與4種智能優化算法相比較，驗證了本文算法的有效性。未來的研究著重于優化模型的訓練，以提供更高質量的解，提升算法的性能，并將算法應用于其他類型的調度問題。