分段自適應遺傳算法在流水車間調度中的應用

安徽理工大學電氣與信息工程 汪 鵬

分段自適應遺傳算法在流水車間調度中的應用

安徽理工大學電氣與信息工程 汪 鵬

針對流水車間的優化調度問題，提出一種分段自適應遺傳算法，對遺傳算法交叉、變異算子進行改進，從而有效避免算法陷入局部，達到算法優化調度的目的。通過對標準遺傳算法和改進算法進行仿真驗證得知，優化后的算法具有更好的適應度曲線，表明其有效的克服了標準遺傳算法不成熟收斂問題，具有一定的工程應用價值。

分段自適應；遺傳算法；流水車間

0 引言

隨著市場競爭的加劇，各制造加工企業為了提高自身的競爭力，必須合理分配資源，提高設備利用率與生產效率，降低生產成本，這就需要制定良好的車間生產調度。為此本文設計一種分段自適應遺傳算法，隨著進化代數和適應度函數自動調整交叉概率和變異概率，以期以較快的收斂速度搜索到全局最優解，從而滿足實際生產應用的需要。

1 問題描述

流水車間調度問題（Flow shop Scheduling Problem, FSSP）是一種最重要的組合優化問題， 該問題通常可以描述為n個工件要在m臺不同機器上加工，每個工件有m道工序，每道工序都要在不同的機器上加工，各個工件加工順序相同，且滿足如下的約束條件：1）每個工件在機器上的加工順序相同，且給定加工順序是1，2，3…，m；2）一個工件不能同時在不同的機器上進行加工；3）每臺機器同時只能夠加工一個工件；4）工序的準備時間與順序無關，且包含在加工時間內；5）工件加工技術上的約束事先給定。

2 問題的算法設計

遺傳算法包括三個基本的操作：選擇、交叉和變異。遺傳算法的交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關鍵，直接影響算法的收斂性，Pc的大小決定種群的更新速度和搜索快慢的指標。Pm是保持種群多樣性，防止早熟的一種手段。基于以上問題，本文提出了分段自適應遺傳算法實時調整交叉概率及變異概率，從而獲得較優解。

該算法分四個進化階段。M為總進化代數，itmax最大迭代代數，iter當前代數，Pcmax最大交叉概率，Pcmin最小交叉概率，Pmmax最大變異概率，Pmmin最小變異概率，f變異個體適應度（目標函數值），fcmax為交叉兩個體較大適應度，fave種群平均適應度，fmax種群適應度最大值。分別是1-0.4M代，Pcmax=0.8，Pcmin=0.6，Pmmax=0.08，Pmmin=0.05；0.4M-0.7M代，Pcmax=0.7，Pcmin=0.5，Pcmax=0.06，Pmmin=0.03；0.7M-0.9M代，Pcmax=0.6，Pcmin=0.4，Pmmax=0.04，Pmmin=0.02；0.9M到M代，Pcmax=0.5，Pcmin=0.3，Pmmax=0.02，Pmmin=0.01。

該算法參數設計的數學表達式如下：

其中，α和β為隨機產生的權重系數。

3 車間調度問題仿真及結果分析

為了驗證算法的有效性，本文分別將標準遺傳算法和分段自適應遺傳算法的性能應用于不同規模的流水車間調度問題，算法均用MATLAB2012a來實現，并在Pentium3.2Ghz×2GB內存的機器上的加工時間使用著名的Taillard’s基準算例。

圖1

如圖1所示，采用ta011(20×10)算例仿真，最優值為1582，明顯看出分段自適應遺傳算法優于標準遺傳算法，具有較好的尋優能力，從而驗證了算法的優越性。

4 結論

本文研究了流水車間調度問題，提出了性能較優的分段自適應遺傳算法，仿真結果表明，該算法在處理流水車間問題更能優化目標函數，取得更好的效果。

[1]王凌．車間調度及其遺傳算法[M]．北京:清華大學出版社,2003．

[2]張博凡,黃宗南．基于變形遺傳算法交叉算子的Flow-Shop問題求解[J]．制造業自動化,2011(19):27-29,46．

[3]Taillard,E．Benchmarks for basic scheduling problems．European Journal of Operational Research[J]．1993,64:278-285．