【正文】 擇后的群體為：X1 ={ 1 2 4 3 3 1 2 4 2 1 2 3 4 1 3 4 }X2 ={ 2 3 1 4 1 2 3 4 3 4 1 2 2 1 4 3 }X3 ={ 3 1 4 2 2 1 4 3 4 3 2 2 1 3 4 1 }X4 ={ 1 2 4 3 3 1 2 4 2 1 2 3 4 1 3 4 } 我們隨機(jī)將染色體進(jìn)行兩兩交叉，如果將染色體X1和染色體X2，染色體X3和染色體X4進(jìn)行交叉。這里我們用第一種交叉算子。交叉后的種群變?yōu)椋篨1 ={1 2 3 4 3 1 2 4 2 1 2 3 4 1 4 3}X2 ={2 4 1 3 1 2 3 4 3 4 1 2 2 1 3 4}X3 ={4 1 3 2 2 1 3 4 3 4 2 2 1 3 4 1}X4 ={1 2 3 4 4 1 2 3 2 1 2 4 3 1 3 4}交叉后的適應(yīng)度值為：F1=32, F2=32, F3=30, F4=32 ,將進(jìn)行后的值和前面的進(jìn)行比較，可以看到大部分個(gè)體經(jīng)過(guò)交叉后的個(gè)體性能大大提高。遺傳算法和生物的進(jìn)化一樣，在進(jìn)化的過(guò)程中，由于某些原因染色體的個(gè)別基因會(huì)發(fā)生變異，一般情況下變異后的個(gè)體比以前的優(yōu)，但有些變異不一定會(huì)產(chǎn)生優(yōu)秀的個(gè)體。為了說(shuō)明變異這個(gè)問(wèn)題。對(duì)這個(gè)例子來(lái)說(shuō)，就是這4條染色體中將有1條染色體會(huì)發(fā)生變異。假設(shè)我們隨機(jī)選擇上面交叉后的染色體X1進(jìn)行變異，我們這里用第一種變異算子。選擇變異位置為3，經(jīng)過(guò)變異后的個(gè)體為：X1 ={1 3 2 4 3 1 2 4 2 1 2 3 4 1 4 3}變異后的適應(yīng)度值F1=31，可以看出染色體X1變異后個(gè)體的適應(yīng)度值比沒(méi)變異前的適應(yīng)度值小，這種變異使得個(gè)體的性能比以前更優(yōu)。經(jīng)過(guò)上面的選擇、交叉、變異后形成的第二代新種群為： X1＇= { 1 3 2 4 3 1 2 4 2 1 2 3 4 1 4 3} X2＇= { 2 4 1 3 1 2 3 4 3 4 1 2 2 1 3 4}X3＇= { 4 1 3 2 2 1 3 4 3 4 2 2 1 3 4 1}X4＇= { 1 2 3 4 4 1 2 3 2 1 2 4 3 1 3 4}上面四個(gè)個(gè)體所對(duì)應(yīng)的適應(yīng)度值為F1＇=31 、F2＇=32 、F3＇=30 、F4＇=32，而第一代的四個(gè)個(gè)體的適應(yīng)度值為F1=3 F2=33 、F3=33 、F4=34，將兩代群體各個(gè)個(gè)體的適應(yīng)度值進(jìn)行比較，可以看出產(chǎn)生的新群體比第1代優(yōu)，可見(jiàn)用遺傳算法解決這個(gè)問(wèn)題是可行的［17］。由于我們?cè)O(shè)定的最大進(jìn)化代數(shù)是50，這里只做了一次進(jìn)化，還沒(méi)滿足結(jié)束的條件，所以還必須按照以上的步驟進(jìn)行下去，就是再對(duì)產(chǎn)生的新群體進(jìn)行選擇，交叉，變異，一直重復(fù)這些操作，直到滿足算法結(jié)束條件為止，算法才能結(jié)束。最后，由仿真得到10，圖中顯示了適應(yīng)度值為10個(gè)工件在10個(gè)機(jī)器加工所需的最短時(shí)間，對(duì)應(yīng)得工序即為工件的加工順序。，虛線代表種群均值的變化。10的調(diào)度。0501001502002503003504004505000500100015002000250030003500 最優(yōu)解的變化種群均值的變化 曲線圖 甘特圖 小結(jié)遺傳算法在解決作業(yè)車間調(diào)度問(wèn)題上比經(jīng)典的啟發(fā)式算法好，同時(shí)遺傳算法比傳統(tǒng)的搜索技術(shù)有更強(qiáng)的優(yōu)越性，因?yàn)樗粌H能解決某一特定問(wèn)題，而且可以適應(yīng)不同的問(wèn)題形式。用遺傳算法來(lái)解決車間調(diào)度問(wèn)題,其中介紹了常用的幾種編碼方式,。并且以四個(gè)工件四個(gè)機(jī)器問(wèn)題進(jìn)行舉例,說(shuō)明了用遺傳算法解決車間調(diào)度問(wèn)題的可行性。結(jié) 論本論文選擇作業(yè)車間的生產(chǎn)調(diào)度為研究和開(kāi)發(fā)對(duì)象，以遺傳算法為基礎(chǔ)，綜合運(yùn)用車間調(diào)度問(wèn)題的基本理論，對(duì)車間調(diào)度問(wèn)題進(jìn)行了系統(tǒng)的研究。作業(yè)車間調(diào)度問(wèn)題(JSP)簡(jiǎn)單來(lái)說(shuō)就是設(shè)備資源優(yōu)化配置問(wèn)題。作業(yè)車間調(diào)度問(wèn)題是計(jì)算機(jī)集成制造系統(tǒng)(CIMS)工程中的一個(gè)重要組成部分，它對(duì)企業(yè)的生產(chǎn)管理和控制系統(tǒng)有著重要的影響。在當(dāng)今的競(jìng)爭(zhēng)環(huán)境下，如何利用計(jì)算機(jī)技術(shù)實(shí)現(xiàn)生產(chǎn)調(diào)度計(jì)劃優(yōu)化，快速調(diào)整資源配置，統(tǒng)籌安排生產(chǎn)進(jìn)度，提高設(shè)備利用率已成為許多加工企業(yè)面臨的重大課題本文的主要工作和研究成果具體總結(jié)如下：，分析了目前該研究領(lǐng)域存在的問(wèn)題及發(fā)展趨勢(shì)，為論文的研究奠定了理論基礎(chǔ)。2. 近年來(lái)遺傳算法得到了很大的發(fā)展，應(yīng)用遺傳算法來(lái)解決車間調(diào)度問(wèn)題早有研究。應(yīng)用遺傳算法來(lái)解決車間調(diào)度問(wèn)題，在解決的過(guò)程中針對(duì)工件加工工藝的順序要求，提出了相應(yīng)的遺傳算子及其適應(yīng)度函數(shù)。并對(duì)幾種染色體編碼做了相應(yīng)的比較，用一種簡(jiǎn)單的編碼方式來(lái)解決車間調(diào)度問(wèn)題，本文在已有算法基礎(chǔ)上詳細(xì)討論了染色體編碼方法并對(duì)其進(jìn)行了改進(jìn)。致 謝在論文即將完成之際,我非常感謝所有幫助過(guò)和支持過(guò)我的人們。首先, 衷心感謝我的指導(dǎo)老師王介生,本文的研究工作是在他的關(guān)懷和悉心指導(dǎo)下完成的。是他的很多建設(shè)性的意見(jiàn)和啟發(fā)，才使得本論文得以完成。在我四年的本科學(xué)習(xí)期間，王介生老師在學(xué)習(xí)上給予了我悉心的指導(dǎo)，生活上給予了無(wú)私的關(guān)懷。王老師嚴(yán)謹(jǐn)求實(shí)的治學(xué)作風(fēng)、誨人不倦的師者風(fēng)范時(shí)刻激勵(lì)著我克服困難，認(rèn)真完成本論文的寫作。他求實(shí)創(chuàng)新的科研精神和言傳身教的師者風(fēng)范，將使我在以后的學(xué)習(xí)和工作中受益匪淺。他熱情隨和、寬大為懷的個(gè)性修養(yǎng)更將使我受益終身! 再次,我非常感謝學(xué)院和系上領(lǐng)導(dǎo)對(duì)我的培養(yǎng),感謝所有老師對(duì)我們的耐心教導(dǎo)。最后感謝在學(xué)習(xí)和生活上給予我?guī)椭乃型瑢W(xué)。謹(jǐn)以此文獻(xiàn)給所有關(guān)心、幫助和支持過(guò)我的人們!參考文獻(xiàn)[1][M].北京:人民郵電出版社,2000:105125.[2]方紅雨,[J].,12(7):6772. [3]張長(zhǎng)水,[J].電子學(xué)報(bào),2002,11(6):4045. [4]張長(zhǎng)水,[J].,4(8):5358. [5]何霆,劉[J]. 機(jī)械工程學(xué)報(bào),2002,7(7):7681.[6]熊銳,[J] .清華大學(xué)學(xué)報(bào)，2002， 11(5):6166.[7]王小平,－理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社， 1999:227256.[8]李剛,[J]. 應(yīng)用科學(xué)學(xué)報(bào)2004,11(8):7782.[9]方紅雨,[J].電腦與信息技術(shù)2001,2(4):6267.[10][M].科學(xué)出版社,2001:315360.[11][M].北京:人民郵電大學(xué)出版社,2001:466470.[12]張長(zhǎng)水,閻平凡.解Jobshop的調(diào)度問(wèn)題神經(jīng)網(wǎng)絡(luò)方法[J].自動(dòng)化學(xué)報(bào)1995，2 (8):5661.[13][J].機(jī)械工程學(xué)報(bào) ,2002,3(7):7883.[14]席裕庚,[J].控制理論與應(yīng)用,1996,13(6):697708.[15][M].北京:清華大學(xué)出版社,2001:157286. [16][J]. 鞍山鋼鐵學(xué)院學(xué)報(bào),2000,13(2):7277.[17]侯格賢,[J].,14(3):257260.附 錄%945T=[21 71 16 52 26 34 53 21 55 95。 55 31 98 79 12 66 42 77 77 39。 34 64 62 19 92 79 43 54 83 37。 87 69 87 38 24 83 41 93 77 60。 98 44 25 75 43 49 96 77 17 79。 35 76 28 10 61 9 95 35 7 95。 16 59 46 91 43 50 52 59 28 27。 45 87 41 20 54 43 14 9 39 71。 33 37 66 33 26 8 28 89 42 78。 69 81 94 96 27 69 45 78 74 84]。M=[ 1 6 9 8 7 2 0 4 3 5。 4 2 5 9 0 7 1 8 6 3。 3 2 8 1 4 9 7 6 0 5。 1 3 2 7 8 9 6 0 5 4。 2 0 5 6 7 1 4 9 3 8。 2 3 5 9 4 6 0 8 1 7。 3 2 0 1 9 8 6 5 4 7。 1 0 3 4 6 9 8 5 2 7。 4 2 8 5 3 7 1 6 9 0。 8 9 2 4 3 0 7 6 1 5 ]。%將機(jī)器號(hào)+1for i=1:10 S=M(i,:)。 for j=1:10 S(j)=S(j)+1。 end M(i,:)=S。endPNumber=10。 %零件個(gè)數(shù) 3MNumber=10。 %機(jī)器個(gè)數(shù) 3WPNumber=[10 10 10 10 10 10 10 10 10 10]。%將時(shí)間處理下TTemp=T。for i=1:10 for j=1:10 TTemp(i,j)=T(M(i,j),i)。 end endT=TTemp。NIND=40。 %個(gè)體數(shù)目(Number of individuals)MAXGEN= 200。 %最大遺傳代數(shù)(Maximum number of generations)GGAP=。 %代溝(Generation gap)XOVR=。 %交叉率MUTR=。 %變異率gen=0。 %代計(jì)數(shù)器trace=zeros(2, MAXGEN)。 %尋優(yōu)結(jié)果的初始值WNumber=0。for i=1:PNumberWNumber=WNumber+WPNumber(1,i)。 %工序個(gè)數(shù)end% 初始化群Chrom=zeros(NIND,WNumber)。for i=1:NINDChrom(i,:)=randperm(WNumber)。end%計(jì)算目標(biāo)函數(shù)值 [PVal ObjV P]=cal(Chrom,NIND,T,M,PNumber,MNumber,WPNumber)。 while genMAXGEN FitnV=ranking(ObjV)。 %分配適應(yīng)度值(Assign fitness values) SelCh=select(39。sus39。, Chrom, FitnV, GGAP)。 %選擇 SelCh=across(SelCh,NIND*GGAP,XOVR,WNumber)。 %交叉 SelCh=aberrance(SelCh,NIND*GGAP,MUTR,WNumber)。 %變異 [PVal ObjVSel P]=cal(SelCh,NIND*GGAP,T,M,PNumber,MNumber,WPNumber)。 %計(jì)算目標(biāo)函數(shù)值 [Chrom ObjV] =reins(Chrom, SelCh,1, 1, ObjV, ObjVSel)。 %重插入子代的新種群 [PVal ObjVl P]=cal(Chrom,NIND,T,M,PNumber,MNumber,WPNumber)。 %計(jì)算目標(biāo)函數(shù)值 gen=gen+1。 %代計(jì)數(shù)器增加% %輸出最優(yōu)解及其序號(hào)，并在目標(biāo)函數(shù)圖像中標(biāo)出，Y為最優(yōu)解,I為種群的序號(hào) trace(1, gen)=min(ObjV)。 %遺傳算法性能跟蹤 trace(2, gen)=sum(ObjV)/length(ObjV)。 % 初始化 if gen= =1 Val1=PVal。 Val2=P。 MinVal=min(ObjV)。 end %記錄最小的工序 if MinVal trace(1,gen) Val1=PVal。 Val2=P。 MinVal=trace(1,gen)。 end end PVal=Val1。 %工序時(shí)間 P=Val2。 %工序 MinVal=MinVal %最小時(shí)間%計(jì)算解的變化 hold on。 plot([0,0],[0,0])。plot(trace(1,:))。hold on。plot(trace(2,:),39。.39。)。grid。legend(39。解的變化39。,39。種群均值的變化39。)。%顯示結(jié)果figure(2)。for i=1:WNumber val= P(1,i)。 a=(mod(val,10))+1。 b=((vala+1)/10)。 mText=M(b,a)。 PlotRec(PVal(1,i),PVal(2,i),mText)。 hold on。 mPoint1=PVal(1,i)。 mPoint2=PVal(2,i)。x1=mPoint1。 y1=。