一種粒子群和改進自適應差分進化混合算法及在生產調度中的應用

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

0 引言

隨著社會的發(fā)展，流水車間調度問題正在引起廣泛的關注。流水車間調度問題是指在一定的時間內，對可用共享資源的分配和生成任務進行合理科學的安排，從而可以在較短時間內獲取較優(yōu)的調度方案。求解流水車間調度問題的方法有很多，如人工智能算法、精確求解方法。其中人工智能算法更適合求解車間調度問題，尤其是差分進化算法和粒子群算法。差分進化算法是可以利用種群個體之間的差異從而逐步進化的一種搜索算法[1]。該算法是R. Storn和K. Price為了求解Chebyshev多項式而提出的[2-3]，而粒子群算法是J. Kennedy和R. C. Eberhart提出的一種進化算法[4]，通過追隨當前搜索到的最優(yōu)值來尋找全局最優(yōu)，并顯示出實際問題的優(yōu)越性。

本文首先介紹了基于自適應變異算子的差分進化算法，并且分析了此算法的缺點，提出一種粒子群算法和改進的自適應差分進化混合算法PSO_FMDE；最后通過實驗分析了該算法的優(yōu)異性能。接著描述了流水車間調度問題的模型，并且通過實驗分析了PSO_FMDE算法求解流水車間調度問題的突出表現。

1 粒子群和改進自適應差分進化混合算法

1.1 粒子群和改進自適應差分進化混合算法

粒子群算法的基本思想是首先初始化種群，計算種群中個體的適應值，然后根據適應值去更新粒子的速度和位置，當前個體通過與種群中最好個體比較跟蹤[5-6]，從而產生新個體。

對于差分進化算法，首先會通過隨機初始化策略把初始種群進行初始化操作，然后隨機選取兩個不同的個體與互不相同的第三個個體通過線性組合的方式產生一個變異后的新個體，再對新個體通過特定的交叉函數得到交叉后的個體，最后將新個體與當前最優(yōu)個體比較，從而選出下一代的最優(yōu)個體。因為標準的差分進化算法變異因子是恒定的，所以在種群初期個體較多進化相對較慢，種群后期個體較少進化相對較快。所以顏學峰等人提出了一種具有自適應變異算子的差分進化算法MDE[7]，根據算法搜索進度自適應的變異算子如下：

(1)

其中:F0為變異算子；Gm為最大進化代數；G為當前進化代數。

該算法在種群進化初期具有較大的變異因子值F=2F0，因此初期個體變化較快，個體多樣；隨著算法的進展變異率逐漸降低，到了算法的后期變異率已經接近于F0，從而避免了最優(yōu)解的破壞，保留了良好的信息，提高了搜索到全局最優(yōu)解的概率。該算法和大多數算法一樣，雖然具有了種群初期進化較快，種群后期進化較慢的特性[8-9]，但是沒有考慮到當代個體的適應值是否向著最優(yōu)個體的適應值逼近，即個體適應值是否朝著最優(yōu)解的方向發(fā)展。假設當代個體經過變異、交叉后, 其適應值并未向著最優(yōu)個體的適應值逼近,偏離了正確的迭代方向，此時恰巧變異算子卻變小了，導致整個子代個體近乎速度放緩，不易快速收斂到全局最優(yōu)值[10-11]。因此本文提出了一種新的自適應差分進化算子FMDE,其中變異算子F的定義為：

(2)

式中,fi(pre)代表上一代個體的函數值，f(min)代表當代的目標函數最優(yōu)值，fi(suf)代表當代個體的函數值。如果當代個體適應值與當代最優(yōu)值的差的絕對值比上一代個體適應值與最優(yōu)值的差的絕對值要小，說明當代的此個體偏離了最優(yōu)值的進化方向，這時采用適當增加變異算子F，稍微加快進化速度，但又考慮到變異算子的取值范圍，所以采取添加一個單調遞減的指數函數的策略[12]。

粒子群算法在優(yōu)化求解過程中早起具有較快的收斂速度，在后期容易陷入局部最優(yōu)，難以獲得全局最優(yōu)解。種群差分進化算法會從當前最優(yōu)個體和經過變異、交叉后產生的新個體中選擇一個較優(yōu)個體作為當前最優(yōu)個體。只有當適應值優(yōu)于父代個體使才選為子代，否則父代直接進入下一代，該機制增加了算法的收斂速度。但該算法有陷入局部最優(yōu)解的缺點，并且粒子群算法和該算法有一定的相似度，因此本文考慮將兩種算法結合，首先讓兩種算法分別迭代，接著為了避免混合算法的迭代后期出現停滯現象，引入一種隨機跳出機制，通過一個隨機函數使出現停滯現象的個體變成一個新個體，這樣就跳出了局部最優(yōu)，實現如下：

(3)

其中:M表示可以允許停滯的最大迭代次數，(Xmin,Xmax)是可以允許的搜索范圍。

因此，本文提出的混合算法PSO_FMDE實現步驟如下:

算法 PSO_FMDE算法

輸入：基本的輸入參數，包括R1、R2、c1、c2、vmax、itermax、F0、Gm、G等

輸出：最優(yōu)個體最優(yōu)值

1)對兩個種群POPPSO和POPFMDE進行隨機初始化，而且位于不同區(qū)域。

2)開始迭代，根據公式(1)～(3)對POPPSO種群中所有個體進行位置和速度更新；

3)利用改進的自適應差分進化算法FMDE對種群中所有個體執(zhí)行變異、交叉、選擇操作。

4)分別選擇當前迭代中，POPPSO種群以及POPFMDE種群中的最佳個體。

5)選擇兩個種群中較優(yōu)的個體，并判斷個體是否出現停滯現象，陷入局部最優(yōu)，如果陷入局部最優(yōu)，則執(zhí)行步驟6)，否則執(zhí)行步驟7)；

6)根據公式(6)更新個體位置，然后重復計算每個種群中個體適應值，選擇較優(yōu)的個體；

7)判斷當前是否達到最大迭代次數或者全局最優(yōu)位置滿足最小界限，如果滿足退出條件，輸出最終結果并退出，否則返回步驟2)；

步驟5中判斷當前的結果陷入局部最優(yōu)，出現停滯現象的方法如下：

(4)

1.2 函數優(yōu)化測試

為了測試和解釋PSO_FMDE算法在求解全局最優(yōu)問題的性能和優(yōu)越性，將該算法分別與MDE、FMDE進行了對比，然后對以下的數學優(yōu)化問題進行尋優(yōu)[13]。

-5.12≤xi≤5.12,i=1,2,…,10

(5)

優(yōu)化問題的目標函數在10維可行域內有210-1個局部最優(yōu)解，差分進化算法可以求解這一問題。為了保證實驗的有效性，3種算法的參數盡可能一致，其中種群大小為Np=100，最大進化代數是800。交叉參數CR=0.1，加速常數C1=0.1，C2=0.2慣性權重參數w=0.9,允許的最大停滯次數numpause=10等。

為了研究變異因子對算法的性能影響，變異因子F分別取值0.1,0.5,0.7,1.5,2。圖1、圖2、圖3分別展示了MDE、FMDE、PSO_FMDE三種算法在不同的變異率情況下，最優(yōu)值與迭代次數的關系。圖x軸代表迭代的次數，y軸代表最優(yōu)值。

圖2 FMDE算法變異參數實驗

圖3 PSO_FMDE算法變異參數實驗

圖4 3種算法的性能比較

從三幅圖可以看出隨著變異參數的增加，會需要更多的迭代次數才能達到最終的全局最優(yōu)解(即進化結束)，比如F=0.1時只需要100次迭代就能進化完成，F=0.7時需要大約250次能完成進化，但是F=2時會需要將近450次才能完成進化，性能逐漸減小。同時也能看出，在固定的迭代次數時，變異率越小，最優(yōu)解的值就更靠近全局最優(yōu)解。

圖4展示了不同算法在相同變異因子下的性能，此時itermax=1000，F=1.5,通過結果可以看出，在迭代初期(前200次迭代), PSO_FMDE算法能夠更快地靠近全局最優(yōu)解0，其次是FMDE算法。當迭代次數固定時，PSO_FMDE算法到MDE算法靠近全局最優(yōu)解地速度依次降低，也就是說從PSO_FMDE算法到MDE算法的性能逐漸下降，表明PSO_FMDE算法使群體的平均適應度和最優(yōu)適應度和其他算法相比都有適當的提高。

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

2.1 流水車間調度問題模型

問題描述：如果要在m臺機器上利用n個工件進行流水加工，每個工件需要經過m道工序，每個工件在每臺機器上只加工一次，每臺機器在某一時刻只能加工一個工件，而且各個工件在機器上所需要的加工時間和準備時間已知，且各個工序都有相應的約束條件，以使工件完工時間最小。

令cik代表工件i在設備k上的完成時間。tik代表工件i在設備k上的加工時間，且cik>0，i,j=1,2,…,n，k=1,2,…,m。該流水車間調度問題的目標函數為：

(6)

約束條件為：

1)設備h先于設備k加工工件i：cik-tik≥cih;

2)工件i先于工件j在設備k上加工：cjk-tjk≥cjh。

2.2 PSO_FMDE求解流水車間調度問題的步驟

差分進化算法求解流水車間調度問題和遺傳算法求解車間調度問題類似[14-15]，主要分為以下幾個步驟：

1)設置差分進化算法的參數，包括最大迭代次數、變異因子等。

2)根據流水車間調度問題，隨機初始化兩個種群。

3)根據交叉變異或者速度位置更新得到臨時種群，對臨時種群進行評價。

4)選擇較優(yōu)個體，并判斷是否陷入局部最優(yōu)，如果是則求解公式(3)。

5)并判斷滿足終止迭代條件。如果滿足，根據最優(yōu)個體得到流水車間調度問題的最佳調度方案；否則進行進化操作，轉步驟3)。

2.3 仿真實驗

采用標準TA類[16]車間調度問題進行實驗測試,設置粒子群算法和改進自適應差分進化的混合算法的種群規(guī)模是40，最大進化次數是800。數據集分別選擇20工件5機器、50工件5機器以及100工件5機器，在上述3個數據集上進行流水車間調度問題的實驗。實驗采用Pascal語言編程實現流水車間調度優(yōu)化算法。

3種算法MDE、FMDE、PSO_FMDE分別對3種不同規(guī)模的數據最進行makespan目標最小化，比較幾種算法的性能。在測試實驗過程中，為了實驗結果科學及更具說服力，3種算法分別運行10次，然后分析10次結果的最優(yōu)值(makespan)和平均值，幾種不同規(guī)模數據的優(yōu)化結果如表1所示。

表1 不同規(guī)模的不同算法的最優(yōu)值

圖5 20*5 PSO_FMDE算法的最優(yōu)調度方案

對于同一個數據規(guī)模單從最優(yōu)值來看，PSO_FMDE算法比其他算法的最優(yōu)值更理想。為了進一步分析算法性能，將算法平均值(Avg)的差作為評價指標。在3種不同規(guī)模的數據集(20*5、50*5、100*5)下，PSO_FMDE算法的平均值與FMDE、MDE算法的平均值差值分別是72.1、108.7、121.1。從差值可以看出，在相同機器數量時，隨著工件數的增加PSO_FMDE算法較其他算法的優(yōu)化強度也隨之增加，說明PSO_FMDE算法隨著數據規(guī)模越大就會越有效。因此，PSO_FMDE算法有著較好的有效性以及穩(wěn)定性。

圖5給出了使用PSO_FMDE算法對規(guī)模為20*5的調度集進行優(yōu)化時得到的第一次計算結果的甘特圖。

3 結語

考慮到粒子群算法和改進的自適應差分進化算法的異同，將兩種算法進行結合，提出了基于粒子群和改進的自適應差分進化的混合算法。因為進化過程中可能會出現局部最優(yōu)的問題，因此本文采用隨機個體替換停滯個體的方法，以便快速跳出局部最優(yōu)解區(qū)域。通過多種算法的性能對比，較單一算法相比，該有更優(yōu)更靠近最優(yōu)解的優(yōu)勢，具有一定的實用價值。為了用PSO_FMDE算法求解流水車間調度問題，將最小化最大完成時間作為調度方案的最優(yōu)評價指標，因為該算法加快了全局搜索速度和跳出局部最優(yōu)解的進度，所以具有一定的實踐意義。