【正文】 y1=。 hold on。 a=(mod(val,10))+1。種群均值的變化39。grid。hold on。 %工序時間 P=Val2。 end %記錄最小的工序 if MinVal trace(1,gen) Val1=PVal。 %遺傳算法性能跟蹤 trace(2, gen)=sum(ObjV)/length(ObjV)。 %計(jì)算目標(biāo)函數(shù)值 [Chrom ObjV] =reins(Chrom, SelCh,1, 1, ObjV, ObjVSel)。, Chrom, FitnV, GGAP)。end%計(jì)算目標(biāo)函數(shù)值 [PVal ObjV P]=cal(Chrom,NIND,T,M,PNumber,MNumber,WPNumber)。 %尋優(yōu)結(jié)果的初始值WNumber=0。 %代溝(Generation gap)XOVR=。 end endT=TTemp。 %零件個數(shù) 3MNumber=10。%將機(jī)器號+1for i=1:10 S=M(i,:)。 3 2 0 1 9 8 6 5 4 7。 3 2 8 1 4 9 7 6 0 5。 33 37 66 33 26 8 28 89 42 78。 98 44 25 75 43 49 96 77 17 79。.解Jobshop的調(diào)度問題神經(jīng)網(wǎng)絡(luò)方法[J].自動化學(xué)報1995，2 (8):5661.[13][J].機(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。謹(jǐn)以此文獻(xiàn)給所有關(guān)心、幫助和支持過我的人們!參考文獻(xiàn)[1][M].北京:人民郵電出版社,2000:105125.[2]方紅雨,[J].,12(7):6772. [3]張長水,[J].電子學(xué)報,2002,11(6):4045. [4]張長水,[J].,4(8):5358. [5]何王老師嚴(yán)謹(jǐn)求實(shí)的治學(xué)作風(fēng)、誨人不倦的師者風(fēng)范時刻激勵著我克服困難，認(rèn)真完成本論文的寫作。致 謝在論文即將完成之際,我非常感謝所有幫助過和支持過我的人們。在當(dā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)域存在的問題及發(fā)展趨勢，為論文的研究奠定了理論基礎(chǔ)。并且以四個工件四個機(jī)器問題進(jìn)行舉例,說明了用遺傳算法解決車間調(diào)度問題的可行性。虛線代表種群均值的變化。選擇變異位置為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)。遺傳算法和生物的進(jìn)化一樣，在進(jìn)化的過程中，由于某些原因染色體的個別基因會發(fā)生變異，一般情況下變異后的個體比以前的優(yōu)，但有些變異不一定會產(chǎn)生優(yōu)秀的個體。而染色體F1的適應(yīng)度值最小，表示加工完零件所需時間最短［16］。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}將這四個染色體作為種群的第一代。遺傳算子也是遺傳算法解決問題的關(guān)鍵所在。本研究以迭代次數(shù)作為是否終止的條件，從而控制優(yōu)化過程。所以采用上述變異算子是不可行的。例如，如果X1，X2的基因鏈碼分別是X1 1 3 8 5 2 7 6 4X2 3 2 4 1 8 7 6 5交叉點(diǎn)位于第三個基因之后，那么從中剔除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這種交叉算子在基于操作的染色體編碼時并不適用，提出來和第一種算子進(jìn)行比較。所以為了滿足我們的工序編碼的要求,本文采用另一種交叉算子。其中,∑fi表示指所有個體適應(yīng)值之和。但是，變異概率太小則不會產(chǎn)生新個體，抑制早熟現(xiàn)象的能力較差，概率太大則會破壞掉很多較好的模式，使GA成為隨機(jī)搜索。交叉概率用于控制交叉操作的頻率。目前，如何確定GA的最優(yōu)參數(shù)仍舊是一個公開的問題，也是研究GA的重要課題之一。STEP2:chrom（i）對應(yīng)相應(yīng)工序的加工機(jī)器為machiner（i）。根據(jù)適應(yīng)度的大小,對個體進(jìn)行優(yōu)勝劣汰。重復(fù)STEP1，STEP2，STEP3，STEP4，直到種群滿。STEP2：產(chǎn)生一個整數(shù)隨機(jī)數(shù)1=p=N?？梢钥闯龉ぜ2的所有工序都用相同的符號2來命名，并且根據(jù)它出現(xiàn)在染色體中的順序加以解釋，工件的工序和加工機(jī)器的對應(yīng)關(guān)系如下所示。只需改變工序的順序，即可得到不同的調(diào)度結(jié)果，即不同的生產(chǎn)周期。前面兩種編碼方式比較復(fù)雜，下面我們用基于操作的編碼方式來解此車間調(diào)度問題： 把調(diào)度編碼為工序的序列，每個基因代表一道工序，給所有同一工件的工序指定相同的符號，其解碼原則是將染色體上得基因按照從左到右得順序解釋為任務(wù)相應(yīng)順序的操作。對于有三項(xiàng)任務(wù)的調(diào)度問題，假設(shè)染色體為[2 3 1]，則可以解釋為首先安排第二項(xiàng)任務(wù)的所有操作，其次是第三項(xiàng)任務(wù)，最后才輪到第一項(xiàng)任務(wù)。t1296J3J3J3J1J1J1J2J2J2tt1M110734M3M2 Gantte圖（jobbased representation）將每個染色體用n個代表工件的基因組成，是所有工件的一個排列。由于遺傳算法不能直接處理空間解的數(shù)據(jù)，在解決此車間調(diào)度問題上把它們轉(zhuǎn)換成遺傳空間的基因按一定結(jié)構(gòu)組成的染色體或個體，也就是通過編碼將它們表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)。 設(shè)備死鎖示意圖，分屬工件1和工件2的總共四個工序都處于循環(huán)等待其前面工序或前道工序結(jié)束加工的狀態(tài)之中，從而使設(shè)備1和設(shè)備2處于空轉(zhuǎn)狀態(tài)，即產(chǎn)生了所謂的死鎖現(xiàn)象。與自然界相似，遺傳算法對待求解問題本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個染色體進(jìn)行評價，并基于適應(yīng)度值來評價染色體，使適用性好的染色體比適應(yīng)性差的染色體有更多的繁殖機(jī)會。與此同時，理論方面同樣有大量工作要做，例如：控制參數(shù)的選擇；交換和突變這兩類最重要的算子的確切作用；并行GA和分布式GA的研究。除了機(jī)器學(xué)習(xí)之外遺傳算法所涉及的主要領(lǐng)域還有自動控制、規(guī)劃設(shè)計(jì)、組合優(yōu)化、圖象處理、信號處理、人工生命、模式識別，神經(jīng)網(wǎng)絡(luò)、自適應(yīng)控制、生物科學(xué)、系統(tǒng)工程、社會科學(xué)等。遺傳算法主要應(yīng)用在機(jī)器學(xué)習(xí)中。1993年，MIT出版社創(chuàng)刊了新雜志《Evolutionary Computation》。1991年，《遺傳算法手冊》（Handbook of Genetic Algorithms），其中包括了遺傳算法在工程技術(shù)和社會生活中的大量應(yīng)用實(shí)例。同年，美國斯坦福大學(xué)的Koza基于自然選擇原則創(chuàng)造性地提出了用層次化的計(jì)算機(jī)程序來表達(dá)問題的遺傳程序設(shè)計(jì)( genetic programming, GP)方法，成功地解決了許多問題。進(jìn)入八十年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應(yīng)用研究都成了十分熱門的課題。同年， Jong完成了他的博士論文《一類遺傳自適應(yīng)系統(tǒng)的行為分析》（An Analysis of the Behavior of a Class of Genetic Adaptive System）。1975年是遺傳算法研究歷史上十分重要的一年。 1996年，舉行了第1次遺傳程序設(shè)計(jì)國際會議，該領(lǐng)域己引起越來越多的相關(guān)學(xué)者們的興趣。所謂人工生命即是用計(jì)算機(jī)模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應(yīng)、進(jìn)化和免疫等現(xiàn)象是人工生命的重要研究對象，而遺傳算法在這方面將會發(fā)揮一定的作用，五是遺傳算法和進(jìn)化規(guī)劃（Evolution Programming,EP）以及進(jìn)化策略（Evolution Strategy,ES）等進(jìn)化計(jì)算理論日益結(jié)合。二是遺傳算法正日益和神經(jīng)網(wǎng)絡(luò)［12］、模糊推理以及混沌理論等其它智能計(jì)算方法相互滲透和結(jié)合，這對開拓21世紀(jì)中新的智能計(jì)算技術(shù)將具有重要的意義。由于仿照基因編碼的工作很復(fù)雜，我們往往進(jìn)行簡化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應(yīng)度（fitness）大小選擇（selection）個體，并借助于自然遺傳學(xué)的遺傳算子（genetic operators）進(jìn)行組合交叉（crossover）和變異（mutation），產(chǎn)生出代表新的解集的種群。 遺傳算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經(jīng)過基因（gene）編碼的一定數(shù)目的個體(individual)組成。 遺傳算法的進(jìn)展地球上自出現(xiàn)生命至今已有30多億年的歷史，從低級生物到高級生命再至擁有智慧的人類，這是一個漫長的生物進(jìn)化過程。而另一種觀點(diǎn)則認(rèn)為交叉過程的作用只不過是在種群中推廣變異過程所造成的更新，對于初期的種群來說，交叉幾乎等效于一個非常大的變異率，而這么大的變異很可能影響進(jìn)化過程。其中一種是所謂觸發(fā)式超級突變，就是當(dāng)染色體群體的質(zhì)量下降(彼此的區(qū)別減少)時增加突變概率。，在存在噪聲的情況下，對同一問題利用遺傳算法求解所得的結(jié)果是相似的。，而不是對參數(shù)本身，因此遺傳算法具有靈活性高的特點(diǎn)。另一種為保優(yōu)策略，首先進(jìn)行純選擇，把目前最優(yōu)個體直接加入下一代種群中，該策略是為了防止最優(yōu)解的丟失，但在實(shí)際應(yīng)用中往往采取這兩種選擇策略結(jié)合的方法，并做適當(dāng)?shù)淖冃汀Ｈ绻儺惛怕侍蟮臅r，遺傳算法易變成隨機(jī)搜索，如果變異概率太小，則不能產(chǎn)生新個體，不利于種群的多樣性。交換概率太小的時候又容易產(chǎn)生搜索停滯不前的現(xiàn)象。(population size)種群數(shù)目的多少直接影響到遺傳算法的優(yōu)化性能和效率，種群選擇太小時，不能提供足夠多的個體，致使算法性能較差，易產(chǎn)生早熟收斂，甚至不能得到可行解。從總體上來說，每代之間所處理的個體要遠(yuǎn)大于其表面的數(shù)目，這就是遺傳算法獨(dú)特的隱含并行性。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會使遺傳算法成為隨機(jī)搜索算法。交叉操作用于個體對，產(chǎn)生新的個體，實(shí)質(zhì)上是在解空間中進(jìn)行有效搜索。通常，種群太小則不能提供足夠的采樣點(diǎn)，以致算法性能很差。上述結(jié)論并沒有得到證明，因而被稱為假設(shè)。這些模式在遺傳中很重要，稱為基因塊。綜合上面所述，考慮到選擇操作、交換操作和變異操作對模式的影響，則第t代種群P(t)經(jīng)過遺傳操作后下一代種群P(t+1)具有模式H的個體總數(shù)為: ()該式表示了下述的模式定理。但是如果其中一方個體不具有模式H，則有可能會引起另一個個體模式的改變。其傳統(tǒng)實(shí)現(xiàn)建立在逐項(xiàng)比較的基礎(chǔ)上，算法復(fù)雜度為O（n＾2）。 基本遺傳算法 遺傳算法的基本思路；，并從求解空間中任選N個點(diǎn)組成初始群體；。大多數(shù)生物體是通過自然選擇和有性生殖這兩種基本過程進(jìn)行演化的。，哪些適應(yīng)性好地個體的染色體經(jīng)常比差的個體的染色體有更多的繁殖機(jī)會。化石記錄表明我們所觀察的復(fù)雜結(jié)構(gòu)的生命是在相對短的時間進(jìn)化而來的，對這一點(diǎn)包括生物學(xué)家在內(nèi)的許多人都感到驚奇。2 遺傳算法相關(guān)理論與實(shí)現(xiàn)技術(shù)遺傳算法(Genetic Algorithm, GA)是一種基于自然群體遺傳演化機(jī)制的高效探索算法，它是美國學(xué)者Holland于1975年首先提出來的［7］。兩個方向的優(yōu)化目標(biāo)之間彼此不是相互孤立的，其中的許多具體目標(biāo)之間的聯(lián)系很密切，有的相互促進(jìn)，有的相互沖突，也有的毫無聯(lián)系。即使得目標(biāo)函數(shù)取值最小(或最大)，且與相容，則稱為車間作業(yè)調(diào)度問題在此目標(biāo)函數(shù)下的最優(yōu)解。表示在i機(jī)器上排在第j位加工的工件號，表示i機(jī)器上依次加工的各工件的排列。 （）T:加工時間陣，此為矩陣。不足，那么其空余的位置用0填滿。假設(shè)有n個工件，要在m臺機(jī)器上加工，每個工件有Pi道工序，每臺機(jī)器上總共要加工Lj道工序。4. 所有機(jī)器處理的加工類型均不同。(機(jī)器)獨(dú)占性約束:任一臺機(jī)器每次只能加工一個工件，且一旦開工就不能中斷，反映了加工隊(duì)列中工件間的時序關(guān)系。用“加工順序”表示各臺機(jī)器上各個工件加工的先后順序。而在本文中，為了研究方便，我們將這項(xiàng)任務(wù)限定為加工一批工件。而傳統(tǒng)的運(yùn)籌學(xué)方法，即便在較大規(guī)模的基于單目標(biāo)優(yōu)化的靜態(tài)調(diào)度問題中也難以有效應(yīng)用。2. 不同工件的加工工序可以不同