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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真實(shí)例

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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

[7] 陳樂(lè)，龍文.求解工程結(jié)構(gòu)優(yōu)化問(wèn)題的改進(jìn)布谷鳥搜索算法[J].計(jì)算機(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)步長(zhǎng)布谷鳥搜索算法[J].計(jì)算機(jī)工程與應(yīng)用，2013,49(10):68-71.

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

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