【正文】 體中的順序來以相應(yīng)的優(yōu)先級別安排任務(wù)。對于有三項任務(wù)的調(diào)度問題，假設(shè)染色體為[2 3 1]，則可以解釋為首先安排第二項任務(wù)的所有操作，其次是第三項任務(wù)，最后才輪到第一項任務(wù)。用于表示機器上加工工件的一個排列順序。前面兩種編碼方式比較復(fù)雜，下面我們用基于操作的編碼方式來解此車間調(diào)度問題： 把調(diào)度編碼為工序的序列，每個基因代表一道工序，給所有同一工件的工序指定相同的符號，其解碼原則是將染色體上得基因按照從左到右得順序解釋為任務(wù)相應(yīng)順序的操作。顯然，這種解碼過程可產(chǎn)生活動調(diào)度。只需改變工序的順序，即可得到不同的調(diào)度結(jié)果，即不同的生產(chǎn)周期。因為每個工件有三道工序，所以每個工件在一個染色體中剛好出現(xiàn)三次?？梢钥闯龉ぜ2的所有工序都用相同的符號2來命名，并且根據(jù)它出現(xiàn)在染色體中的順序加以解釋，工件的工序和加工機器的對應(yīng)關(guān)系如下所示。 初始種群的生成在N個工件M臺機器的排序問題中，對每個機器的加工存在加工工藝順約束，這個工藝約束表示為工件的加工順序矩陣：M11 M12 … M1MM（J,M）= M21 M22 … M2M ： ： ： ： ()Mn1 Mn2 … MnM。STEP2：產(chǎn)生一個整數(shù)隨機數(shù)1=p=N。STEP4：重復(fù)STIP2，STEP3，直到GEN的所有元素為零。重復(fù)STEP1，STEP2，STEP3，STEP4，直到種群滿。初始種群的生成也可以用隨機方法產(chǎn)生，這是因為群體中的個體都是由工件的符號組成的。根據(jù)適應(yīng)度的大小,對個體進行優(yōu)勝劣汰。從生物學(xué)角度講,適應(yīng)度相當(dāng)于“生存競爭,適者生存”的生物生存能力,在遺傳過程中具有重要意義。STEP2:chrom（i）對應(yīng)相應(yīng)工序的加工機器為machiner（i）。STEP4:求出適應(yīng)度函數(shù)F=ti(chorm(n))。目前，如何確定GA的最優(yōu)參數(shù)仍舊是一個公開的問題，也是研究GA的重要課題之一。通常，種群太小時，不能提供足夠的采樣點，以致算法性能很差，甚至得不到問題得可行解；種群太大時，盡管可增加優(yōu)化信息以阻止早熟收斂的發(fā)生，但無疑會增加計算量，從而使收斂時間太長。交叉概率用于控制交叉操作的頻率。變異概率是加大種群多樣性的重要因素。但是，變異概率太小則不會產(chǎn)生新個體，抑制早熟現(xiàn)象的能力較差，概率太大則會破壞掉很多較好的模式，使GA成為隨機搜索。評價值(目標(biāo)函數(shù))較小的個體有較高的概率生存,即在下一代群體中再次出現(xiàn)。其中,∑fi表示指所有個體適應(yīng)值之和。第一種交叉算子在用遺傳算法解決作業(yè)車間調(diào)度問題中,在對工序編碼的排序問題中,交叉算子不能簡單交換兩個個體的相應(yīng)位置的基因段,因為這樣得到的后代個體可能不能滿足每個工件號重復(fù)M次的要求。所以為了滿足我們的工序編碼的要求,本文采用另一種交叉算子。例如:對于一個4個工件4個機器問題,假如父母個體為:Parent1:1 3 4 2 4 2 3 3 1 4 3 2 1 4 2 1Parent2:3 2 4 1 1 2 3 4 4 2 3 1 2 4 1 3 假設(shè)隨機選擇工件1，2，則從parent1得到的新串為：New1:1 h h 2 h 2 h h 1 h h 2 1 h 2 1Part1:1 2 2 1 2 1 2 1Part2:3 4 4 3 3 4 3 4同樣從Parent2得到的新串為New2:h 2 h 1 1 2 h h h 2 h 1 2 h 1 hPart1: 2 1 1 2 2 1 2 1Part2: 3 4 3 4 4 3 4 3然后用Parent2個體的part2：3 4 3 4 4 3 4 3按照原來的相對順序逐個替換第一個父母個體Parent1產(chǎn)生的新串New1：1 h h 2 h 2 h h 1 h h 2 1 h 2 1中的h，得到的后代個體為：Parent1＇:1 3 4 2 3 2 4 4 1 3 4 2 1 3 2 1同理用Parent1個體的part2：3 4 4 3 3 4 3 4按照原來的相對順序逐個替換第二個父母個體Parent2產(chǎn)生的新串New2：h 2 h 1 1 2 h h h 2 h 1 2 h 1 h中的h，得到的后代個體為：Parent2′:3 2 4 1 1 2 4 3 3 2 4 1 2 3 1 4第二種交叉算子假定選擇兩個個體X1，X2做雙親，在做交叉時先產(chǎn)生一個隨機數(shù)來決定交叉點對于基因鏈碼的具體位置，從這一位置將鏈碼一分為二，第一個后代X1＇的前一小段鏈碼使用X1的前一小段鏈碼，然后把這一小段鏈碼的每個基因從X2中剔掉，X2中剩下的基因保持順序不變，構(gòu)成X1＇的后一小段鏈碼。例如，如果X1，X2的基因鏈碼分別是X1 1 3 8 5 2 7 6 4X2 3 2 4 1 8 7 6 5交叉點位于第三個基因之后，那么從中剔除X1的前一小段基因1 3 8之后，得到的基因鏈碼片段為2 4 7 6 5，所以X1ˊ的基因鏈碼為：X1ˊ 1 3 8 2 4 7 6 5同樣可以得到X2ˊ的基因鏈碼為：X2ˊ 3 2 4 1 8 5 7 6這種交叉算子在基于操作的染色體編碼時并不適用，提出來和第一種算子進行比較。在此作業(yè)調(diào)度算法中，不能簡單的將基因的值做改變。所以采用上述變異算子是不可行的。同樣，以1 3 2 3 1 2 3 1 2為例，假設(shè)變異位置為2，則變異前后的基因鏈碼為：變異前：1 3 2 3 1 2 3 1 2變異后：3 1 2 3 1 2 3 1 2 遺傳算法終止條件GA的收斂理論說明了GA具有概率1收斂的極限性質(zhì)，然而實際算法通常難以實現(xiàn)理論上的收斂。本研究以迭代次數(shù)作為是否終止的條件，從而控制優(yōu)化過程。本文運用基于操作的編碼方式,文章還簡要講述了一下基于工件的編碼和基于先后表的編碼。遺傳算子也是遺傳算法解決問題的關(guān)鍵所在。經(jīng)過這種改進之后，再配合最優(yōu)保存的選擇策略，就能夠保證種群的最好個體的適應(yīng)度函數(shù)單調(diào)下降，即調(diào)度時間單調(diào)下降，大大改善遺傳算法的搜索效率。X1=chrom1（16）={1 2 4 3 3 1 2 4 2 1 2 3 4 1 3 4}X2=chrom2（16）={2 3 1 4 1 2 3 4 3 4 1 2 2 1 4 3}X3=chrom3（16）={3 1 4 2 2 1 4 3 4 3 2 2 1 3 4 1}X4=chrom4（16）={4 1 3 2 1 2 3 3 4 2 1 3 4 1 2 4}將這四個染色體作為種群的第一代。ti(chorm(7))=ti(chorm(6))=22ti(chorm(11))=ti(chorm(10)…=ti(chorm(7))=22ti(chorm(12))=ti(chorm(11))+max(ti(3,3),ti(4,4))=22+max(8,4))=30ti(chorm(14))=ti(chorm(13))=ti(chorm(12))=30ti(chorm(15))=ti(chorm(14))+max(ti(3,4))=30+1=31所以F1=31，同理可以求的 F2=33 ,F3=33, F4=34。而染色體F1的適應(yīng)度值最小，表示加工完零件所需時間最短［16］。這里我們用第一種交叉算子。遺傳算法和生物的進化一樣，在進化的過程中，由于某些原因染色體的個別基因會發(fā)生變異，一般情況下變異后的個體比以前的優(yōu)，但有些變異不一定會產(chǎn)生優(yōu)秀的個體。對這個例子來說，就是這4條染色體中將有1條染色體會發(fā)生變異。選擇變異位置為3，經(jīng)過變異后的個體為：X1 ={1 3 2 4 3 1 2 4 2 1 2 3 4 1 4 3}變異后的適應(yīng)度值F1=31，可以看出染色體X1變異后個體的適應(yīng)度值比沒變異前的適應(yīng)度值小，這種變異使得個體的性能比以前更優(yōu)。由于我們設(shè)定的最大進化代數(shù)是50，這里只做了一次進化，還沒滿足結(jié)束的條件，所以還必須按照以上的步驟進行下去，就是再對產(chǎn)生的新群體進行選擇，交叉，變異，一直重復(fù)這些操作，直到滿足算法結(jié)束條件為止，算法才能結(jié)束。虛線代表種群均值的變化。0501001502002503003504004505000500100015002000250030003500 最優(yōu)解的變化種群均值的變化 曲線圖 甘特圖 小結(jié)遺傳算法在解決作業(yè)車間調(diào)度問題上比經(jīng)典的啟發(fā)式算法好，同時遺傳算法比傳統(tǒng)的搜索技術(shù)有更強的優(yōu)越性，因為它不僅能解決某一特定問題，而且可以適應(yīng)不同的問題形式。并且以四個工件四個機器問題進行舉例,說明了用遺傳算法解決車間調(diào)度問題的可行性。作業(yè)車間調(diào)度問題(JSP)簡單來說就是設(shè)備資源優(yōu)化配置問題。在當(dāng)今的競爭環(huán)境下，如何利用計算機技術(shù)實現(xiàn)生產(chǎn)調(diào)度計劃優(yōu)化，快速調(diào)整資源配置，統(tǒng)籌安排生產(chǎn)進度，提高設(shè)備利用率已成為許多加工企業(yè)面臨的重大課題本文的主要工作和研究成果具體總結(jié)如下：，分析了目前該研究領(lǐng)域存在的問題及發(fā)展趨勢，為論文的研究奠定了理論基礎(chǔ)。應(yīng)用遺傳算法來解決車間調(diào)度問題，在解決的過程中針對工件加工工藝的順序要求，提出了相應(yīng)的遺傳算子及其適應(yīng)度函數(shù)。致 謝在論文即將完成之際,我非常感謝所有幫助過和支持過我的人們。是他的很多建設(shè)性的意見和啟發(fā)，才使得本論文得以完成。王老師嚴(yán)謹(jǐn)求實的治學(xué)作風(fēng)、誨人不倦的師者風(fēng)范時刻激勵著我克服困難，認(rèn)真完成本論文的寫作。他熱情隨和、寬大為懷的個性修養(yǎng)更將使我受益終身! 再次,我非常感謝學(xué)院和系上領(lǐng)導(dǎo)對我的培養(yǎng),感謝所有老師對我們的耐心教導(dǎo)。謹(jǐn)以此文獻給所有關(guān)心、幫助和支持過我的人們!參考文獻[1][M].北京:人民郵電出版社,2000:105125.[2]方紅雨,[J].,12(7):6772. [3]張長水,[J].電子學(xué)報,2002,11(6):4045. [4]張長水,[J].,4(8):5358. [5]何.解Jobshop的調(diào)度問題神經(jīng)網(wǎng)絡(luò)方法[J].自動化學(xué)報1995，2 (8):5661.[13][J].機械工程學(xué)報 ,2002,3(7):7883.[14]席裕庚,[J].控制理論與應(yīng)用,1996,13(6):697708.[15][M].北京:清華大學(xué)出版社,2001:157286. [16][J]. 鞍山鋼鐵學(xué)院學(xué)報,2000,13(2):7277.[17]侯格賢,[J].,14(3):257260.附 錄%945T=[21 71 16 52 26 34 53 21 55 95。 34 64 62 19 92 79 43 54 83 37。 98 44 25 75 43 49 96 77 17 79。 16 59 46 91 43 50 52 59 28 27。 33 37 66 33 26 8 28 89 42 78。M=[ 1 6 9 8 7 2 0 4 3 5。 3 2 8 1 4 9 7 6 0 5。 2 0 5 6 7 1 4 9 3 8。 3 2 0 1 9 8 6 5 4 7。 4 2 8 5 3 7 1 6 9 0。%將機器號+1for i=1:10 S=M(i,:)。 end M(i,:)=S。 %零件個數(shù) 3MNumber=10。%將時間處理下TTemp=T。 end endT=TTemp。 %個體數(shù)目(Number of individuals)MAXGEN= 200。 %代溝(Generation gap)XOVR=。 %變異率gen=0。 %尋優(yōu)結(jié)果的初始值WNumber=0。 %工序個數(shù)end% 初始化群Chrom=zeros(NIND,WNumber)。end%計算目標(biāo)函數(shù)值 [PVal ObjV P]=cal(Chrom,NIND,T,M,PNumber,MNumber,WPNumber)。 %分配適應(yīng)度值(Assign fitness values) SelCh=select(39。, Chrom, FitnV, GGAP)。 %交叉 SelCh=aberrance(SelCh,NIND*GGAP,MUTR,WNumber)。 %計算目標(biāo)函數(shù)值 [Chrom ObjV] =reins(Chrom, SelCh,1, 1, ObjV, ObjVSel)。 %計算目標(biāo)函數(shù)值 gen=gen+1。 %遺傳算法性能跟蹤 trace(2, gen)=sum(ObjV)/length(ObjV)。 Val2=P。 end %記錄最小的工序 if MinVal trace(1,gen) Val1=PVal。 MinVal=trace(1,gen)。 %工序時間 P=Val2。 plot([0,0],[0,0])。hold on。.39。grid。解的變化39。種群均值的變化39。%顯示結(jié)果figure(2)。 a=(mod(val,10))+1。 mText=M(b,a)。 hold on。 mPoint2=PVal(2,i)。 y1