布谷鳥算法在置換流水車間調(diào)度中的應(yīng)用

布谷鳥算法在置換流水車間調(diào)度中的應(yīng)用

置換流場(chǎng)績(jī)效交換問題（pfsp）是在基于流場(chǎng)績(jī)效交換問題的限制下形成的生產(chǎn)計(jì)劃的問題。在對(duì)pfsp的規(guī)劃優(yōu)化方面，可以有效提高公司的生產(chǎn)效率。然而，garo等人證實(shí)，機(jī)器數(shù)量超過等于3的pfsp是一個(gè)完全問題，沒有計(jì)算復(fù)雜的多因素優(yōu)化算法。因此，pfsp的研究和設(shè)計(jì)具有重要的實(shí)際意義和技術(shù)價(jià)值。從現(xiàn)有文獻(xiàn)來看，pfsp的算法主要包括經(jīng)典算法、結(jié)構(gòu)式算法和智能優(yōu)化算法。在此基礎(chǔ)算法（如分支邊界法、動(dòng)態(tài)規(guī)劃法等）的幫助下，可以獲得問題的精確解，但問題的大小和計(jì)算復(fù)雜性受到限制。結(jié)構(gòu)復(fù)雜，通常的解質(zhì)量較差。主要用于解決兩個(gè)機(jī)器和三個(gè)機(jī)器的pfsp。智能優(yōu)化算法（如遺傳算法、蟻群算法、粒子群算法、蜂群算法和各種混合算法等）可以快速構(gòu)建問題的布局解，結(jié)構(gòu)復(fù)雜，普通結(jié)構(gòu)差。主要用于解決各種生產(chǎn)計(jì)劃問題。如cowep算法等。此外，通過對(duì)鄰居區(qū)域的不斷搜索和不斷改進(jìn)，我們可以獲得最優(yōu)解或滿意的解，并在很短的時(shí)間內(nèi)實(shí)現(xiàn)良好的優(yōu)化效果，這可以達(dá)到良好的優(yōu)化效果。根據(jù)之前的結(jié)果計(jì)算，該算法的算法簡(jiǎn)單，調(diào)幅參數(shù)少，收斂速度快?，F(xiàn)在，它只能在優(yōu)化領(lǐng)域應(yīng)用，并且還在研究組合優(yōu)化領(lǐng)域的性質(zhì)和應(yīng)用?；诓脊萨B算法的優(yōu)化機(jī)制和特點(diǎn)，本文提出了布谷鳥算法的結(jié)構(gòu)特點(diǎn)。在這項(xiàng)工作中，我們使用該算法來解決變換流場(chǎng)的配置問題，并評(píng)估組合優(yōu)化領(lǐng)域的優(yōu)化性能。模擬實(shí)驗(yàn)表明，該算法在分散空間中也具有良好的開發(fā)機(jī)制，有利于擴(kuò)大其他組合優(yōu)化問題的求解。1最大工商工藝時(shí)間的遞歸方程如果考核的調(diào)度指標(biāo)為最大完工時(shí)間,此類PFSP用調(diào)度三元法可表示為FmprmuCmax,其中,Fm為m臺(tái)機(jī)器的流水車間調(diào)度;prmu表明所有工件在任一臺(tái)機(jī)器上的加工順序均相同;Cmax為最大完工時(shí)間.數(shù)學(xué)描述為:令tjk,i表示工件jk在機(jī)器i上的加工時(shí)間(假設(shè)各工件的加工準(zhǔn)備時(shí)間已包含在加工時(shí)間內(nèi)),Cjk,i表示工件jk在機(jī)器i上的完工時(shí)間,π∈{Ω|(j1,j2,…,jn)},Ω為所有排序的集合,加工過程滿足不可中斷約束、機(jī)器唯一性約束和工件唯一性約束,假設(shè)各工件按照機(jī)器1到m的順序進(jìn)行加工,則工件在各機(jī)器上的完工時(shí)間可以通過遞歸方程計(jì)算其中,式(1)~式(3)為計(jì)算完工時(shí)間的遞歸方程,式(4)為最大完工時(shí)間,式(5)為最小化最大完工時(shí)間所對(duì)應(yīng)的調(diào)度方案,n表示工件數(shù).2布谷鳥算法的優(yōu)化機(jī)制2.1布谷鳥的仿生方法布谷鳥是典型的巢寄生鳥類,其巢寄生行為表現(xiàn)在:a.布谷鳥自己不筑巢也不孵卵,將卵寄生在宿主的鳥巢里,讓其替自己孵化養(yǎng)育;b.布谷鳥在繁殖期尋找與孵化期和育雛期相似、雛鳥食性基本相同、卵形與顏色易仿的宿主;c.寄生時(shí)間上,布谷鳥多在宿主開始孵卵之前,乘宿主離巢外出時(shí)快速寄生產(chǎn)卵.宿主如果發(fā)現(xiàn)巢中的卵不是自己所產(chǎn),會(huì)將“外來者”扔出或者棄巢另建新窩.因此,布谷鳥后代只能以一定概率得以孵化存活,概率大小取決于所選寄生鳥巢的狀況.如果所選寄生宿主的卵形與顏色相近、孵化期和育雛期相似、雛鳥食性基本相同,則后代被孵化并得以存活的可能性就大些;反之,就小一些.布谷鳥算法是模擬自然界中布谷鳥寄生孵育雛鳥的生物行為構(gòu)造出的隨機(jī)搜索算法,體現(xiàn)了自然的擇優(yōu)機(jī)制.其仿生原理是:將布谷鳥所選宿主鳥巢映射為搜索空間中的點(diǎn),將搜索和優(yōu)化過程模擬成布谷鳥搜尋和選擇鳥巢的過程,用宿主鳥巢所處位置的優(yōu)劣來代表孵育環(huán)境的好壞,進(jìn)而代表待求解問題的適應(yīng)度.將宿主鳥巢的擇優(yōu)過程類比為搜索和優(yōu)化過程中用好的可行解取代較差可行解的迭代過程.和真實(shí)的寄生孵育行為相比,算法中做了一些假設(shè):假設(shè)宿主鳥巢的數(shù)量是固定的,并且布谷鳥在一巢只產(chǎn)一卵;宿主鳥巢位置越好,布谷鳥后代孵化存活的幾率越大.2.2利維分布的隨機(jī)搜索向量布谷鳥寄生孵育雛鳥的生物行為可以用如下過程進(jìn)行模擬:定義1布谷鳥選擇宿主鳥巢的位置更新式為式中,xit為布谷鳥在第t次搜尋中所選的第i個(gè)鳥巢的空間位置;α為步長(zhǎng)因子;Lévy(λ)是服從參數(shù)為λ(1<λ≤3)的利維分布的隨機(jī)搜索向量;ue067表示某種運(yùn)算,如矩陣運(yùn)算或邏輯運(yùn)算等.定義2宿主發(fā)現(xiàn)“外來者”的概率為Pa,Pa大則布谷鳥后代孵化存活的概率小,反之則大.算法實(shí)現(xiàn)優(yōu)化的過程是:布谷鳥首先在解空間內(nèi)隨機(jī)選擇一定數(shù)量的鳥巢并產(chǎn)卵,評(píng)估鳥巢優(yōu)劣,找出當(dāng)前最好的鳥巢,然后按照式(6)選擇新的鳥巢產(chǎn)卵(保留當(dāng)前最好鳥巢).宿主若發(fā)現(xiàn)(概率為Pa)自己鳥巢中有“外來者”則放棄該鳥巢另建新巢,否則就接受更新位置后的鳥巢.布谷鳥對(duì)更新后的鳥巢進(jìn)行評(píng)估,找出最佳鳥巢,若更優(yōu),則在當(dāng)前最佳鳥巢中產(chǎn)卵.這樣通過多次搜索和選擇后,布谷鳥可以找到最好的鳥巢(最優(yōu)位置),從而保證后代得以孵化存活.3置換流場(chǎng)規(guī)劃問題的解決3.1布谷鳥隨機(jī)應(yīng)變運(yùn)動(dòng)學(xué)PFSP屬于典型的組合優(yōu)化問題,應(yīng)用布谷鳥算法求解PFSP首先需要構(gòu)造合理的編碼方式來表示調(diào)度問題的解.針對(duì)PFSP的特性,本文采用基于最小位置值規(guī)則的隨機(jī)鍵編碼方式,將布谷鳥選擇宿主鳥巢的一個(gè)連續(xù)位置向量Xi=[xi,1,xi,2,…,xi,n]轉(zhuǎn)換為機(jī)器上一個(gè)工件的加工順序π=(j1,j2,…,jn),從而可以計(jì)算鳥巢位置所對(duì)應(yīng)調(diào)度解的適應(yīng)度值.這種編碼方式,保證了Xi→π得到的調(diào)度解均是可行解,同時(shí)無需修改布谷鳥算法的進(jìn)化操作.3.2最佳鳥巢條件確定綜上所述,求解置換流水車間調(diào)度問題的布谷鳥算法流程如下:a.初始化算法基本參數(shù),布谷鳥選擇宿主鳥巢數(shù)目m,發(fā)現(xiàn)概率Pa,步長(zhǎng)因子α,搜索精度ε或最大搜索次數(shù)maxT;b.布谷鳥隨機(jī)選擇鳥巢位置xi(i=1,…,m),按照編碼方式轉(zhuǎn)換為工件加工順序,計(jì)算各鳥巢適應(yīng)度,找出當(dāng)中前最佳鳥巢位置x*;c.根據(jù)式(6)更新鳥巢的空間位置xi;d.產(chǎn)生隨機(jī)數(shù)rand1,若rand1>Pa,宿主放棄自己的鳥巢另建新巢,否則接受更新位置后的鳥巢;e.對(duì)全部鳥巢進(jìn)行評(píng)估,找出當(dāng)前最佳鳥巢及所處位置,若優(yōu)于以往最佳鳥巢則替換;f.當(dāng)滿足搜索精度或達(dá)到最大搜索次數(shù)轉(zhuǎn)g,否則轉(zhuǎn)c,進(jìn)行下一輪搜索;g.輸出最優(yōu)值和對(duì)應(yīng)調(diào)度方案.4算法性能測(cè)試為了驗(yàn)證布谷鳥算法求解PFSP的性能,對(duì)算法沒有采用任何改進(jìn)策略,完全依靠算法自身進(jìn)化機(jī)制來尋優(yōu).選擇Car類基準(zhǔn)測(cè)試問題進(jìn)行仿真測(cè)試,并與螢火蟲算法(fireflyalgorithm,FA)、粒子群算法(particleswarmoptimization,PSO)在離散空間的優(yōu)化性能進(jìn)行對(duì)比.仿真環(huán)境:WindowsXP操作系統(tǒng),MATLABR2010a編譯軟件,處理器主頻2.4GHz,內(nèi)存2GB.算法參數(shù)設(shè)置為布谷鳥算法:發(fā)現(xiàn)概率Pa=0.75,步長(zhǎng)因子α=1.0.螢火蟲算法:光強(qiáng)吸收系數(shù)γ=1.0,最大吸引度β0=1.0,步長(zhǎng)因子α=0.2.粒子群算法:采用線性減少的慣性權(quán)重Wmax=0.9,Wmin=0.4.學(xué)習(xí)因子:C1=C2=1.4962.這3種算法中群體數(shù)m=25,最大搜索次數(shù)maxT=500,每種算法獨(dú)立運(yùn)行10次,p代表測(cè)試問題類型,C*表示對(duì)應(yīng)調(diào)度問題的最小化完工時(shí)間,測(cè)試結(jié)果如表1所示.為對(duì)比算法的性能,采用了尋優(yōu)成功率(successrate,SR)、最優(yōu)相對(duì)誤差(bestrelativeerror,BRE)、平均相對(duì)誤差(averagerelativeerror,ARE)、最差相對(duì)誤差(worstrelativeerror,WRE)4項(xiàng)指標(biāo)進(jìn)行衡量.從測(cè)試結(jié)果可以看出,對(duì)于上述測(cè)試問題,CS均能找到已知下界值而且尋優(yōu)成功率高于對(duì)應(yīng)的FA和PSO算法,反映出CS具有良好的全局收斂性.從ARE和BRE指標(biāo)來看,CS所求得調(diào)度解的質(zhì)量遠(yuǎn)高于FA和PSO算法,顯示出CS在離散空間具有優(yōu)良的進(jìn)化機(jī)制,而且CS求得ARE和BRE的值很小,表明CS算法對(duì)初始值具有較強(qiáng)的魯棒性.從測(cè)試尋優(yōu)曲線可以直觀看出,對(duì)于Car3、Car5問題,FA與PSO均出現(xiàn)了早熟收斂,而CS收斂速度和收斂精度均高于對(duì)比算法,限于篇幅,只列出了有代表性的兩幅圖(如圖1和圖2所示).5優(yōu)化機(jī)制的驗(yàn)證