基于機器加工時間最短的混合遺傳算法

王 威， 徐 兵， 岳曉峰

（長春工業(yè)大學(xué)機電工程學(xué)院，吉林長春 130012）

0 引 言

車間作業(yè)調(diào)度問題（Job Shop Problem，JSP）是最困難的組合優(yōu)化問題之一。近年來，基于概率搜索方法的發(fā)展為求解車間作業(yè)調(diào)度問題帶來了巨大推動，它已經(jīng)成為解決該類問題的有效方法之一，如模擬退火（Simulation Anneal，SA）、禁忌搜索（Taboo Search）、遺傳算法（Genetic Algorithm，GA）［1］。它們在求解時最大的特點是以概率的方式搜索問題的解空間，并通過目標(biāo)函數(shù)的評價，使搜索過程不斷收斂于一個值上。然而，單獨使用標(biāo)準(zhǔn)遺傳算法解決車間調(diào)度問題時，效果往往不理想［2］。這是因為標(biāo)準(zhǔn)遺傳算法是一種通用的優(yōu)化算法，采用它來解決調(diào)度方案時，必須與調(diào)度本身的一些特點結(jié)合，如調(diào)度產(chǎn)生時必須滿足加工工藝等約束條件，指導(dǎo)迭代的搜索方向，而且企業(yè)的調(diào)度問題比較復(fù)雜，在實際的調(diào)度問題中，往往是零件與可加工機器之間存在一對多的情況，為了確定機器與工件的關(guān)系，文中提出了一種混合式遺傳算法，它在遺傳算法中嵌入了基于機器加工時間最短為策略的啟發(fā)式方法，從局部和全局引導(dǎo)遺傳算法的搜索方向，提高了算法的效率，并且實例考證了HGA算法在解決某軍工企業(yè)生產(chǎn)調(diào)度問題時的有效性［3－4］。

1 GA模塊

1.1 編碼

文中采用了基于工件的編碼方式。編碼問題是設(shè)計遺傳算法的首要和關(guān)鍵問題。遺傳算法必須要考慮“染色體”的合法性、可行性、有效性以及對問題解空間表征的完全性，求解JSP同樣如此。鑒于JSP的組合特性以及工藝約束性，染色體的Lamarkian特性、解碼的復(fù)雜性、編碼空間特性和存儲量的需求是設(shè)計遺傳算法編碼時需要考慮的問題。由于二進制編碼方式存在著不能直接反應(yīng)所求問題的結(jié)構(gòu)特征，不便于開發(fā)針對問題的專門知識的遺傳算子，同時也很難滿足積木塊兒編碼原則等的諸多缺點［5］。采用簡單的二進制串編碼方式已不能有效地解決JSP問題。文中根據(jù)問題特點采用基于工件的編碼方式。這樣編碼的好處是染色體Lamarkian性，并且通過簡單的映射關(guān)系就能實現(xiàn)解碼的相應(yīng)編碼，任意工件的置換排列均能表示可行調(diào)度，編碼長度也遠小于二進制的編碼方式。

1.2 遺傳算子

1.2.1 選擇算子

采用賭輪法進行選擇。由于賭輪選擇的非負性要求，以及為了提高個體之間的差異性，文中采用了sigma truncation的縮放方法來確定個體的適應(yīng)值，其公式為［6］：

式中：score——個體的原目標(biāo)函數(shù)值；

ave——種群的均值；

dev——種群的方差。

1.2.2 交叉算子

文中交叉策略采用部分匹配法，該方法是不直接進行兩個父代之間的交叉，而是兩子代分別依據(jù)各自的父代，通過交換自己相應(yīng)位置的基因而實現(xiàn)相對意義上的交叉，這種方式的好處在于不會產(chǎn)生非法解，從而免去非法解的過程，提高了程序的運行效率［7］。

1.2.3 變異算子

為保證種群的多樣性以及使算法能在更廣闊的可行解空間中搜索最優(yōu)解，同時為了防止程序陷入局部最優(yōu)解的瓶頸，文中采用了如下方法：隨機得出兩個點后，將兩點之間的基因按概率進行互換，這樣既保證了個體的多樣性，同時又保留了部分基因，使得程序免于因變異隨機性太大而影響程序的收斂［8］。

1.3 混合遺傳算法的過程描述

步驟1：生成初始種群。采用基于工件的編碼方式進行編碼。

步驟2：計算適應(yīng)值。采用sigma truncation的縮放方法來確定個體的適應(yīng)值。

步驟3：判斷是否達到迭代次數(shù)或者遺傳是否趨于穩(wěn)定。如果達到，則輸出最優(yōu)調(diào)度解，并退出；否則進行步驟4。

步驟4：遺傳操作。

1）依據(jù)前述的選擇策略選擇出要交叉的父代個體。

2）依據(jù)交叉概率來確定兩個父代是否需要交叉，若需要則采用部分匹配法進行交叉，否則直接將兩父代復(fù)制給下一代。

3）變異操作。

4）轉(zhuǎn)步驟3，看是否滿足終止條件，滿足則終止；否者返回步驟2。

2 基于混合遺傳算法求某軍工企業(yè)柔性制造車間一期工程的生產(chǎn)調(diào)度

文中以某軍工企業(yè)柔性制造車間一期工程的生產(chǎn)任務(wù)為例，在Visual C＋＋6.0上實現(xiàn)的混合遺傳算法，以驗證其有效性，并與用標(biāo)準(zhǔn)遺傳算法產(chǎn)生的結(jié)果進行比較［9］。

2.1 實例

種群規(guī)模為40，交叉概率為0.9，變異概率為0.01。

在算法設(shè)計上，將該軍工企業(yè)一期工程所有要加工的13種工件按照順序依次確定1～13，給出的11臺機器也是按其標(biāo)號來確定的，見表1。

表1 加工機器及編號詳細表

續(xù)表1

其中，機器編號12表示工件可能的加工機床“M1，M2，M3，M4，M5，M6，M8，M10”，13表示工件可能的加工機床“M1，M3，M8”，14表示工件可能的加工機床“M2，M3”，15表示工件可能的加工機床“M1，M3”，16表示工件可能的加工機床“M2，M3，M11”，17表示工件可能的加工機床“M3，M8”。

工件的機器順序矩陣見表2。

表2 工件的機器順序矩陣

表2是工件的機器順序矩陣，其存儲在txt格式的文件中，這樣的好處是在機器或者零件發(fā)生變動時便于改動數(shù)據(jù)。一旦程序運行，就會從文件中讀取數(shù)據(jù)，并存儲在相應(yīng)的機器矩陣中?！?555”是換行標(biāo)志。

工件的加工時間矩陣見表3。

表3 工件的加工時間矩陣

表3表示工件的加工時間矩陣，其初始數(shù)據(jù)也是存儲在txt的文件當(dāng)中，其中“5555”也是換行標(biāo)志。

2.2 實驗結(jié)果

針對問題本身進行了如下處理，對于機器M7，M9，M10，由于均不在本車間加工，且它們都是進行熱處理之類的工序，故假設(shè)其加工能力很強，對于同時進入外車間的工件可以同時進行加工，且能夠保證按時完工。對于工件能在多臺機器上加工的情況，根據(jù)其可用于加工的機器，從總體上將其化為一個整體中，然后根據(jù)全部劃分，對這些機器整體進行編號。

2.2.1 標(biāo)準(zhǔn)遺傳算法

標(biāo)準(zhǔn)遺傳算法是從一組調(diào)度解出發(fā)，利用各種遺傳操作實施大范圍的解空間探尋，通過評價函數(shù)對每個解進行評估，保留好的種群，并以此來不斷尋找最佳的調(diào)度解。該方式具有尋找最優(yōu)解的能力，但該方式本質(zhì)上是以隨機方式進行的，其尋找過程可能是漫無目的和無價值的運算過程，求解質(zhì)量無法保證。

標(biāo)準(zhǔn)遺傳算法的生產(chǎn)調(diào)度Gantt圖如圖1所示。

圖1 標(biāo)準(zhǔn)遺傳算法的生產(chǎn)調(diào)度Gantt圖

圖1是使用標(biāo)準(zhǔn)遺傳算法運行3 944代后生成的Gantt圖，完成工程的總時間為660h，效果不理想。

2.2.2 混合遺傳算法

在解決工件與機器之間一對多的關(guān)系上，標(biāo)準(zhǔn)遺傳算法是隨機確定的，缺乏目的性。文中設(shè)計的程序在處理一對多問題上，為每個個體添加了一個機器加工矩陣，所謂機器加工矩陣，是指程序根據(jù)個體的工件序列以及機器順序矩陣和加工時間矩陣來確定工件的各道序的機器加工分配矩陣。針對這一問題，文中巧妙地利用基于機器最短加工時間的方法來生成機器加工矩陣，程序每次訪問個體的一個基因（工序），就調(diào)用一次排序函數(shù)對所有機器按工作時間長短進行升序排列，然后根據(jù)工序可調(diào)度的機器與排序后的機器進行比較，來確定工件的工序的加工機器，直到完成機器加工矩陣。

混合遺傳算法的生產(chǎn)調(diào)度Gantt圖如圖2所示。

圖2 混合遺傳算法的生產(chǎn)調(diào)度Gantt圖

圖2是文中設(shè)計的混合遺傳算法在運行60代之后生成的Gantt圖結(jié)果，完成整個工程的時間為520h，比對圖1標(biāo)準(zhǔn)遺傳算法660h的結(jié)果，混合遺傳算法的效果明顯優(yōu)于標(biāo)準(zhǔn)遺傳算法，并在取得較好結(jié)果的同時其運行代數(shù)也明顯少于標(biāo)準(zhǔn)遺傳算法。

3 結(jié) 語

將機器最短加工時間的概念融入算法中的混合遺傳算法，全面引導(dǎo)遺傳算法的搜索過程，從而避免了單一使用啟發(fā)式規(guī)則給遺傳算法帶來的早熟現(xiàn)象。當(dāng)某一工序出現(xiàn)可選擇多臺機床時，使用機器最短加工時間的啟發(fā)式方法來選定機床，可實施解的局部優(yōu)化，大大減少了遺傳算法的搜索空間，并以此提高算法的效率與染色體的質(zhì)量。由此可見，混合遺傳算法充分體現(xiàn)了其探索解空間的能力，由此也證明了混合遺傳算法充分結(jié)合啟發(fā)式方法與遺傳算法的優(yōu)勢，實例考證也說明了混合遺傳算法的有效性。

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

［2］ 張長水，沈剛，閻平凡.解Job-shop調(diào)度問題的遺傳算法［J］.電子學(xué)報，1995（1）：346-348.

［3］ 金芬，孫春華，鐘鳴.遺傳算法中適應(yīng)度函數(shù)的改進［J］.機械設(shè)計與制造，2010（3）：217-219.

［4］ De Jong K A.Genetic algorithm：a 25year perspective，computational intelligence imitating Life［C］／／The Institute of Electrical and Electronics Engineers，Inc.1994.

［5］ Srinivas M，Patnaik K M.Adaptive probabilities of crossover and mutation in genetic algorithms［C］／／IEEE Transactions on Systems，Man and Cybernetics.1994.

［6］ 曾益.一種基于改進遺傳算法的車間調(diào)度問題研究［J］.機械設(shè)計與制造，2011（7）：180-182.

［7］ 王凌.基于遺傳算法的Jobshop調(diào)度研究進展［J］.控制與決策，2001，16（1）：641-646.

［8］ 沈斌，周瑩君，王家海.基于自適應(yīng)遺傳算法的Jobshop調(diào)度［J］.計算機應(yīng)用，2009，29：161-164.

［9］ 孟祥萍，張紅，王暉.基于混合遺傳算法的泵站優(yōu)化運行［J］.電氣應(yīng)用，2008，29（1）：30-33.