模擬退火算法優(yōu)化PSO-GA算法解決柔性流水車間調(diào)度問題

景會成，王 穎

(華北理工大學(xué) 電氣工程學(xué)院，河北 唐山 063210 )

E-mail ：925683837@qq.com

1 引 言

柔性流水車間調(diào)度問題(Flexible Flow Shop scheduling，F(xiàn)FSP)是數(shù)字化車間首要解決的問題，是大量實(shí)際生產(chǎn)調(diào)度問題中最常見的簡化模型，是一類重要的組合優(yōu)化問題，已經(jīng)成為先進(jìn)制造技術(shù)實(shí)踐的關(guān)鍵[1].FFSP問題可以被描述為一批工件需要經(jīng)過n道工序在m臺數(shù)控機(jī)床上進(jìn)行加工，其中n道工序有一定的先后順序，m臺數(shù)控機(jī)床存在并行情況.由于實(shí)際生產(chǎn)過程中n、m的數(shù)值往往比較大，F(xiàn)FSP問題成為典型的NP-hard問題.目前針對于FFSP問題的解決方法有很多.韓忠華[2]等采用最優(yōu)個體集和自適應(yīng)位置更新對蝙蝠算法進(jìn)行優(yōu)化的方法對FFSP問題求解.畢孝儒[3]等采用混沌算子對人工群峰算法進(jìn)行優(yōu)化的方法對FFSP問題求解.張海月[4]提出了模擬退火擾動(SADA)算法與NEH貪婪搜索算法結(jié)合后對粒子群算法進(jìn)行優(yōu)化的方法對FFSP問題求解，上述文章都對經(jīng)典的算法進(jìn)行了優(yōu)化，但依然存在著一個局部最優(yōu)和收斂速度之間的對立，若過于追求收斂速度，則可能限于局部最優(yōu)，為了防止局部最優(yōu)，必然會影響到收斂速度.本文針對FFSP問題提出了一種改進(jìn)的遺傳算法，針對于傳統(tǒng)遺傳算法收斂速度慢的問題對未能直接進(jìn)入下一代種群的剩余個體采用粒子群算法(PSO)，該算法能夠加快收斂速度.針對于傳統(tǒng)遺傳算法局部搜索能力弱容易限于局部最優(yōu)的問題在迭代過程引入模擬退火算法(SA)，該算法能夠概率性的跳出局部最優(yōu)解并最終趨于全局最優(yōu).改進(jìn)后的遺傳算法能快速、高效的解決FFSP問題.

2 車間數(shù)學(xué)模型

車間共有m臺機(jī)床，機(jī)床號集M={M1，M2，M3，…，Mm}，令i∈{1，2，3，…，m}，則Mi表示機(jī)床號為i的機(jī)床.有n個待工件，待加工工件集N={N1，N2，N3，…，Nn}，令j∈{1，2，3，…，n}，則Nj表示第j個未加工工件.工藝路線集L={L1，L2，L3，…，Ll}，其中l(wèi)∈R.Nj可以在不同的Mi上加工，并且一旦開始加工便不能停止.Nj需要Oj道加工工序，工序順序集P={Pj1，Pj2，Pj3，…，PjOj}，令k∈{1，2，3，…，Oj}則Pjk表示Nj在第k道工序加工，Tjk記為Nj在第k道工序加工對應(yīng)的加工時間，Sjk記為Nj在第k道工序加工對應(yīng)的加工時間，STik記為Mi在第k道工序的起始加工時間，ETik記為Mi在第k道工序的加工結(jié)束時間.Cmax為車間排產(chǎn)調(diào)度的最大完成時間，Cj記為Nj所有工序加工完成時間.Cjk記為Nj在第k道工序的總完成時間.Cj的具體表達(dá)式：

(1)

其中

Cjk=Sjk+Tjk

(2)

目標(biāo)函數(shù)

f=min{Cmax}=min{max(Cj)}j∈{1，2，3，…，n}

(3)

約束條件

Tj(k-1)≤Tjk(k≥1)

(4)

STik≥ETi(k-1)(k≥1)

(5)

公式(3)中f為最小完工時間，使Cmax達(dá)到最小即找出最優(yōu)的加工方案使總加工時間最小.k-1道工序的結(jié)束時間先于第k道工序的起始時間，保證工序的先后順序不變.Mi在第k-1道工序的加工結(jié)束時間先于Mi在第k道工序的起始加工時間，保證一臺機(jī)床只能加工一個工件.

3 PSO-GA算法改進(jìn)

粒子群優(yōu)化算法最初是由Eberhart和Kennedy在1995 年提出的，是基于迭代的優(yōu)化方法，可用對復(fù)雜問題優(yōu)化求解[5]，粒子群里的個體(即粒子)代表問題的一個可能解，每個粒子具有位置和速度兩個特征，粒子通過位置來決定自身的適應(yīng)度各個粒子記憶并追隨當(dāng)前的最優(yōu)解.

把規(guī)定了行為規(guī)則的粒子作為個體，多個個體組合成為一個復(fù)雜的群體，便可用來對FFSP問題求最優(yōu)解.Xi=(xi1，xi1，…，xiD)記為第i個粒子的位置；Vi=(vi1，vi1，…，viD)記為第i個粒子的速度；Pg(k)=(pg1(k)，pg2(k)，…，pgD(k))記為經(jīng)過k次迭代后的粒子i的最優(yōu)位置；Pg(k)=(pg1(k)，pg2(k)，…，pgD(k))記為次迭代后的最優(yōu)粒子的位置.

vid(k+1)=ω·vid(k)+c1·r1·[pid(k)-xid(k)]+

c2·r2·[pgd(k)-xid(k)]

(6)

(7)

xid(k+1)=xid(k)+vid(k+1)

(8)

其中c1、c2為加速因子，ω為慣性因子，r1∈[0，1]、r2∈[0，1]、d∈[1，D]，D表示粒子群搜索空間的維數(shù).從上述公式可以看出PSO在迭代中期的收斂速度快、搜索效率高、精度高但在其他時期搜索效率低，在迭代后期更新速度幾乎趨近于0，容易陷于局部極值.最初由美國Michigan大學(xué)Holland教授于1975年首先提出來的遺傳算法(Genetic Algorithm，GA)，是通過對自然進(jìn)化過程進(jìn)行模擬來實(shí)現(xiàn)搜尋最優(yōu)解的一種方法[6].遺傳算法具有很強(qiáng)全局尋優(yōu)能力，尤其在迭代前期進(jìn)化速度很快.這對于兩者的優(yōu)缺點(diǎn)很多學(xué)者提出了粒子群優(yōu)化遺傳算法對兩種算法進(jìn)行優(yōu)勢互補(bǔ).本文對文獻(xiàn)[7]中提出的PSO優(yōu)化遺傳算法進(jìn)行了改進(jìn).

3.1 染色體編碼

在黃志清[8]等提出的雙層編碼的思路上，對工藝路線的工序數(shù)進(jìn)行定量后對染色體進(jìn)行編碼.基因Njlk表示工件Nj的l條工藝路線的k道工序.假設(shè)車間有4條工藝路線L1、L2、L3、L4，8個工件N1、N2、N3、N4、N5、N6、N7、N8進(jìn)行加工.第一層編碼4-2-1-1-3-1-4-3，第二層編碼為1-1-3-5-3-8-1-7-8-5-2-4-2-6-2-8-6-2-4-3-7-8-5-2-8-5-5-4-2-6，其中工藝路線L1擁有3道工序，L2擁有6道工序、L3擁有5道工序、擁有2道工序.最終編碼為：

N141-N311-N531-N312-N831-N142-N741-N832-N532-N221-N411-N222-N611-N223-N833-N612-N224-N412-N313-N742-N834-N533-N225-N835-N534-N535-N413-N226-N613

3.2 適應(yīng)度函數(shù)及選擇操作

適應(yīng)度函數(shù)的選擇的原則是，適應(yīng)度函數(shù)大于等于0，同向于優(yōu)化方向，并且一般在目標(biāo)函數(shù)的基礎(chǔ)上進(jìn)行變換.對完成時間進(jìn)行去量綱處理后得到最大完工時間CTmax最小完工時間CTmin.適應(yīng)度函數(shù)如公式(9)所示：

(9)

采用輪盤賭局的方式，根據(jù)Fit函數(shù)對個體的適應(yīng)度進(jìn)行計(jì)算，然后按照適應(yīng)度值對應(yīng)的選擇概率進(jìn)行隨機(jī)選取，一直到選出滿足設(shè)定數(shù)量的個體數(shù)[9,10].

3.3 交叉和變異操作

交叉和變異操作的目的是產(chǎn)生新的個體保證種群的多樣性，其中遺傳算法的全局搜索能力由交叉操作控制，局部搜索能由變異操作決定.

交叉操作是對父代個體配對進(jìn)行基因交換重組，產(chǎn)生新的個體，從而使更優(yōu)個體出現(xiàn)成為可能[11]，交叉因子pc1的取值對遺傳算法的收斂性有很大的影響，若pc1取值過小，進(jìn)化緩慢不利于個體的優(yōu)勝劣汰，若pc1取值過大，新個體產(chǎn)生的速度加快但同時增大了個體迅速被破壞的風(fēng)險.所以此次采用了自適應(yīng)交叉因子.

保證最大適應(yīng)度值與平均適應(yīng)度值不相等時的基礎(chǔ)上，當(dāng)前適應(yīng)度值Fit(x)高于平均適應(yīng)度值Fitavg時給pc0乘上一個小于1的數(shù)，減小交叉因子pc1的數(shù)值使優(yōu)秀個體能夠進(jìn)入下一代.

(11)

變異操作是通過對個體內(nèi)部基因的更改產(chǎn)生新的個體，自適應(yīng)變異操作公式與交叉操作類似.

4 模擬退火算法

模擬退火算法(Simulated Annealing，SA)最早的思想是由N.Metropolis[12]，通過賦予搜索過程一種時變且最終趨于0的概率突跳性，來有效的避免陷于局部極小并最終趨于全局最優(yōu)的串行結(jié)構(gòu)的優(yōu)化算法.將模擬退火算法應(yīng)用于遺傳算法的迭代過程中加入SA判斷函數(shù)用來確定是否執(zhí)行SA操作，SA算法的步驟如下：

1)初始化參數(shù)設(shè)置：初始解S、初始溫度T、迭代次數(shù)L、循環(huán)計(jì)數(shù)器K；

2)Metropolis準(zhǔn)則.增量ΔT=C(S′)-C(S)，C(S)為評價函數(shù)；

3)ΔT判斷.若T<0，S′變?yōu)楫?dāng)前解，若ΔT≥0以概率exp(-ΔT/T)接受S′變?yōu)楫?dāng)前解;

4)終止條件判定：根據(jù)經(jīng)驗(yàn)若連續(xù)K個新解都沒有被選擇，那么當(dāng)前解為最優(yōu)解輸出并結(jié)束.如果不滿足終止條件那么進(jìn)行降溫操作.降溫公式為：

tW=γtW-1

(12)

5)重復(fù)上述步驟，完成對所有個體抽樣.

5 SA優(yōu)化改進(jìn)PSO-GA算法

前期利用遺傳算法前期搜索效率高的優(yōu)勢產(chǎn)生初始種群，前期迭代次數(shù)所占總次數(shù)的百分比為GAΦ，中期利用粒子群算法收斂速度快的特點(diǎn)進(jìn)行中期迭代，中期迭代次數(shù)所占總次數(shù)的百分比為PSOΦ，后期利用模擬退火算法來避免PSO-GA后期容易陷入局部極值的問題，后期迭代次數(shù)百分比為SAΦ，且PSOΦ+GAΦ+SAΦ=1.參數(shù)初始化時需要根據(jù)經(jīng)驗(yàn)設(shè)定了GAΦ、PSOΦ、SAΦ的值.SA優(yōu)化PSO-GA算法以下簡稱SA-PSO-GA算法流程圖如圖1所示.

圖1 SA-PSO-GA算法流程圖

首先進(jìn)行參數(shù)初始化設(shè)置并由遺傳算法產(chǎn)生一個初始種群，計(jì)算適應(yīng)度函數(shù)對滿足條件的直接進(jìn)入下一步，不滿足的通過PSO優(yōu)化之后進(jìn)入下代種群.中期對種群選擇、交叉、操作等操作進(jìn)行迭代，后期對符合SA判斷函數(shù)條件的進(jìn)行模擬退火操作，不滿足的通過對舊種群與新種群合并成新的種群的再判斷是否滿足SA判斷函數(shù).進(jìn)行適應(yīng)值判斷后保存每代進(jìn)化的最優(yōu)解直到輸出最終的最優(yōu)解.

6 生產(chǎn)車間調(diào)度實(shí)例仿真

贛州某機(jī)器人生產(chǎn)車間負(fù)責(zé)對6kg、8kg、12kg、20kg等多種型號的工業(yè)機(jī)器人本體件的加工工作.工業(yè)機(jī)器人本體由大臂、小臂、轉(zhuǎn)座、腕部、手部等組成.采用該公司提供的8kg機(jī)器人本體件，6個工件每個工件6道工序的數(shù)據(jù)進(jìn)行排產(chǎn)實(shí)驗(yàn).定義8kg機(jī)器人型號對應(yīng)的工藝路線l為0.表1所示為該公司應(yīng)用案例中各工件加工時間.

表1 工業(yè)機(jī)器人本體加工車間部分工件加工時間(h)

對改進(jìn)PSO-GA算法進(jìn)行排產(chǎn)的初始粒子數(shù)為50、迭代次數(shù)150、pc0為0.85、pm0為0.35、γ為0.95.SA優(yōu)化PSO-GA算法進(jìn)行排產(chǎn)的初始粒子數(shù)、迭代次數(shù)、pc0、pm0不變，模擬退火初始值500、模擬退火終值0，兩種算法對應(yīng)甘特圖分別如圖2、圖3所示.甘特圖用jlk表示Njlk.

圖2 傳統(tǒng)PSO-GA算法對應(yīng)甘特圖

圖3 SA-PSO-GA算法對應(yīng)甘特圖

通過圖2和圖3可以看出，傳統(tǒng)PSO-GA算法甘特圖排產(chǎn)結(jié)果顯示48個小時可完成6個工件的生產(chǎn)，GA-PSO-SA算法甘特圖排產(chǎn)結(jié)果顯示46個小時即可完成生產(chǎn)任務(wù)，說明GA-PSO-SA算法排產(chǎn)實(shí)際效果優(yōu)于傳統(tǒng)PSO-GA算法.兩種算法的進(jìn)化曲線圖如圖4所示.

圖4 進(jìn)化曲線圖

從進(jìn)化曲線圖可以看出傳統(tǒng)PSO-GA算法陷于局部最優(yōu)，所輸出的最優(yōu)解并不是實(shí)際的最優(yōu)解.并且運(yùn)行結(jié)果顯示傳統(tǒng)PSO-GA算法運(yùn)算時間一般為24-20S，SA-PSO-GA運(yùn)算時間一般為19-16S.SA-PSO-GA算法達(dá)到預(yù)期效果，優(yōu)于傳統(tǒng)PSO-GA算法.

7 結(jié) 語

本文通過對通過對柔性流水車間調(diào)度的分析和模型的建立后，提出了一種新的SA-PSO-GA算法.SA-PSO-GA算法在迭代前期繼承GA算法前期搜索效率高的特點(diǎn)，在中期繼承PSO算法精度、搜索效率高的特點(diǎn)，在后期繼承SA算法的概率突跳性跳出局部極值的特點(diǎn)，最終達(dá)到快速、高效地得到全局最優(yōu)解的要求.通過實(shí)驗(yàn)仿真比較，驗(yàn)證了SA-PSO-GA算法的優(yōu)勢.