【正文】 很少進行，從而會使搜索停滯不前，造成算法的不收斂。 交叉操作用于個體對，產(chǎn)生新的個體，實質(zhì)上是在解空間中進行有效搜索。 影響 選擇操作使高適應(yīng)度個體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。 通常，種群太小則不能提供足夠的采樣點，以致算法性能很差 。 遺傳算法的收斂性分析 遺傳算法要實現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 9 頁 上述結(jié)論并沒有得到證明，因而被稱為假設(shè)。 模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在 。這些模式在遺傳中很重要，稱為基因塊。 模式定理保證了較優(yōu)的模式 (遺傳算法的較優(yōu)解 )的數(shù)目呈指數(shù)增長，為解釋遺傳算法機理提供了數(shù)學(xué)基礎(chǔ)。 綜合上面所述，考慮到選擇操作、交換操作和 變異操作對模式的影響，則第 t 代種群 P(t)經(jīng)過遺傳操作后下一代種群 P(t+1)具有模式 H 的個體總數(shù)為 : _( ) ( )( , 1 ) ( , ) ( 1 ) ( 1 ( ) )1cmf H Hm H t m H t P P o Hlf?? ? ? ??? () 該式表示了下述的模式定理。 通過變異操作對個體串中單個位置進行代碼替換，替換的概率為變異概率 Pm，則該位置不發(fā)生變異的概率為 1Pm。但是如果其中一方個體不具有模式 H， 則有可能會引起另一個個體模式的改變。 交換操作是有規(guī)則的信息交換，它能創(chuàng)建新的模式結(jié)構(gòu)，但又最低限度地破壞選擇操作過程所選擇的高適應(yīng)度的模式。其傳統(tǒng)實現(xiàn)建立在逐項比較的基礎(chǔ)上，算法復(fù)雜度為 O（ n＾ 2） 。 遺傳算法的 模式定理 選擇操作是遺傳算法中體現(xiàn)“適者生存”的關(guān)鍵一環(huán)，它能控制高適應(yīng)度的模式成指數(shù)級增長。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 7 頁 基本 遺傳算法 遺傳算法的基本思路 ； 將求解空間中的每一個點進行編碼，并從求解空間中任選 N個點組成初始群體； 。自然選擇決定了群體中那些個個體能存活并繁殖，有性生殖保證了后代基因中的混合與重組。 大多數(shù)生物體是通過自然選擇和有性生殖這兩種基本過程進行演化的。 。 ，哪些適應(yīng)性好地個體的染色體經(jīng)常比差的個體的染色體有更多的繁殖機會。進化是發(fā)生在編碼染色體上，通過對染色體的譯碼部分生成生物體，但下面幾個關(guān)于進化理論的一般特性已被廣大人們所接受?；涗洷砻魑覀兯^察的復(fù)雜結(jié)構(gòu) 的生命是在相對短的時間進化而來的，對這一點包括生物學(xué)家在內(nèi)的許多人都感到驚奇。它將問題域中的可能解看作是群體的一個個體或染色體，并將每一個體編碼成符號串形式，對群體反復(fù)進行基于遺傳學(xué)的操作（遺傳，交叉和變異），根據(jù)預(yù)定的目標(biāo)適應(yīng)度函數(shù)對每個個體進行評價，依據(jù)適者生存，優(yōu)勝劣汰的進化規(guī)則，不斷得到更優(yōu)的群體，同時以全局并行搜索方式來搜索優(yōu)化群體中的最優(yōu)個體，求得滿足要求的最優(yōu)解。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 6 頁 2 遺傳算法相關(guān)理論與實現(xiàn)技術(shù) 遺傳算法 (Geic Algorithm, GA)是一種基于自然群體遺傳演化機制的高效探索算法，它是美國學(xué)者 Holland 于 1975 年首先提出來的 ［ 7］ 。第一章簡要介紹了車間調(diào)度問題和求解調(diào)度問題的基本方法 ；第 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 5 頁 二章介紹了遺傳算法的基本理論；第三章用遺傳算法來解決車間調(diào)度問題 ,其中介紹了常用的幾種編碼方式 ,在比較的情況下提出本文主要用基于操作的編碼方式 .還有提出了幾種主要的遺傳算子。兩個方向的優(yōu)化目標(biāo)之間彼此不是相互孤立的，其中的許多具體目標(biāo)之間的聯(lián)系很密切，有的相互促進，有的相互沖突，也有的毫無聯(lián)系。調(diào)度問題從生產(chǎn)成本方面來考慮，其優(yōu)化目標(biāo)有 :庫存最少、在制品最少、設(shè)備利用率最高等 。即 jM? 使得目標(biāo)函數(shù) ()jfM 取值最小 (或最大 )，且與 MJ 相容，則稱 jM? 為車間作業(yè)調(diào)度問題在此目標(biāo)函數(shù)下的最優(yōu)解。事實上，工件排列陣就是調(diào)度的一種表示形式。 (, )jMi j 表示在 i機器上排在第 j位 加工的工件號， (, )jMi? 表示 i機器上依次加工的各工件的排列。同樣地，如果某工件的工序數(shù)不足 12max{ , , }nP P P，那么其空余的位置用 0 填滿 。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 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:加工時間陣，此為 12m ax{ , , }nn P P P? 矩陣。 MJ （ i， j）表示 i工件的第 j 道工序的機器號， (, )MJi? 表示 i工件的所有工序按優(yōu)先順序加工的各機器號的排列。不足 12max{ , , }nP P P，那么其空余的位置用 0 填滿。 P（ i， j） 表 示 i工件的第 j 道工序。 假設(shè)有 n個工件，要在 m臺機器上加工，每個工件有 Pi 道工序，每臺機器上總共要加工 Lj 道工序。 6. 緩沖區(qū)容量為無窮大。 4. 所有機器處理的加工類型均不同 。 2. 不考慮工件加工的優(yōu)先權(quán)，即工件之間沒有優(yōu)先約束關(guān)系限制的 。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 3 頁 (機器 )獨占性約束 :任一臺機器每次只能加工一個工件，且一旦開工就不能中斷，反映了加工隊列中工件間的時序關(guān)系。它所要解決的問題就是確定每臺機器上不同工件的加工順序，以及每個工件的所有工序的起始加工時間，以最優(yōu)化某個性能指標(biāo)。用“加工順序”表示各臺機器上各個工件加工的先后順序。一個工件在一臺機器上的加工程序稱為一道“工序”，相應(yīng)的加工時間稱為該工序的“加工時間”。而在本文中，為了研究方便，我們將這項任務(wù)限定為加工一批工件。 車間作業(yè)是指利用車間資源 (如機床、刀具、夾具等 )完成的某項任務(wù)。而傳統(tǒng)的運籌學(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 問題為代表的基于最小完工時間的調(diào)度問題上。 作業(yè) 車間調(diào)度問題表述 作業(yè)車間調(diào)度（ jobshop）問題可以表述為：設(shè)有 N個工件在 M臺機器上加工，根據(jù)工件加工工藝的要求，每個工件使用 機器的順序及其每道工序所花時間已給定，調(diào)度問題的目標(biāo)就是如何選擇加工順序使得總的加工時間最短最優(yōu)。它特別適合于處理傳統(tǒng)搜索算法解決不好的復(fù)雜和非線性問題。 由于一般車間調(diào)度問題的復(fù)雜性，各種不同的具體問題往往有許多不同的算法來解決，例如經(jīng)典的啟發(fā)式算法，傳統(tǒng)的搜索方法等。 雖然對其研究已有幾十年的 歷史 但至今尚未形成一套系統(tǒng)的方法和理論，理論研究與實際應(yīng)用之間還存在著較大距離。遺傳算法的蓬勃發(fā)展正體現(xiàn)了科學(xué)發(fā)展的這一特點和趨勢。此外，有效的調(diào)度方法已經(jīng)成為先進制造技術(shù)實踐的基礎(chǔ)和關(guān)鍵，所以對它的研究具有重要的理論和實用價值。 涉密論文按學(xué)校規(guī)定處理。 作者簽名： 日期： 年 月 日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國家有關(guān)部門或機構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。對本文的研究做出重要貢獻的個人和集體，均已在文中以明確方式標(biāo)明。 作者簽名： 日 期： 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 IV頁 學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所呈交 的論文是本人在導(dǎo)師的指導(dǎo)下獨立進行研究所取得的研究成果。對本研究提供過幫助和做出過貢獻的個人或集體，均已在文中作了明確的說明并表示了謝意。 production cycl 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 III 頁 畢業(yè)設(shè)計（論文）原創(chuàng)性聲明和使用授權(quán)說明 原創(chuàng)性聲明 本人鄭重承諾：所呈交的畢業(yè)設(shè)計（論文），是我個人在指導(dǎo)教師的指導(dǎo)下進行的研究工作及取得的成果。 geic algorithm。 最后根據(jù)改進的編碼進行遺 傳算法的設(shè)計，本文提出了一種求解車間作業(yè)調(diào)度問題的改進的遺傳算法，并給出仿真算例表明了該算法的有效性。該算法是將 sigmoid 函數(shù)的變形函數(shù)應(yīng)用到自適應(yīng)遺傳算法中，并將作業(yè)車間調(diào)度問題中的完工時間大小作為算法的評價指標(biāo)，實現(xiàn)了交叉率和變異率隨著完工時間的非線性自適應(yīng)調(diào)整，較好地克服了標(biāo)準(zhǔn)遺傳算法在解決作業(yè)車間調(diào)度問題時的“早熟”和穩(wěn)定性差的缺點，以及傳統(tǒng)的線性自適應(yīng)遺傳算法收斂速度慢的缺點。本文在已有算法基礎(chǔ)上詳細(xì)討論了染色體編碼方法并對其進行了改進。在當(dāng)今的競爭環(huán)境下，如何利用計算機技術(shù)實現(xiàn)生產(chǎn)調(diào)度計劃優(yōu)化，快速調(diào)整資源配置，統(tǒng)籌安排生產(chǎn)進度，提高設(shè)備利用率已成為許多加工企業(yè)面臨的重大課題。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 I 頁 基于 遺傳算法 求解 作業(yè) 車間調(diào)度問題 摘 要 作業(yè) 車間調(diào)度問題 (JSP)簡單來說就是設(shè)備資源優(yōu)化配置問題。 作業(yè) 車間調(diào)度問題是計算機集成制造系統(tǒng) (CIMS)工程中的一個重要組成部分，它對企業(yè)的生產(chǎn)管理和控制系統(tǒng)有著重要的影響。 近年來遺傳算法得到了很大的發(fā)展，應(yīng)用遺傳算法來解決車間調(diào)度問題早有研究。 在研究了作業(yè)車 間調(diào)度問題數(shù)學(xué)模型和優(yōu)化算法的基礎(chǔ)上，將一種改進的自適應(yīng)遺傳算法應(yīng)用在作業(yè)車間調(diào)度中。以改進的自適應(yīng)遺傳算法和混合遺傳算法為調(diào)度算法，設(shè)計并實現(xiàn)了作業(yè)車間調(diào)度系統(tǒng)，詳細(xì)介紹了各個模塊的功能與操作。 關(guān)鍵詞 ： 作業(yè) 車間調(diào)度； 遺傳算法；改進染色體編碼 ； 生產(chǎn)周期 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 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 quickly and to plan production with due consideration for all concernedhas bee a great subject for many recent years,the geic algorithms obtained great development it was used to solve the job shop scheduling problem paper discusses the chromosome code method in detail based on the geic algorit