基于混合GA算法求解車間調度問題

王 粟，陳新彥，曾 亮

(湖北工業大學 電氣與電子工程學院，湖北 武漢 430068)

0 引 言

在如今數字化車間普及的時代，工作車間調度問題(job shop scheduling problem)更為優化的解決，對先進制造技術的進一步發展十分關鍵[1]。

使用優化算法來解決車間調度問題，難免會出現收斂速度與局部最優之間的矛盾，為了盡可能減小帶來的影響，已經有很多不同改進的優化算法被應用在解決JSP上[4]。魏勝利等[5]使用了改進的生物地理學優化算法處理車間調度問題；葉彥斐等[6]在基于傳統遺傳算法的基礎上，將種群災變機制加入到算法的遺傳環節中以預防種群早熟收斂，尋優能力明顯提高；曹坤煜等[7]以最小化最大完工時間為目標建立了生產調度模型，并在此模型的基礎上設計了一種收斂速度和求解穩定性均較優的免疫遺傳算法。盡管上述方法取得了一定的效果，但是探索新的方法求解JSP仍在不斷進行。

本文針對JSP提出了一種混合GA算法，主要從變異策略和種群生成兩方面進行了改進。一方面，對遺傳算法中的變異算子的改進，根據種群的平均適應度值來決定是否進行變異操作，使變異朝著確定的方向進行，加快了收斂速度；另一方面，當變異趨勢的確定后，將會造成種群的多樣性下降、收斂速度過快的問題，這些問題就使得出現局部最優解的可能性上升，于是本文借鑒SA算法的重升溫策略，使用PSO算法中的個體極值來代替GA算法的特定代數的種群，幫助在尋優迭代過程中跳出局部最優，增強了全局搜索能力。借鑒SA算法的改進思想，使得PSO算法更好優化GA算法，最終使該算法能更加快速、高效找出JSP的最優解。

1 車間數學模型

1.1 符號定義

本章節使用的所有數學符號及其代表的含義見表1。

表1 數學符號

1.2 模型建立

優化目標選擇車間調度問題中最常使用的最小化最大完工時間[8]，有如下表達式

(1)

目標函數

f=min{Cmax}

(2)

約束條件：

(1)由于工件本身加工上的工藝約束，對每個工件來說，必須在前一道工序加工完成后才能加工后一道工序

Si,j>Si,j-1

(3)

(2)對于任意一臺機器，如果正在對某個工件的某道工序加工，其它工件不得在此時間段使用該機器，保證一臺機器只能加工一個工件

?Mk?M,x、y∈{1,2,3,…,m},x≠y, ?Mx,η,θ,My,α,β

(4)

2 GA算法和PSO算法簡介

對遺傳算法來說，其特有的遺傳操作，使得種群的多樣性豐富，增強了全局搜索的能力，減少了陷入局部最優解的風險[9]。但較強的全局搜索能力意味著需要較大的迭代次數，才能在尋優迭代的過程找到最優解。這就說明了遺傳算法相對于其它優化算法來說，收斂速度較慢，要較長的時間才可以使種群進化到包含近似最優解的狀態，最終在全局最優解位置收斂[10]。

而對粒子群算法，其核心要素就是用來更新粒子在解空間位置的速度-位移公式，具體如下

vij(t+1)=w·vij(t)+c1r1[pij(t)-xij(t)]+c2r2[pgj(t)-xij(t)]

(5)

xij(t+1)=xij(t)+vij(t+1)

(6)

其中，c1、c2為加速因子，c1體現了粒子對自身歷史位置記憶能力的強弱，反映了粒子向歷史個體極值趨近的快慢；c2體現了粒子對整個種群最優位置信息汲取能力的大小，反映了粒子向歷史全局極值趨近的快慢[11]。可以看出c1代表著粒子對自身“認知”能力的好壞，而c2代表著粒子間有效信息共享能力的優劣。r1、r2代表[0,1]范圍內的均勻隨機數。pij(t) 代表第i個粒子迄今為止搜索到的最優位置，pgj(t) 代表整個粒子群迄今為止搜索到的最優位置。對于具有保證粒子運動慣性的控制參數w，反映了粒子對前一代速度的保持能力的大小[12]。vij(t)、vij(t+1) 分別代表粒子當前的速度和迭代一次后的速度，而xij(t)、xij(t+1) 分別代表粒子當前的位置和迭代一次后的位置。從公式中可以很明顯的看出，這些關鍵的控制因子并沒有隨搜索過程的變化而變化。對于不同的迭代次數，即不同的“外界環境”，也就需要不同大小的控制因子，才能更好發揮控制因子的效果，從而使得算法能夠準確高效地尋找出問題的最優解。

3 混合GA算法

本文中提出的混合GA算法，結合了GA算法和PSO算法，根據第2節分析這兩種經典優化算法的優劣。首先詳細闡述了混合GA算法的思想，說明了如何借鑒SA算法中的重升溫策略，使PSO算法更好補償GA算法的缺陷，接著針對它們在處理車間調度問題的不足之處，改進了GA算法中的變異策略，并在PSO算法中引入了自適應控制因子和排列操作，然后描述混合GA算法的步驟總流程并畫出該算法的流程圖，最后通過仿真驗證了混合GA算法思想的可行性。

3.1 混合GA算法的思想

改進變異策略的遺傳算法依據平均適應度值來判斷是否進行變異操作，提高了收斂速度，有效解決變異的隨機性的問題。但對于某些特殊的初始種群，改進變異策略的遺傳算法大概率會得出局部最優解。分析改進變異策略的遺傳算法未產生更優解的原因有兩點：一是可能由于收斂速度過快；二是在整個進化過程中，個體包含最優解的特征少，很難產生最優解。對于收斂過快的情況，借鑒模擬退火算法中的重升溫策略，由于收斂過快造成陷入局部極小值停滯不前時，可以通過將粒子群算法產生的個體最優位置代替遺傳算法中迭代特定次數種群的位置，從而跳出局部最優解，調整搜索進程。之所以采用個體最優位置，因為個體最優解包含全局最優解的大多數特征，這正好彌補了最優解特征少的缺陷，在尋優迭代過程中，通過粒子間的協同合作與知識共享，對最優解的尋找起到一定的輔助作用。

3.2 變異策略

遺傳算法的變異操作雖然保證了種群的多樣性，但變異并沒有一個確定的方向，隨機性較強。在改進的變異操作中，舍棄了傳統意義上決定變異比列的變異概率，在一定程度上違背了自然規律，但這樣對于具體的問題，能夠盡早收斂，提高效率[13]。偽代碼如下：

Input:

第r條染色體的適應度值為Sr；第g代經過選擇和交叉操作種群的平均適應度值為avgfitnessg；

Procedure:

IfSr>avgfitnessgthen

將該染色體執行變異操作；

End

Output: 經過變異操作的染色體；

判斷是否變異不再由隨機數與變異概率的大小關系來決定，而是根據種群的平均適應度值來決定。對進行了選擇和交叉操作的種群求其適應度的平均值，然后對大于該平均值的進行變異操作，小于該平均值的不進行變異操作。

3.3 種群生成策略

本文使用PSO算法產生的個體極值種群代替GA算法特定代數的種群,為了使PSO算法在處理車間調度這一具體問題能發揮良好效果，引入了改進的自適應控制因子和排列操作。

3.3.1 自適應學習因子和慣性權重因子

粒子群算法的控制因子在整個迭代過程中，始終保持不變。但隨著迭代次數的增加，種群所處的解空間的環境在不斷發生著變化，所以為了使控制因子更好控制尋優過程向著好的方向進行[14]，本文對學習因子和慣性權重因子進行了改進，公式如下

(7)

(8)

其中，c1max、c2max為c1、c2的最大值，c1min、c2min為c1、c2的最小值，i表示當前迭代次數，maxgen1表示最大迭代次數。可以從上式看出，在算法開始時，賦給c1、c2較小值，接近cmin， 使粒子對自身先前速度的記憶能力較弱，在一定程度上保證粒子在偏離原先的尋優軌跡上進行搜索，進而在未知的解空間中展開尋優探測，體現了全局搜索；而在算法執行后期，迭代次數i接近maxgen1，c1、c2有較大值，接近cmax， 則粒子對上一次迭代時具有的速度維持能力較強，使得粒子在近似原先的搜索范圍進行更為深入的探索，根據原有的尋優軌跡在附近范圍來搜索更好的解，體現了局部搜索。

另外，對慣性權重因子w也進行了動態調整，表達式如下

(9)

其中，wmax、wmin代表慣性權重因子的最大值和慣性權重因子的最小值， max(pbest)、 min(pbest) 分別代表個體極值的最大值和最小值，pbest(j) 代表當前粒子的個體極值，k為當前迭代次數[15]。上式反映出，對于個體極值較小的粒子，賦給的慣性權重因子較大，維持粒子歷史速度的能力較強，便于粒子在原有的搜索軌跡上進行更細致的搜索；對于個體極值較大的粒子，賦給的慣性權重因子較小，維持粒子歷史速度的能力較弱，便于粒子在偏離原有的搜索軌跡上進行“開發”。而最后的部分e-k是隨著迭代次數的增加而減小，使得在算法開始時，具有較強的“探索”能力，而在算法的后期，具有較強的“開發”能力。

3.3.2 排列操作

對于車間調度這種采用實數編碼的問題，引入了一種新的進化操作——排列操作。排列操作的方法是：隨機截取染色體的一部分，包含x個基因位，對這x個基因位隨機排列，共有x！種情況，再隨機從中選取一種來替代之前的染色體片段。與變異操作和交叉操作所起到的作用相似，排列操作的作用也是增加種群的多樣性，但不同的是排列操作能夠產生更加多種的情況，特別是采用實數編碼的染色體，操作簡單且效果明顯。排列操作如圖1所示，從圖中可以看出隨機選擇了5個連續的基因位，所以共有5！=120種可能的替換情況，此圖中是將5-2-2-6-7替換為2-5-6-7-2。圖1(a)是父代選擇出的部分基因位，圖1(b)是進行排列操作后的子代部分基因位。

圖1 排列操作方法

3.4 混合GA算法基本流程

綜上所述，混合GA算法步驟具體描述如下：

步驟1 初始化參數，產生初始種群。

步驟2 計算種群的適應度值。

步驟3 判斷迭代次數是否等于最大迭代次數n。

步驟4 如果條件不滿足，則依次進行選擇、交叉、變異、保優操作，并計算當代種群中個體的適應度值，保留每代中的最優個體，轉到步驟3。如果條件滿足，再判斷改進后的遺傳算法是否產生了更優解，如果產生了更優解，則輸出該解；否則，使用粒子群算法迭代k次，得到由個體極值組成的種群。

步驟5 將由個體極值組成的種群代替遺傳算法的第k代的種群。

步驟6 轉到步驟2，重復上述步驟直到算法達到終止條件，輸出最優解。

混合GA算法流程如圖2所示。

圖2 混合GA算法流程

3.5 混合GA算法思想測試

如果僅僅改進變異策略的GA算法對尋找更優解有效果時，直接輸出最優解。而當改進變異策略的遺傳算法未得出更優解時，使用了粒子群算法產生的個體極值代替遺傳算法迭代特定次數的種群，不僅彌補了改進變異策略可能帶來收斂速度過快的問題，也有效應對了初始種群隨機產生所帶來的影響。分別以粒子群算法產生的個體極值作為第50代種群和以遺傳算法原始的第50代種群完成迭代的進化曲線如圖3所示。

圖3 效果對比

圖3是在第4章提到的測試算例MNO_10中得出的，其中圖中虛線是先通過粒子群算法對初始種群進行迭代50次，將產生的個體極值組成的種群代替遺傳算法的第50代的種群，再使用遺傳算法進行迭代250次得出的進化曲線；而點畫線是對同一初始種群直接使用遺傳算法完成迭代，截取50～300代的進化曲線。從對比圖可以很明顯看出，使用粒子群算法迭代50次產生的個體極值組成的種群與遺傳算法第50代的種群，前者的目標函數值高于后者的目標函數值，符合自己的分析，起到了重升溫的效果。同時，由于通過粒子群算法產生的種群由個體極值組成，其中攜帶最優解的特征元素較多，最后產生的最優解也要更加優良。

4 車間調度仿真

4.1 測試算例生成

本文為驗證混合GA算法(hybrid optimization genetic algorithm，HOGA)求解所提問題的性能，使用車間調度問題中3種不同規模的算例進行測試。其中，每個測試算例的機器數量、工件數量和工件的加工工序數都不相同，分別為10臺機器、10個加工工件、每個工件有10道工序；8臺機器、8個加工工件、每個工件有8道工序；6臺機器、6個加工工件、每個工件有6道工序。以10臺機器、10個加工工件、每個工件有10道工序的這個測試算例為例，命名為MNO_10，則另外兩種測試算例分別命名為MNO_8和MNO_6。此外，每臺機器有各自的工藝約束，只能夠加工某些工件的某些工序。對于工件的某道工序，只能在固定的機器上進行加工。測試算例MNO_10的調度加工時間與加工機器見表2，測試算例MNO_8的調度加工時間與加工機器見表3，測試算例MNO_6的調度加工時間與加工機器見4。

表2 MNO_10調度加工時間與加工機器

表3 MNO_8調度加工時間與加工機器

4.2 參數配置

對HOGA的初始種群規模設置為20、最大迭代次數為300、使用粒子群算法產生個體極值種群的迭代次數為50、交叉率為0.8、保優率為0.05；對GA的初始種群規模、最大迭代次數、交叉率、保優率不變，此外的變異率為0.01；對PSO的初始種群規模、最大迭代次數不變，此外的學習因子為1.5，慣性權重因子為0.8，粒子的最大速度為35，粒子的最小速度為0。

表4 MNO_6調度加工時間與加工機器

4.3 算法對比分析

HOGA、GA、PSO這3種算法在測試算例MNO_10上對應甘特圖分別如圖4(a)、圖4(b)、圖4(c)所示，在測試算例MNO_8上對應甘特圖分別如圖5(a)、圖5(b)、圖5(c)所示，在測試算例MNO_6上對應甘特圖分別如圖6(a)、圖6(b)、圖6(c)所示[16]。

從圖4、圖5、圖6對比可以發現，通過HOGA對工序優化排序后，相較于GA和PSO這兩種算法來說，充分利用了有限的加工機器，提高了效率，縮短了總加工時長，體現HOGA在解決車間調度問題上的優勢。3種算法的分別在MNO_10、MNO_8、MNO_6這3種測試算例中的進化曲線如圖7、圖8、圖9所示。

對比HOGA、GA、PSO這3種算法在3種不同的測試算例中的進化曲線圖，可以清楚看出，首先在同一個測試算例中，對于同樣的初始種群，HOGA不僅在搜索的初期具有較快的收斂速度，而且在后續搜索中具有較好的跳出局部最優的能力；而對于PSO和GA來說，容易陷入局部最優解，導致最終所輸出的最優解并不是實際的最優解。

圖4 MNO_10對應的甘特圖

圖5 MNO_8對應的甘特圖

圖6 MNO_6對應的甘特圖

圖7 MNO_10的算法收斂性對比

圖8 MNO_8的算法收斂性對比

而在HOGA處理規模較大的MNO_10測試算例時，對比另外兩種算法，取得最優解之間的差異更大；而在處理規模較小的MNO_6測試算例時，HOGA憑借它優異的性能仍然能夠最大限度找出更好的最優解。HOGA達到了預期的優化效果，優于PSO和GA。測試結果的匯總見表5。

圖9 MNO_6的算法收斂性對比

表5 測試結果匯總

5 結束語

本文結合車間調度問題，提出了一種混合GA算法：該算法首先改進了GA算法的變異操作策略，減小了傳統變異的隨機性帶來的影響，加快了收斂速度；然后借鑒模擬退火算法思想，將PSO算法產生的個體極值種群代替GA算法迭代特定次數的種群，有效解決了初始種群隨機產生造成的問題，并跳出了局部最優解，起到重升溫的作用，最終達到快速、高效得出全局最優解的目的。通過MNO_10、MNO_8、MNO_6這3個測試算例進行實驗仿真比較，驗證了混合GA算法的優勢。下一步，將從PSO算法中參數尋優方面開展工作，進一步優化混合GA算法的性能。