帶學習策略的遺傳算法求解柔性作業調度問題

王公堂，許化強

（山東師范大學 物理與電子科學學院，山東 濟南 250014）

傳統的作業調度問題中，作業的每一道工序都是預先知道的，而且工序的加工機器和時間也是預先確定好的。而在柔性作業調度問題中，工序的加工機器是不確定的。作業的每一道工序都可以在多個加工機器上加工，而且不同的加工機器所需要的加工時間也不相同。在處理此類問題上，不僅要處理作業之間的調度問題，而且要考慮每一道工序面臨可選擇機器的問題，使問題更難以解決。針對柔性車間調度問題的特點，筆者在Yasuhiro Tsujimura[1]等人提出的主從共生遺傳算法的基礎上進行改進，加入學習策略，在進化過程中發掘并保留種群中的優秀特征，并指導后代的進化，加快收斂速度，提高搜索效率。

1 帶操作柔性的作業調度問題描述

具有操作柔性（OF）的柔性車間調度問題（Flexible Job-Shop Scheduling Problem，FJSP）是指同一個操作（或工序）可以在不同的機器上運行。FJSP假定加工系統中有M臺機器和N個作業，每個作業包括一道或多道操作，操作順序是預先確定的，每道操作可以選擇在多臺不同的設備上加工，操作的加工時間隨加工設備的不同而變化。例如，表1是FJSP的一個例子，共有2個作業，3個加工機器，每道工序可以選擇在不同機器上以不同的加工時間加工。調度目標是為每道工序選擇最合適的加工設備，以及每臺設備上各工序的最佳加工順序，使所有作業的流通時間最短。該問題所需滿足的約束條件[2]是:1）所有作業在初始時刻都可加工；2）工序在可供選擇的若干機器上加工的時間已確定；3）每臺加工機器在固定的時間段內只能加工一個作業；4）每個作業在固定時刻只能在一臺機器上加工。

表1 一個FJSP的實例 2×3Tab.1 An example of the FJSP 2×3

2 共生遺傳算法設計

柔性車間調度可分成兩個子問題，一是為操作選擇加工機器，二是類似經典車間調度問題，給作業一個合適的排序，得到最優調度?？蓪⑦@兩個子問題看作是共生機制中的兩個不同的物種，進而用不同的種群來表示，一個種群為控制種群，為工序選定合適的加工機器；另一個種群為調度種群，在控制種群的限制下優化調度。

2.1 編碼設計

將柔性車間調度問題分為兩個子問題，對應兩個不同類的種群，其個體分別稱為控制染色體和調度染色體，每個種群的個體都應該有自己的編碼方式[3]。

控制染色體編碼方法：將所有的操作按照其所屬的作業號和其在作業中的加工順序依次排列，并將其選擇的加工機器放在工序對應的位置上。即是控制染色體采用基于作業的編碼方式，將每個作業的所有工序選擇的加工機器的順序排列作為控制染色體的一個基因塊。例如，對表1中所示例子，可以有控制染色體12321，其中基因塊123為作業1（J1）的各個操作選擇的加工機器：操作 O1，1選擇的加工機器為 M1，O1，2選擇的加工機器為M2，O1，3選擇的加工機器為M3；基因塊21為作業2（J2）的操作所選擇的加工機器排序序列。

調度染色體編碼方法：調度染色體采用基于操作的編碼方式，并把操作按照加工機器的不同分為不同的基因塊。因此，如果有m臺加工設備，則調度染色體有m個基因塊。如果某個設備基因塊中包含同一個作業的多個操作，則這個基因塊中的所有操作排序時，必須注意同一個作業的多個操作之間的先后約束關系，即先加工的操作必須排列在后加工的操作的前面。 例如作業 1 有 3 個操作 O1，1，O1，2，O1，3；作業 2 有2 個操作 O2，1，O2，2。 假設這 5 個操作選 取 的加工 機器分別為M1，M2，M3，M2，M1。 則在機器 M1上加工的操作一個可能的排列為O1，1O2，2，這個字符串為調度染色體編碼的一個基因塊；同理，在機器M2上加工的操作可能的排列為O1，2O2，1；在M3上加工的操作可能的排列為O1，3。按照機器序號，將這些基因塊組合到一塊，則組成了調度染色體 O1，1O2，2O1，2O2，1O1，3。 這種編碼方式的一個優點就是可以將對染色體的操作提高到基因塊的級別上。

2.2 進化過程中的學習

進化過程是基于隨機自然選擇和基因重組。如果不考慮保留種群中優秀的特性而進行種群進化，則可能需要很長的時間才能找到全局最優解。針對控制種群和調度種群，分別設立學習機制，用于學習、記錄以及指導后代種群的進化，提高搜索質量和效率。設立兩個信息存儲空間，即染色體空間和操作空間[4]。

染色體空間：具有最大適應度值的不同染色體之間具有很多相似的特征[5]，如果當某個調度染色體中出現了最優解的一些排序特征，就應該及時把它保存下來，希望多個調度中的不同的最優特征經過交叉之后能夠在進化機制的幫助下逐漸集中，就可以使算法很快向最優解收斂。染色體空間中存儲的是前幾代中挑選出來的最好的染色體。進化到當前代時從當前種群中選擇一定數量的適應度最高的染色體，每一個選出的染色體要與染色體空間中的染色體做比較。染色體空間中k個具有最高相似度的染色體將被復制到當前代種群中。采用基于染色體中操作的差異來定義兩個染色體的相似度。相似度可以用下面的公式計算：

其中M表示調度染色體中設備基因塊的個數，Qi表示設備基因塊i中操作的個數。Chm1和Chm2表示調度染色體，Opt1、Opt2 表示 Chm1、Chm2 中的操作，Opt1（i，j）表示染色體Chm1 中設備基因塊 i中第 j個操作。 如果 Opt1（i，j）、Opt2（i，j）表示的兩個操作相同則操作符返回0，否則返回1。S越小，則表示兩個染色體Chm1、Chm2越相近。染色體空間主要用來保存以前代中的優秀染色體，用來提高后代交叉的效果。

操作空間：在進化過程中為作業的工序選擇最合適的加工機器。如圖1所示，其全部信息是要加工的作業以及作業的全部操作和操作對應的可選加工機器集合，作業對應的加工機器各自都有一個參考數據，該數據表示在以往的優秀染色體中，該加工機器被選中加工此操作的情況，重新選擇加工機器時可以根據這個信息選擇最可能合適的機器。該空間數據在進化過程中每隔n代更新一次。圖1中展示的共有N個作業，其中作業3有x個操作，操作O3，3有3個機器可以選擇M1M2M3，其中機器M1以往較優染色體中選中率為30%，M2以往選中率為20%，M3被以往被選中的概率為50%。當對控制染色體執行變異操作時，如果為某個操作重新選擇加工機器，可以在此空間數據的指導下選擇最可能合適的加工機器。

圖1 操作空間示例Fig.1 Example of operational memory

2.3 算法設計

對FJSP問題來說，因為不同的子問題有其本身的特征，因而在進化過程中，應該考慮到不同的種群的地位和進化速度也應該不同，適當搭配不同物種之間的進化速度會獲得比較好的結果。因為調度種群是在控制種群的指導下進化的，調度種群的進化結果影響控制種群中染色體的適應度，因而，在進化速度方面，調度種群應該比控制種群要快得多。筆者將控制種群作為進化主過程，調度種群作為從過程，改進后的共生遺傳算法如下：

1）主進化過程：控制染色體的適應度取其控制下的調度種群進化后最優調度染色體的適應度。

Step 1：生成初始種群，大小為pop_size；

Step 2：種群中的每一個控制染色體都對應一個調度種群，使用2）從進化過程對調度種群進化，依次得到每個控制染色體的適應度fc。

Step 3：統計控制染色體的最大適應度fcmax和平均適應度fcavg。

Step 4：如果連續m代最大適應度沒有變化或者達到最大進化代數，則算法結束。否則繼續執行Step 5。

Step 5：選擇：對控制染色體種群執行輪盤賭選擇操作[6]。

Step 6：交叉，變異：根據操作空間的信息指導變異操作：

Step 7：更新：選出一定數目的最優控制染色體，對操作空間進行更新。轉到Step 2）繼續。

2）從進化過程：調度染色體的進化。

Step 1：初始化調度種群。根據控制染色體為操作選定的加工機器，生成初始種群。

Step 2：計算調度種群中每個染色體p的最早完工時間MS，同時計算適應度值=1/MS。

Step 5：對調度染色體種群進行選擇操作。選擇出來的部分染色體還要和染色體空間中的染色體做比較，并將染色體空間中最相似的k個染色體插入到當前種群中。

Step 6：交叉變異操作。

在紅磷及其三鹵化物或氯化亞砜的催化下，脂肪酸的a-H可被氯、溴取代生成a-鹵代酸，此反應被稱為Hell-Volhard-Zelin-Sky反應，反應機理如下：

Step 7：更新：每隔k代更新染色體空間。轉Step 1繼續。

3 遺傳算子設計

3.1 交叉算子

對控制染色體的交叉操作采用染色體中多點交換操作。隨機決定發生交換的染色體中基因的個數和位置，并將兩個父個體中對應位置的基因交換，生成新的個體。對調度染色體的交叉操作采用基于設備基因塊交叉法。兩個調度染色體可能會發生與設備基因塊數目M相同多的多點交叉。

3.2 變異算子與學習引導

控制染色體變異主要針對某個作業的全部操作。因此，首先應該選中需要變異的作業。如果選中某個作業變異，則這個作業的所有操作都要重新選擇加工機器。這樣控制染色體會發生與作業數目N相同的多點變異。有兩種選擇方式，一種是在可選機器集合中隨機選擇，一種是在操作空間的指導下選擇，方法如下：

Step 0：對作業Ji中每個操作Oi，j重新選擇加工機器：

找出Mk機器：Mk機器目前用來加工Oi，j。找出可以加工操作 Oi，j的機器集合 P（Oi，j）。

Step 1：產生一個隨機數字 r∈[0，1]：

如果 r＜=0.5，則使用隨機變異操作：從 P（Oi，j）中隨機選擇一個機器加工操作Oi，j。否則，操作空間中的機器選擇信息對變異算子施加影響：如果 P（Oi，j）僅包含 Mk，則仍然使用 Mk來加工Oi，j，否則，根據操作空間中機器被選擇情況的概率，以輪盤賭方式從 P（Oi，j）中選擇一個機器來加工操作 Oi，j。

Step 2：轉到 step 0。

調度染色體的變異操作，主要是對不合理基因塊執行變異，對操作排序做一些改動。因此首先選中執行變異操作的設備基因塊，然后對基因塊執行兩點易位法。這樣，調度染色體會發生與設備基因塊數M（設備數目）相同的多點變異。

4 實驗仿真及分析

這里采用文獻[7]中的不同規模的柔性車間調度問題的數據作為測試數據。為了更加準確，對于要測試的每一種規模的問題數據，分別運行10次，然后取這10次運行結果的最好值以及平均值。表2給出了實驗結果，共有6列。第一列給出了問題規模，第二列是文獻[7]中的方法獲取的最優調度結果，右邊4列是通過使用本文給出的方法仿真得出的數據，分別是只用共生遺傳算法得出的最好值和平均值，加入學習策略后得到的最好值和平均值。

表2 仿真實驗結果Tab.2 Simulation experimental results

由表2可以看出，使用本文提出的方法在其中3種規模的柔性車間調度問題中可以取得較好的效果，有明顯改進，每次運行中都能取得比原來好的調度值。但在10×10規模的問題上，結果不如原來優秀。第3列中是同等條件下僅使用基于共生機制的遺傳算法獲取的結果。總體來看，加入學習策略之后能獲取質量更高的結果。

5 結 論

根據柔性作業調度問題的特點，將該問題分為兩個子問題，看作是共生遺傳算法中兩個相互影響，共同進化的不同類種群。根據子問題的特點，設定兩個不同類種群有不同的進化角色和進化速度。在進化過程中，加入學習策略，使遺傳算法能夠在進化過程中不斷學習，將染色體中的優秀特征保留下來指導后代的進化。實驗證明，加入學習策略后對提高解的質量有一定的效果。

[1]Tsujimura Y， Mafune Y， Gen M.Effects of symbiotic evolution in genetic algorithms for job-shop scheduling[C]//Proceeding of the 34th Hawaii International Conference on System Sciences.[S.1.]:the IEEE Computer Society，2001:3026－3032.

[2]楊曉梅，曾建潮.遺傳算法求解柔性job shop調度問題[J].控制與決策，2004，19（10）：1197－1200.

YANG Xiao-mei，ZENG Jian-chao.Solving flexible job shop scheduling problem using genetic algorithm[J].Control and Decision，2004，19（10）:1197－1200.

[3]張維存，鄭丕諤，吳曉丹.基于主－從遺傳算法求解柔性調度問題[J].計算機集成制造系統，2006，12（8）:1241－1245.

ZHANG Wei-cun，ZHENG Pi-e，WU Xiao-dan.Solving flexible job-shop scheduling problems based on master-slave genetic algorithm[J].ComputerIntegrated Manufacturing Systems，2006，12（8）:1241－1245.

[4]Ho N B，Tay J C.LEGA:an architecture for learning and evolving flexible job-shop schedules[C]//The 2005 IEEE Congress on Evolutionary Computation，2005，2（2－5）:1380－1387.

[5]許化強，邱洪澤.用屬性導向歸納法發掘job-shop調度中的排序規則[C]//第三屆智能CAD與數字娛樂學術會議，濟南:山東大學出版社，2006:231－237.

[6]王小平.遺傳算法—理論、應用及軟件實現[M].西安:西安交通大學出版社，2002.

[7]Kacern I， Hammadi S， Borne P.Pareto-optimality approach for flexible job-shop scheduling problems:Hybridization of evolutionary algorithms and fuzzy logic[J].Mathematics and Computers in Simulation， 2002，60（3－5）:245－276.