改進(jìn)粒子群算法在作業(yè)車間調(diào)度問題中的應(yīng)用

1、2009年1月第32卷第1期四川師范大學(xué)學(xué)報(bào)(自然科學(xué)版Journal of Sichuan Nor mal University (Natural Science Jan .,2009Vol .32,No .1收稿日期:2007-09-25基金項(xiàng)目:國家自然科學(xué)基金(70671057和教育部高等學(xué)校博士點(diǎn)專項(xiàng)科研基金(20051065002資助項(xiàng)目作者簡介:常桂娟(19762,女,博士生,主要從事供應(yīng)鏈管理、生產(chǎn)調(diào)度、遺傳算法、微粒群算法的研究改進(jìn)粒子群算法在作業(yè)車間調(diào)度問題中的應(yīng)用常桂娟(青島農(nóng)業(yè)大學(xué)理學(xué)院,山東青島266109摘要:調(diào)度問題是一類典型的NP 2hard 問題,傳統(tǒng)粒子群優(yōu)

2、化算法在解決該類問題上具有一定的局限性.通過分析其優(yōu)化機(jī)理,提出了改進(jìn)粒子群算法,結(jié)合了粒子群優(yōu)化算法的全局搜索能力和交換粒子位置的局部搜索能力,提出了新的粒子編碼方法基于粒子坐標(biāo)值排列編碼(PPP ,發(fā)展了一種快速、易實(shí)現(xiàn)的新的混合啟發(fā)式算法.大量實(shí)驗(yàn)仿真結(jié)果表明本算法可以有效求解作業(yè)車間調(diào)度問題,通過與遺傳算法比較,驗(yàn)證了改進(jìn)粒子群算法是求解Job 2shop 調(diào)度問題可行而高效的方法.關(guān)鍵詞:粒子群優(yōu)化;作業(yè)車間調(diào)度;混合優(yōu)化中圖分類號(hào):TP18文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):100128395(200901201392040引言粒子群優(yōu)化算法(PS O 是一種基于群體智能理論的優(yōu)化算法,由J

3、.Kennedy 和R.Eberhart 1在1995年提出的,該算法通過模擬鳥類群體調(diào)整自身飛行速度和飛行方向,將所有個(gè)體移動(dòng)到適應(yīng)度好的環(huán)境中,從而抽象出一種可以求解具有復(fù)雜解空間性質(zhì)問題的優(yōu)化算法.同時(shí)在進(jìn)化過程中該算法保留位置與速度上的信息,由于其概念和參數(shù)調(diào)整簡單而且容易編程實(shí)現(xiàn),它既保持傳統(tǒng)進(jìn)化算法深刻的群體智慧背景,同時(shí)又有自己許多良好的優(yōu)化性能.因此,PS O 算法一經(jīng)提出,立刻引起進(jìn)化計(jì)算領(lǐng)域?qū)W者們的廣泛關(guān)注225.傳統(tǒng)粒子群算法的早期應(yīng)用是在連續(xù)函數(shù)優(yōu)化問題上展開的,其優(yōu)化性能通過大量的實(shí)驗(yàn)已得到證實(shí).此外,粒子群算法還被應(yīng)用于神經(jīng)網(wǎng)絡(luò)的訓(xùn)練、混合整數(shù)非線性優(yōu)化問題、整數(shù)規(guī)

4、劃問題、帶約束函數(shù)優(yōu)化等問題的求解.在粒子群算法中,粒子的位置和速度均以連續(xù)參數(shù)形式表示,這種連續(xù)實(shí)數(shù)域中的位置2速度計(jì)算模型限制了粒子群算法在離散組合優(yōu)化問題領(lǐng)域的應(yīng)用.從查閱的國內(nèi)外文獻(xiàn)看,近兩三年粒子群算法才開始被應(yīng)用于求解組合優(yōu)化問題,由于組合優(yōu)化問題求解的困難性,相關(guān)文獻(xiàn)較少,主要涉及旅行商問題(TSP 和車輛路徑優(yōu)化問題(VRP 等.近幾年,國內(nèi)一些用粒子群算法解決車間調(diào)度問題的文獻(xiàn)也開始陸續(xù)出現(xiàn),其中有夏蔚軍等3提出的微粒群算法與模擬退火算法結(jié)合的混合啟發(fā)式算法.彭傳勇等4提出的利用遺傳算法交叉變異操作的思想,將粒子群算法與禁忌搜索相結(jié)合的廣義粒子群優(yōu)化算法.作業(yè)車間調(diào)度問題是典

5、型的組合優(yōu)化問題,求解該類問題的方法很多.目前常用的方法主要有遺傳算法、禁忌搜索、模擬退火等近似求解方法及這些方法的混合算法627.本文通過分析傳統(tǒng)粒子群算法的優(yōu)化機(jī)理,提出了一種基于粒子坐標(biāo)值排列編碼的改進(jìn)粒子群優(yōu)化模型,并以此模型為基礎(chǔ)構(gòu)建了適合JSP 求解的改進(jìn)粒子群優(yōu)化算法.該算法與已有的其它JSP 求解方法遺傳算法相比,在收斂精度上有了較大的提高.仿真結(jié)果也表明了該算法的可行性和有效性.并且算法在JSP 問題上的成功應(yīng)用也為粒子群算法在其它離散問題領(lǐng)域的應(yīng)用拓展了思路.1Job 2shop 問題的簡單描述JSP 問題可簡單描述為有n 個(gè)工件在m 臺(tái)機(jī)器上加工,每個(gè)工件包含m 個(gè)工序.

6、加工過程中要滿足:(1每個(gè)時(shí)刻每臺(tái)機(jī)器只能加工一個(gè)工件,且每個(gè)工件只能被一臺(tái)機(jī)器加工;(2工序一旦開始,中途不能被打斷;(3每個(gè)工件在同一臺(tái)機(jī)器上最多加工一次;(4每個(gè)工件必須按照工藝路線加工.本文性能指標(biāo)即適應(yīng)度函數(shù)定為總工期最短.2粒子群算法描述在n維空間中有N個(gè)粒子,每個(gè)粒子的坐標(biāo)為X i=(X i1,X i2,X in,并具有與優(yōu)化目標(biāo)函數(shù)相關(guān)的適應(yīng)度Fiti,同時(shí)每個(gè)粒子具有各自的速度V i=(Vi1,V i2,V in.對(duì)于粒子i所經(jīng)歷過的歷史最好位置記為Pi =(Pi1,P i2,P in,也稱為p best.群體所有粒子經(jīng)歷過的最好位置表示為Pg =(Pg1,P g2,Pgn,

7、也稱為g best.粒子群算法描述如下:V id(t+1=W V id(t+c1r1(P id(t-X id(t+c2r2(P gd(t-X id(t,(1X id(t+1=X id(t+V id(t+1,(2如果Vid>V max,則V id=V max;如果Vid<-V max,則V id=-V max.利用上述兩式計(jì)算第t+1代第i維的速度和位置.式中下標(biāo)d表示粒子的維度,i指第i個(gè)粒子, W是慣性權(quán)值,c1,c2都是正的常數(shù),稱為加速系數(shù),r1,r2是兩個(gè)在0,1范圍內(nèi)變化的隨機(jī)數(shù).V max是常數(shù),限制了速度的最大值.當(dāng)Vmax較大時(shí),粒子的飛行速度大,有利于全局搜索,但

8、有可能飛過最優(yōu)解;若較小,粒子可以在較小的區(qū)域內(nèi)進(jìn)行局部精細(xì)搜索,但易陷入局部最優(yōu).粒子群算法流程如下:(1初始化一群粒子,隨機(jī)產(chǎn)生每個(gè)粒子的位置和速度;(2評(píng)價(jià)每個(gè)粒子的適應(yīng)度;(3對(duì)于每個(gè)粒子,將其適應(yīng)度值與自身p best比較,如果優(yōu)于pbest,則將當(dāng)前值設(shè)為該粒子的p best;(4對(duì)于全體粒子,將當(dāng)前最優(yōu)適應(yīng)度值與g best比較,如果優(yōu)于g best,則將當(dāng)前最優(yōu)適應(yīng)度值設(shè)為群體gbest;(5由(1和(2式計(jì)算每個(gè)粒子的新速度和位置;(6如未達(dá)到終止條件,則返回第二步.3改進(jìn)粒子群算法(I PS O3.1編碼在傳統(tǒng)的粒子群算法中,粒子的位置和速度均以連續(xù)參數(shù)形式表示,這種連續(xù)實(shí)

9、數(shù)域中的位置2速度計(jì)算模型限制了粒子群算法在離散組合優(yōu)化問題領(lǐng)域的應(yīng)用.針對(duì)這一問題,本文提出了一種新的PPP編碼方法,即基于粒子坐標(biāo)位置排列編碼.這種編碼方法成功的將解決連續(xù)優(yōu)化問題的粒子群算法應(yīng)用到JSP這種離散問題當(dāng)中,操作簡單、易于實(shí)現(xiàn).例如,對(duì)于3個(gè)工件3臺(tái)機(jī)器加工的排序問題,表1給出了粒子的位置對(duì)應(yīng)JSP問題解的表達(dá)形式.表1中,粒子位置中最小的坐標(biāo)值對(duì)應(yīng)數(shù)字1,倒數(shù)第二的坐標(biāo)值對(duì)應(yīng)數(shù)字2,依此類推.如表1,根據(jù)粒子位置,我們得到這樣一組排列X=(76391284 5.這種解的表示方法使得粒子中每一位置坐標(biāo)對(duì)應(yīng)一個(gè)工件的一個(gè)工序,由此可以得到工件序列(32 1311322.序列中第

10、二個(gè)3表示工件3的第二個(gè)工序,第一個(gè)1表示工件1的第一個(gè)工序,等等.這樣,可以滿足每個(gè)工件工序的優(yōu)先約束.3.2粒子的局部搜索粒子在進(jìn)化過程中,為避免陷入局部最優(yōu)解,本文采用了簡單但有效的局部搜索機(jī)制,對(duì)全局最優(yōu)粒子隨機(jī)產(chǎn)生兩個(gè)位置,交換兩個(gè)位置的坐標(biāo),若所得粒子適應(yīng)度值優(yōu)于原來粒子,則替換原來粒子,終止程序;否則,繼續(xù)運(yùn)行,直到到達(dá)終止條件為止.3.3慣性權(quán)重與加速系數(shù)在粒子群優(yōu)化算法中,慣性權(quán)重W是關(guān)系到PS O算法搜索能力的重要參數(shù),將W從相對(duì)較大的值線性地減小到相對(duì)較小的值,使PS O算法在開始時(shí)具有很強(qiáng)的全局搜索能力而在算法接近結(jié)束時(shí)具有更好的局部搜索能力,計(jì)算公式為W=W max-

11、W max-W m inN maxN,其中,Wmax,W m in為慣性權(quán)重的初始值和最終值,N max 為最大迭代次數(shù),N為當(dāng)前迭代次數(shù).在本文的計(jì)算實(shí)例中,Wmax4改進(jìn)粒子群算法流程(I PS O步驟1設(shè)定參數(shù).通過對(duì)問題及解的特性進(jìn)行分析和了解,設(shè)定粒子群體規(guī)模,最大迭代次數(shù).步驟3評(píng)價(jià)粒子.利用本文提出的編碼方法給每個(gè)粒子進(jìn)行編碼,計(jì)算粒子的適應(yīng)度值,并記錄全局最優(yōu)粒子gbest及個(gè)體最優(yōu)粒子pbest.041四川師范大學(xué)學(xué)報(bào)(自然科學(xué)版32卷中所述的局部尋優(yōu)操作.將得到的粒子作為全局最優(yōu)粒子.步驟5利用改進(jìn)粒子群(I PS O算法優(yōu)化粒子群.對(duì)N個(gè)粒子利用粒子群優(yōu)化(1和(2式產(chǎn)生

12、新一代粒子群的位置及速度,并對(duì)全局最優(yōu)粒子和個(gè)體最優(yōu)粒子進(jìn)行更新.步驟6判斷滿足的終止條件.滿足最大迭代次數(shù)則輸出最優(yōu)適應(yīng)度函數(shù)值并終止;否則,返回步驟4.5仿真結(jié)果下面選擇了不同維數(shù)n×m的標(biāo)準(zhǔn)算例來說明改進(jìn)粒子群優(yōu)化算法的有效性.本文用MAT LAB語言編程,對(duì)于上述設(shè)計(jì)的算子,表2的FT06算例是引自文8中的標(biāo)準(zhǔn)算例;LA012LA15是引自S. La wrence9的算例.種群規(guī)模設(shè)為微粒維數(shù)的2倍,進(jìn)化代數(shù)為100代.先以FT06問題為例來說明其收斂性,另外給出了使用基于優(yōu)先權(quán)編碼兩點(diǎn)交叉的標(biāo)準(zhǔn)遺傳算法的仿真數(shù)據(jù),仿真10次結(jié)果如表2所示.該算例為6個(gè)工件6臺(tái)機(jī)器的調(diào)度問題

13、,最優(yōu)解為55,通過兩個(gè)算法的仿真結(jié)果比較,體現(xiàn)了I P2 S O算法解決這類問題的優(yōu)越性.表1JSP問題中的粒子表示Table1Parti cle presen t a ti on of JSP proble m表2I PS O算法與G A算法求解FT06問題仿真結(jié)果比較Table2The com par ison of a lgor ith m s I PS O and G A for FT06proble m現(xiàn)的次數(shù)最差解I PS O算法555755565757555558555556558 G A算法585862605958595860585859062對(duì)于較大規(guī)模的算例,本文算法同樣

14、表現(xiàn)出了良好的收斂性能.保持參數(shù)不變,分別用本文算法及遺傳算法對(duì)LA類問題中幾個(gè)不同規(guī)模的算例進(jìn)行了計(jì)算機(jī)仿真.仿真結(jié)果顯示本文算法明顯優(yōu)于G A算法.其中,這些標(biāo)準(zhǔn)算例在規(guī)定迭代次數(shù)內(nèi)都得到了其最優(yōu)解,而G A算法只對(duì)其中幾個(gè)算例得到最優(yōu)解.對(duì)其中的LA05、LA10、LA14問題,本文算法表現(xiàn)出了強(qiáng)收斂性,基本每次仿真均可快速收斂到最優(yōu)解.對(duì)其它算例,若擴(kuò)大種群規(guī)模和進(jìn)化代數(shù),仿真結(jié)果還會(huì)得到進(jìn)一步改善.表3記錄了仿真10次的實(shí)驗(yàn)數(shù)據(jù).圖1給出了對(duì)LA05、LA10、LA14問題的仿真圖,橫坐標(biāo)表示迭代次數(shù),縱坐標(biāo)表示最優(yōu)解.由圖可見,I PS O算法對(duì)這類問題表現(xiàn)了良好的收斂性能及收斂速

15、度.3次實(shí)驗(yàn),均仿真一次,每次都以很快表3I PS O算法和G A算法求解LA類若干問題仿真結(jié)果T able3The co mp arison of algorith ms I PS O and G A for LA proble ms 編號(hào)算例(規(guī)模最優(yōu)解最好解I PS O/G A平均值I PS O/G A1LA01(10×5666666/678680/705 2LA02(10×5655655/689679/723 3LA03(10×5597597/635621/655 4LA04(10×5590590/638610/641 5LA05(10×

16、;5593593/593593/598 6LA06(15×5926926/930933/956 7LA07(15×5890890/946910/996 8LA08(15×5863863/923883/957 9LA09(15×5951951/951967/991 10LA10(15×5958958/958958/967 11LA11(20×512221222/12771238/1312 12LA12(20×510391039/10791049/1120 13LA13(20×511501150/11981161/12

17、37 14LA14(20×512921292/12921292/1299141第1期常桂娟:改進(jìn)粒子群算法在作業(yè)車間調(diào)度問題中的應(yīng)用的速度收斂到了最優(yōu)解.6結(jié)語本文提出了一種基于粒子坐標(biāo)值排列編碼的改進(jìn)粒子群算法,算法中結(jié)合粒子群算法的全局搜索能力和交換粒子位置的局部搜索能力,將解決連續(xù)優(yōu)化問題的標(biāo)準(zhǔn)粒子群優(yōu)化算法成功應(yīng)用于Job2shop調(diào)度問題中,為解決生產(chǎn)調(diào)度問題提供了一個(gè)高速有效的尋優(yōu)算法.通過對(duì)不同維數(shù)的標(biāo)準(zhǔn)算例進(jìn)行計(jì)算機(jī)仿真,實(shí)驗(yàn)結(jié)果令人滿意,表明本文提出算法的有效性.將這種改進(jìn)粒子群算法應(yīng)用于其它調(diào)度問題是作者下一步的研究方向.致謝感謝青島農(nóng)業(yè)大學(xué)高層次人才啟動(dòng)基金項(xiàng)目

18、(630806的資助 .參考文獻(xiàn)1Kennedy J,Eberhart R.Particle S war m Op ti m izati onC/I EEE I nternati onal Conference on Neural Net w orks.Ne w Jersey:Pis2cata way,1995:194221948.2馬細(xì)霞,儲(chǔ)冬冬.粒子群優(yōu)化算法在水庫調(diào)度中的應(yīng)用分析J.鄭州大學(xué)學(xué)報(bào):工學(xué)版,2006,27(4:1212124.3夏蔚軍,吳智銘,張偉,等.微粒群優(yōu)化在Job2shop調(diào)度中的應(yīng)用J.上海交通大學(xué)學(xué)報(bào),2005,39(3:3812385.4彭傳勇,高亮,邵新宇,

19、等.求解作業(yè)車間調(diào)度問題的廣義粒子群優(yōu)化算法J.計(jì)算機(jī)集成制造系統(tǒng),2006,12(6:9112917.5王明春,唐萬生,劉鑫,等.一種基于PS O的投影尋蹤聚類算法J.曲阜師范大學(xué)學(xué)報(bào):自然科學(xué)版,2008,34(2:43246.6姜思杰,張付亮,王孔茂.基于遺傳和禁忌算法求解一類車間調(diào)度問題J.計(jì)算機(jī)集成制造系統(tǒng),2003,9(11:9842988.7梁旭,黃明,常征.求解車間調(diào)度問題的一種新遺傳退火混合策略J.計(jì)算機(jī)集成制造系統(tǒng),2005,11(6:8512854.8M uth J F,Thomp s on G L.I ndustrial SchedulingM.Englewood Cl

20、iffs,Ne w Jersey:Prentics Hall,1963.9La wrance S.Res ource Constrained Pr oject Scheduling:an Experi m ental I nvestigati on of Heuristic Scheduling TechniquesM.Pittsburgh:Carnegie Mell on Univ,1984.App licati on of I m p r oved Particle S war m Op ti m izati on t oJob2shop Scheduling Pr oblemCHANG Gui2juan(College of Science,Q ingdao A gricultural U niversity,Q ingdao266109,ShandongAbstract:Traditi onal particle s war m op ti m izati on has s ome li m itati ons in s olving the typ ical NP2ha