【正文】 通常一個(gè)較低的變異概率足以防止整個(gè)群體中任一位置的基因一直保持不變。 個(gè)體的適應(yīng)度函數(shù) 在遺傳算法中 ,適應(yīng)度是描述個(gè)體 性能的主要指標(biāo)。 對于 n 個(gè)工件 m 機(jī)器問題，一個(gè)染色體 包括個(gè) n*m 個(gè)基因，每個(gè)個(gè)體出現(xiàn)在染色體中 m次，每個(gè)基因不表明具體的工序，而是指上下依賴關(guān)系的工序。對于同一問題可以有不同的編碼表示方法。由于多樣性和復(fù)雜性，通常難以建立完善的理論以指導(dǎo)整個(gè)學(xué)習(xí)過程，從而使傳統(tǒng)尋 優(yōu)技術(shù)的應(yīng)用受到限制，而這恰好是遺傳算法發(fā)揮的長處。該書總結(jié)了遺傳算法研究的主要成果，對 遺傳算法及其應(yīng)用作了全面而系統(tǒng)的論述 。 近年來，遺傳程序設(shè)計(jì)運(yùn)用 遺傳算法的思想自動生成計(jì)算機(jī)程序解決了許多問題，如預(yù)測、分類、符號回歸和圖像處理等，作為一種新技術(shù)它己經(jīng)與遺傳算法并駕齊驅(qū)。經(jīng)過長時(shí)間的遺傳、變異和選擇，生物便逐漸從簡單到復(fù)雜，從低級到高級不斷地進(jìn)化和發(fā)展。由于遺傳算法使用適應(yīng)度值這一信息進(jìn)行搜索，并不需要問題導(dǎo)數(shù)等與問題直接相關(guān)的信息。交換概率太大的時(shí)，易產(chǎn)生更新過快，從而破壞掉高適應(yīng)度個(gè)體的 現(xiàn)象。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個(gè)體保留下來，不參加交叉和變異操作，使之直接進(jìn)入下一代，最終可使遺傳算法以概率 1 收斂于全局最優(yōu)解。要使一個(gè)模式 H 在變異操作過程中不被破壞，就要保證模式 H 中確定位必須保證不變，因此，模式 H 保持不變的概率為 : ()(1 ) 1 ( )OHs m mp p P o H? ? ? ? ? () 上式中 O(H)為該模式的階數(shù)。有關(guān)產(chǎn)生個(gè)體的信息包含在個(gè)體所攜帶的染色體的集合以及染色體編碼的結(jié)構(gòu)之中，這些個(gè)體會很好的適應(yīng)它們的環(huán)境。從生產(chǎn)時(shí)間方面來考慮，其優(yōu)化目標(biāo)有 :最大程度滿足交貨期、最小完成時(shí)間、最小流動時(shí)間和最小等待時(shí)間等。 ( , )ijPi P??，表示 i 工件的所有工序按優(yōu)先順序的排列。用事先給定的“加工路線”表示工件加工時(shí)技術(shù)上的約束 ，即工件的加工工藝過程。由于遺傳算法是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來的高度并行、隨機(jī)、自適應(yīng)搜索算法 ［ 1］ 。 作 者 簽 名： 日 期： 指導(dǎo)教師簽名： 日 期： 使用授權(quán)說明 本人完全了解 大學(xué)關(guān)于收集、保存、使用畢業(yè)設(shè)計(jì)（論文）的規(guī)定，即：按照學(xué)校要求提交畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版本；學(xué)校有權(quán)保存畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學(xué)校可以采用影印、縮印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的前提下，學(xué)校可以公布論文的部分或全部內(nèi)容。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 I 頁 基于 遺傳算法 求解 作業(yè) 車間調(diào)度問題 摘 要 作業(yè) 車間調(diào)度問題 (JSP)簡單來說就是設(shè)備資源優(yōu)化配置問題。 作者簽名： 日 期： 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 IV頁 學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交 的論文是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的研究成果。它特別適合于處理傳統(tǒng)搜索算法解決不好的復(fù)雜和非線性問題。用“加工順序”表示各臺機(jī)器上各個(gè)工件加工的先后順序。不足 12max{ , , }nP P P，那么其空余的位置用 0 填滿。兩個(gè)方向的優(yōu)化目標(biāo)之間彼此不是相互孤立的，其中的許多具體目標(biāo)之間的聯(lián)系很密切，有的相互促進(jìn)，有的相互沖突，也有的毫無聯(lián)系。 大多數(shù)生物體是通過自然選擇和有性生殖這兩種基本過程進(jìn)行演化的。 綜合上面所述，考慮到選擇操作、交換操作和 變異操作對模式的影響，則第 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è)體對，產(chǎn)生新的個(gè)體，實(shí)質(zhì)上是在解空間中進(jìn)行有效搜索。交換概率太小的時(shí)候又容易產(chǎn)生搜索停滯不前的現(xiàn)象。 ，在存在噪聲的情況下，對同一問題利用遺傳算法求解所得的結(jié)果是相似的。 遺傳 算法 是從代表問題可能潛在的解集的一個(gè)種群 （ population） 開始的，而一個(gè)種群則由經(jīng)過基因 （ gene） 編碼的一定數(shù) 目的個(gè)體 (individual)組成。 1996 年，舉行了第 1 次遺傳程序設(shè)計(jì)國際會議，該領(lǐng)域己引起越來越多的相關(guān)學(xué)者們的興趣。同年，美國斯坦福大學(xué)的 Koza 基于自然選擇原則創(chuàng)造性地提出了用層次化的計(jì)算機(jī)程序來表達(dá)問題的遺傳程序設(shè)計(jì) ( geic programming, GP)方法，成功地解決了許多問題。 除了機(jī)器學(xué)習(xí)之外遺傳算法所涉及的主要領(lǐng)域還有自動控制、規(guī)劃設(shè)計(jì)、組合優(yōu)化、圖象處理、信號處理、人工生命、 模式識別，神經(jīng)網(wǎng)絡(luò)、自適應(yīng)控制、生物科學(xué)、系統(tǒng)工程、社會科學(xué)等。由于遺傳算法不能直接處理空間解的數(shù)據(jù)，在解決此車 間調(diào)度問題上把它們轉(zhuǎn)換成遺傳空間的基因按一定結(jié)構(gòu)組成的染色體或個(gè)體，也就是通過編碼將它們表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)。只需改變工序的順序，即可得到不同的調(diào)度結(jié)果，即不同的生產(chǎn)周期。根據(jù)適應(yīng)度的大小 ,對個(gè)體進(jìn)行優(yōu)勝劣汰。但是，變異概率太小則不會產(chǎn)生新個(gè)體 ，抑制早熟現(xiàn)象的能力較差，概率太大則會破壞掉很多較好的模式，使 GA 成為隨機(jī)搜索。 pm 變異概率是加大種群多樣性的重要因素。 初始種群的生成也可以用隨機(jī)方法產(chǎn)生，這是因?yàn)槿后w中的個(gè)體都是由工件的符號組成的，而且工件任意排列總能產(chǎn)生可行調(diào)度 .在下文的舉例驗(yàn)證過程中我們運(yùn)用了隨機(jī)的方法產(chǎn)生初始種群。顯然，這種解碼過程可產(chǎn)生活動調(diào)度。遺傳算法的工作基礎(chǔ)是選擇適當(dāng)?shù)姆椒ū硎緜€(gè)體和問題的解 (作為進(jìn)化的個(gè)體 )。一般的學(xué)習(xí)系統(tǒng)要求具有隨時(shí)間推移逐步調(diào)整有關(guān)參數(shù)或者改變自身結(jié)構(gòu)以更加適應(yīng)環(huán)境，更好達(dá)到目標(biāo)的能力。 1989 年， Holland 的學(xué) 生 出版了專著《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法》 （ Geic Algorithms in Search , Optimization, and Machine Learning） 。目前，這三者之間的比較研究和彼此結(jié)合的探討正形成熱點(diǎn)。通過不斷的選擇，使有利于生存發(fā)展的變異遺傳下去，積累下來，使變異和遺傳向著適應(yīng)環(huán)境的方向發(fā)展。 ，容易形成通用算法程序。 (crossover rate) 交換概率 Pc 用于控制交換操作的頻率。 影響 選擇操作使高適應(yīng)度個(gè)體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。 通過變異操作對個(gè)體串中單個(gè)位置進(jìn)行代碼替換，替換的概率為變異概率 Pm，則該位置不發(fā)生變異的概率為 1Pm。 。調(diào)度問題從生產(chǎn)成本方面來考慮，其優(yōu)化目標(biāo)有 :庫存最少、在制品最少、設(shè)備利用率最高等 。 P（ i， j） 表 示 i工件的第 j 道工序。一個(gè)工件在一臺機(jī)器上的加工程序稱為一道“工序”，相應(yīng)的加工時(shí)間稱為該工序的“加工時(shí)間”。 由于一般車間調(diào)度問題的復(fù)雜性，各種不同的具體問題往往有許多不同的算法來解決，例如經(jīng)典的啟發(fā)式算法，傳統(tǒng)的搜索方法等。對本研究提供過幫助和做出過貢獻(xiàn)的個(gè)人或集體，均已在文中作了明確的說明并表示了謝意。 作業(yè) 車間調(diào)度問題是計(jì)算機(jī)集成制造系統(tǒng) (CIMS)工程中的一個(gè)重要組成部分，它對企業(yè)的生產(chǎn)管理和控制系統(tǒng)有著重要的影響。除了文中特別加以標(biāo)注引用的內(nèi)容外，本論文不包含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫的成果作品。一些學(xué)者們經(jīng)過大量的實(shí)踐證明了 遺傳算法在解決作業(yè)車間調(diào)度問題上 比經(jīng)典的啟發(fā)式算法好，同時(shí)遺傳算法比傳統(tǒng)的搜索技術(shù) 有更強(qiáng)的 優(yōu)越 性，因?yàn)樗粌H能解決某一特定問題，而且可以適應(yīng)不同的問 題形式 ［ 2］ 。車間作業(yè)調(diào)度問題中，每個(gè)工件都有獨(dú)特的加工路線 ［ 5］ 。 1 11 1 1 111121 2 ( 1 )110 0 000in n n n iiiP PPj j j Pj j j p j PPPPP P PPP P P P?????????????? （ ） MJ :機(jī)器順序陣， 此為 12m ax{ , , }nn P P P? 矩陣。 課題研究內(nèi)容及結(jié)構(gòu)安排 本文共分為三 章。自然選擇的原則是適應(yīng)者生存，不適者淘汰。 模式定理 :在遺傳算子選擇、交換、變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式，在子代中將得以指數(shù)級增長。交叉概率太大時(shí)，種群中個(gè)體更新很快，會造成高適應(yīng)度值的個(gè)體很快被破壞掉 。 (mutation rate) 變異概率 Pm。 遺傳算法的缺點(diǎn) ，而不能達(dá)到全局最優(yōu)。每個(gè)個(gè)體實(shí)際上是染色體 (chromosome)帶有特征的實(shí)體。 1967 年， Holland 的學(xué)生 在博士論文中首次提出 “ 遺傳算法 （ Geic Algorithms） ” 一詞。 在歐洲，從 1990 年開始每隔一年舉辦一次 Parallel Problem Solving from Nature 學(xué)術(shù)會議，其中遺傳算法是會議主要內(nèi)容之一。在人工智能研究中，現(xiàn)在還認(rèn)為人們認(rèn)為“遺傳算法、自適應(yīng)系統(tǒng)、細(xì)胞自動機(jī)、混沌理論與人工智能一樣，都是對今后十年的計(jì)算技術(shù)有重大影響的關(guān)鍵技術(shù)”。 目前，調(diào)度問題中主要的遺傳算法編碼方式有以下幾種： （ operationbased representation） 其基本思想是將所有工件的操作進(jìn)行編碼，不同的工件用不同的編碼表示，而同一 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 17 頁 工件的所有操作在染色體中則用相同的編碼表示，其解碼原則是將染色體上的基因按照從左到右的順序解釋為相應(yīng)工件的操作順序，具有相同編碼的基因按照其在整個(gè)染色體中的位置解釋為工件相應(yīng)順序的 操作。 如果染色體位為 [3 2 2 1 1 2 3 1 3 1]，其中 1 表示工件 j1， 2 表示工件 j2， 3 表示工件 j3。適應(yīng)度是驅(qū)動遺傳算法的動力。 遺傳算子的設(shè)計(jì) 選擇操作是對自然界“適者生存 ” 的模擬。交叉概率太大時(shí)，種群中串的更新很快，進(jìn)而會使高適應(yīng)值的個(gè)體很快被破壞掉；概率太小時(shí)，交叉操作很少進(jìn)行，從而會使搜索停滯不前。 這是用遺傳算法解決車間調(diào)度問題的一種初始化群體方法 ［ 13］ ，但是它并不適用于基于操作的編碼方式。這是一種直接對調(diào)度方案進(jìn)行編碼的方式。 參數(shù)編碼 遺傳編碼技術(shù)是實(shí)施遺傳算法的核心。 遺傳算法適合于維數(shù)很高、體積很大、環(huán)境復(fù)雜、問題結(jié)構(gòu)不十分清楚的場合，機(jī)器學(xué)習(xí)就屬于這類情況。 1985 年，在美國召開了第一屆遺傳算法國際會議 （ International Conference on Geic Algorithms ， ICGA） ，并且成立國際遺傳算法學(xué)會 （ International Society of Geic Algorithms ， ISGA） ，以后每兩年舉行一次。 EP 和 ES 幾乎是和遺傳算法同時(shí)獨(dú)立發(fā)展起來的，同遺傳算法一樣，它們也是模擬自然界生物進(jìn)化機(jī)制的智能計(jì)算方法，即同遺傳算法具有相同之處，也有各自的特點(diǎn)。 1859 年，達(dá)爾文根據(jù)長 期對世界各地的考察以及人工選擇的實(shí)驗(yàn)，發(fā)表了 《 物種起源 》 ，系統(tǒng)地提出并建立了以“優(yōu)勝劣汰”、“適者生存”的自然選擇為基礎(chǔ)的進(jìn)化論學(xué)說，根據(jù)他的進(jìn)化論，生物發(fā)展進(jìn)化的原因主要有三個(gè)，就是遺傳、變異和選擇。 ，而非傳統(tǒng)方法的采用目標(biāo)函數(shù)的導(dǎo)數(shù)信息或者求解問題域內(nèi)知識，因此具有普遍適應(yīng)性和可規(guī)模化的特點(diǎn)。種群選擇過大時(shí)，雖然能避免早熟收斂，但是增加了計(jì)算量。種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會增加計(jì)算量，造成收斂時(shí)間太長，表現(xiàn)為收斂速度緩慢。其中一方不具有模式 H 的概率為 1 p(H, t)，當(dāng)兩個(gè)個(gè)體發(fā)生交換時(shí)，如果引起模式 H 的改變，只可能將交換的起始位置選擇在第一個(gè)模式位到最后一個(gè)模式位之間的任何一個(gè)位置上，此時(shí)，使模式 H 生存的概率 Ps，為 : ()1 1scHPPl??? ? () 在交換過程中，可能使兩個(gè)都不具備模式 H 的個(gè)體經(jīng)交換后產(chǎn)生模式 H，故生存概率（ ()1 1c HP l?? ?）只是一個(gè)下界，則有： 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 8 頁 ()1