基于多色集合的遺傳算法優化求解

鄧建勝，姜莉莉，李德治，卿前茂

(廣東工業大學 機電工程學院，廣東 廣州 510006)

0 引言

遺傳算法具有很強的全局搜索能力，從理論上講，算法從任意初始種群出發，都可以找到全局最優解。但是當種群數量很大時，算法由于存在早熟收斂的問題，即容易收斂到局部最優解而不再進化或者種群中不能再產生性能超過父代的個體。多色集合的優點是將傳統的集合涂上不同的顏色，即給傳統的集合及集合中的各個元素賦予一定的意義。如果集合為遺傳算法中的編碼，那么編碼就可以具有一定的意義或者與其他編碼建立一定的關系。

將約束模型引入遺傳算法的作用主要體現在兩方面:1)去掉無意義的解或無效解從而保證所有解都是有效解。設計特定的染色體編碼或遺傳算子來保證解的可行性，這樣遺傳編碼和遺傳算子的設計成為遺傳算法的應用瓶頸。2)通過縮小解的空間而減少早熟收斂的可能性和改善收斂速度［1］。當種群數目一定時，解的空間越大，種群中的采樣點覆蓋全局解的概率就越小，產生早熟收斂的幾率就越大。并且當解的空間很大，但有效解的數量相對較少時，不但容易產生早熟收斂，而且收斂速度較慢，得到的解也有可能是無效解。反之，如果縮小解的空間或去掉無意義的解，不但可以減少早熟收斂的可能，而且可以加快收斂速度。

1 算法總流程

針對柔性車間作業調度問題受到工藝約束和設備約束，結合實例講述如何采用多色集合理論描述這兩個約束條件，其他的FJSS 問題都可以采用同意的方法描述調度任務中待加工工序的工藝約束和設備約束。

表1 工序加工設備和加工時間［2］

例有4 個待加工工件，共12 道工序，6 臺設備，各工序具體可加工設備和相應的加工時間如表1 所示。

為了便于理解，在針對表1 中的4×6 FJSS 問題建立的約束模型基礎上詳細設計算法。基于約束模型的遺傳算法求解0 問題的流程圖［3］如圖1 所示，其中2N +1 為種群大小。此圖比一般的遺傳算法流程圖有著明顯的特點:1)采用保優策略，將每一代中最有個體直接復制進入下一代，從而每一代中都能得到目前為止最好的解。2)編碼、解碼、適應度計算以及變異過程在模型約束下進行。

圖1 基于約束模型的遺傳算法求解FJSS 問題流程圖

2 基于約束模型進行編碼

編碼是遺傳算法實施優化的首要和關鍵問題，鑒于車間調度問題的約束性，編碼技術必須考慮其合法性和可行性。針對經典的調度問題，大多數研究采用的是基于工序的編碼。這種編碼方法把調度編碼為工序，每個基因代表一道工序，給所有同一工件的工序指定相同的符號，然后根據它們在給定染色體中出現的順序加以解釋。對于本文的FJSS 問題，問題的解包含兩方面的內容:工序的順序和［4］設備的選擇，因此編碼也要反映這兩方面的內容。為此采用基于工序和設備的兩層編碼方法。

第一層編碼采用基于優先權規則的自然編碼方法，其優點是:具有Lamarckian 特性，且能保證調度的可行性，具有2 類解碼復雜性［5］。各基因對應的工序按照式(1)矩陣Mwp的行對應的工序的排序依次放置，基因值為優先權隨機數。若有12 道工序，則在{1，…，12}中產生不同的隨機數作為基因。

第二層編碼采用實數編碼方法，為第一層編碼對應各工序所使用的設備，通過搜索式(2)矩陣Mpm獲得各基因，其優先是:具有Lamarckian 特性，且能保證調度的可行性，具有0 類解碼復雜性，即不需要解碼。各工序的基因從矩陣Mpm中對應的統一顏色中為1 的個人顏色所對應的設備編號中隨機獲取，以保證每個基因是有效的。

表2 就是采用以上編碼方法解決表1 中FJSS 問題的一種編碼方案，即一條染色體。

表2 一種編碼方案

3 基于約束模型進行解碼

由于第一層編碼具有2 類解碼復雜性，第二層具有0類編碼復雜性，所以解碼是針對第一層的。解碼的目的是確定工序的加工順序。基于約束模型的解碼步驟如下:

步驟1 搜索式(1)矩陣Mwp，挑出各列第一個不為0的元素所在的行對應的工序，由于同一工件的工序在式(1)矩陣Mwp的行中是按先后順序排列，這樣就能滿足同一工件每個工序之間的先后關系約束。

步驟2 比較這些工序在第一層編碼中對應的基因的大小，選出基因最小的工序(基因值越小，即優先權值越小，則優先權越高，所以基因值小的工序先加工)。

步驟3 根據上一步選出的基于對應的工件和工序，將式(1)矩陣Mwp中對應位置的元素置0，即去掉已經選出的工序。

重復步驟1，步驟2，步驟3，直至確定出所有工序的加工順序。每個工件的各工序是按照先后關系選取，所以一定滿足約束條件——各工件必須按照工藝路線以指定的次序在設備上加工。部分解碼過程如下:

1)搜索式(1)矩陣Mwp，找出各列第一個不為0 的元素所在的工序為101，201，301，401，如圖2 所示。

圖2 解碼第二步示意圖

2)找出工序101，201，301，401，在第一層編碼中對應的基因分別為9、4、3、5，如表3 所示，并選取最小基因值為3 對應的工序301。

表3 解碼第二部示意圖

3)對上一步選出的工序301，即第三個工件的第一道工序，將式(1)矩陣Mwp中的第七行第三列元素置0，如圖3 所示。

重復解碼過程1)、2)和3)，可得第一層編碼解碼后的工序加工順序為:301→201→202→401→402→403→203→101→102→302→303→103。第二層編碼可得加工這些工序的設備依次為:1→5→2→4→2→3→5→1→4→4→6→3。各設備上先后加工的工序如表4 所示。

圖3 解碼第三步示意圖

表4 解碼后各設備上先后加工的工序

4 基于約束模型計算適應度

遺傳算法中，以個體適應度的大小來確定該個體被遺傳呆下一代群體中的概率。個體的適應度越大，該個體被遺傳到下一代的概率也越大。反之，個體的適應度越小，該個體被遺傳呆下一代的概率就越小。計算個體適應度首先要確定目標函數，不妨設目標函數為fk，定義適應度fit(k)為的倒數，即:

式中:k——染色體標識。

適應度的具體計算如下:

步驟1 計算染色體中按解碼后的順序加工的各工序的開始加工時間和完工時間。設工序i(i=1，…，n)的開始加工時間為Si，完工時間為Fi，在設備上的加工時間為Pi，則Fi=Si+Pi，所以下面主要計算Si。

1)根據工序i 的編號，搜索式(1)矩陣Mwp，確定它是所屬工件的第幾道工序，若i 不是所屬工件的第一道工序，則搜索矩陣Mwp，確定工序i 所屬工件的上一道工序的編號i0，再根據工序編號i0確實工序的上一道工序的完工時間為FRi，則要求Si≥FRi;若i 是所屬工件的第一道工序，則要求Si≥0。

2)根據工序i 的編號確定加工工序i 的的設備j 上加工的上一道工序的編號。若工序i 是設備上j 上的第一道加工工序，設備j 可以開始加工的時間為MSj，則要求Si≥MSj;若工序i 不是設備上j 上的第一道加工工序，設備j上加工的上一道工序的完工時間為FRi，則要求Si≥FRi。為得到最短完工時間，Si取1)和2)過程的極小值。依次求出解碼后的工序的開始加工時間和完工時間。

步驟2 計算fk。

步驟3 計算適應度fit(k)。

對上面解碼后得到的工序加工順序301→201→202→401→402→403→203→101→102→302→303→103，不妨設設備2 可以加工時間為2 之外，其他設備可以加工時間均為0，適應度計算如下:

1)第一道工序301，對應屬于工件3，搜索式(1)矩陣Mwp，可知它在Mwp中的第7 行、第3 列，由行列位置確定的元素值是第3 列中第一個不為0 的元素，所以工序301 是工件3 的第一道工序，所以要求Si≥0;由表4 可知，工序301 是設備1 的第一道工序，所以要求S1≥0。故S1=max(0，0)，F1=S1+P1=0 +3=3。類似的，第二道加工工序201 在設備5 上的開始加工時間和完工時間分別為S2=max(0，0)，F2=S2+P2=0 +4=4。第三道工序202，對應屬于工件2，搜索式(1)矩陣Mwp，可知它在第5 行、第2 列，由行列位置確定的元素值是第2 列中第二個不為0 的元素，所以要求S3≥F2=4;由表4 可知，工序202 是設備2 上加工的第一道工序，所以要求S3≥2。綜合以上結果得S3=max(4，2)=4，F3=S3+P3=4+2=6。依次類推，最后一道加工工序103 在設備3 上的開始加工時間和完工時間分別為S12=max(F9，F6)，F12=S12+P12=20 +12=32。

2)計算目標函數值:f=F12=32。

3)計算適應度:fit=1/f=1/32。

5 結論

若以調度任務開始時刻為零時刻，設各設備對該時刻的加工時間為0，運行參數如下:種群大小為51，終止代數為100，交叉概率為0.2。使用基于約束模型的遺傳算法求解柔性作業車間調度問題得到的最優解為17 h，其滿意解對應的甘特圖如圖4 所示。

連續運行5 次得到的結果與文獻［6］比較的結果見表5。用理論和實例證明了基于約束模型的遺傳算法求解FJSS 問題，加快了收斂到最優解的速度且計算過程穩定。

圖4 滿意解的甘特圖

表5 比較結果

［1］高集體，洪圣巖，梁華.部分線性模型中估計的收斂速度［J］.數學學報，1995，38(5).

［2］余琦瑋，趙亮，潘雙夏.基于遺傳算法的柔性作業車間調度優化［J］.組合機床與自動化加工技術，2004，(4):32-34.

［3］王凌.車間調度及其遺傳算法［M］.北京:清華大學出版社，2003.

［4］郝建波，李宗斌，趙麗萍.工步排序問題的約束模型及其遺傳算法的求解［J］.西安交通大學學報，2008，42(7):860-864.

［5］陳亞瓊.基于一種新編碼的作業車間調度［D］.西安:西安電子科技大學，2007.

［6］Nasr N，Elsayed E A.Job shop scheduling with alternative machine［J］.International Journal of Production Research，1990，29(9):1595-1609.