基于改進的布谷鳥算法求解流水車間調度問題

高楊 云曉燕

摘 ?要：針對基本的布谷鳥算法在求解流水車間調度問題時存在搜索能力差、收斂速度慢的缺點，提出了一種高斯擾動的布谷鳥搜索算法（GCS）。該算法不僅增加了鳥窩移動的活力，還改善了搜索能力差的情況。仿真實驗結果表明，改進的布谷鳥算法在求解流水車間調度問題上具有良好的優化性能，要優于基本的布谷鳥算法。

關鍵詞：流水車間調度問題;高斯擾動;搜索速度

中圖分類號：TP18;TB497 ? ? 文獻標識碼：A 文章編號：2096-4706（2019）13-0018-03

Solving Flow Shop Scheduling Problem Based on Improved Cuckoo Algorithms

GAO Yang，YUN Xiaoyan

（School of Software，Liaoning University of Science and Technology，Anshan ?114051，China）

Abstract：Aiming at the shortcomings of the basic cuckoo algorithm in solving flow shop scheduling problems，such as poor search ability and slow convergence speed，a new cuckoo search algorithm based on Gauss perturbation （GCS） is proposed. This algorithm not only increases the vitality of birds nest movement，but also improves the poor search ability. The simulation results show that the improved cuckoo algorithm has good optimization performance in solving flow shop scheduling problems，and is superior to the basic cuckoo algorithm.

Keywords：flow shop scheduling problem;Gauss perturbation;search speed

0 ?引 ?言

隨著世界各地的經濟與技術的發展，城市整體規模不斷擴大，我國成為制造業大國，產品需求量非常大。因此流水車間調度問題（Flow Shop Scheduling Problem，簡稱為FSSP）在先進制造業中受到了廣泛的關注。

流水車間調度問題在車間生產中是極其常見的問題，也一直被認為是NP-hard問題。在求解流水車間調度問題上不但有通過啟發式來解決的，另外還有通過仿生智能優化方式或群智能算法來解決的。上世紀70年代—90年代，蟻群算法、禁忌算法、遺傳算法、粒子群算法、分布估計算法、螢火蟲算法、貪婪算法[1-8]等一些智能優化算法逐漸被科學家提出并在實際的工程領域內取得了很大的成功。

本文針對流水車間調度的問題，提出了一種改進的布谷鳥算法。該算法與高斯擾動相結合，進而提高了搜索性能，實驗結果表明該算法與基本的布谷鳥算法相比，在求解流水車間調度問題上得到了很好的改良。

1 ?FSSP問題的數學模型

流水車間調度問題是一個加工資源分配的問題，它主要是在滿足某些加工機器、完工時間、資源配置等約束條件下，對車間的任務進行最佳分配。在滿足一定的約束條件下，流水車間調度問題可描述為：一個加工系統中有n個工件要在m臺機器上加工，每個工件包含a道工序，工件的加工順序是一定的，每道工序在不同機器上加工。假設工件i在機器x上的加工時間確定，設加工的時間為tj（i=1，2，…，n;j=1，2，…，n）。該問題的主要目的是n個工件在每臺機器上的加工順序一定時，使得最小化最大完工時間[9]。在上一個假設成立的前提下，流水車間還可描述為：

（1）每個工件在每臺加工機器上的加工順序一定;

（2）每個工件在同一時間時只能在一臺機器上加工;

（3）每臺機器在同一時間時只能加工一個工件;

（4）工件工序的就緒時間與順序無關，且包含在總加工時間內。

令C（ji，k）代表工件ji在機器k上完成工作時所用的時間，每個工件工作的順序為（j1，j2，…，jm），則n個工件在m臺機器上完成工作時所用的時間為：

2 ?基本布谷鳥算法

布谷鳥搜索（Cuckoo Search，CS）算法是由Xin-She Yang和Suash Deb開發的一種新型元啟發式搜索算法，是模擬布谷鳥繁衍后代所提出一種新型群智能優化算法[11]。布谷鳥的繁殖策略就是找到和它們能產出相似的卵的鳥巢并將它們的蛋放入這個鳥巢里，同時避免這個鳥發現，它們也會移走寄主巢中的一個或多個蛋，保持鳥巢內的蛋數目不變，這樣增加了自己蛋的孵化概率。如果寄主發現了該行為，寄主就會扔出外來蛋或是尋找新地方來搭建自己的鳥窩。CS算法就是通過模擬布谷鳥尋找適合孵化自己下一代鳥巢的方式來尋找最優值。為了模擬布谷鳥的繁衍機制，Yang等在文獻中設定了3種理想狀態[11]：

（1）每只布谷鳥一次只產一枚卵，并隨機找到一個鳥窩來孵化;

（2）在隨機選擇的這些窩的過程當中，選擇最好的鳥窩將會保存到下一代;

（3）選擇的鳥窩數量n是一定的，設寄主發現外來卵的概率是Pa，Pa∈[0，1]，倘若寄主發現了鳥窩中有外來的蛋，它們就會放棄自己現有的鳥窩另尋地方搭建自己新窩。

在上文的三個理想狀態基礎上，參考布谷鳥孵化鳥蛋的過程，布谷鳥尋巢的位置更新公式如下：

其中a為步長的大小，并且一般情況下a=1。⊕為點對點乘法。Levy（λ）是隨機搜索的路徑，并且a服從Levy分布。Levy（λ）～u=t-λ，（1<λ≤3）。xi（t）代表第t代鳥窩在第i個鳥窩的位置。隨機產生一個數Ra，Ra與Pa進行數值比較，若Ra>Pa，則對xi（t+1）進行隨機改變鳥巢位置，獲得一組新的鳥巢。否則不變。比較出新鳥窩位置與當前鳥窩位置哪個是最優解，并保留這個最優解。

3 ?求解流水車間的GCS算法思想

GCS算法是在CS算法的基礎上加了個高斯擾動，更加快速地找到了更優的鳥窩位置。若CS算法在第t次循環時找到了一組較優的鳥窩的位置為：xi（t）i=1，2，…，n。而這個GCS算法就是在CS算法執行第t次循環時加入高斯擾動，不讓它執行下一次循環，而是進一步搜尋。設矩陣Pt=[x1（t），x2（t），x3（t），…，xn（t）]T，令Pt為m*n階矩陣。則GCS為Pt′=Pt+a⊕β。其中β為m*n階矩陣，⊕為點對點乘法，因為β的取值范圍比較大，所以設a=1/4來控制β的取值范圍，進而適當地增大了鳥窩移動的活力，經過高斯擾動得到了一個Pt′，讓它與Pt進行比較，得到更優的位置，再繼續進行GCS算法，得到下一個更優的位置Pt″。

4 ?GCS算法具體實施步驟

Step1：初始化參數，隨機產生宿主鳥窩的個數為n，外來蛋發現的概率為Pa，寄生鳥窩的維度為m，初始化鳥窩的位置。

Step2：依照測試函數計算出當前最優鳥窩的位置Xj（0）j ∈{1，2，…，n}和最優值Fmin。

Step3：保留上一代最優鳥窩的位置，并操作Step2對剩余鳥窩的位置進行更新，獲得最新的一組鳥窩位置，并對這組鳥窩進行測試，將最優鳥窩位置與上一代鳥窩位置進行比較，得出一組最優的位置來替代之前的鳥窩位置，令最新的一組鳥窩位置為Kt=[x1（t），x2（t），x3（t），…，xn（t）]T。

Step4：在最新的一組鳥窩位置中，用服從隨機分布的r∈[0，1]與Pa進行比較。若r>Pa，則保留Kt中發現幾率最小的鳥窩位置，并對剩余鳥窩的位置進行隨機改變，獲得一組新的鳥窩位置Pt。

Step5：對Pt加入高斯擾動，又得到一組鳥窩的位置Pt′，與Pt進行比較得出最優的一組鳥窩位置，讓測試值中最好的替換之前的鳥窩位置，令現在最優的一組鳥窩位置為Pt″，并將Pt″賦值給Pt，以便更好地進入下一次循環。

Step6：對Pt連續執行Step4的步驟，在Pt中找到最優的鳥窩位置和最優解為Fmin，并且判斷Fmin是否達到了算法的終止條件，倘若達到，則輸出最優位置和最優值，不然連續執行這個Step3。

5 ?仿真實例

為了進一步測試GCS算法的搜索性能，本文中選用了Benchmarks測試函數集中的Sphere函數、Rastrigin函數進行測試，用于測試GCS算法的函數參數如表1所示。首先設鳥窩數量n=20，維度為10，并且最大迭代次數為4000，若迭代次數大于4000認為尋優失敗。測試函數如下：

6 ?結 ?論

本文的目的是最小化最大完成時間，在基本布谷鳥算法迭代的過程當中對更新后的鳥窩位置加入高斯擾動，擴大了搜索范圍，增加了鳥窩位置變化的多樣性。與基本布谷鳥算法尋優結果比較，得出改良后的布谷鳥算法搜索性能更好，證明了該算法在求解流水車間調度的問題中是有效的。

參考文獻：

[1] 劉延風，劉三陽.多構造蟻群優化求解置換流水車間調度問題 [J].計算機科學，2010，37（1）：222-224.

[2] 屈國強，周永良.蟻群優化結合變鄰域搜索求解NWFS調度問題 [J].計算機工程與應用，2012，48（16）：216-219+248.

[3] 張建萍，張武貞.基于改進的禁忌搜索算法求解車間作業調度問題 [J].信息技術與信息化，2011（3）：77-80.

[4] 姚嫣菲.基于改進遺傳算法的車間作業調度問題研究 [D].杭州：浙江大學，2011.

[5] 王凌，劉波.微粒群優化與調度算法 [M].北京：清華大學出版社，2008：114-137.

[6] 王軒，李元香.分布估計算法在車間調度問題中的應用研究 [D].青島：中國石油大學（華東），2012.

[7] 李永林，葉春明.基于螢火蟲算法的零等待流水線調度優化 [J].機械設計與研究.2013，29（6）：50-54.

[8] Pan Q K，Wang L，Zhao B H . An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion [J].The International Journal of Advanced Manufacturing Technology，2008，38（7-8）：778-786.

[9] 肖輝輝，段艷明.基于差分進化的布谷鳥搜索算法 [J].計算機應用，2014，34（6）：1631-1635+1640.

[10] Yang X S，Deb S . Cuckoo Search via Levy Flights [J].Mathematics，2010：210-214.

作者簡介：高楊（1997-），女，漢族，遼寧朝陽人，本科在讀，研究方向：軟件工程。