基于多色集合的遺傳算法優(yōu)化求解

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

(廣東工業(yè)大學(xué) 機(jī)電工程學(xué)院，廣東 廣州 510006)

0 引言

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

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

1 算法總流程

針對(duì)柔性車間作業(yè)調(diào)度問題受到工藝約束和設(shè)備約束，結(jié)合實(shí)例講述如何采用多色集合理論描述這兩個(gè)約束條件，其他的FJSS 問題都可以采用同意的方法描述調(diào)度任務(wù)中待加工工序的工藝約束和設(shè)備約束。

表1 工序加工設(shè)備和加工時(shí)間［2］

例有4 個(gè)待加工工件，共12 道工序，6 臺(tái)設(shè)備，各工序具體可加工設(shè)備和相應(yīng)的加工時(shí)間如表1 所示。

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

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

2 基于約束模型進(jìn)行編碼

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

第一層編碼采用基于優(yōu)先權(quán)規(guī)則的自然編碼方法，其優(yōu)點(diǎn)是:具有Lamarckian 特性，且能保證調(diào)度的可行性，具有2 類解碼復(fù)雜性［5］。各基因?qū)?yīng)的工序按照式(1)矩陣Mwp的行對(duì)應(yīng)的工序的排序依次放置，基因值為優(yōu)先權(quán)隨機(jī)數(shù)。若有12 道工序，則在{1，…，12}中產(chǎn)生不同的隨機(jī)數(shù)作為基因。

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

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

表2 一種編碼方案

3 基于約束模型進(jìn)行解碼

由于第一層編碼具有2 類解碼復(fù)雜性，第二層具有0類編碼復(fù)雜性，所以解碼是針對(duì)第一層的。解碼的目的是確定工序的加工順序?；诩s束模型的解碼步驟如下:

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

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

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

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

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

圖2 解碼第二步示意圖

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

表3 解碼第二部示意圖

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

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

圖3 解碼第三步示意圖

表4 解碼后各設(shè)備上先后加工的工序

4 基于約束模型計(jì)算適應(yīng)度

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

式中:k——染色體標(biāo)識(shí)。

適應(yīng)度的具體計(jì)算如下:

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

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

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

步驟2 計(jì)算fk。

步驟3 計(jì)算適應(yīng)度fit(k)。

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

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

2)計(jì)算目標(biāo)函數(shù)值:f=F12=32。

3)計(jì)算適應(yīng)度:fit=1/f=1/32。

5 結(jié)論

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

連續(xù)運(yùn)行5 次得到的結(jié)果與文獻(xiàn)［6］比較的結(jié)果見表5。用理論和實(shí)例證明了基于約束模型的遺傳算法求解FJSS 問題，加快了收斂到最優(yōu)解的速度且計(jì)算過程穩(wěn)定。

圖4 滿意解的甘特圖

表5 比較結(jié)果

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

［2］余琦瑋，趙亮，潘雙夏.基于遺傳算法的柔性作業(yè)車間調(diào)度優(yōu)化［J］.組合機(jī)床與自動(dòng)化加工技術(shù)，2004，(4):32-34.

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

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

［5］陳亞瓊.基于一種新編碼的作業(yè)車間調(diào)度［D］.西安:西安電子科技大學(xué)，2007.

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