改進的遺傳算法在機加車間排產優化的研究

王明星，李利民

WANG Ming-xing1，LI Li-min2

(1.中北大學 計算機與控制工程學院，太原 030051；2.山西汾西重工有限責任公司，太原 030027)

0 引言

科學的計劃排產是提升加工制造企業市場競爭力的關鍵因素。但車間計劃排產長期以來都是生產調度的難題[1,2]，原因在于車間加工過程復雜，把不同零件按各自工藝路線有效的組織起來進行加工并非易事，所以能以最短的時間、最高的效率、最少的成本完成生產指標是很多企業的共同追求。20世紀80年代以來，模擬退火算法（Simulated Annealing, SA）、禁忌搜索算法（Tabu Search, TS）和遺傳算法（Genetic Algorithms, GA）等智能算法在生產調度領域應用廣泛，優化效果顯著[3]。其中，遺傳算法求解復雜優化問題時潛力巨大，為車間的排產調度提供了新的思路。

遺傳算法（Genetic Algorithm, GA）是由美國學者J.H.Holland等人提出，模擬生物進化自然選擇過程的計算模型。Wang H[4]用標準遺傳算法（SGA）求解調度問題時存在早熟收斂、求解精度低等問題，劉晶晶等人[5]將適應度引入到父代之間的交叉操作中，克服了SGA交叉操作中較大的盲目性，劉愛珍等人[6]利用混沌優化技術，對遺傳算法的交叉和變異概率進行動態控制，得到了可行解。

目前對基本遺傳算法改進后應用于機加車間排產的研究很少。借鑒相關文獻算法優點，以工件加工時間最短為目標，結合機加車間實際生產情況，建立對應數學模型，以個體適應度值為參照自動調節交叉概率和變異概率，根據加工任務高度值劃分基因段來改善交叉操作，引入混沌理論優化變異算子增強算法的全局搜索能力。最后用此算法和參考文獻中方法對給定算例進行求解并做了對比分析。

1 機加車間生產工藝流程

機加車間依靠機床加工零件，主要負責中小型零件的車、銑、鏜、鉆、鉗、磨、電加工等機械加工及熱處理。其車間調度問題可描述如下：

在m臺機床上加工n個不同的工件，機床集M由m臺機床Mj（j=1，2，…，m）組成，工件集N由n個待加工工件Pi（i=1，2，…，n）組成，工件Pi的加工工藝有qi道工序序列集Oik（k=1，2，…，qi）組成，工序Oik的加工機床組合為Mik，對應加工時間為tik，Mik表示第i個工件的第k道工序使用的機床號，Mik=0表示工件Pi在第k道工序不加工。機床集，工件集，工序序列集都用矩陣表示[7]。

該調度問題要求在一定條件下，整個調度的最大完工時間Cmax（從第一個工件開始加工到最后一個工件完成加工所需時間）最小，即：

其中，Cik表示工序Oik完工時間，Sik表示工序Oik開始加工時間，tik表示工序Oik加工時間。調度方案末道工序完工時間就是整個調度最大完工時間Cmax。假設改進的遺傳算法在以下條件運行：

1）每臺機床同一時間只能有一個加工任務且不能中斷；

2）各工件的加工工序一般相同，不同工件同一工序加工時間一般不同；

3）每個工件工序之間存在約束關系，工序應該依次按順序執行；

4）每個工件的工藝路線事先確定；

5）初始時刻，任何工件都能被加工。

2 改進的遺傳算法

2.1 個體編碼

由于工件的加工順序存在優先級，我們采用基于工序的編碼方式，每段基因代表加工的工序數，對于n個工件m臺機床的調度問題，編碼可表示為[k11，k12, …, k1m，…kn1，kn2，knm]，其中kj（j=11，12, …, nm）表示工件編號。工件Ji（i=1，2, …, n）的工件編號i在整個編碼中出現m次表示該工件共m道工序。上述編碼中，工件號i第一次出現表示Ji的第一道工序Oi1，工件號i第二次出現表示Ji的第二道工序Oi2，以此類推，Oim表示Ji的末道工序。

例如編碼[251415]表示工序順序為[O21，O51，O11，O41，O12，O52]。

2.2 對交叉和變異概率自適應調節

交叉與變異算子是影響遺傳算法性能的關鍵因素，通過交叉和變異不但可以把父代個體的優秀品質遺傳給子代，而且子代可能獲得比父代更好的基因結構。SGA通常設定一定的交叉概率和變異概率，然后由貝努利實驗決定是否進行交叉或變異運算，交叉概率和變異概率過大可能導致隨機搜索，過小可能導致早熟收斂，產生局部極值。對交叉概率和變異概率的改進如下：

其中，Pc0和Pm0是初始化的交叉概率和變異概率，Pc1和Pm1是調整后的交叉概率和變異概率，Wmax是群體中的最大適應度，Wavg是群體平均適應度，W(x)是兩個待交叉個體中的較大適應度。觀察表達式(2)和式(3)可知，適應度低于平均適應度的個體受破壞的可能性大，被淘汰；適應度高于平均適應度的個體受破壞的可能性小，被保存到下一代。

2.3 改進的交叉操作

交叉在遺傳算法中發揮核心作用，當交叉概率偏大時，遺傳算法對新空間的搜索能力增強，但優秀基因遭到破壞的可能性也變大，算法收斂速度和穩定性下降；當交叉概率偏小時，遺傳算法的搜索會有滯后性。

隨機在父代中選擇交叉點盲目性很大，算法性能會嚴重下降，此改進策略放棄對父代基因隨機交換，而是按照加工任務的高度值把父代基因劃分為若干個小段，高度值相同的加工任務劃分到一個基因段，劃分完成后在父代中按序選取等位基因段組成一個子代。父代的等位基因段適應度越高，被選作子代基因段的可能性越大。這一改進的最大優勢在于：沒有改變加工任務的任何前驅限制關系，得到的結果都是可行解。交叉算法具體操作步驟如下：

1）計算工件x1和x2中每道工序的加工時間，然后將分配到同一機床的加工任務按加工時間劃分為若干個基因段；

2）按照如下方法選取等位基因段（即工件x1和x2工序中在相同機床上相等的基因段）概率；

3）生成一個任意的隨機數Hi（i=1,2,3…,k；k為基因段個數），然后將Hi與 P (x1)或P (x2)進行比較來確定所選取的等位基因段。如果 P(x1)＜ P (x2)，當Hi＞ P (x2)時，選取x2的等位基因；當Hi＜ P (x1)時，選取X1的等位基因。

2.4 混沌優化變異算子

受加工任務之間約束關系的限制，SGA容易產生早熟收斂。SGA的變異操作通常采用隨機數決定，這會導致新個體產生的隨機性過大，不具有遍歷性和規律性?；煦缡亲匀唤缙毡榇嬖诘姆蔷€性現象，它看似很混亂，內部結構卻很精致，具有遍歷性、隨機性、敏感性和規律性?；煦绗F象在一定范圍之內能依據自身規律沒有重復的遍歷所有狀態，這一特性可作為搜索過程中避免陷入局部最優解的優化機制[8]。因此，本文把混沌理論應用到遺傳算法的變異操作中?；煦缧蛄胁捎萌缦滤緇ogistic映射公式，其中k為控制系數：

其中k=4，此時系統處于完全混沌狀態。任意取一個初始值X0，可產生一個迭代序列Xn+1，該序列會在[0,1]之間來回變化。本文將Xn+1作為控制遺傳算法是否變異的標尺。

假設染色體中個體基因的取值范圍是[α,β]，即可供選擇的加工工序的范圍，混沌優化變異的操作步驟如下：

1）選出待變異個體，確定個體進行變異操作的基因位i和基因位對應的工序碼Gi，取X0=Gi；

2）將X0代入式(7)調整為基因取值范圍內的數；

3）將X1代入混沌優化的映射公式(6)，得到X2；

4）再將X2調整為[0,1]之間的數；

5）令Gi= X3，更新個體基因編碼；

6）判斷變異操作是否結束，若結束，則返回到遺傳算法中，否則，選取下一個待變異的個體，轉步驟1）。

2.5 適應度函數的建立

車間排產問題是求解加工工件耗費總時間的最小值，這需要讓適應度值最大化，所以適應度函數定義為：

其中，tij為第i個工件第j道工序的加工時間；qi是加工第i個工件需要的最大工序數；n是最大工件數；C是的某極限值，保證F(x)是非負數，便于選擇和排序概率的計算。

3 改進的遺傳算法求解流程

改進的遺傳算法操作步驟：

1）獲取算法基礎數據：讀入工件的種類、加工工序數和對應工序的加工時間，讀入機床的加工產能；

2）初始化算法各參數：設定算法的群體規模和結束的循環代數，設定算法的初始交叉概率Pc0和變異概率Pm0。設定初始解集作為初始染色體；

3）計算當前染色體適應度值，把函數適應度值最大的個體設定為當前一代的最佳解；

4）檢驗是否滿足算法收斂準則 ，若滿足，則轉步驟7），否則進行步驟5）；

5）對染色體當前的交叉概率和變異概率進行動態的自適應調整，以調整后的交叉概率進行改進的交叉操作，以調整后的變異概率進行混沌優化變異操作；

6）對染色體進行選擇操作[9]，把經過遺傳操作的染色體作為當前染色體。轉步驟3）；

7）得到最佳個體，輸出結果。

該算法的流程圖如圖1所示。

圖1 改進的遺傳算法流程圖

4 實驗結果及分析

4.1 實驗數據

設定機加車間要加工9個工件，每個工件都要經過車、銑、磨3道工序的處理，現有2臺車床，3臺銑床，2臺磨床，不同工件在不同機床的加工時間各不相同，具體加工情況如表1所示。

表1 工件加工時間明細表

4.2 最優解比較

將標準遺傳算法（SGA）[4]和本文算法應用于該車間實際生產進行仿真對比。設定初始交叉概率Pc0=0.70，變異概率Pm0=0.05，種群規模M=100，進化代數T=100，分別獨立運行20次取平均值[10]。得到的結果如表2所示。

表2 SGA和本文算法排產結果

比較分析可得：本文算法波動率小，動態穩定性高，最優解為77.7，排產效果優于SGA。但由于算法復雜，運行時間比SGA稍長，這對于排產優化效果影響不大。

4.3 搜索能力比較

我們選用標準遺傳算法（SGA）、文獻[5]中算法、文獻[6]中算法和本文算法分別求解進行性能評估。文獻[4～6]中GA主要參數見原文，本文算法參數和4.2中設置相同。仿真過程在一臺PC機上完成，操作系統是Windows XP，CPU是Intel(R)Q6600，內存為3GB，工具是Matlab2012b。設平均改進量為I，仿真結果如圖2所示。

為了減小算法隨機性產生的誤差，更加準確的體現各算法的性能，圖2中每組數據都是各自運行20次取平均值得到的，觀察可知，此算法得到的加工時間最短，全局搜索能力最好。

8個機床加工40個工件條件下四種算法分別進化產生的靜態性能曲線如圖3所示。

圖2 各算法仿真結果比較

圖3 靜態性能曲線(m=8,n=40)

觀察圖3可以得到以下結論：

1）在不降低獲得最優解質量的前提下，本文算法擴大了搜索范圍，提高了收斂速度，求解質量和運行效率比圖中其他算法顯著提高；

2）隨著進化代數的遞增，完成時間持續減少最后趨于穩定，說明優秀基因被遺傳下來，使排產效果得以優化；

3）收斂速度方面：此算法＞文獻[6]算法＞文獻[5]算法＞ SGA；

4）收斂代數方面：各算法進化代數收斂區間：[50,200]。

5 結束語

通過研究某公司機加車間排產調度問題，建立其數學模型，并用遺傳算法對其求解。通過對基本遺傳算法三個方面的改進，即以個體適應度值為參照自動調節交叉概率和變異概率，根據加工任務高度值劃分基因段來改善交叉操作，引入混沌理論優化變異算子，極大提高了遺傳算法的收斂速度和對最優解的搜索能力。通過對仿真結果的分析比較，改進算法顯著縮短了機加車間的生產總時間，優化效果比現有的算法更明顯，對機器加工行業排產優化有一定借鑒意義。

[1]帥飛,陳兆剛,李向東.基于遺傳算法的橋式起重機節能調度優化研究[J].制造業自動化,2013, 35(14):97-99.

[2]王進峰,陰國富,雷前召,等.基于改進遺傳算法的柔性作業車間調度[J].現代制造工程,2013(5):50-53.

[3]張國慶,劉永進,梅中義.改進的遺傳算法在復合材料車間計劃排產中的應用研究[J].現代制造工程,2010(7):56-59.

[4]Wang H.Flexible flow shop scheduling: optimum,heuristics and artificial intelligence solutions[J].Expert Systems,2005,22(2):78-85.

[5]劉晶晶,翟正軍.基于改進的遺傳算法的任務分配與調度[J].微電子學與計算機,2006, 23(6):216-219.

[6]劉愛珍,王嘉禎,賈紅麗,等.改進的多任務分配與調度遺傳算法[J].微電子學與計算機,2007,24(9):162-168.

[7]張昕.改進的遺傳算法在車間作業調度中的應用研究[J].國防制造技術,2013,2:019.

[8]李耀華,徐樂江,胡國奮,等.基于混沌遺傳算法的板坯入庫決策優化方法[J].系統仿真學報,2006,17(11):2620-2623.

[9]陳憶群,周如旗,林淑金,等.有車輛數限制的開放式車輛調度問題研究[J].小型微型計算機系統,2013,34(003):595-601.

[10]蔣佳穎,王萬良,徐新黎,等.基于量子遺傳算法的染缸排產問題研究[J].計算機工程,2011,37(21):159-161,164.