求解多目標柔性作業車間調度問題的混合自適應差分進化算法

陳永燦 劉 宇 周艷平

（青島科技大學信息科學技術學院，山東 青島 266061）

車間調度問題是典型的NP-Hard 問題，調度問題解決的好壞影響著企業對市場的反應能力和競爭力。柔性作業車間調度問題[1]（flexible job-shop scheduling problem，FJSP）是對傳統作業車間調度問題更深入的研究，是比JSP 更復雜的NP-hard 問題。傳統的FJSP 研究主要集中在單目標調度上，但多目標FJSP 更貼近人們實際生產需求[2]。目前，求解多目標優化問題[3]（multi-objective optimization problem，MOP）的方法分為兩類：根據每個目標函數的權重將MOP 轉換為單目標問題；運用Pareto 優化策略[4]。

差分進化算法[5]（differential evolution，DE）是Stom R 和Price K 提出的一種隨機的并行直接搜索算法，因其具有結構簡單、易于實現、收斂速度快、魯棒性強等特點被學者們廣泛使用。郭麗[6]提出了一種自適應DE 算法，通過對參數的改進來解決MOP；侍倩[7]將混合選擇機制和Archive 群體更新應用到DE 算法中，提高了DE 算法在解決MOP時搜索Pareto 最優解的質量與速度；張敬敏等[8]將混沌優化策略與DE 算法相結合來解決算法早熟的問題，并在多目標FJSP 中解決了收斂性能與早熟之間的矛盾；Wisittipanich W 等[9]為提高最優解的質量，用5 種具有不用搜索行為的變異策略解決MOP 問題；Qian B 等[10]將一種最小階值規則解決MOP 問題。在以上的研究中可以發現，學者們都是將DE 算法的參數進行各種自適應改進或將DE算法與其他算法相融合，從而提高DE 算法性能。

本文介紹了多目標柔性作業車間調度模型，提出了一種結合Pareto 支配關系的精英選擇策略和模擬退火（simulated annealing，SA）算法[11]的混合自適應差分進化（hybrid adaptive differential evolution，HADE）算法，通過測試函數證明了HADE 算法的優良性能，并通過仿真實驗證明了HADE 算法是解決多目標FJSP 的有效方法。

1 多目標FJSP 模型

1.1 多目標FJSP 描述

FJSP 是研究如何在m臺機器上加工n個工件的問題。每個工件包含多道工序，工件的工序數量不一定相等；同一工件的工序之間有確定的加工順序；每道工序可在多臺機器上加工[12]。在確定工序的加工機器及工件加工順序的基礎上，實現對最大加工時間、最大機器負荷和總機器負荷等調度目標的優化。

為了便于描述模型，本文涉及的參數見表1。

表1 模型參數表

1.2 目標函數及約束條件

本文模型共有3 個目標函數。

（1）最小化最大加工時間：

（2）最小化機器最大負荷：

（3）最小化總機器負荷：

約束條件說明：

（1）一臺機器在某一時刻只能加工一道工序。

（2）任何工序在同一時刻只能被一臺機器加工。

（3）任何開始加工的工序不能被中斷。

（4）在零時刻，所有工件都可以加工，即所有工件具有相同優先級。

（5）同一工件的工序之間有先后約束。

2 HADE 算法

2.1 編碼與初始化

HADE 算法采用一種整數編碼MSOS，由機器選擇（machine selection，MS）部分和工件排序（operations sequencing，OS）部分組成[13]。MS 部分中每個基因位用整數表示，依次按照工件和工件的工序順序進行排列，每個整數表示當前工序選擇的加工機器在可選機器集中的順序編號。OS 部分用工件號直接編碼，工件號的出現順序表示該工件工序的先后加工順序。與傳統的集成編碼、二進制編碼等編碼方式相比，MSOS 編碼使染色體更易于表現，同時在進行變異、交叉等行為時具有更強的操作性。

如圖1 所示，第一道工序可以選擇5 臺機器進行加工，但其對應的MS 部分的整數為3，則代表該工序所選擇的加工機器為其可選擇的5 臺機器中的第3 臺機器；OS 部分染色體為[1,2,3,1,1,3]，則表示的加工順序為O11→O21→O31→O12→O13→O32。

圖1 MSOS 編碼

DE 算法采用隨機分布法產生初始種群，導致種群內個體多樣性差，最優解質量與收斂速度并不理想。HADE 算法采用全局選擇（global selection，GS）、局部選擇（local selection，LS）和隨機選擇（random selection，RS）相結合的方式生成初始種群。GS 和LS 主要是為平衡被選擇的各臺機器的工作負荷，提高機器的利用率；RS 使初始種群分散于整個解空間。經測試，將GS∶LS∶RS 以4∶4∶2的比例生成初始種群。

2.2 變異操作

變異操作通常是通過改變染色體的某些基因，對染色體進行較小的改動來生成一個新個體，在增加種群的多樣性的同時也在一定程度上影響著算法的搜索能力。因HADE 算法采用MSOS 編碼方式，所以變異分為MS 部分變異和OS 部分變異。

MS 部分變異：在MS 部分中隨機選擇x個位置，依次將這些位置所選擇的機器設置為當前工序可選加工機器中加工該工序用時最少的機器。

OS 部分變異：采用部分隨機變異。在OS 部分中隨機選擇一段基因，然后將這段基因重新排序后放回染色體中，如圖2 所示。

圖2 OS 部分變異

同時，變異算子F的取值大小對種群的進化也有十分重要的影響。F過大時，個體變化較大，算法不容易收斂；F過小時，種群多樣性會降低，容易陷入局部最優解。為提高算法的收斂速度，保證種群的多樣性，HADE 算法根據沈孝龍等[14]提出的一種自適應差分進化（adaptive differential evolution，ADE）算法進行了一定的改進，使F能夠隨著迭代的進行由大變小。ADE 算法中F的取值范圍為[0.4,0.55]，與F的一般取值范圍[0,2]相比范圍較小，為進一步提升進化前期種群的多樣性，將F的取值范圍擴大為(0.55,1]，提高了種群前期的變異能力，如圖3 所示。F具體公式如下：

圖3 自適應變異算子對比圖

其中：Fmax=0.55；Fmin=0.4；，G為總迭代次數，m為當前迭代次數。

2.3 交叉操作

DE 算法將變異后種群中的個體與原始種群中的個體進行交叉操作，好的交叉操作在提高種群的多樣性的同時還能提高算法的收斂速度。HADE 算法的交叉操作分為MS 部分交叉和OS 部分交叉。

（1）MS 部分交叉

該部分交叉采用改進的均勻交叉的方式，具體步驟如下：

①隨機生成一個大于1 并且小于所有工件的工序總數的整數l。

②按照隨機數l再隨機生成l個不相等的整數。

③根據步驟②中產生的l個整數，依次將原始種群染色體中對應l個整數位置的基因覆蓋變異后種群染色體中對應位置的基因。

（2）OS 部分交叉

采用改進的POX 交叉方法，在每個染色體中對多個工件進行操作，能夠較好地繼承父代個體的優良特征，具體操作如下：

①在工件集{J1,J2,J3,···,Jm}隨機選取任意數量的工件構成子工件集Jobset1。

②將原始個體中包含在工件集Jobset1 中的工件復制到新個體中，并保持它們的位置和順序。

③將變異后個體中不包含在工件集Jobset1 中的工件復制到新個體中，并保持它們的順序。

OS 部分交叉如圖4 所示。

圖4 改進POX 交叉

2.4 結合Pareto 支配關系的精英選擇策略

為加速算法收斂，保證種群最優解不會因變異操作和交叉操作的影響而消失，本文對迭代過程中的原始種群與交叉后的種群進行結合，采用基于Pareto 支配關系的非劣解快速排序方法對種群中的個體進行分類，將種群分為具有支配關系但互不相交的子種群，最后通過擁擠距離的計算得到新種群。傳統的精英選擇策略在處理MOP 時選擇的最優個體很難滿足多個目標函數；基于聚合的精英選擇策略按照權重比將MOP 轉換成了單目標問題，但該方法難以確定合適的權重比；基于準則的精英選擇策略只能求出每個目標函數的最優個體，難以確定滿足所有目標函數的個體。結合Pareto 支配關系的精英選擇策略通過Pareto 支配關系的非劣解快速排序方法和擁擠距離計算，可以得到滿足各目標函數的多個最優個體，該策略既可以保留算法在進化過程中的多個最優個體，還保護了種群的多樣性，同時對算法的收斂速度有一定的提升。

結合Pareto 支配關系的精英選擇策略的具體步驟如下。

（1）將原始種群與交叉后的種群合并為一個臨時種群。

（2）根據整體規則和個體規則將臨時種群生成新的種群。

①整體規則：按照從低到高的順序排列用快速排序方法生成的Pareto 等級，根據Pareto 等級將種群中的個體按層劃分，依次將每層種群中的個體放入新種群中，直到父代種群達到種群規模；

②個體規則：按照擁擠距離從大到小的順序排列該層個體，依次放入父代種群中，直到父代種群填滿。

2.5 融合SA 算法的選擇操作

傳統DE 算法的選擇操作是將交叉后的個體與原始個體逐一對比，按照適應度值擇優選擇。這個方法的弊端是容易陷入局部最優解，為解決這一弊端，HADE 算法在選擇操作中結合了SA 算法，對適應度值比原始個體差的交叉后的個體進行操作，嘗試選出更好的個體替代原始個體，從而跳出局部最優解，具體步驟如下：

（1）將交叉后的個體與原始個體按照0.6∶0.3∶0.1 的權重比對最大加工時間、最大機器負荷、總機器負荷進行適應度值計算。

（2）判斷適應度值大小。若交叉后的個體適應度值更低，將交叉后的個體替代原始個體；否則，對交叉后個體進行SA 處理。

（3）設置初始溫度T0，T=T0。

（4）令T=λT，λ表示退火速率，λ∈(0,1)。

（5）對當前個體的OS 部分進行隨機擾動，使其產生一個新個體，計算出原始個體與新個體的差值，若差值小于0，則接受該個體替換原始個體，結束循環。

（6）判斷是否達到終止溫度，若是，則結束循環，否則轉到步驟（4）。

2.6 HADE 算法流程

HADE 算法流程如圖5 所示。

圖5 HADE 算法流程圖

利用HADE 算法求解多目標FJSP 主要步驟如下：

（1）設置HADE 算法中種群規模、最大迭代次數、Fmax、Fmin、T等參數。

（2）根據調度問題將GS、LS 與RS 結合使用生成初始種群。

（3）對種群進行改進自適應變異操作和改進交叉操作。

（4）求交叉后種群與原始種群合并后的Pareto最優解，根據計算出的擁擠度距離擇優保留。

（5）將新種群與原始種群根據權重比得到的適應度值進行選擇操作，若新個體優于原始個體，則更新原個體；否則，進行SA 操作。

（6）判斷是否達到最大迭代次數。若滿足，循環結束；否則，轉到步驟（3）。

（7）將輸出的最優個體解碼并轉換成對應的調度序列，算法結束。

2.7 函數優化測試

根據劉昊等[15]對標準測試函數的描述，選取表2 中的兩個函數作為本文的測試函數，驗證HADE 算法相較于ADE 算法與DE 算法的優越性。對3 種算法設置相同的操作參數及相同的初始種群。圖5 和圖6 所示為DE、ADE 和HADE 三種算法在最大迭代次數為30、種群規模為100 時得到的最優解與迭代次數的變化曲線。

圖6 3 種算法在測試函數1 中的性能比較

表2 測試函數

由圖6 和圖7 可知，HADE 算法比ADE 算法和DE 算法到達全局最優解0 需要更少的迭代次數；在迭代次數相同時，HADE 算法所獲得的最優解要比ADE 算法和DE 算法更好。實驗結果表明，HADE 算法的收斂速度和平均適應度都有一定的提高。

圖7 3 種算法在測試函數2 中的性能比較

3 仿真實驗及結果分析

本文使用Brandimarte P[16]所提出的Mk02（10個工件6 臺機器）、Mk04（15 個工件8 臺機器）、Mk08（20 個工件10 臺機器）三種數據集，使用Python 編程，將Windows 10 運行平臺下的Pycharm軟件作為仿真環境。設置初始種群規模為40，迭代次數為80，T0為5，λ為0.8，將HADE 算法與混合差分進化（hybrid differential evolution，HDE）算法[7]、ADE 算法和DE 算法進行比較，為防止實驗的偶然性，每種算法各運行10 次。選取最大完工時間最小的3 組解進行對比，實驗結果見表3，其中(67,67,390)代表最大加工時間為67、最大機器負荷為67、總機器負荷為390。

表3 實驗結果比較

由表3 的Mk02、Mk04 結果可以看出，HADE算法對最大加工時間和最大機器負荷兩個目標函數的優化明顯優于其他三種算法，其中，DE 算法的優化效果是最差的。單看總機器負荷這一目標函數在Mk04 中的優化結果，四種算法的總機器負荷平均值為383.7、388.7、400、396，說明HADE 算法對這一目標函數的優化也是最好的，但相差不大。在處理較大規模數據集Mk08 時，HADE 算法雖比其他3 種算法更優，但無太大差距。總體來說，HADE 算法相較于HDE 算法、ADE 算法和DE 算法的優化效果更優，是一種適用于求解多目標FJSP的算法。

圖8 所示為權重占比最高的最大加工時間在Mk04 數據集中四種算法的迭代過程曲線。當迭代次數相同時，HADE 算法的最大加工時間最小；當最大加工時間相同時，HADE 算法的迭代次數更少。綜上所述，HADE 算法具有更好的尋優能力，在求解多目標FJSP 問題時具有一定優勢。

圖8 最大加工時間在Mk04 中4 種算法的進化曲線

圖9 所示為對比4 種算法在Mk04 中得到的Pareto 解集，可以看出HADE 算法的尋優能力更強，能得到更好的解。

圖9 去重Pareto 解集對比

圖10 所示為使用HADE 算法對Mk04 數據集優化時得到的最大加工時間為67、最大機器負荷為66、總機器負荷為376 的調度結果甘特圖。

圖10 調度優化結果甘特圖

4 結語

本文提出了HADE 算法對多目標FJSP 進行求解，針對最小化最大加工時間、最小化機器最大負荷、最小化總機器負荷等目標函數進行優化，在Mk02、Mk04 和Mk08 這3 種數據集中與HDE 算法、ADE 算法、DE 算法進行仿真對比，最終表明本文算法收斂性更好，尋優能力更強，在求解FJSP 時效果更優。但在處理Mk08 等較大規模數據集時收斂速度相對較慢，后續工作將針對處理大規模問題時進一步提升算法的尋優能力和收斂速度。