【正文】 注目的新動(dòng)向 ［ 9］ ：一是基于遺傳算法的機(jī)器學(xué)習(xí)，這一新的研究課題把遺傳算法從歷來(lái)離散的搜索空間 的優(yōu)化搜索算法擴(kuò)展到具有獨(dú)特的規(guī)則生成功能的嶄新的機(jī)器學(xué)習(xí)算法 ［ 10］ 。目前，這三者之間的比較研究和彼此結(jié)合的探討正形成熱點(diǎn)。 Holland 在該書(shū)中系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對(duì)遺傳算法的理論研究和發(fā)展極其重要的模式理論 （ schema theory） 。 1989 年， Holland 的學(xué) 生 出版了專(zhuān)著《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法》 （ Geic Algorithms in Search , Optimization, and Machine Learning） 。 1994 年，他又出版了《遺傳程序設(shè)計(jì)，第二冊(cè) :可重用程序的自動(dòng)發(fā)現(xiàn)》深化了遺傳程序設(shè)計(jì)的研究，使程序設(shè)計(jì)自動(dòng)化展現(xiàn)了新局面。一般的學(xué)習(xí)系統(tǒng)要求具有隨時(shí)間推移逐步調(diào)整有關(guān)參數(shù)或者改變自身結(jié)構(gòu)以更加適應(yīng)環(huán)境，更好達(dá)到目標(biāo)的能力。這對(duì) GA 的實(shí)際應(yīng)用關(guān)系重大 。遺傳算法的工作基礎(chǔ)是選擇適當(dāng)?shù)姆椒ū硎緜€(gè)體和問(wèn)題的解 (作為進(jìn)化的個(gè)體 )。 其基本思想是只對(duì)任務(wù)進(jìn)行編碼，然后按照編碼在染色體中的順序來(lái)以相應(yīng)的優(yōu)先級(jí)別安排任務(wù)。顯然，這種解碼過(guò)程可產(chǎn)生活動(dòng)調(diào)度。 初始種群的生成 在 N 個(gè)工件 M臺(tái)機(jī)器的排序問(wèn)題中，對(duì)每個(gè)機(jī)器的加工存在加工工藝順約束，這個(gè)工藝約束表示為工件的加工順序矩陣： M11 M12 ? M1M M（ J,M） = M21 M22 ? M2M ： ： ： ： () Mn1 Mn2 ? MnM 其中第 J行表示第 J個(gè)工件的機(jī)器順序 .機(jī)器號(hào)為零表示工件加工結(jié)束。 初始種群的生成也可以用隨機(jī)方法產(chǎn)生，這是因?yàn)槿后w中的個(gè)體都是由工件的符號(hào)組成的，而且工件任意排列總能產(chǎn)生可行調(diào)度 .在下文的舉例驗(yàn)證過(guò)程中我們運(yùn)用了隨機(jī)的方法產(chǎn)生初始種群。 STEP4:求出適應(yīng)度函數(shù) F=ti(chorm(n))。 pm 變異概率是加大種群多樣性的重要因素。 第一種交叉算子 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 22 頁(yè) 在用遺傳算法解決作業(yè)車(chē)間調(diào)度問(wèn)題中 ,在對(duì)工序編碼的排序問(wèn)題中 ,交叉算子不。但是，變異概率太小則不會(huì)產(chǎn)生新個(gè)體 ，抑制早熟現(xiàn)象的能力較差，概率太大則會(huì)破壞掉很多較好的模式，使 GA 成為隨機(jī)搜索。目前，如何確定 GA 的最優(yōu)參數(shù)仍舊是一個(gè)公開(kāi)的問(wèn)題，也是研究 GA 的重要課題之一。根據(jù)適應(yīng)度的大小 ,對(duì)個(gè)體進(jìn)行優(yōu)勝劣汰。 STEP2：產(chǎn)生一個(gè)整數(shù)隨機(jī)數(shù) 1=p=N。只需改變工序的順序，即可得到不同的調(diào)度結(jié)果，即不同的生產(chǎn)周期。對(duì)于有三項(xiàng)任務(wù)的調(diào)度問(wèn)題，假設(shè)染色體為 [2 3 1]，則可以解釋為首先安排第二項(xiàng)任務(wù)的所有操作，其次是第三項(xiàng)任務(wù)，最后才輪到第一項(xiàng)任務(wù)。由于遺傳算法不能直接處理空間解的數(shù)據(jù)，在解決此車(chē) 間調(diào)度問(wèn)題上把它們轉(zhuǎn)換成遺傳空間的基因按一定結(jié)構(gòu)組成的染色體或個(gè)體，也就是通過(guò)編碼將它們表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)。與自然界相似，遺傳算法對(duì)待求解問(wèn)題本身一無(wú)所知，它所需要的僅是對(duì)算法所產(chǎn)生的每個(gè)染色體進(jìn)行 評(píng)價(jià)，并基于適應(yīng)度值來(lái)評(píng)價(jià)染色體，使適用性好的染色體比適應(yīng)性差的染色體有更多的繁殖機(jī)會(huì)。 除了機(jī)器學(xué)習(xí)之外遺傳算法所涉及的主要領(lǐng)域還有自動(dòng)控制、規(guī)劃設(shè)計(jì)、組合優(yōu)化、圖象處理、信號(hào)處理、人工生命、 模式識(shí)別，神經(jīng)網(wǎng)絡(luò)、自適應(yīng)控制、生物科學(xué)、系統(tǒng)工程、社會(huì)科學(xué)等。 1993 年，MIT 出版社創(chuàng)刊了新雜志《 Evolutionary Computation》。同年，美國(guó)斯坦福大學(xué)的 Koza 基于自然選擇原則創(chuàng)造性地提出了用層次化的計(jì)算機(jī)程序來(lái)表達(dá)問(wèn)題的遺傳程序設(shè)計(jì) ( geic programming, GP)方法，成功地解決了許多問(wèn)題。同年， Jong 完成了他的博士論文《一 類(lèi)遺傳自適應(yīng)系統(tǒng)的行為分析》 （ An Analysis of the Behavior of a Class of Geic Adaptive System） 。 1996 年，舉行了第 1 次遺傳程序設(shè)計(jì)國(guó)際會(huì)議，該領(lǐng)域己引起越來(lái)越多的相關(guān)學(xué)者們的興趣。二是遺傳算法正日益和神經(jīng)網(wǎng)絡(luò) ［ 12］ 、模糊推理以及混沌理論等其它智能計(jì)算方法相互滲透和結(jié)合，這對(duì)開(kāi)拓 21 世紀(jì)中新的智能計(jì)算技術(shù)將具有重要的意義。 遺傳 算法 是從代表問(wèn)題可能潛在的解集的一個(gè)種群 （ population） 開(kāi)始的，而一個(gè)種群則由經(jīng)過(guò)基因 （ gene） 編碼的一定數(shù) 目的個(gè)體 (individual)組成。而另一種觀點(diǎn)則認(rèn)為交叉過(guò)程的作用只不過(guò)是在種群中推廣變異過(guò)程所造成的更新，對(duì)于初期的種群來(lái)說(shuō)，交叉幾乎等效于 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 12 頁(yè) 一 個(gè)非常大的變異率，而這么大的變異很可能影響進(jìn)化過(guò)程。 ，在存在噪聲的情況下，對(duì)同一問(wèn)題利用遺傳算法求解所得的結(jié)果是相似的。另一種為保優(yōu)策略，首先進(jìn)行純選擇，把目前最優(yōu)個(gè)體直接加入下一代種群中，該策略是為了防止最優(yōu)解的丟失， 但在實(shí)際應(yīng)用中往往采取這兩種選擇策略結(jié)合的方法，并做適當(dāng)?shù)淖冃?。交換概率太小的時(shí)候又容易產(chǎn)生搜索停滯不前的現(xiàn)象。從總體上來(lái)說(shuō)，每代之間所處理的個(gè)體要遠(yuǎn)大于其表面的數(shù)目，這就是遺傳算法獨(dú)特的隱含并行性。 交叉操作用于個(gè)體對(duì)，產(chǎn)生新的個(gè)體，實(shí)質(zhì)上是在解空間中進(jìn)行有效搜索。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 9 頁(yè) 上述結(jié)論并沒(méi)有得到證明，因而被稱(chēng)為假設(shè)。 綜合上面所述，考慮到選擇操作、交換操作和 變異操作對(duì)模式的影響，則第 t 代種群 P(t)經(jīng)過(guò)遺傳操作后下一代種群 P(t+1)具有模式 H 的個(gè)體總數(shù)為 : _( ) ( )( , 1 ) ( , ) ( 1 ) ( 1 ( ) )1cmf H Hm H t m H t P P o Hlf?? ? ? ??? () 該式表示了下述的模式定理。其傳統(tǒng)實(shí)現(xiàn)建立在逐項(xiàng)比較的基礎(chǔ)上，算法復(fù)雜度為 O（ n＾ 2） 。 大多數(shù)生物體是通過(guò)自然選擇和有性生殖這兩種基本過(guò)程進(jìn)行演化的?；涗洷砻魑覀兯^察的復(fù)雜結(jié)構(gòu) 的生命是在相對(duì)短的時(shí)間進(jìn)化而來(lái)的，對(duì)這一點(diǎn)包括生物學(xué)家在內(nèi)的許多人都感到驚奇。兩個(gè)方向的優(yōu)化目標(biāo)之間彼此不是相互孤立的，其中的許多具體目標(biāo)之間的聯(lián)系很密切，有的相互促進(jìn)，有的相互沖突，也有的毫無(wú)聯(lián)系。 (, )jMi j 表示在 i機(jī)器上排在第 j位 加工的工件號(hào)， (, )jMi? 表示 i機(jī)器上依次加工的各工件的排列。不足 12max{ , , }nP P P，那么其空余的位置用 0 填滿。 4. 所有機(jī)器處理的加工類(lèi)型均不同 。用“加工順序”表示各臺(tái)機(jī)器上各個(gè)工件加工的先后順序。而傳統(tǒng)的運(yùn)籌學(xué)方法，即便在較大規(guī)模的基于單目標(biāo)優(yōu)化的靜態(tài)調(diào)度問(wèn)題中也難以有效應(yīng)用 。它特別適合于處理傳統(tǒng)搜索算法解決不好的復(fù)雜和非線性問(wèn)題。此外，有效的調(diào)度方法已經(jīng)成為先進(jìn)制造技術(shù)實(shí)踐的基礎(chǔ)和關(guān)鍵，所以對(duì)它的研究具有重要的理論和實(shí)用價(jià)值。 作者簽名： 日 期： 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 IV頁(yè) 學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交 的論文是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的研究成果。 最后根據(jù)改進(jìn)的編碼進(jìn)行遺 傳算法的設(shè)計(jì)，本文提出了一種求解車(chē)間作業(yè)調(diào)度問(wèn)題的改進(jìn)的遺傳算法，并給出仿真算例表明了該算法的有效性。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 I 頁(yè) 基于 遺傳算法 求解 作業(yè) 車(chē)間調(diào)度問(wèn)題 摘 要 作業(yè) 車(chē)間調(diào)度問(wèn)題 (JSP)簡(jiǎn)單來(lái)說(shuō)就是設(shè)備資源優(yōu)化配置問(wèn)題。以改進(jìn)的自適應(yīng)遺傳算法和混合遺傳算法為調(diào)度算法，設(shè)計(jì)并實(shí)現(xiàn)了作業(yè)車(chē)間調(diào)度系統(tǒng)，詳細(xì)介紹了各個(gè)模塊的功能與操作。 作 者 簽 名： 日 期： 指導(dǎo)教師簽名： 日 期： 使用授權(quán)說(shuō)明 本人完全了解 大學(xué)關(guān)于收集、保存、使用畢業(yè)設(shè)計(jì)（論文）的規(guī)定，即：按照學(xué)校要求提交畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版本；學(xué)校有權(quán)保存畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學(xué)校可以采用影印、縮印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的前提下，學(xué)校可以公布論文的部分或全部?jī)?nèi)容。 作者簽名： 日期： 年 月 日 導(dǎo)師簽名： 日期： 年 月 日 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 V 頁(yè) 目 錄 摘 要 ......................................................................................................................................... I Abstract .................................................................................................................................... II 1 緒論 ......................................................................................................................................1 課題來(lái)源 .....................................................................................................................1 作業(yè)車(chē)間調(diào)度問(wèn)題表述 .............................................................................................1 車(chē)間作業(yè)調(diào)度問(wèn)題研究的假設(shè)條件及數(shù)學(xué)模型 .....................................................2 車(chē)間作業(yè)調(diào)度問(wèn)題研究的假設(shè)條件 ...............................................................2 車(chē)間作業(yè)調(diào)度問(wèn)題的數(shù) 學(xué)模型 .......................................................................3 課題研究?jī)?nèi)容及結(jié)構(gòu)安排 .........................................................................................4 2 遺傳算法相關(guān)理論與實(shí)現(xiàn)技術(shù) ..................................................................................6 自然進(jìn)化與遺傳算法 .................................................................................................6 基本遺傳算法 .............................................................................................................7 遺傳算法的基本思路 .......................................................................................7 遺傳算法的模式定理 .......................................................................................7 遺傳算法的收斂性分析 ...................................................................................9 基本遺傳算法參數(shù)說(shuō)明 ...................................................................