一種多尺度協同變異的螢火蟲粒子群混合算法及在車間調度中的應用

周艷平,劉永娟

(青島科技大學 信息科學技術學院, 山東 青島 266061)

0 引言

作為有效的資源配置與優化手段，生產調度在整個制造體系中扮演關鍵的角色，應用范圍非常廣泛，包括工業、商業等各方面。作為整個生產調度的關鍵部分，車間調度同時也是制造類企業的核心問題，是一個典型的NP-hard問題[1]，一直以來也是組合優化領域內的重點內容，對整個生產流程能否順利完成有很大的影響。車間調度問題的本質是在符合約束條件的基礎上，根據生產指標，給出每個工件的加工順序、機器、操作方式等的組合問題。流水車間調度作為其中的一類，是流水線生產調度的簡化模型，對流水車間調度模型進行研究，有非常重要的意義。

在研究的初期，學者們通過使用精確算法來求解流水車間調度問題，但存在難度大、耗時長等問題，求解效果并不理想。后來研究者們采用近似算法去尋找問題的最優解，近似算法又叫做啟發式算法，不斷被研究改進的啟發式算法成為了調度問題的主要求解辦法。

粒子群算法(PSO,particle swarm optimization)是美國的社會心理學家Eberhart和電氣工程師Kennedy[2]受達爾文“物競天擇、適者生存”的啟發，模擬了鳥群群聚、覓食的群體性行為，于1995年提出的，算法步驟簡單、參數少并且易于實現；英國劍橋大學工程系的X.S.Yang[3]在對螢火蟲種群的發光行為進行建模的基礎上提出了螢火蟲算法(FA， firefly algorithm)，算法的提出時間不長，對算法的改進和優化仍然處于初級階段。但不斷被研究改進的螢火蟲、粒子群算法已被應用于車間調度、資源調度、組合優化等領域。

J.I.FISTER等人[4]提出了一種模因螢火蟲算法(MFFA)，將螢火蟲算法與局部搜索啟發式算法進行結合，并應用于組合優化問題中，具有一定的實用性。鄭捷等[5]采用機器選擇策略進行種群生成，并對適應度較優的個體之間進行局部搜索，從而產生了一種改進的離散螢火蟲算法，并成功地應用在柔性作業車間調度模型中。劉長平等[6]提出了一種DFA算法，用NEH構造初始解，并根據問題的特性，重新定義了距離公式，通過交叉、變異操作實現位置的更新，并對處在最佳位置的個體進行局部搜索，成功地應用在零空閑置換流水車間調度中。張其亮等[7]結合了粒子群、貪婪算法，通過變異操作來改變粒子停滯或群體陷入局部最優狀態，并依據模擬退火接收變異個體，在置換流水車間調度問題的求解質量上有一定的提高。吳瓊等[8]結合了粒子群、引力搜索算法，當粒子群進化停滯時，引入引力搜索算法，并采用協同進化的思想，使得兩種算法并行優化，并且子種群之間交流，以獲得最優粒子，并應用到對作業車間調度問題的求解中。從實驗數據來看，以上算法在不同程度上都提高了算法的性能，但在求解精度上還可以繼續改進，而且隨著車間的日益復雜化，求解算法也應該不斷的被改進完善。

單一算法在適應性上是有限的，螢火蟲和粒子群算法有一定的相似性，在全局搜索能力方面也有一定的互補性，為更好地發揮兩種算法的潛能，取長補短獲得更優的解，本文在螢火蟲粒子群混合算法的基礎上，做出了進一步的改進，提出了一種多尺度協同變異的螢火蟲粒子群混合算法(HFPMCV, a hybrid firefly and particle swarm optimization algorithm with multi-scale cooperative variation)，引入多尺度協同變異算子，提高求解精度，混沌初始化種群以提高初始解質量，根據高斯擬合把種群分為兩組；平行進化，提高求解速度，函數優化實驗驗證了改進算法的有效性，流水車間調度問題實驗，表明了改進算法的優越性。

1 多尺度協同變異的螢火蟲粒子群混合算法

1.1 螢火蟲算法

螢火蟲算法的提出是建立在螢火蟲種群中個體的種種社會行為的基礎之上的，在實際的應用中，只考慮發光特性，通過發光特性搜索目標附近特定區域，向一定范圍內定位較優的螢火蟲移動[9]，螢火蟲進化和目標函數尋優的最主要的兩個關鍵因素就是熒光亮度和吸引度。亮度表明螢火蟲所處方位的好壞，決定了飛行方向，吸引度影響螢火蟲的移動距離，利用吸引度和亮度更新、迭代來尋求目標函數最優解。數學描述如下：

在D維搜索空間內螢火蟲i的位置向量Xi=(xi1,xi2,xi3,…xiD)，螢火蟲熒光亮度公式：

I=I0e-γrij

(1)

式中，I0為自身亮度，γ為光吸收系數，r為距離。

螢火蟲之間的相對吸引度正比于亮度：

(2)

式中，β0為其初始吸引度。

螢火蟲移動距離：

(3)

α是擾動的步長因子，rand()是一個隨機擾動，取值為[-0.5,0.5]范圍內的均勻分布，α取值為[0,1]范圍。

最亮的螢火蟲位置移動：

(4)

中心思想就是，所有個體都飛向比自己更亮的個體四周，飛行的最后結果即所有的個體都圍在了亮度最強的個體周圍，從而達到算法求解的目的。

螢火蟲算法 FA：

1)初始化參數，螢火蟲數目n，吸引度β0，步長因子α，迭代次數Generation，搜索精度ε。

2)初始化個體位置，最大熒光亮度I0用螢火蟲的目標函數值表示。

3)由1)、2)計算群體中個體的I、β，飛行方向由相對亮度決定。

4)由3)更新個體位置，由4)移動最佳個體。

5)計算個體更新位置后的亮度。

6)滿足終止條件則輸出最優解，否則轉3)步。

1.2 粒子群算法

粒子群算法的核心思想在于利用粒子與種群之間的信息改變粒子的速率和定位，在飛行范圍內，粒子隨機飛行，飛行過程中通過學習、模仿周圍粒子的信息來獲取個體、全體最佳位置，綜合分析經驗后，調整自身的飛行經驗以實現更好的飛行，完成種群間個體協作探索，利用速率和定位的不斷更新迭代來尋求目標函數的最佳解[10]。數學描述如下：

D維搜索區域內，任意一個粒子都在以一定的初速度隨機飛行，粒子i的當前位置向量Xi=(xi1,xi2,xi3,…xiD)，第i個粒子當前速率：

Vi=(vi1,vi2,…viD)，i=1,2,…N

(5)

Pbest=(pi1,pi2,…piD)i=1,2,…,N為個體極值,全局極值為gbest=(pg1,pg2,…pgD)。

粒子進行速度更新：

vid=w*vid+c1r1(pid-xid)+c2r2(pgd-xid)

(6)

ω是慣性權重，平衡全局、局部搜索能力，c1、c2是學習因子，r1、r2是[0,1]里的隨機數。速度公式包含三部分，w*vid表示個體之前的速度對現在速度的影響，c1r1(pid-xid)是個體歷史最好位置對現在速度的影響，c2r2(pgd-xid)是個體之間的信息傳遞對現在速度的影響。

粒子進行位置更新：

xid=xid+vid

(7)

c1、c2是學習因子，r1、r2是[0,1]區間的隨機數。

步驟如下：

粒子群算法 PSO:

1)設置參數，包括種群規模、個體的速度和位置，并設置其它參數。

2)初始化種群。

3)計算適應度值，選出個體、全局極值。

4)粒子飛行，據式(6)、(7)更新個體的速度、位置。

5)符合終止條件就輸出最優解，反之返回3)。

1.3 多尺度協同變異的螢火蟲粒子群混合算法

考慮到螢火蟲算法和粒子群算法的優缺點，楊小東等提出了螢火蟲粒子群混合算法FAPSOMA[11]，本文在此基礎上引入多尺度協同變異算子，提出了HFPMCV算法，初期，通過多尺度變異算子快速找到全局最優解空間，不斷迭代，靠近最優解領域時，通過小尺度變異算子快速收斂到最優解,以有效的進行變異，并且對種群進行混沌初始化，同時動態自適應策略把種群分成兩組，兩組種群平行進化以尋找優化問題的精確解。

1.3.1 改進策略

1)混沌初始化：隨機初始化會造成個體位置分布不均，個體間差異較大，阻礙全局尋優，影響求解效果[12]，為了獲得質量較好的初始解，對種群進行混沌初始化，將變量映射到混沌變量的取值區域，通過線性變換把混沌序列轉化到搜索空間[13]。

由Logistic 映射：

Zn+1=μZn(1-Zn)，n=0,1,2,…

(8)

得混沌序列，μ為控制參量，μ∈[0,4]，當μ=4時為完全混沌狀態。

將混沌序列映射為求解空間范圍的混沌變量：

pn,i=ai+(bi-ai)Zn,i，i=1,2,…，I

(9)

Zn,i為個體在第i維迭代n次得到的混沌序列值，I為搜索空間維度，pn,i為一個混沌變量，[pn,1,pn,2,…pn,I]代表一個可行解。

因為PSO算法主要更新速度、位置、目標函數值，而FA算法主要更新位置和目標函數值，本文用FA算法中的個體位置和目標值來替代PSO算法中的位置和目標值，并在FA算法中創建速度信息，所以在本改進算法中，創建FA算法的速度序列：

zi(n)=μzi(n-1)(1-zi(n-1))

(10)

zi(n)是[0,1]中符合正態分布的隨機數，n是迭代數，μ值為4。

2)動態自適應控制策略：在傳統算法中，種群分組采用隨機分組、平均分組的方法，沒有充分考慮種群中個體的運動軌跡。

HFPMCV算法采用高斯擬合函數[14]進行種群分組，在混沌初始化種群后，計算并按照種群中各個體的適應度值進行高斯擬合，因適應度值是由目標函數得來，因此擬合曲線與目標函數曲線有較強關聯度[15]，求解擬合曲線峰值的加權平均數[16]，并以此為根據把整個種群劃分為兩組族群。

3)多尺度協同變異算子：為了提高求解精度，避免陷入局部最優，引入多尺度協同變異算子[17]，多尺度協同變異利用方差不同的高斯變異機制探索解空間，初期，通過大尺度變異算子快速找到全局最優解空間，不斷迭代，靠近最優解領域時，通過小尺度變異算子快速收斂到最優解,以有效的進行變異[18]，設尺度個數為M，首先初始化方差:

(11)

對方差、優化變量設置一樣的取值范圍，隨著迭代次數的增加，方差會一直變化，所有個體生成M個子群，個體個數為P=N/M，迭代次數為K，子種群適應度：

(12)

f是適應度函數，第m個變異算子的標準差：

(13)

(14)

(15)

變異算子的進化過程為一個遞歸的過程，HFPMCV算法要求的是隨著迭代次數的增加變異算子逐漸減小，因此需要規范變異算子的標準差：

(16)

W為待優化變量空間的寬度。

位置更新公式如下：

If(vid

Elsevid=rand*Vmax

(17)

其中：Td是設置好的閾值，閾值Td過大會降低算法的深度局部搜索能力，閾值過小會降低算法的搜索速度，因此，自適應設定閾值，不同維的速度設置不同的閾值，當達到該值時，閾值會自動下降，當速度小于閾值時，個體進行逃逸：

其中:

(18)

ifGd(t)>k1then

Gd(t)=0;Td=Td/k2

(19)

k1、k2是常數，Size為種群大小，Gd(t)是種群在第d維速度的逃逸次數。

4)平行進化：結合FA和PSO的優點，使FA和PSO平行的單獨進化[19]，每一代進化結束后，各自保存最優個體，選出較優個體，并與父代最優個體進行比較選出更優個體作為本代最優個體，全部迭代結束后，輸出整體最優值，大大提升了求解速度[20]。

1.3.2 算法流程

HFPMCV算法流程如圖1所示。

圖1 HFPMCV算法流程圖

1.3.3 函數優化測試

為了測試和解釋HFPMCV算法的性能和優越性，將HFPMCV算法與FA算法、FAPSOMA算法進行了對比，分別采用HFPMCV算法以及FA算法、FAPSOMA算法對以下函數[21]進行尋優：

xi∈[-5.12,5.12]，i=1,2,…,30

(20)

是一個多峰函數，在30維可行域中有230-1個局部求解，最優值是0，對3個算法中的各參數設定一樣的值以提高計算有效性和結果精確度，迭代500次，種群規模是100，維度是30等。

3種算法的性能對比如圖2所示，圖中可以看出，迭代次數相同時，HFPMCV算法收斂更快，精度更高，求解結果相同時，FA、FAPSOMA需要迭代更多次才能得到最優解，通過函數測試驗證了HFPMCV算法的優良性能。

圖2 3種算法性能比較圖

2 HFPMCV算法求解流水車間調度問題

2.1 流水車間調度問題模型

FSP問題[22]:n個工件在m臺機器上加工，i工件工序數為Li，總工序數L，工序加工時間固定，并按工序加工。在約束條件下安排工件加工順序以優化指標。

具體表述如下：

(21)

凡事都有一個標準，評價調度方案好壞的標準就是是否達到指標，如客戶滿意度指標、完工時間指標、性能指標等。本章選取的指標為最大完工時間，以最大完工時間中的最小值作為優化目標[23]，目標函數如下：

min{maxTi,j},i=1,…,n;j=1,…,m

(22)

maxTi,j為所有工件中最后完成加工的結束時間；min{maxTi,j}為最大完工時間中的最小值。

以流水車間調度問題為模型，公式(21)中的約束如下：

1)一個機器不可同時加工多個工件。

2)每個待加工工件的加工工序是固定的，只有完成了前面工序的加工工作，才可以進行之后工序的加工工作。

3)工件零等待，完成當前工序加工的工件必須要立刻被運輸到下臺機器，準備加工。

4)當前機器沒有需要加工的工件時可以進行等待，直到工件運輸到該機器。

5)工件、機器已知，明確機器上加工工件的時間。

2.2 HFPMCV算法求解流水車間調度問題步驟

HFPMCV算法求解流水車間調度問題的求解步驟如下：

輸入：種群規模popsize、迭代次數iteration、搜索范圍bound、維度vardim

輸出：工件加工最優次序、最小完工時間

步驟1：根據流水車間調度問題，采用基于工件的編碼方式，對于整個種群，將位置向量xi[D]，由公式(8)生成向量xi+1[D],xi+2[D],…,xN[D]，N為種群數，通過公式(9)將xi[D],xi+1[D],xi+2[D],…,xN[D]映射到位置變量的取值空間，獲取最初位置X1[D],X2[D],…,XN[D]，生成n個類似[pn,1,pn,2,…pn,I]的可行解，即采用混沌映射的方式生成一個可以進化的初始種群。

步驟2：根據動態自適應控制策略，計算并依據初始適應度值進行高斯擬合，把整個種群劃分為兩組族群。

步驟3：根據初始適應度值，選出兩族群各自的最優個體，通過比較，選出較優個體作為本代最優個體，即第一代最優加工次序。

步驟4：開始平行進化，FA和PSO分別搜索最優值：PSO加入多尺度協同變異算子，據式(17)更新速度、位置，重新計算適應度值，FA加入多尺度協同變異算子，據式(1)、(2)更新亮度、吸引度，據式(17)更新位置、速度，重新計算適應度值，FA和PSO各自保存本代最優個體。根據式(13)～(15)分別更新兩族群中多尺度協同變異算子的方差，根據變異次數更新閾值。

步驟5：判斷兩者保存的最優值哪一個更優，比較更優個體與上一代最優個體，選出較優者作為本代最優個體，即最優方案。

步驟6：達到最大迭代次數則輸出最優加工次序和相對應的最優加工時間，否則轉步驟4，開始下一次并行迭代。

2.3 HFPMCV算法求解流水車間調度問題復雜度分析

G*O[O(m*D)+2*O(M*D)+O(M)+O(M)

整理后為：

O(G*m*D)+7*O(G*M*D)+2*O(G*M)可近似看作O(G*M*D)，即復雜度與基本算法仍處于一個數量級。

2.4 仿真實驗

2.4.1 實驗準備

在Windows10操作系統下的PyCharm軟件上運行程序，采用python語言編程。種群規模為50，迭代800次，保證幾個算法參數一致，基于工件編碼，選擇TA類車間調度數據集[24]，用20*5、50*5及100*5這3個數據集為基礎，分別選擇每一個數據集下面的一個典型問題，來進行流水車間調度問題的實驗以驗證算法。

2.4.2 實驗結果與分析

為了測試和解釋HFPMCV算法的性能和優越性，分別使用FA、FAPSOMA、HFPMCV對3種不同規模的調度集進行對比實驗，并以最小化最大完工時間為指標，為避免實驗的偶然性，3種算法在對3個不同規模的數據集進行求解的時候，分別運行10次，把10次結果的平均值和最優值作為結果參考指標。實驗結果如表1～3所示。

表1 3種算法在規模為20*5下的輸出結果

表2 3種算法在規模為50*5下的輸出結果

表3 3種算法在規模為100*5下的輸出結果

仿真結果如表3所示，對于同一個規模的數據集，單從最優值來看，例如50*5規模，FA的最優值為2 886，FAPSOMA的最優值為2 837，HFPMCV算法最優值為2 739，即HFPMCV算法可以得到比FA、FAPSOMA算法更佳的完工時間，FAPSOMA算法相比FA算法所得到的完工時間更佳。對于同一規模，單從十次結果的平均值來看，例如100*5規模，HFPMCV算法的平均值為5 507，FAPSOMA的平均值為5 565.9，FA的平均值為5 628.4，HFPMCV算法的平均值小于FA、FAPSOMA算法，FAPSOMA算法相比FA算法得到的平均值更小。綜合兩個指標來看，HFPMCV算法在求解流水車間調度問題方面與FA、FAPSOMA算法相比，性能更優、強度更高、求解結果更加精準。

甘特圖，別名條狀圖，較為簡單、直觀，以圖示的方式來向人們展示工程進度安排，甘特圖上面標識著工件加工順序，每一個工件在每一臺機器上的開始加工時間、結束加工時間，整個優化方案的用時等。通過生成的甘特圖可以直觀的看到算法求解流水車間調度的結果，即生成的最優加工順序以及最小完工時間。

圖3展示了HFPMCV算法求解一次20*5的車間調度問題時所得的甘特圖，X軸表示加工時間，Y軸表示機器號，J代表工件號，st代表工件開始加工時間，ft代表工件結束加工時間，如工件8在第5臺機器上面的開始加工時間為138，結束加工時間為207，加工用時69，所有的工件在第一臺機器上全部加工完成的時間為1 121，所有的工件在第五臺機器上全部加工完成的時間為1 305，從圖中可以看出工件的加工順序為[8,7,16,14,5,13,10,11,1,2,15,12,4,17,3,0,18,9,6,19]，最小完工時間為1 305。

圖3 HFPMCV算法求解車間調度問題的甘特圖

3 結束語

本文針對流水車間調度模型求解問題，并考慮到單種算法對全局最優解的收斂局限性，并且結合前人提出的螢火蟲粒子群混合算法，在螢火蟲粒子群混合算法的基礎上，提出了HFPMCV算法，通過引入多尺度協同變異算子、混沌初始化、動態自適應策略以及平行進化模式，提高了算法的求解速率和精度，函數優化實驗驗證了HFPMCV算法的可行、有效，用HFPMCV、FA、FAPSOMA算法解決以最小化最大完工時限為指標的流水車間調度問題，對比實驗結果顯示HFPMCV算法得到的完工時間均小于FA、FAPSOMA算法，說明了HFPMCV算法速率更快、精度更高，與基本算法相比較，在求解流水車間調度模型時，更具有一定的實用價值。但螢火蟲位置更新公式仍需要優化，以改善算法時間復雜度，獲得更優的求解結果。接下來將著重于研究HFPMCV算法在其他車間調度問題中的應用。