分段自適應(yīng)遺傳算法在流水車(chē)間調(diào)度中的應(yīng)用

安徽理工大學(xué)電氣與信息工程 汪 鵬

分段自適應(yīng)遺傳算法在流水車(chē)間調(diào)度中的應(yīng)用

安徽理工大學(xué)電氣與信息工程 汪 鵬

針對(duì)流水車(chē)間的優(yōu)化調(diào)度問(wèn)題，提出一種分段自適應(yīng)遺傳算法，對(duì)遺傳算法交叉、變異算子進(jìn)行改進(jìn)，從而有效避免算法陷入局部，達(dá)到算法優(yōu)化調(diào)度的目的。通過(guò)對(duì)標(biāo)準(zhǔn)遺傳算法和改進(jìn)算法進(jìn)行仿真驗(yàn)證得知，優(yōu)化后的算法具有更好的適應(yīng)度曲線，表明其有效的克服了標(biāo)準(zhǔn)遺傳算法不成熟收斂問(wèn)題，具有一定的工程應(yīng)用價(jià)值。

分段自適應(yīng)；遺傳算法；流水車(chē)間

0 引言

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

1 問(wèn)題描述

流水車(chē)間調(diào)度問(wèn)題（Flow shop Scheduling Problem, FSSP）是一種最重要的組合優(yōu)化問(wèn)題， 該問(wèn)題通常可以描述為n個(gè)工件要在m臺(tái)不同機(jī)器上加工，每個(gè)工件有m道工序，每道工序都要在不同的機(jī)器上加工，各個(gè)工件加工順序相同，且滿(mǎn)足如下的約束條件：1）每個(gè)工件在機(jī)器上的加工順序相同，且給定加工順序是1，2，3…，m；2）一個(gè)工件不能同時(shí)在不同的機(jī)器上進(jìn)行加工；3）每臺(tái)機(jī)器同時(shí)只能夠加工一個(gè)工件；4）工序的準(zhǔn)備時(shí)間與順序無(wú)關(guān)，且包含在加工時(shí)間內(nèi)；5）工件加工技術(shù)上的約束事先給定。

2 問(wèn)題的算法設(shè)計(jì)

遺傳算法包括三個(gè)基本的操作：選擇、交叉和變異。遺傳算法的交叉概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵，直接影響算法的收斂性，Pc的大小決定種群的更新速度和搜索快慢的指標(biāo)。Pm是保持種群多樣性，防止早熟的一種手段?；谝陨蠁?wèn)題，本文提出了分段自適應(yīng)遺傳算法實(shí)時(shí)調(diào)整交叉概率及變異概率，從而獲得較優(yōu)解。

該算法分四個(gè)進(jìn)化階段。M為總進(jìn)化代數(shù)，itmax最大迭代代數(shù)，iter當(dāng)前代數(shù)，Pcmax最大交叉概率，Pcmin最小交叉概率，Pmmax最大變異概率，Pmmin最小變異概率，f變異個(gè)體適應(yīng)度（目標(biāo)函數(shù)值），fcmax為交叉兩個(gè)體較大適應(yīng)度，fave種群平均適應(yīng)度，fmax種群適應(yīng)度最大值。分別是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。

該算法參數(shù)設(shè)計(jì)的數(shù)學(xué)表達(dá)式如下：

其中，α和β為隨機(jī)產(chǎn)生的權(quán)重系數(shù)。

3 車(chē)間調(diào)度問(wèn)題仿真及結(jié)果分析

為了驗(yàn)證算法的有效性，本文分別將標(biāo)準(zhǔn)遺傳算法和分段自適應(yīng)遺傳算法的性能應(yīng)用于不同規(guī)模的流水車(chē)間調(diào)度問(wèn)題，算法均用MATLAB2012a來(lái)實(shí)現(xiàn)，并在Pentium3.2Ghz×2GB內(nèi)存的機(jī)器上的加工時(shí)間使用著名的Taillard’s基準(zhǔn)算例。

圖1

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

4 結(jié)論

本文研究了流水車(chē)間調(diào)度問(wèn)題，提出了性能較優(yōu)的分段自適應(yīng)遺傳算法，仿真結(jié)果表明，該算法在處理流水車(chē)間問(wèn)題更能優(yōu)化目標(biāo)函數(shù)，取得更好的效果。

[1]王凌．車(chē)間調(diào)度及其遺傳算法[M]．北京:清華大學(xué)出版社,2003．

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

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