置換流水車間調(diào)度粒子群算法與參數(shù)設(shè)置分析

1、置換流水車間調(diào)度粒子群算法與參數(shù)設(shè)置分析第34卷第6期2021年12月武漢理工大學(xué)(交通科學(xué)與工程版)JournalofWuhanUniversityofTechnology(TransportationScience&.Engineering)置換流水車間調(diào)度粒子群算法與參數(shù)設(shè)置分析*劉志雄.'嚴(yán)新平.'趙潤(rùn)軍'(武漢科技大學(xué)機(jī)械自動(dòng)化學(xué)院"武漢430081)(天津港(集團(tuán))博士后科研工作站天津300461)(武漢理工大學(xué)水路公路交通平安控制與裝備教育部工程研究中心武漢430063)摘要:針對(duì)置換流水車間調(diào)度問(wèn)題,在介紹了基于粒子位置次序的粒

2、子群算法二維編碼方法之后,采用慣性權(quán)重線性遞減粒子群算法對(duì)置換流水車間調(diào)度問(wèn)題進(jìn)行了優(yōu)化.在此根底上,對(duì)粒子群算法的相關(guān)參數(shù)設(shè)置問(wèn)題展開(kāi)分析,主要針對(duì)慣性權(quán)重的取值,粒子群種群數(shù)量,粒子位置和速度將有助于提高求解置換流水車間調(diào)度問(wèn)題的粒子群算法優(yōu)化效率和優(yōu)化性能.關(guān)鍵詞:粒子群算法;置換流水車間;調(diào)度;參數(shù)設(shè)置;實(shí)驗(yàn)分析0引言置換流水車間調(diào)度問(wèn)題(permutationflowshopschedulingproblem,PFSP)是對(duì)流水車間調(diào)度問(wèn)題(flowshopschedulingproblem)的延伸.對(duì)于流水車間調(diào)度問(wèn)題,如果在每臺(tái)機(jī)器上加工的工件順序也相同,那么此時(shí)的問(wèn)題就是置換流

3、一定的加工工藝約束,隨著問(wèn)題規(guī)模的增加,調(diào)度問(wèn)題的解空間容量巨大,其求解過(guò)程仍十分復(fù)雜.已有的研究成果已經(jīng)說(shuō)明,智能優(yōu)化算法能夠有效地對(duì)調(diào)度問(wèn)題進(jìn)行優(yōu)化,從而得到調(diào)度問(wèn)題的最優(yōu)解或者次優(yōu)解.粒子群算法(particleswarmoptimization,PSO)是一種基于群體智能的進(jìn)化類算法,在連續(xù)函數(shù)優(yōu)化問(wèn)題領(lǐng)域,粒子群算法顯示了其有效問(wèn)題,如調(diào)度問(wèn)題.目前,對(duì)于連續(xù)空問(wèn)的函數(shù)優(yōu)化問(wèn)題,粒子群算法相關(guān)參數(shù)的設(shè)置已經(jīng)得到一些學(xué)者的分析蜘,其研究結(jié)果也說(shuō)明粒子群算法的相關(guān)參數(shù)設(shè)置對(duì)粒子群算法的優(yōu)化性能有著較大的影響.而對(duì)于調(diào)度問(wèn)題,更多的研究那么放在了對(duì)粒子群計(jì)算模型的改良以及相關(guān)的編碼及解碼方

4、法等方面,而對(duì)于粒子群算法相關(guān)參數(shù)問(wèn)題的探討,相關(guān)研究比擬少.本文在介紹了置換流水車間調(diào)度問(wèn)題粒子群優(yōu)化算法的編碼方法后,分別利用根本PSO,慣性權(quán)重線性遞減PSO和帶收斂因子的PSO對(duì)置PSO算法,對(duì)粒子群算法的相關(guān)參數(shù),包括慣性權(quán)重,粒子種群數(shù)量,粒子位置和速度的初始化以及粒子位置和速度限制等進(jìn)行分析.1置換流水車間調(diào)度問(wèn)題的描述假設(shè)t,.,為工件.,在機(jī)器J上的加工時(shí)間;.J為機(jī)器志上加工完工件.,后馬上加工工件所需的準(zhǔn)備時(shí)間(如果不加特殊說(shuō)明,一設(shè)各工件按照機(jī)器1m的順序進(jìn)行加工,令J=(1,.,)為所有工件的一個(gè)加工排序,那么有收稿日期:2()lO0710劉志雄(1975一):男,在

5、站博士后,副教授,主要研究領(lǐng)域?yàn)樯a(chǎn)凋度及其智能優(yōu)化算法國(guó)家自然科學(xué)基金工程(批準(zhǔn)號(hào):70801047),中國(guó)博士后科研基金工程(批準(zhǔn)號(hào):20210450769),湖北省教育廳科學(xué)技術(shù)研究計(jì)劃優(yōu)秀中青年人才工程(批準(zhǔn)號(hào):Q2021l115)資助武漢理T大學(xué)(交通科學(xué)與工程版)2021年第34卷fCtjJCj,一Cj廠l,-+.,+,ICj一Cj1一l+【CJ,maxC2+廠l,Cj一l+tj,i一2,m;J一2,n(1)minfminCj.,(2)2求解PFSP的粒子群算法設(shè)計(jì)采用基于粒子位置次序(particlepositionsequence,PPS)的二維編碼方法,即采用粒子位置的次序來(lái)

6、映射調(diào)度問(wèn)題巾的工件或者任務(wù)次序,維粒子編碼方法時(shí),第一維用自然數(shù)1,2,3,n來(lái)表示個(gè)工件,第二維表示粒子的位置向量值.粒子的長(zhǎng)度為所有加工工件的數(shù)量,一個(gè)完整的二維粒子如表1所列.表1二維粒子編碼方法工件1位置zn2.2解碼過(guò)程(調(diào)度方案的生成)在進(jìn)行調(diào)度計(jì)算之fjif,對(duì)二維粒子巾的粒子位置向量值進(jìn)行從小到大的排序,同時(shí),各位置向量值對(duì)應(yīng)的工件序弓'排列也發(fā)牛改變,由此生成的新的工件排序即為有效的調(diào)度方案,即將位置向量值較小的對(duì)應(yīng)的工什先加工.采用慣性權(quán)重線性遞減PSO,對(duì)置換FlowShop調(diào)度中的典型算例(Car類問(wèn)題)進(jìn)行優(yōu)化的一類針對(duì)置換FlowShop調(diào)度問(wèn)題的典型汁算

7、算例,包含8個(gè)算例,分別是Carl(11×5)(11×5表示問(wèn)題的規(guī)模,即11個(gè)工件5臺(tái)機(jī)器,其他算例類似),Carl(13×4),Carl(12×5),Carl(14×4),Carl(10×6),Carl(8×9),Carl(7X7)和Carl(8×8).性權(quán)重線性遞減PSO模型,那么是設(shè)定式(3)中的慣性權(quán)重訓(xùn)隨著迭代次數(shù)線性遞減時(shí),本文設(shè)定從0.9線性遞減至0.4.c一f一2.Vi+l一酬z+f1nd.m()(一)+(3)C2random()(g)z件1一:ri+l(4)對(duì)于每個(gè)問(wèn)題,設(shè)定最大迭代次數(shù)為300

8、次,粒子的初始位置是在0,2之間隨機(jī)產(chǎn)生,而速度時(shí),為了對(duì)算法進(jìn)行比擬,本文采用遺傳算法GA對(duì)Car類問(wèn)題進(jìn)行了計(jì)算,計(jì)算結(jié)果如表2所列.表中最大偏差,最小偏差是指每個(gè)算例20次計(jì)算指2O次計(jì)算后得到的平均值與最優(yōu)值之間的偏差.表2PSO和GA優(yōu)化Car類問(wèn)題的計(jì)算結(jié)果由表2可見(jiàn),PSO能夠有效地對(duì)Car類問(wèn)題進(jìn)行優(yōu)化,其優(yōu)化結(jié)果要好于遺傳算法GA的計(jì)算結(jié)果.3粒子群算法的參數(shù)設(shè)置分析為了對(duì)慣性權(quán)重的取值進(jìn)行分析,本文采用性權(quán)重分別取o.2,2之間的不同值,計(jì)算結(jié)果如圖1所示.璺/,t.l/,/,/,.1_|.卜.,叫慣性權(quán)重圖l不隕性權(quán)重取值F的計(jì)算結(jié)果算結(jié)果中,不慣性權(quán)重取值下,對(duì)于8個(gè)C

9、ar類問(wèn)題,PSO算法的最小偏差均為0,即都找到了最優(yōu)解.從計(jì)算結(jié)果看,當(dāng)權(quán)重值在0.8,1,1.3,1.51和1.7,2等范圍內(nèi)取值時(shí),計(jì)算結(jié)果的最大1,1.5和2時(shí),計(jì)算結(jié)果的最大偏差和平均偏差者5很/J,.為了分析粒子種群數(shù)量對(duì)優(yōu)化性能的影響,這里采用慣性權(quán)重線性遞減PSO對(duì)Car類問(wèn)題的優(yōu)化進(jìn)行分析(下文的參數(shù)分析均是采用慣性權(quán)重PSO得到的計(jì)算結(jié)果).設(shè)定最大迭代次數(shù)為300,重復(fù)優(yōu)化2o次,分別設(shè)定種群的數(shù)量為第6期劉志雄,等:置換流水車間調(diào)度粒子群算法參數(shù)設(shè)置分析10,20,30,40和5O,計(jì)算結(jié)果如圖2所示67薹;3lO一最大偏差平均值一平均偏差平均值一l【)2():jU4U

10、0U粒子種群數(shù)量圖2Car類問(wèn)題的計(jì)算結(jié)果圖2是對(duì)Car類問(wèn)題的計(jì)算結(jié)果(最小偏差均為O).隨著粒子種群數(shù)量的增加,最大和平均偏差平均值均是逐漸遞減的,說(shuō)明粒子種群數(shù)量的增加可以進(jìn)一步提高粒子群算法優(yōu)化調(diào)度問(wèn)題的性能,但同時(shí)需要注意的是,當(dāng)粒子種群數(shù)量大于40以后,最大和平均偏差平均值的減小幅度不是很大.因此,綜合上述分析,對(duì)于優(yōu)化置換FlowShop調(diào)度問(wèn)題,粒子種群數(shù)量取4O50時(shí)可以取得較好的優(yōu)化結(jié)果.對(duì)于凋度問(wèn)題,粒子初始位置和初始速度的取值范圍是否對(duì)優(yōu)化結(jié)果產(chǎn)生影響需要進(jìn)行分置初始化的取值范圍分別為0,2,0,2o,0,6O和0.1ool,同時(shí)對(duì)于每個(gè)位罱取值范,分別沒(méi)定速度的取值范

11、圍為2,2,5,5,1O,1ol,一20,2O,一3O,3O,一4O.40.一50,5o1.L一60,60,一80,sol和100,loo.在每個(gè)位置和速度取值范同下,分別計(jì)算8個(gè)Car類問(wèn)題的最大偏差和平均偏差(最小偏差均為0),每種情況下Car類問(wèn)題最大偏差和平均偏差的平均值分別如圖3和圖4所示.從計(jì)算結(jié)果看,當(dāng)粒子速度的取值范圍一定時(shí),粒子何置的取值范圍越大,優(yōu)化結(jié)果的最大偏差和平均偏差均有增大的趨勢(shì);而當(dāng)粒子位置的取值范圍一定時(shí),隨著粒子速度取值范罔的增加,一2,21O,1O30,30一5O,5O一8O,8O速度取值范岡圖3小同位置和速度取值范圍時(shí)Car類問(wèn)題的最大偏差堡誣腰取值范J圖

12、4不同位置和速度取值范時(shí)Car類問(wèn)題的平均偏差速度取值范圍增加一定幅度時(shí),最大偏差和平均偏差的這種減少趨勢(shì)那么出現(xiàn)波動(dòng),反而可能出現(xiàn)最大偏差和平均偏差逐漸增加的趨勢(shì),這種情況對(duì)于平均偏差的計(jì)算結(jié)果較為明顯.因此,保持較小的位置初始化取值范圍,同時(shí)使速度在一個(gè)相對(duì)較大的范圍內(nèi)初始化取值,PSO算法的優(yōu)化結(jié)果會(huì)較好.化范圍為0,2,速度初始化的范圍為一2,2,在計(jì)算過(guò)程中,對(duì)位置和速度值進(jìn)行限制,將粒子的速度值限定在一2.2之內(nèi),而將粒子的位置向量值分別限定在2,2,一5,5,一10,10,一50,5ol和一10000,10ooo之問(wèn),對(duì)Car類的8個(gè)問(wèn)題進(jìn)行優(yōu)化,每個(gè)問(wèn)題重復(fù)優(yōu)化20次,得到的優(yōu)

13、化結(jié)果的平均偏差如表3所列.從上述計(jì)算結(jié)果看,山于粒子位置和速度的初始化范圍較小,當(dāng)粒子位置的限定范圍較小時(shí),其計(jì)算結(jié)果的平均偏差平均值就較大,優(yōu)化性能相對(duì)較差;當(dāng)粒子位置的限定范圍變大時(shí),計(jì)算結(jié)果的平均偏差平均值變小,這是因?yàn)榱Ｗ拥奈恢孟蛄恐党尸F(xiàn)多樣性,進(jìn)而使得生成的調(diào)度方案也呈現(xiàn)多樣性,算法的搜索范圍擴(kuò)大,從而使得算法的優(yōu)化性能較好.綜合上述分析,對(duì)于本文所設(shè)計(jì)的粒子群算法,可以不對(duì)粒子的位置向量設(shè)定范罔限制.限制與否對(duì)調(diào)度優(yōu)化結(jié)果的影響,設(shè)定粒子位置子速度的初始化范同和限制范圍分別取值在一2,2,一5,5,L一10,10,2O,20和一30,3ol之內(nèi).對(duì)Car類的8個(gè)調(diào)度問(wèn)題進(jìn)行優(yōu)化,

14、每個(gè)問(wèn)題重復(fù)優(yōu)化2O次,最大迭代次數(shù)為300,經(jīng)過(guò)計(jì)算后8個(gè)問(wèn)題的最大偏差和平均偏差平均值如表4所列.1ll11O0OO765432lO瑤?1132?武漢理工大學(xué)(交通科學(xué)與程版)2021年第34卷表3不同粒子位置限定范圍下Car類問(wèn)題的平均偏差粒子速度的對(duì)速度小加限制對(duì)速度限制限制范圍最大偏差平均偏差最大偏差平均偏差從上述計(jì)算結(jié)果看,無(wú)論是優(yōu)化結(jié)果中的最大偏差還是平均偏差,不限定粒子速度的計(jì)算結(jié)果均好于限定速度的計(jì)算結(jié)果.因此,用本文所設(shè)計(jì)PSO算法優(yōu)化置換FlowShop調(diào)度問(wèn)題(至少是針對(duì)Car類調(diào)度問(wèn)題),對(duì)粒子速度不加限制的優(yōu)化結(jié)果要好于限制粒子速度的優(yōu)化結(jié)果.4結(jié)束語(yǔ)對(duì)于一種優(yōu)化算

15、法,算法參數(shù)的設(shè)定直接影問(wèn)題的粒子群算法,對(duì)不同粒子群模型,慣性權(quán)重的取值,粒子種群數(shù)量,位置和速度的初始化取值范圍以及位置和速度的限制范圍等相關(guān)參數(shù)的取置的分析研究,為置換FlowShop調(diào)度問(wèn)題的求解提供了參數(shù)的設(shè)置范圍,有助于提高粒子群算法優(yōu)化調(diào)度問(wèn)題的優(yōu)化性能.參考文獻(xiàn)1鄭大鐘,趙千川.離散事件動(dòng)態(tài)系統(tǒng)E1.北京:清華大學(xué)出版社,2001.2BruckerP.SchedulingalgorithmM.Fhefifthedition.Berlin:SpringerVerlag,2007.tionC/ProceedingsofIEEEInternationalConferenceonNeu

16、tralNetworks,Perth,Australia,1995:l9421948.E43EberhartRC,ShiYH.Particleswarmoptimization:development,applicationsandresourcesC/Proceedingsof2001CongressonEvolutionaryComputation,Seoul,korea,200l'8186粒子群優(yōu)化算法J2.河南科技大學(xué):自然科學(xué)版,2021,29(6):4952.cleswarn-ioptimizationc/Proceedingofthe7thAnnualConference

17、onEvolutionaryProgramming.WashingtonDC.1998.59卜600.swarmoptimizationc/Proceedingsof1999CongressonEvolutionaryComputation,Washington,D.E82C.USA,Piscataway,N:IEEEServiceCenter,1999,19451949.EiGalladA,Eicingtheparticleswarmoptimizerviaproperparameteesselectionc/Proceedingsofthe2002IEEECanadianConferenc

18、eonElectrical&ComputerEngineering,2002,792797.(下轉(zhuǎn)第1137頁(yè))第6期肖同權(quán),等:轎車發(fā)動(dòng)機(jī)艙內(nèi)流動(dòng)與散熱特性數(shù)值研究?l137?rateandairrecirculationatvehicleidleconditions_J.SAEpaper,2004010053SimulationonVehicleUnderhoodThermalManagementSystemXiaoGuoquanYangZhigang(SchoolofMechanical&AutomotiveEngineering,SouthChinaUn

19、iversityofTechnology,Guangzhou510640,China)(SchooloAutomotive,TongjiUniversity,Shanghai202104,China)Abstract:TheobiectiveofthisworkistoanalysistheunderhoodairflowandheattransfercharacteristicsofthesamevehicleoperationconditionbyStarCDcodeandtheF1uentcodewereobtainedanddifferentvehicleoperationcondit

20、ionswereobtainedandtheresultsshowedtheETAdecreasesandthemassfluxincreaseastheincreaseofthevehiclespeed.Moreover,theunderhoodheattransfercharacteristicsofdifferentvehicleoperationconditionswerealsosimulatedandanalyzed,theresultsshowtheexistenceofthefrontendairrecirculationshouldbenotedespeciallyatveh

21、icleidlecondition,therearethemosttemperaturedistributionatvehicleuphillconditionwithfull1oadandthefanscanbeshutoffathighspeedfromthepointofviewoftheunderhoodthermalenvironment.Keywords:underhood;airflow;heattransfer;thermalmanagement;numericalsimulation(上接第1132頁(yè))ParticleSwarmOptimizationandParameter

22、SettingAnalysisforPermutationFlowShopSchedulingProblemLiuZhixiong''.'YanXinping.'ZhaoRunjun(CollegeofMachinervandAutomation,WuhanUniversityo/ScienceandTechnology,ban430081,China)"(PostdoctoralResearchCenter,TianJinPort(GrouP)Co.,LTDTianin300461,China)(EngineeringResearchCenterofTr""s戶