應用改進區塊遺傳算法求解置換流水車間調度問題

裴小兵，張春花

（天津理工大學 管理學院，天津 300384）

置換流水車間調度問題(permutation flow-shop scheduling problem, PFSP)是廣泛受到研究的一種組合優化問題，屬于NP-hard問題。PFSP的搜索空間中存在諸多局部最優解，且問題復雜度越高，越容易局部最優化，因此許多學者針對PFSP特性不斷對求解PFSP的算法進行優化。求解PFSP的算法可分為精確算法和近似算法，精確算法雖能求出最優解，但時間復雜性較高，隨著問題的規模增大將變得不可行。近似算法對于較大規模的問題能在可行時間內求出近優解，是研究PFSP問題的重要方法。近似算法包括遺傳算法[1]、蟻群算法[2]、模擬退火算法[3]等。

遺傳算法(genetic algorithm, GA)通過選擇、交叉和變異等操作搜索解空間的最優解，已經成功應用于解決旅行商問題、車輛路徑問題和車間調度問題等不同領域的組合問題。但是遺傳算法的局部搜索能力較差，在實際應用中容易產生早熟收斂的問題。怎么運用遺傳算法既能保留優良個體，又能維持群體的多樣性，一直是遺傳算法中較難解決的問題。近年來針對PFSP，不少學者為提高遺傳算法的有效性，將遺傳算法與其他算法相結合對該問題進行求解，取得了不錯的效果。Benbouzid等[4]針對PFSP提出VacGA(introduces vaccination into the field of GAs)，將遺傳算法和免疫算法相結合，遺傳算法執行全局搜索，人工免疫系統執行局部搜索，以克服演化過程中遺傳算法局部搜索能力不足的問題。Chen等[5]將遺傳算法與廣義鄰域搜索相結合，提出一種新型混合遺傳算法求解PFSP。Bessedik等[6]提出一種基于免疫的遺傳算法，這種算法分為兩種形式：1）將接種引入到基于免疫理論的遺傳算法；2）從免疫網絡理論得到啟發，并將其運用到遺傳算法中。Ganguly等[7]將貪婪局部搜索算子引入到遺傳算法，有效地解決大范圍的排序和調度離散優化問題。齊學梅等[8]為求解PFSP問題，將變鄰域搜索算法與遺傳算法相結合，加快了收斂速度。吳秀麗等[9]將變鄰域搜索算法和遺傳算法相結合提出了一種變鄰域改進遺傳算法求解混合流水車間調度問題，增強了遺傳算法的局部搜索能力。

Chang等[10]針對置換流水車間調度問題，提出一種基于區塊的遺傳算法(puzzle-based artificial chromosome genetic algorithm，p-ACGA)，將遺傳算法和蟻群算法相結合，通過簡單遺傳算法的交叉、突變等操作產生精英群體，針對這些精英群體，利用蟻群算法的信息素濃度對工件與工件的關系進行統計分析，進而建立信息素相依矩陣并根據矩陣挖掘區塊，利用區塊和非區塊重組形成人工染色體，然后將其注入到進化過程中。雖然p-ACGA能夠避免局部最優問題，一定程度上改善了解的質量，加快了進化速度，但是算法在初始化、信息素分布統計等方面還存在一些不足。因此本文提出一種改進區塊遺傳算法(puzzlebased improved artificial chromosome genetic algorithm，p-IACGA)。該算法在種群初始化時引入反向學習的思想，并對其進行了改進，將其與隨機機制相結合產生初始解，大大提高了初始解的多樣性和質量；為進一步描述信息素在路徑上的分布情況，算法考慮了信息素在節點上的分布情況，即工件與所在解序列位置的關系，并將其與p-ACGA中的統計分析工件與工件的相鄰關系相結合，以全面地描述解的空間分布情況。然后，根據這兩種關系建立相依信息素矩陣和位置信息素矩陣，進而挖掘區塊以組合人工染色體。最后，引入染色體重組機制，進一步提高解的質量。

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

PFSP生產調度問題可以描述為：有 n 個作業以相同的順序在 m 臺機器上加工。同時，要滿足的約束條件包括：1)操作是獨立的，可以在零時間開始；2)每臺機器在同一時間最多加工一個工件；3)每一個工件在同一時間只能在一臺機器上加工。用 P ( i,j) 表 示工件 i 在 機器 j 上的處理時間，用(π1,π2,···,πn) 表示工件序列，用 C ( πi,j) 表示完成時間的計算，即

2 求解置換流水車間調度問題的改進區塊遺傳算法

p-IACGA主要分為5部分：產生初始解、挖掘區塊、構建人工染色體、染色體重組和保留優勢解。p-IACGA流程如圖1所示，因為染色體攜帶的較優信息是逐代積累的，所以為了挖掘出較優人工染色體，每執行 n(給定的一個數)代遺傳算法后挖掘一次區塊，這樣每一輪執行的總代數是 n + 1。解并對每條初始解求出它的反向解；然后，將兩種群混合在一起形成規模為2 N 的種群，計算每個解的適應度，并按照適應度大小對解降序排列；最后，選擇前 N 條適應度較大的解作為進化的初始種群。

圖 1 p-IACGA流程Fig. 1 Flow chart of p-IACGA

圖 2 改進反向學習法Fig. 2 Improved opposition-based learning

2.1 改進反向學習法初始化種群

1)反向學習法

通過同時評估這兩個解可以獲得更好的結果。

2)應用改進反向學習法進行種群初始化

初始化過程采用隨機機制和改進反向學習機制相結合的方式，以兼顧初始解的多樣性和質量。本研究對反向學習法作了改進以減少優秀解的丟失，基本思路就是將所有原始解和所有反向解混合在一起形成混合群體，然后從混合群體中選出適應度較高的解，如圖2所示。首先利用隨機方式產生 N(N 為給定的初始種群規模)條初始

2.2 挖掘區塊

在遺傳算法中，進化若干代后，大部分染色體都會攜帶與較優解相似的一些信息，這些信息具有相似性并且這些相似性在大規模的種群中具有一定的可靠性[12]。在p-IACGA中，使用蟻群優化算法(ant colony optimization，ACO)中的螞蟻信息素濃度來識別染色體中較好的相似序列并通過區塊的方式將它們挖掘出來。

1)建立信息素矩陣

本研究使用相依信息素矩陣和位置信息素矩陣來記錄螞蟻經過的路徑信息，其中位置信息素矩陣記錄每個節點(工件在解序列中的位置)的信息素濃度信息，相依信息素矩陣記錄兩節點間的路徑(兩工件間的相鄰關系)的信息素濃度信息。矩陣建立過程如下：

從第 n 代中選擇一條最優染色體進行矩陣初始化。圖3為初始相依信息素矩陣生成過程，兩個工件間的初始信息素表示為 τ0(見式(1))。同樣的方法生成初始位置信息素矩陣如圖4。

式中 L 表示完工時間。

圖 3 初始相依信息素矩陣Fig. 3 Initially dependent pheromone matrix

圖 4 初始位置信息素矩陣Fig. 4 The initial position pheromone matrix

由遺傳算法產生的最新一代的前30%適應度較高的染色體更新信息素矩陣，更新過程如圖5，更新公式如式(2)：

圖 5 更新相依信息素矩陣Fig. 5 Update dependent pheromone matrix

同理，得到更新的位置信息素矩陣如圖6。更新公式如式(3)：

圖 6 更新的位置信息素矩陣Fig. 6 Updated positional information matrix

2)構建區塊

區塊是簡短的染色體片段，本研究通過學習鏈接關系[13]構建區塊。首先確定區塊的最小長度，然后隨機選擇起始位置，最后為各位置選擇工序。在區塊最小長度內，起始位置采用位置信息素矩陣中的信息選擇工序，如圖7，假設選擇工件 J1放 入起始位置 S1。其他位置采用位置信息素矩陣和相依信息素矩陣的合并信息，以輪盤賭選擇法(roulette wheel section，RWS)[13]對工序進行篩選，已經入選的工件不再進行篩選，如圖8，假設 C P2最大，選擇工件 J2放入位置 S2。

圖 7 起始位置工序挑選Fig. 7 Starting position process selection

圖 8 區塊最小長度內其他位置工件選擇Fig. 8 Workpiece selection at other positions within the block's minimum length

當出現兩個或多個較大值時隨機選擇。位置信息素濃度概率計算公式為

式中：i 表示工件號；j 表 示 i 所連接的上一個工件號； m 表示染色體上的工件的位置；n 表示染色體長度； P′表示工件 i 與 位置 m 在位置矩陣的概

im率； Pij表 示相依矩陣中工件 j 相 連于工件 i 之后的概率； C Pi表 示工件 i 的 合并概率； W′與 W 分別表示位置矩陣與相依矩陣的權重值，權重值會隨著進化代數的增加不斷改變[14]。

對最小長度外的位置進行工序選擇時設立合并概率最小閾值[15]，作為篩選條件。當工件的合并概率大于最小閾值時，選擇該工件，否則停止選擇工件，本區塊完成挖掘，如圖9所示。因為當區塊包含的工件越多總體概率越低，組合錯誤的概率越大，區塊閾值將會保證區塊的質量，同時也將會導致挖掘出的區塊長度也有所不同。挖掘的區塊均存放在區塊資料庫中。

3)區塊競爭

區塊競爭[16]就是去除有重復信息的區塊。將區塊資料庫中的區塊的工序與位置進行比對，如果區塊之間出現重復的工序或涵蓋的位置重復，則通過比較平均概率的方式進行選擇，平均概率較大者保留至區塊資料庫，較小者則刪除，舉例如圖10。平均概率的計算公式為表示區塊的長度；表示第 i 條區塊的第 l 個工件的位置概率； C PBil表示第 i 個區塊的第 l 個工件的合并概率。

圖 9 區塊最小長度外的工件選擇Fig. 9 Selection of workpieces outside the block minimum length

圖 10 區塊競爭Fig. 10 Block competition

2.3 組合染色體

本研究利用新建區塊資料庫中的區塊和非區塊資料庫中的工件組合出較優染色體。先將區塊資料庫中的所有區塊復制到確定長度的空白染色體對應位置，對于尚未放入工序的空位置依照其位置順序(由左到右)，利用RWS方法根據合并概率從剩余的工件中選擇合適工件放入其中。例如圖11區塊資料庫中有2個區塊，非區塊資料庫有2個工件，合并概率 C P6大 于 C P5， 選擇 J6放至位置5，剩下 J5放至位置9。

2.4 染色體重組

為了進一步提高算法搜索到最優解的機會，對每一代染色體進行重組。首先隨機選擇 N 個切點，將一條完整的染色體分割成 N +1 個片段，再從這些片段中選擇出長度最長的片段進行重組。以工件數為10切點數為2為例，如圖12，切割完成后的段數為 3 段，分別為{5，2}、{2，6，10，9，1，7}及{7，4，3，8}，選擇長度較長的片段進行重組，過程如圖13所示。

圖 12 切割人工染色體Fig. 12 Cutting an artificial chromosome

圖 13 人工染色體重組Fig. 13 Artificial chromosome reorganization

2.5 留存優勢解

將重組后的GA最新子代 μi和人工染色體Ci放入選擇池，使用二元競賽法[17]選擇出優秀染色體作為子代進入下一代進化。首先，從選擇池中隨機選擇兩條染色體，比較適應度，選擇適應度較大的染色體放入染色體庫，適應度較小的染色體放回選擇池繼續篩選，反復執行上述步驟，直到染色體庫中染色體的數量滿足設定的群體大小，如圖14。

圖 14 留存優勢解Fig. 14 Retention of advantage solution

3 實驗結果分析

為了評估所提出的算法的性能，本研究將通過對不同實例進行測試，使用誤差率(ER)作為對比指標，與其他算法進行比較。誤差率是指測試中算法所得最優解與實例已知最優解的差值占實例已知最優解的比例，ER計算公式為

式中： Ui是 實例的已知最優解； Cmax是測試算法的最優解。

本文所提算法由C++語言編寫，程序的運行環境為：處理器Intel(R) Core(TM) i5-4005U CPU @3.40 GHz，內存為4.0 GB的計算機。在本文中，選擇了29個調度問題進行比較，其中21個Reeves實例和8個Taillard實例，每個實例獨立運行30次，并求出ER的平均值。為了達到性能評價的目的，在 SGA[18]、ACGA[19]、p-ACGA[10]、BBEDA[18]、LMBBEA[20]、p-IACGA 的參數設置上選擇了最佳的、相同的參數配置以保證了算法的可比性。

以 SGA、ACGA、p-ACGA、BBEDA、LMBBEA和p-IACGA計算Taillard實例，結果如表1所示。從表 1可以看出，ta005、ta010、ta020、ta030、ta070和 ta080這6個實例中的ER值均為0，即找到了6個與實例已知解相同的解，多于其他算法所能找到的個數。盡管在 ta050實例中，BBEDA和LMBBEA的 ER值為0.85，p-IACGA的ER值為0.97，前兩者的結果優于p-IACGA，但是p-IACGA的平均值ER為0.32%，均低于其他算法，表明p-IACGA的整體求解問題的性能優于其他算法。同理，用這些算法計算Reeves實例，結果如表2。通過對Reeves的21個實例測試，發現p-IACGA在Rec0 1 、 R e c0 3 、 R e c0 9 、 R e c1 1 和 R e c35實例中ER的值為0，找到了5個與實例已知解相同的解，多于其他算法，且p-IACGA的平均誤差率為0.46，均小于其他算法，充分表明p-IACGA求解PFSP的優良性能。

表 1 Taillard實例測試結果比較Table 1 Comparison of Taillard instance test results

表 2 Reeves實例測試結果比較Table 2 Comparison of Reeves instance test results

續表 2

為了更直觀地比較算法性能，圖15給出了關于p-ACGA和p-IACGA兩個算法測試部分Taillard實例的收斂圖。從圖15中可以看出，在相同的最大迭代次數下，p-IACGA的收斂速度比p-ACGA更快。在進化初期，算法通過優化初始方法提高初始解的質量，保證進化過程中解的質量；采用節點信息濃度和路徑信息度相結合的方式生成矩陣，提高了區塊質量。在進化的后期，應用二元競賽法來尋找具有更優適應值的解，加快了進化速度。

圖 15 算例收斂圖Fig. 15 Instance convergence diagram

通過實驗數據分析，對于求解PFSP，本文提出的p-IACGA相較于SGA、ACGA、p-ACGA、BBEDA、LMBBEA和p-IACGA具有較優的求解性能。

4 結束語

本文針對置換流水車間調度問題，通過對p-ACGA改進，提出了p-IACGA。該算法初始化采用隨機機制和改進反向學習機制相結合的方式，提高了初始種群的多樣性和質量。進一步考慮了工件與所在解序列的位置關系，對節點信息素濃度進行了分析，通過位置信息素矩陣和相依信息素矩陣挖掘區塊加快了收斂速度，提高了最終解的質量。該算法保留了傳統GA的交叉、變異等操作，通過若干代的GA進化過程產生精英群體，不斷更新區塊，提高了人工染色體的質量和更新速度。實驗中，通過Taillard和Reeves實例進行測試，以誤差率作為比較指標，將結果與其他算法比較，驗證了p-IACGA的有效性。

未來研究方向可以將所提出的p-IACGA應用于其他組合優化問題，如旅行商問題、車輛路徑問題等。也可以通過改進該算法對PFSP的最小化流程時間、最小化延遲時間等其他一個或多個目標進行研究。