模擬退火算法優化PSO-GA算法解決柔性流水車間調度問題

景會成，王 穎

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

E-mail ：925683837@qq.com

1 引 言

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

2 車間數學模型

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

(1)

其中

Cjk=Sjk+Tjk

(2)

目標函數

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達到最小即找出最優的加工方案使總加工時間最小.k-1道工序的結束時間先于第k道工序的起始時間，保證工序的先后順序不變.Mi在第k-1道工序的加工結束時間先于Mi在第k道工序的起始加工時間，保證一臺機床只能加工一個工件.

3 PSO-GA算法改進

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

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

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表示粒子群搜索空間的維數.從上述公式可以看出PSO在迭代中期的收斂速度快、搜索效率高、精度高但在其他時期搜索效率低，在迭代后期更新速度幾乎趨近于0，容易陷于局部極值.最初由美國Michigan大學Holland教授于1975年首先提出來的遺傳算法(Genetic Algorithm，GA)，是通過對自然進化過程進行模擬來實現搜尋最優解的一種方法[6].遺傳算法具有很強全局尋優能力，尤其在迭代前期進化速度很快.這對于兩者的優缺點很多學者提出了粒子群優化遺傳算法對兩種算法進行優勢互補.本文對文獻[7]中提出的PSO優化遺傳算法進行了改進.

3.1 染色體編碼

在黃志清[8]等提出的雙層編碼的思路上，對工藝路線的工序數進行定量后對染色體進行編碼.基因Njlk表示工件Nj的l條工藝路線的k道工序.假設車間有4條工藝路線L1、L2、L3、L4，8個工件N1、N2、N3、N4、N5、N6、N7、N8進行加工.第一層編碼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 適應度函數及選擇操作

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

(9)

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

3.3 交叉和變異操作

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

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

保證最大適應度值與平均適應度值不相等時的基礎上，當前適應度值Fit(x)高于平均適應度值Fitavg時給pc0乘上一個小于1的數，減小交叉因子pc1的數值使優秀個體能夠進入下一代.

(11)

變異操作是通過對個體內部基因的更改產生新的個體，自適應變異操作公式與交叉操作類似.

4 模擬退火算法

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

1)初始化參數設置：初始解S、初始溫度T、迭代次數L、循環計數器K；

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

3)ΔT判斷.若T<0，S′變為當前解，若ΔT≥0以概率exp(-ΔT/T)接受S′變為當前解;

4)終止條件判定：根據經驗若連續K個新解都沒有被選擇，那么當前解為最優解輸出并結束.如果不滿足終止條件那么進行降溫操作.降溫公式為：

tW=γtW-1

(12)

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

5 SA優化改進PSO-GA算法

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

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

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

6 生產車間調度實例仿真

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

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

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

圖2 傳統PSO-GA算法對應甘特圖

圖3 SA-PSO-GA算法對應甘特圖

通過圖2和圖3可以看出，傳統PSO-GA算法甘特圖排產結果顯示48個小時可完成6個工件的生產，GA-PSO-SA算法甘特圖排產結果顯示46個小時即可完成生產任務，說明GA-PSO-SA算法排產實際效果優于傳統PSO-GA算法.兩種算法的進化曲線圖如圖4所示.

圖4 進化曲線圖

從進化曲線圖可以看出傳統PSO-GA算法陷于局部最優，所輸出的最優解并不是實際的最優解.并且運行結果顯示傳統PSO-GA算法運算時間一般為24-20S，SA-PSO-GA運算時間一般為19-16S.SA-PSO-GA算法達到預期效果，優于傳統PSO-GA算法.

7 結 語

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