改進(jìn)的布谷鳥算法求解置換流水車間調(diào)度問題

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

（上海理工大學(xué) 管理學(xué)院，上海 200093）

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

0 引言

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

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

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

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

1 相關(guān)問題數(shù)學(xué)描述

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

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

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

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

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

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

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

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

2 求解置換流水車間調(diào)度問題的改進(jìn)布谷鳥算法

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

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

2.3 改進(jìn)后算法流程

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

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

Step3當(dāng)不滿足最大迭代次數(shù)或停止條件，則繼續(xù)；

Step4根據(jù)式（1）選擇更新鳥窩，并保留當(dāng)前最優(yōu)鳥窩；

Step5評估鳥窩適應(yīng)度，若更新后鳥窩適應(yīng)度更優(yōu)，則在更新后鳥窩中產(chǎn)卵，并找出更新后最優(yōu)鳥窩位置；

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

Step7當(dāng)滿足搜索精度e或者達(dá)到最大迭代次數(shù)maximum generation轉(zhuǎn)Step8，否則轉(zhuǎn)Step3，進(jìn)行下一輪搜索；

Step8輸出最優(yōu)值和最終的調(diào)度方案。

3 仿真實例

為測試改進(jìn)后算法（即DECS算法）的優(yōu)化性能，選擇Carlier提出的Car類共8個不同規(guī)模的測試問題對算法進(jìn)行測試，并將測試結(jié)果與選擇同樣算法參數(shù)的標(biāo)準(zhǔn)布谷鳥算法（CS算法）和文獻(xiàn)[11]中的算法（CSO）比較。

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

表1 DECS算法與CS算法尋優(yōu)效果比較

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

表2 本文算法與文獻(xiàn)[11]算法尋優(yōu)效果比較

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

4 結(jié)束語

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

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

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

[3] 盛曉華，葉春明.基于蝙蝠算法的PFSP調(diào)度干擾管理研究[J].計算機工程與應(yīng)用，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]聶慧，劉波，韋向遠(yuǎn),等.一種求解資源受限項目調(diào)度問題的差分進(jìn)化——布谷鳥搜索算法[J].桂林理工大學(xué)學(xué)報，2014,34(2):315-321.

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

[7] 陳樂，龍文.求解工程結(jié)構(gòu)優(yōu)化問題的改進(jìn)布谷鳥搜索算法[J].計算機應(yīng)用研究，2014,31(3):679-683.

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

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

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

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