【正文】 所以為了滿足我們的工序編碼的要求 ,本文采用另一種交叉 算子。 其中 ,∑fi 表示指所有個(gè)體適應(yīng)值之和。但是，變異概率太小則不會產(chǎn)生新個(gè)體，抑制早熟現(xiàn)象的能力較差，概率太大則會破壞掉很多較好的模式，使 GA 成為隨機(jī)搜索。 pc 交叉概率用于控制交叉操作的頻率。目前，如何確定 GA 的最優(yōu)參數(shù)仍舊是一個(gè)公開的問題，也是研究 GA 的重要課題之一。 STEP2:chrom（ i） 對應(yīng)相應(yīng)工序的加工機(jī)器為 machiner（ i）。根據(jù)適應(yīng)度的大小 ,對個(gè)體進(jìn)行優(yōu)勝劣汰。重復(fù) STEP1， STEP2， STEP3， STEP4，直到種群滿。 STEP2：產(chǎn)生一個(gè)整數(shù)隨機(jī)數(shù) 1=p=N。可以看出工件 j2 的所有工序都用相同的符號 2 來命名，并且根據(jù)它出 現(xiàn)在染色體中的順序加以解釋，工件的工序和加工機(jī)器的對應(yīng)關(guān)系如下 所示。只需改變工序的順序，即可得到不同的調(diào)度結(jié)果，即不同的生產(chǎn)周期。 前面兩種編碼方式比較復(fù)雜，下面我們用基于操作的編碼方式來解此車間調(diào)度問題： 把調(diào)度編碼為工 序的序列，每個(gè)基因代表一道工序，給所有同一工件的工序指定相同的符號，其解碼原則是將染色體上得基因按照從左到右得順序解釋為任務(wù)相應(yīng)順序的操作。對于有三項(xiàng)任務(wù)的調(diào)度問題，假設(shè)染色體為 [2 3 1]，則可以解釋為首先安排第二項(xiàng)任務(wù)的所有操作，其次是第三項(xiàng)任務(wù)，最后才輪到第一項(xiàng)任務(wù)。 圖 Gantte 圖 t 12 9 6 J3 J3 J3 J1 J1 J1 J2 J2 J2 t t 1 M1 10 7 3 4 M3 M2 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 18 頁 （ jobbased representation） 將每個(gè)染色體用 n個(gè)代表工件的基因組成，是所有工件的一個(gè)排列。由于遺傳算法不能直接處理空間解的數(shù)據(jù)，在解決此車間調(diào)度問題上把它們轉(zhuǎn)換成遺傳空間的基因按一定結(jié)構(gòu)組成的染色體或個(gè)體，也就是通過編碼將它們表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)。 圖 設(shè)備死鎖示意圖 在圖 中，分屬工件 1 和工件 2 的總共四個(gè)工序都處于循環(huán)等待其前面工序或前道工序結(jié)束加工的狀態(tài)之中，從而使設(shè)備 1 和設(shè)備 2 處于空轉(zhuǎn) 狀態(tài)，即產(chǎn)生了所謂的死鎖現(xiàn)象。與自然界相似，遺傳算法對待求解問題本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個(gè)染色體進(jìn)行評價(jià)，并基于適應(yīng)度值來評價(jià)染色體，使適用性好的染色體比適應(yīng)性差的染色體有更多的繁殖機(jī)會。與此同時(shí)，理論方面同樣有大量工作要做，例如：控制參數(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 Geic Algorithms） ，其中包括了遺傳算法在工程技術(shù)和社會生活中的大量應(yīng)用實(shí)例。同年，美國斯坦福大學(xué)的 Koza 基于自然選擇原則創(chuàng)造性地提出了用層次化的計(jì)算機(jī)程序來表達(dá)問題的遺傳程序設(shè)計(jì) ( geic programming, GP)方法，成功地解決了許多問題。 進(jìn)入八十年代，遺傳算法迎來了興盛發(fā)展時(shí)期，無論是理論研究還是應(yīng)用研究都成了十分熱門的課題。同年， Jong 完成了他的博士論文《一類遺傳自適應(yīng)系統(tǒng)的行為分析》 （ An Analysis of the Behavior of a Class of Geic 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ù)問題域中個(gè)體的適應(yīng)度 （ fitness） 大小選擇 （ selection）個(gè)體，并借助于自然遺傳學(xué)的遺傳算子（ geic operators） 進(jìn)行組合交叉 （ crossover）和變異 （ mutation） ，產(chǎn)生出代表新的解集的種群。 遺傳 算法 是從代表問題可能潛在的解集的一個(gè)種群 （ population） 開始的，而一個(gè)種群則由經(jīng)過基因 （ gene） 編碼的一定數(shù)目的個(gè)體 (individual)組成。 遺傳算法的 進(jìn)展 地球上自出現(xiàn)生命至今已有 30 多億年的歷史，從低級生物到高級生命再至擁有智慧的人類，這是一個(gè)漫長的生物進(jìn)化過程。而另一種觀點(diǎn)則認(rèn)為交叉過程的作用只不過是在種群中推廣變異過程所造成的更新，對于初期的種群來說，交叉幾乎等效于 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 12 頁 一個(gè)非常大的變異率，而這么大的變異很可能影響進(jìn)化過程。其中一種是所謂觸發(fā)式超級突變，就是當(dāng)染色體群體的質(zhì)量下降 (彼此的區(qū)別減少 )時(shí)增加突變概率 。 ，在存在噪聲的 情況下，對同一問題利用遺傳算法求解所得的結(jié)果是相似的。 ，而不是對參數(shù)本身，因此遺傳算法具有靈活性高的特點(diǎn)。另一種為 保優(yōu)策略，首先進(jìn)行純選擇，把目前最優(yōu)個(gè)體直接加入下一代種群中，該策略是為了防止最優(yōu)解的丟失， 但在實(shí)際應(yīng)用中往往采取這兩種選擇策略結(jié)合的方法，并做適當(dāng)?shù)淖冃汀Ｈ绻儺惛怕侍蟮臅r(shí)，遺傳算法易變成隨機(jī)搜索，如果變異概率太小，則不能產(chǎn)生新個(gè)體，不利于種群的 多樣性。交換概率太小的時(shí)候又容易產(chǎn)生搜索停滯不前的現(xiàn)象。 (population size) 種群數(shù)目的多少直接影響到遺傳算法的優(yōu)化性能和效率，種群選擇太小時(shí)，不能提供足夠多的個(gè)體，致 使算法性能較差，易產(chǎn)生早熟收斂，甚至不能得到可行解。從總體上來說， 每代之間所處理的個(gè)體要遠(yuǎn)大于其表面的數(shù)目，這就是遺傳算法獨(dú)特的隱含并行性。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會使遺傳算法成為隨機(jī)搜索算法。 交叉操 作用于個(gè)體對，產(chǎn)生新的個(gè)體，實(shí)質(zhì)上是在解空間中進(jìn)行有效搜索。 通常，種群太小則不能提供足夠的采樣點(diǎn)，以致算法性能很差 。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 9 頁 上述結(jié)論并沒有得到證明，因而被稱為假設(shè)。這些模式在遺傳中很重要，稱為基因塊。 綜合上面所述，考慮到選擇操作、交換操作和變異操作對模式的影響，則第 t 代種群 P(t)經(jīng)過遺傳操作后下一代種群 P(t+1)具有模式 H 的個(gè)體總數(shù)為 : _( ) ( )( , 1 ) ( , ) ( 1 ) ( 1 ( ) )1cmf H Hm H t m H t P P o Hlf?? ? ? ??? () 該式表示了下述的模式定理。但是如果其中一方個(gè)體不具有模式 H，則有可能會引起另一個(gè)個(gè)體模式的改變。其傳統(tǒng)實(shí)現(xiàn)建立在逐項(xiàng)比較的基礎(chǔ)上，算法復(fù)雜度為 O（ n＾ 2） 。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 7 頁 基本 遺傳算法 遺傳算法的基本思路 ； 將求解空間中的每一個(gè)點(diǎn)進(jìn)行編碼，并從求解空間中任選 N個(gè)點(diǎn)組成初始群體； 。 大多數(shù)生物體是通過自然選擇 和有性生殖這兩種基本過程進(jìn)行演化的。 ，哪些適應(yīng)性好地個(gè)體的染色體經(jīng)常比差的個(gè)體的染色體有更多的繁殖機(jī)會?；涗洷砻魑覀兯^察的復(fù)雜結(jié)構(gòu)的生命是在相對短的時(shí)間進(jìn)化而來的，對這一點(diǎn)包括生物學(xué)家在內(nèi)的許多人都感到驚奇。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 6 頁 2 遺傳算法相關(guān)理論與實(shí)現(xiàn)技術(shù) 遺傳算法 (Geic Algorithm, GA)是一種基于自然群體遺傳演化機(jī)制的高效探索算法，它是美國學(xué)者 Holland 于 1975 年首先提出來的 ［ 7］ 。兩個(gè)方向的優(yōu)化目標(biāo)之間彼此不是相互孤立的，其中的許多具體目標(biāo)之間的聯(lián)系很密切，有的相互促進(jìn)，有的相互沖突，也有的毫無聯(lián)系。即 jM? 使得目標(biāo) 函數(shù) ()jfM 取值最小 (或最大 )，且與 MJ 相容，則稱 jM? 為車間作業(yè)調(diào)度問題在此目標(biāo)函數(shù)下的最優(yōu)解。 (, )jMi j 表示在 i機(jī)器上排在第 j位 加工的工件號， (, )jMi? 表示 i機(jī)器上依次加工的各工件的排列。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 4 頁 1 11 2 1 1111 2 1 ( 1 )1 1100 000ijPjjjpj j n j Pn n n iiiP PPP P PMP P P PPPPM M MJM M M M?????????????? （ ） T:加工時(shí)間陣，此為 12m ax{ , , }nn P P P? 矩陣。不足 12max{ , , }nP P P，那么其空余的位置用 0 填滿。 假設(shè)有 n個(gè)工件，要在 m臺機(jī)器上加工，每個(gè)工件有 Pi 道工序，每臺機(jī)器上總共要加工 Lj 道工序。 4. 所有機(jī)器處理的加工類型均不同 。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 3 頁 (機(jī)器 )獨(dú)占性約束 :任一臺機(jī)器每次只能加工一個(gè)工件，且一旦開工就不能中斷，反映了加工隊(duì)列中工件間的時(shí)序關(guān)系。用“加工順序”表示各臺機(jī)器上各個(gè)工件加工的先后順序。而在本文中，為了研究方便，我們將這項(xiàng) 任務(wù)限定為加工一批工件。而傳統(tǒng)的運(yùn)籌學(xué)方法，即便在較大規(guī)模的基于單目標(biāo)優(yōu)化的靜態(tài)調(diào)度問題中也難以有效應(yīng)用。 2. 不同工件的加工工序可以不同； 3. 所有工件的工序數(shù)不大于設(shè)備數(shù)； 4. 每道工序必須在指定的某種設(shè)備上加工； 5. 任何作業(yè)沒有搶先加工的優(yōu)先權(quán)； 6. 在作業(yè)優(yōu)化過程中既沒有新的工件加入也沒有取消的工件； 調(diào)度問題具有相當(dāng)?shù)碾y度，目前調(diào)度問題的理論研究成果主要在 jobshop 問題為代表的基于最小完工時(shí)間的調(diào)度問題上。它特別適合于處理傳統(tǒng)搜索算法解決不好的復(fù)雜和非線性問題。 雖然對其研究已有幾十年的 歷史 但至今尚未形成一套系統(tǒng)的方法和理論，理論研究與實(shí)際應(yīng)用之間還存在著較大距離。此外，有效的調(diào)度方法已經(jīng)成為先進(jìn)制造技術(shù)實(shí)踐的基礎(chǔ)和關(guān)鍵，所以對它的研究具有重要的理論和實(shí)用價(jià)值。 關(guān)鍵詞 ： 作業(yè) 車間調(diào)度； 遺傳算法；改進(jìn)染色體編碼 ； 生產(chǎn)周期 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 II 頁 Solving jopshop scheduling problem based on geic algorithm Abstract Simply speaking, the job shop scheduling problem(JSP) is the equipment resources optimization question. Job Shop Scheduling Problem as an important part of Computer IntegratedManufacturing System (CIMS) engineering is indispensable, and has vital effect onproduction management and control system. In the petion ecvironment nowadays, how touse the assignments qu