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

徐楊麗，葉春明 XU Yang-li,YE Chun-ming

（上海理工大學 管理學院，上海 200093）

(College of Management,University of Shanghai for Science and Technology,Shanghai 200093,China)

0 引言

置換流水車間調度問題（Permutation Flow-shop Scheduling Problem，PFSP）是組合優化問題的簡單模型，是流水車間調度問題當工件在機器上加工順序一定時的特殊模式，具有很強的工程代表性。對該問題求解質量、求解速度的研究關系到企業生產資源集約化、生產效率高速化和生產過程機械化的實現。PFSP問題可描述為n工件要在m臺機器上加工，每個工件在每臺機器上的加工時間已知，且每個工件在每臺機器上的加工順序一定，工件加工順序相同。同時規定每個工件同一時間只能被一臺機器加工，每臺機器同一時間也只能加工一個工件，工件在機器上加工不間斷。PFSP問題的目的是求出最優的工件加工順序，使總流程完工時間最短。

國內外許多學者對該問題進行了研究，并對其求解算法不斷進行優化。已知的優化算法如精確算法（分枝定界法、動態規劃法、整數規劃法等）對求解小規模調度問題能尋得問題精確解；啟發式算法（Johnson法、Palmer法、Gupta法、NEH法等）能快速建立問題的解，但算法的優化質量差，算法設計復雜，收斂速度慢，難以滿足工程需要。智能優化算法（如遺傳算法、果蠅算法、蝙蝠算法等[1-3]）是新的啟發式算法，是模仿自然界“優勝劣汰，適者生存”規則發展而成的，在問題優化求解方面表現出高度有效性。

布谷鳥算法（Cuckoo Search，CS）是2009年由劍橋大學Xin-SheYang和S.Deb提出的一種新興啟發式智能算法[4]，該算法選用參數少，全局搜索能力強，編程易實現，目前已被廣泛應用于項目調度、函數優化、工程結構優化、整數規劃等[5-8]許多領域。已有文獻中布谷鳥算法主要用來求解連續問題，對離散組合優化生產調度問題應用較少。針對布谷鳥算法求解精度較低，后期收斂速度慢，容易陷入局部最優解等問題，目前許多學者對其進行了改進，如鄭洪清等[9]通過調整布谷鳥現有鳥窩位置和最佳鳥窩位置之間的距離以調整布谷鳥搜索步長，屈遲文等[10]在原始布谷鳥算法上引入非均勻變異算子對鳥窩位置進行變異，并對陷入局部最優的鳥窩位置用高斯變異算子進行調整，仿真實驗均取得了較好的效果。

本文引入差分進化算子改進原始布谷鳥算法被發現鳥窩位置，并將其應用到PFSP問題求解，以求在不斷更新、保持種群多樣性的同時，提高算法的求解精度，避免陷入局部最優。通過與原始布谷鳥算法和貓群算法（Cat Swarm Optimization，CSO）[11]求解結果的比較，證明改進后的布谷鳥算法優化效果顯著。

1 相關問題數學描述

1.1 布谷鳥算法數學描述。布谷鳥算法是模擬布谷鳥為尋找合適產卵的鳥窩而隨機游走的尋窩過程。布谷鳥是自然界少有的通過寄生而不是自己孵化產卵繁殖后代的鳥類，為了提高繁殖率，布谷鳥在選擇宿主鳥窩時需要選擇跟自己的卵形相似，卵的顏色、孵化周期一樣的鳥窩。即使如此也存在被宿主發現寄生卵的可能性。若寄生卵被發現，則在下一次選擇宿主鳥窩時就要放棄該鳥窩，重新選擇。為了更好地實現算法的優化性能，假設布谷鳥種群可利用的宿主鳥窩數量固定，且宿主發現外來蛋的概率固定。布谷鳥每一次隨機選擇一個宿主鳥窩孵化所產的一個卵，布谷鳥種群在隨機選擇的一組寄生卵鳥窩中，具有最優位置的寄生卵鳥窩將會保留到下一代。

在布谷鳥算法中，每個宿主鳥窩原有的卵表示一個候選解，每個新入住的布谷鳥的卵表示一個新的解。依據上述假設可將布谷鳥尋窩的路徑和位置更新公式如下：

1.2 差分進化算法數學描述。差分進化算法與遺傳算法、粒子群算法一樣是一種基于群體智能理論的隨機并行搜索優化算法，由Storn R和Price K于1995年提出，并且在1996年舉行的第一屆國際IEEE進化優化競賽中，被證明是速度最快的進化計算。算法主要通過變異操作、交叉操作、選擇操作實現對群體和個體更新。算法為保持在搜索方向和搜索步長上的自適應性[4]，將種群中任意兩個個體的差分向量加權后，根據一定的規則加到第三個個體上，作為第三個個體的擾動向量。在進化早期，因為種群中個體的差異性較大使得擾動量較大，從而使得算法能夠在較大范圍內搜索，具有較強的勘探能力；而到了進化后期，當算法趨向于收斂時，種群中個體的差異性小，算法在個體附近搜索，這使得算法具有較強的局部開采能力。這里主要介紹算法的變異算子、交叉算子和選擇算子。

（1）差分變異算子。常見的差分方法有四種：隨機向量差分法（DE/rand/1）、最優解加隨機向量差分法（DE/best/1）、最優解加多個隨機向量差分法（DE/best/2）、最優解與隨機向量差分法（DE/rand-best/1）。本文為保持種群的多樣性，采用隨機向量差分法，其變異公式描述如下：為需要變異的個體，在當前種群隨機選擇兩個個體則產生變異個體表達式如式（3） 所示：

其中，F為放大因子，是差分向量的加權值，一般F∈［0,2］，i、j、k為互不相同的三個個體。經過變異后的個體X（ t+1）即保留了父代Xi（t）的部分信息，又借鑒了個體Xj（t）、Xk（t）的信息又實現了個體間信息的傳遞。

（2）交叉算子。差分進化算法的交叉算子是依據交叉概率Pc使得父代個體和由他經過差分變異操作產生的新個體之中的部分基因位進行交換，從而生成新個體，具體規則如下所示：i

（3）貪婪選擇算子。貪婪選擇操作是通過比較經過變異、交叉操作后得到的子代個體與原向量適應度值，只有當子代個體適應度優于原向量時，才會被選取成為下一代的父代，否則原向量將直接進入下一代。貪婪選擇算子如式（5）所示規則生成：

其中，Ui（t）表示經過變異、交叉后生成的新個體，Xi（t）表示原始個體，DECS_fitness（）表示計算適應度值函數。

2 求解置換流水車間調度問題的改進布谷鳥算法

2.1 改進后算法思想。布谷鳥采用萊維飛行更新步長和路徑后，考率后期尋優過程中由于種群多樣性缺乏而造成的尋優速度慢，收斂精度不高問題，改進后在每一代的尋優過程中引入差分進化算子，對被發現的鳥窩進行隨機擾動，選擇三個未被發現的鳥窩進行變異、交叉、選擇操作，生成新的子代個體，若新的子代個體適應度優于父代個體則保留，否則拋棄新的子代個體，使用父代個體之間進入下一代循環。

2.2 編解碼方法。本文采用基于最大位置法的編碼方法，即一個布谷鳥表示一個加工序列，但具有最大值的位置將被首先加工的編碼方法。如一個布谷鳥的各維度值為 （-2.1680,1.7131,17.8920,13.8472,-6.7494,15.1746 ）則其對應的加工順序為（3,6,4,2,1,5），即首先應該加工第三個工件，其次加工第六個工件，然后加工第四個工件，再依次加工第二個工件，第一個工件和第五個工件，一個維數為一道工序。

2.3 改進后算法流程

Step1初始化算法基本參數，布谷鳥選擇宿主鳥窩數目N，發現概率Pa，差分進化操作的縮放因子F，交叉概率CR，最大迭代次數maximum generation或搜索精度e；

Step2布谷鳥隨機選擇鳥窩位置xi（ i=1,2,…,N ），基于最大位置法的編碼規則將鳥窩位置轉換為工序排列，根據各鳥窩位置評估各鳥窩的適應度，在初始鳥窩中找出最優鳥窩Xbest；

Step3當不滿足最大迭代次數或停止條件，則繼續；

Step4根據式（1）選擇更新鳥窩，并保留當前最優鳥窩；

Step5評估鳥窩適應度，若更新后鳥窩適應度更優，則在更新后鳥窩中產卵，并找出更新后最優鳥窩位置；

Step6產生隨機數r，若r>Pa，則通過差分進化算法的變異、交叉、選擇操作來重建被宿主拋棄的鳥窩，否則，接受更新位置后的鳥窩；

Step7當滿足搜索精度e或者達到最大迭代次數maximum generation轉Step8，否則轉Step3，進行下一輪搜索；

Step8輸出最優值和最終的調度方案。

3 仿真實例

為測試改進后算法（即DECS算法）的優化性能，選擇Carlier提出的Car類共8個不同規模的測試問題對算法進行測試，并將測試結果與選擇同樣算法參數的標準布谷鳥算法（CS算法）和文獻[11]中的算法（CSO）比較。

實驗仿真環境為Windows 7操作系統，處理器主頻1.87GHZ，CPU為Intel（R） Core（TM） i3-350M和內存2G，采用MATLAB R2012a實現算法編程。算法參數設置為：初始種群規模Popsize=25，最大迭代次數N_iterTotal=100，步長控制因子a=0.5，發現概率Pa=0.25，變異概率F=0.8，交叉概率PC=0.5，算法獨立運行30次。表1為改進后的布谷鳥算法（即DECS算法）與標準布谷鳥算法（即CS算法）獨立運行20次的尋優效果對比。其中Max表示20尋優過程中出現的最大值，Min表示20次尋優過程中出現的最小值，Avg表示20次尋優的平均值，BNO表示20次尋優最優解最早出現代數，C*表示求解問題已知最優解。為測試算法的優化性能，將本文算法獨立運行20次并與文獻[11]算法的尋優效果比較，表2為兩個算法尋優結果對比，其中WRE為算法尋得最差結果相對已知最優解C*的百分比，ARE為平均值相對C*的百分比，BRE為最優結果相對C*的百分比。圖1為兩算法BRE比較結果圖。

表1 DECS算法與CS算法尋優效果比較

從表1可以看出，在求解8個規模的不同問題時，改進的布谷鳥算法和原始布谷鳥算法的Min值均與已知最優解C*相同，說明兩個算法均能求得問題最優解。比較兩個算法的Max值和Avg值可知，在求解Car1、Car2、Car4、Car7和Car8問題時，兩個算法也都表現出極好的優化性能。對于Car3、Car5問題兩個算法表現良好，雖能求得算法最優解，但不是每次運行都取得良好的效果，尤其是原始布谷鳥算法，所求得近似解遠遠大于改進后的布谷鳥算法所求得近似解。對于Car6問題，改進后的布谷鳥算法Max值、Min值和Avg值相等且均等于C*值，說明該算法每次都能尋得問題最優解，但原始布谷鳥算法只能求得問題近似解。改進后的布谷鳥算法的BNO值均小于原始布谷鳥算法的BNO值，顯示出改進后的布谷鳥算法能更快地向全局最優解收斂，說明其具有更優異的種群多樣性。

表2 本文算法與文獻[11]算法尋優效果比較

表2本文算法與文獻[11]算法BRE值均為0顯示兩算法均能求得問題最優解，均具有很好的優化性能，圖1顯示出本文算法最差誤差百分比在尋求每一個問題時都比文獻[11]算法小，尤其是求解Car2和Car4問題時，本文算法與文獻[11]算法差距很大，對Car5問題求解差距最小。說明本文算法求解能力更強，尋優性能更好，魯棒性更高。

4 結束語

本文以最小化最大完工時間為目標，改進原始布谷鳥算法，在保持布谷鳥算法強全局尋優能力的基礎上引入差分進化算子，促進被發現鳥窩中候選解與未被發現候選解之間的信息交互，以增加種群多樣性。通過與原始布谷鳥算法和文獻[11]算法處理Car類問題尋優結果比較，顯示改進后的布谷鳥算法求解優化效果明顯，證明該算法求解置換流水車間調度問題是可行和有效的。但是改進后的布谷鳥算法依然有局限性，如變異概率和交叉概率的選擇，步長因子控制及其與進化代數的關系等，及其影響算法的收斂速度和收斂精度，這些問題是進一步需要研究的內容。

[1] 李小繽，白焰，耿林霄.求解置換流水車間調度問題的改進遺傳算法[J].計算機應用，2013,33(12):3576-3579.

[2] 鄭曉龍，王凌，王圣堯,等.求解置換流水線調度問題的混合離散果蠅算法[J].控制理論與應用，2014,31(2):159-164.

[3] 盛曉華，葉春明.基于蝙蝠算法的PFSP調度干擾管理研究[J].計算機工程與應用，2014,50(8):241-246.

[4] Xin-She YANG,Suash Deb.Cuckoo search via Lévy flights[C]//Proc of World Congress on Nature and Biologically Inspired Computing[S.I]:IEEE Press,2009:210-214.

[5]聶慧，劉波，韋向遠,等.一種求解資源受限項目調度問題的差分進化——布谷鳥搜索算法[J].桂林理工大學學報，2014,34(2):315-321.

[6] 胡欣欣.求解函數優化問題的改進布谷鳥搜索算法[J].計算機工程與設計，2013,34(10):3639-3642.

[7] 陳樂，龍文.求解工程結構優化問題的改進布谷鳥搜索算法[J].計算機應用研究，2014,31(3):679-683.

[8] 吳炅，周健勇.整數規劃的布谷鳥算法[J].數學理論與應用，2013,33(3):99-106.

[9] 鄭洪清，周永權.一種自適應步長布谷鳥搜索算法[J].計算機工程與應用，2013,49(10):68-71.

[10]屈遲文，傅彥銘.基于混合變異算子的布谷鳥優化算法[J].科學技術與工程，2013,13(27):8008-8013.

[11]馬邦雄，葉春明.利用貓群算法求解流水車間調度問題[J].現代制造工程，2014(6):12-15,71.