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

王 威， 徐 兵， 岳曉峰

（長春工業大學機電工程學院，吉林長春 130012）

0 引 言

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

1 GA模塊

1.1 編碼

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

1.2 遺傳算子

1.2.1 選擇算子

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

式中：score——個體的原目標函數值；

ave——種群的均值；

dev——種群的方差。

1.2.2 交叉算子

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

1.2.3 變異算子

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

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

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

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

步驟3：判斷是否達到迭代次數或者遺傳是否趨于穩定。如果達到，則輸出最優調度解，并退出；否則進行步驟4。

步驟4：遺傳操作。

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

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

3）變異操作。

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

2 基于混合遺傳算法求某軍工企業柔性制造車間一期工程的生產調度

文中以某軍工企業柔性制造車間一期工程的生產任務為例，在Visual C＋＋6.0上實現的混合遺傳算法，以驗證其有效性，并與用標準遺傳算法產生的結果進行比較［9］。

2.1 實例

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

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

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

續表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格式的文件中，這樣的好處是在機器或者零件發生變動時便于改動數據。一旦程序運行，就會從文件中讀取數據，并存儲在相應的機器矩陣中?！?555”是換行標志。

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

表3 工件的加工時間矩陣

表3表示工件的加工時間矩陣，其初始數據也是存儲在txt的文件當中，其中“5555”也是換行標志。

2.2 實驗結果

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

2.2.1 標準遺傳算法

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

標準遺傳算法的生產調度Gantt圖如圖1所示。

圖1 標準遺傳算法的生產調度Gantt圖

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

2.2.2 混合遺傳算法

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

混合遺傳算法的生產調度Gantt圖如圖2所示。

圖2 混合遺傳算法的生產調度Gantt圖

圖2是文中設計的混合遺傳算法在運行60代之后生成的Gantt圖結果，完成整個工程的時間為520h，比對圖1標準遺傳算法660h的結果，混合遺傳算法的效果明顯優于標準遺傳算法，并在取得較好結果的同時其運行代數也明顯少于標準遺傳算法。

3 結 語

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

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

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

［3］ 金芬，孫春華，鐘鳴.遺傳算法中適應度函數的改進［J］.機械設計與制造，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］ 曾益.一種基于改進遺傳算法的車間調度問題研究［J］.機械設計與制造，2011（7）：180-182.

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

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

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