基于混合GA算法求解車間調(diào)度問題

王 粟，陳新彥，曾 亮

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

0 引 言

在如今數(shù)字化車間普及的時(shí)代，工作車間調(diào)度問題(job shop scheduling problem)更為優(yōu)化的解決，對(duì)先進(jìn)制造技術(shù)的進(jìn)一步發(fā)展十分關(guān)鍵[1]。

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

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

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

1.1 符號(hào)定義

本章節(jié)使用的所有數(shù)學(xué)符號(hào)及其代表的含義見表1。

表1 數(shù)學(xué)符號(hào)

1.2 模型建立

優(yōu)化目標(biāo)選擇車間調(diào)度問題中最常使用的最小化最大完工時(shí)間[8]，有如下表達(dá)式

(1)

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

f=min{Cmax}

(2)

約束條件：

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

Si,j>Si,j-1

(3)

(2)對(duì)于任意一臺(tái)機(jī)器，如果正在對(duì)某個(gè)工件的某道工序加工，其它工件不得在此時(shí)間段使用該機(jī)器，保證一臺(tái)機(jī)器只能加工一個(gè)工件

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

(4)

2 GA算法和PSO算法簡(jiǎn)介

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

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

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

3 混合GA算法

本文中提出的混合GA算法，結(jié)合了GA算法和PSO算法，根據(jù)第2節(jié)分析這兩種經(jīng)典優(yōu)化算法的優(yōu)劣。首先詳細(xì)闡述了混合GA算法的思想，說明了如何借鑒SA算法中的重升溫策略，使PSO算法更好補(bǔ)償GA算法的缺陷，接著針對(duì)它們?cè)谔幚碥囬g調(diào)度問題的不足之處，改進(jìn)了GA算法中的變異策略，并在PSO算法中引入了自適應(yīng)控制因子和排列操作，然后描述混合GA算法的步驟總流程并畫出該算法的流程圖，最后通過仿真驗(yàn)證了混合GA算法思想的可行性。

3.1 混合GA算法的思想

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

3.2 變異策略

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

Input:

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

Procedure:

IfSr>avgfitnessgthen

將該染色體執(zhí)行變異操作；

End

Output: 經(jīng)過變異操作的染色體；

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

3.3 種群生成策略

本文使用PSO算法產(chǎn)生的個(gè)體極值種群代替GA算法特定代數(shù)的種群,為了使PSO算法在處理車間調(diào)度這一具體問題能發(fā)揮良好效果，引入了改進(jìn)的自適應(yīng)控制因子和排列操作。

3.3.1 自適應(yīng)學(xué)習(xí)因子和慣性權(quán)重因子

粒子群算法的控制因子在整個(gè)迭代過程中，始終保持不變。但隨著迭代次數(shù)的增加，種群所處的解空間的環(huán)境在不斷發(fā)生著變化，所以為了使控制因子更好控制尋優(yōu)過程向著好的方向進(jìn)行[14]，本文對(duì)學(xué)習(xí)因子和慣性權(quán)重因子進(jìn)行了改進(jìn)，公式如下

(7)

(8)

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

另外，對(duì)慣性權(quán)重因子w也進(jìn)行了動(dòng)態(tài)調(diào)整，表達(dá)式如下

(9)

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

3.3.2 排列操作

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

圖1 排列操作方法

3.4 混合GA算法基本流程

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

步驟1 初始化參數(shù)，產(chǎn)生初始種群。

步驟2 計(jì)算種群的適應(yīng)度值。

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

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

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

步驟6 轉(zhuǎn)到步驟2，重復(fù)上述步驟直到算法達(dá)到終止條件，輸出最優(yōu)解。

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

圖2 混合GA算法流程

3.5 混合GA算法思想測(cè)試

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

圖3 效果對(duì)比

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

4 車間調(diào)度仿真

4.1 測(cè)試算例生成

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

表2 MNO_10調(diào)度加工時(shí)間與加工機(jī)器

表3 MNO_8調(diào)度加工時(shí)間與加工機(jī)器

4.2 參數(shù)配置

對(duì)HOGA的初始種群規(guī)模設(shè)置為20、最大迭代次數(shù)為300、使用粒子群算法產(chǎn)生個(gè)體極值種群的迭代次數(shù)為50、交叉率為0.8、保優(yōu)率為0.05；對(duì)GA的初始種群規(guī)模、最大迭代次數(shù)、交叉率、保優(yōu)率不變，此外的變異率為0.01；對(duì)PSO的初始種群規(guī)模、最大迭代次數(shù)不變，此外的學(xué)習(xí)因子為1.5，慣性權(quán)重因子為0.8，粒子的最大速度為35，粒子的最小速度為0。

表4 MNO_6調(diào)度加工時(shí)間與加工機(jī)器

4.3 算法對(duì)比分析

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

從圖4、圖5、圖6對(duì)比可以發(fā)現(xiàn)，通過HOGA對(duì)工序優(yōu)化排序后，相較于GA和PSO這兩種算法來說，充分利用了有限的加工機(jī)器，提高了效率，縮短了總加工時(shí)長(zhǎng)，體現(xiàn)HOGA在解決車間調(diào)度問題上的優(yōu)勢(shì)。3種算法的分別在MNO_10、MNO_8、MNO_6這3種測(cè)試算例中的進(jìn)化曲線如圖7、圖8、圖9所示。

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

圖4 MNO_10對(duì)應(yīng)的甘特圖

圖5 MNO_8對(duì)應(yīng)的甘特圖

圖6 MNO_6對(duì)應(yīng)的甘特圖

圖7 MNO_10的算法收斂性對(duì)比

圖8 MNO_8的算法收斂性對(duì)比

而在HOGA處理規(guī)模較大的MNO_10測(cè)試算例時(shí)，對(duì)比另外兩種算法，取得最優(yōu)解之間的差異更大；而在處理規(guī)模較小的MNO_6測(cè)試算例時(shí)，HOGA憑借它優(yōu)異的性能仍然能夠最大限度找出更好的最優(yōu)解。HOGA達(dá)到了預(yù)期的優(yōu)化效果，優(yōu)于PSO和GA。測(cè)試結(jié)果的匯總見表5。

圖9 MNO_6的算法收斂性對(duì)比

表5 測(cè)試結(jié)果匯總

5 結(jié)束語

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