【正文】 一種常用的選擇方法是按比例選擇 ,即若個體 i適應值 (目標函數(shù) )是 fi,則個體在群體中復制 (再生 )的子代個數(shù)在群體中的比例將為 : /iiff? 。當然，在優(yōu)化過程中種群數(shù)目是允許變化的，也可以將較大規(guī)模的種群分解成若干子種群進行優(yōu)化。 適應度函數(shù)就是目標函數(shù)，在用遺傳算法解決車間調(diào)度問題里，定義個體的適應度函數(shù)為在 M 臺機器上排序加工完 N 個工件所需的時間，根據(jù)染色體編碼的思想提出的適應度算法如下： STEP1:定義 ti(n)為每個工件的可加工時間，初始化向量為零向量。產(chǎn)生的 chrom 為一個個體。例如， 遼寧科技大學本科生畢業(yè)設計 第 19 頁 在以上給定的染色體中出現(xiàn)三個 2 表示工件 j2 的三道工序，第一個 2 對應工件 j2 的第一道工序在機器 1 上加工，第二個 2 對應工件 j2 的第二道工序在機器 2 上加工，第三個2 對應工件 j2 的第三道工序在機器 3 上加工。 () 對染色體的解釋為 ：在第一臺機器上首先應該安排第二項工件的操作，其次是第一項工件的操作，第三項工件的操作；在第二臺機器上首先應該安排第三項工件的操作，然后是第一、二項任務的操作，以此類推。進而相應的調(diào)度如圖 （我們用 Gantte圖表示一個調(diào)度）。本研究的設備死鎖不在同一臺機器上而是在不同的機器上產(chǎn)生死鎖現(xiàn)象，所謂的設備死鎖現(xiàn)象如圖所示，其 中括號內(nèi)的兩個數(shù)據(jù)，意義為（工件號，工序號）。這也是本世紀高新技術(shù)迅速發(fā)展帶有規(guī)律性的特點，即面向應用。目前，關(guān) 于遺傳算法研究的熱潮仍在持續(xù)，越來越多的從事不同領域的研究人員已經(jīng)或正在置身于有關(guān)遺傳算法的研究或應用之中 現(xiàn)在隨著科學技術(shù)的日益發(fā)展，遺傳算法有了突飛猛進的發(fā)展， 不僅 遼寧科技大學本科生畢業(yè)設計 第 15 頁 理論研究十分活躍，而在越 來越多的領域得到發(fā)展。這些國際會議論文，集中反映了遺傳算法近些年來的最新發(fā)展和動向?？梢哉J為， De Jong 的研究工 作為遺傳算法及其應用打下了堅實的基礎，他所得出的許多結(jié)論，迄今仍具有普遍的指導意義。 1971年， 在他的博士論文中首次把遺傳算法用于函數(shù)優(yōu)化。四是遺傳算法和另一個稱為人工生命的嶄新研究領域正不斷滲透。因此，在一開始需要實現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。所以在使用遺傳算法的同時，也可以嘗試其它算法，互相補充，甚至根本不用遺傳算法。對于這個問題，研究者提出了一些方法增加基因的多樣性，從而防止過早的收斂。 ，遺傳算法的初始種群本身就帶有大量與最優(yōu)解甚遠的信息，通過選擇、交換、變異操作，能迅速排除與最優(yōu)解相差極大的串，這是一個強烈的濾波過程，并且是一個并行濾波機制。通常選取一個較低的變異概率。 基本遺傳 算法參數(shù)說明 對遺傳算法性能有影響的參數(shù)主要有 :種群數(shù)目 N、交換概率 Pc、變異概率 Pm、代溝 G、尺度窗口 W、和選擇策略 S 等。 變異操作是對種群 模式的擾動，有利于增加種群的多樣性。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。 由模式定理可知，具有低階、短定 義距以及平均適應度高于群體平均適應度的模式在后代中呈指數(shù)級增長。假設交換操作是采用的單點隨機雜交方式，隨機選取雜交的起始位置，交叉概率為 Pc，兩個具有相同模式 H 的個體發(fā)生交換，即雜交操作，不會改變模式 H。比起那些僅包 含 單個親本的基因拷貝和依靠偶然變異來改進的后代，這種由基因重組產(chǎn)生的后代進化要 快得多。 ，而不是發(fā)生在它們所編碼地生物個體上。并且以四個工件四個機器問題進行舉例 ,說明了用遺傳算法解決車間調(diào)度問題的可行性 。 由此，我們可以給出一般性的車間作業(yè)調(diào)度數(shù)學模型的 定義 : 如 果 對 應 于 一 個確 定 的 jM? ，滿足 * 1 2( ) m i n { ( ) , ( ) , ( ) }nj j j jf M f M f M f M? 或* 1 2( ) m a x { ( ) , ( ) , ( ) }nj j j jf M f M f M f M? 。注意 : 如果某工件的工序數(shù)不足 12max{ , , }nP P P，那么其空余的位置用 0填滿 。 車間作業(yè) 調(diào)度問題的數(shù)學模型 建立車間作業(yè)調(diào)度問題的數(shù)學模型，是我們研究該問題的出發(fā)點，同時也為其后的研 究奠定了基礎。 車間作業(yè)調(diào)度問題研究的假設條件及數(shù)學模型 車間作業(yè)調(diào)度問題研究的假設條件 在研究一般的車間作業(yè)調(diào)度問題中往往需要明確兩類重要假設條件 : :工件的任一工序必須在其前道工序完成后才能開始，并保證同一工件不會同時在兩臺機器上 加工，反映了工件不同工序間的時序關(guān)系 。在實際生產(chǎn)中，這項任務可能是裝配一種產(chǎn)品，也可能是完成一批工件的加工。 前提假設 ［ 3］ ： 1. 每一臺機器每次只能加工一個工件，每一個工件在機器上的加工被成為一道工 遼寧科技大學本科生畢業(yè)設計 第 2 頁 序。 所謂生產(chǎn)調(diào)度，即對生產(chǎn)過程進行作業(yè)計劃，作為一個關(guān)鍵模塊，是整個先進生產(chǎn)制造系統(tǒng)實現(xiàn)管理技術(shù)、運籌方法、優(yōu)化技術(shù)、自動化與計算機技術(shù)發(fā)展的核心，有效的調(diào)度方法和優(yōu)化技術(shù)的研究與應用，是實現(xiàn)先進制造和提高生產(chǎn)效益的基礎和關(guān)鍵。本人完全意識到本聲明的法律后果由本人承擔。 improvement chromosome code。 近年來遺傳算法得到了很大的發(fā)展，應用遺傳算法來解決車間調(diào)度問題早有研究。本文在已有算法基礎上詳細討論了染色體編碼方法并對其進行了改進。 production cycl 遼寧科技大學本科生畢業(yè)設計 第 III 頁 畢業(yè)設計（論文）原創(chuàng)性聲明和使用授權(quán)說明 原創(chuàng)性聲明 本人鄭重承諾：所呈交的畢業(yè)設計（論文），是我個人在指導教師的指導下進行的研究工作及取得的成果。 作者簽名： 日期： 年 月 日 學位論文版權(quán)使用授權(quán)書 本學位論文作者完全了解學校有關(guān)保留、使用學位論文的規(guī)定，同意學校保留并向國家有關(guān)部門或機構(gòu)送交論文的復印件和電子版，允許論文被查閱和借閱。 雖然對其研究已有幾十年的 歷史 但至今尚未形成一套系統(tǒng)的方法和理論，理論研究與實際應用之間還存在著較大距離。 2. 不同工件的加工工序可以不同； 3. 所有工件的工序數(shù)不大于設備數(shù)； 4. 每道工序必須在指定的某種設備上加工； 5. 任何作業(yè)沒有搶先加工的優(yōu)先權(quán) ； 6. 在作業(yè)優(yōu)化過程中既沒有新的工件加入也沒有取消的工件； 調(diào)度問題具有相當?shù)碾y度，目前調(diào)度問題的理論研究成果主要在 jobshop 問題為代表的基于最小完工時間的調(diào)度問題上。而在本文中，為了研究方便，我們將這項任務限定為加工一批工件。 遼寧科技大學本科生畢業(yè)設計 第 3 頁 (機器 )獨占性約束 :任一臺機器每次只能加工一個工件，且一旦開工就不能中斷，反映了加工隊列中工件間的時序關(guān)系。 假設有 n個工件，要在 m臺機器上加工，每個工件有 Pi 道工序，每臺機器上總共要加工 Lj 道工序。 遼寧科技大學本科生畢業(yè)設計 第 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? 矩陣。即 jM? 使得目標函數(shù) ()jfM 取值最小 (或最大 )，且與 MJ 相容，則稱 jM? 為車間作業(yè)調(diào)度問題在此目標函數(shù)下的最優(yōu)解。 遼寧科技大學本科生畢業(yè)設計 第 6 頁 2 遺傳算法相關(guān)理論與實現(xiàn)技術(shù) 遺傳算法 (Geic Algorithm, GA)是一種基于自然群體遺傳演化機制的高效探索算法，它是美國學者 Holland 于 1975 年首先提出來的 ［ 7］ 。 ，哪些適應性好地個體的染色體經(jīng)常比差的個體的染色體有更多的繁殖機會。 遼寧科技大學本科生畢業(yè)設計 第 7 頁 基本 遺傳算法 遺傳算法的基本思路 ； 將求解空間中的每一個點進行編碼，并從求解空間中任選 N個點組成初始群體； 。但是如果其中一方個體不具有模式 H， 則有可能會引起另一個個體模式的改變。這些模式在遺傳中很重要，稱為基因塊。 通常，種群太小則不能提供足夠的采樣點，以致算法性能很差 。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會使遺傳算法成為隨機搜索算法。 (population size) 種群數(shù)目的多少直接影響到遺傳算法的優(yōu)化性能和效率，種群選擇太小時，不能提供足夠多的個體，致使算法性能較差，易產(chǎn)生早熟收斂，甚至不能得到可行解。如果變異概率太大的時，遺傳算法易變成隨機搜索，如果變異概率太小，則不能產(chǎn)生新個體，不利于種群的多樣性。 ，而不是對參數(shù)本身，因此遺傳算法具有靈活性高的特點。其中一種是所謂觸發(fā)式超級突變，就是當染色體群體的質(zhì)量下降 (彼此的區(qū)別減少 )時增加突變概率 。 遺傳算法的 進展 地球上自出現(xiàn)生命至今已有 30 多億年的歷史，從低級生物到高級生命再至擁有智慧的人類，這是一個漫長的生物進化過程。由于仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代 （ generation） 演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù) 問題域中個體的適應度 （ fitness） 大小選擇 （ selection）個體，并借助于自然遺傳學的遺傳算子（ geic operators） 進行組合交叉 （ crossover）和變異 （ mutation） ，產(chǎn)生出代表新的解集的種群。所謂人工生命即是用計算機模 擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應、進化和免疫等現(xiàn)象是人工生命的重要研究對象，而遺傳算法在這方面將會發(fā)揮一定的作用，五是遺傳算法和進化規(guī)劃 （ Evolution Programming,EP） 以及進化策略 （ Evolution Strategy,ES）等進化計算理論日益結(jié)合。 1975 年是遺傳算法研究 歷史上十分重要的一年。 進入八十年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應用研究都成了十分熱門的課題。 1991 年， 編輯出版了《遺傳算法手冊》 （ Handbook of Geic Algorithms） ，其中包括了遺傳算法在工程技術(shù)和社會生活中的大量應用實例。 遺傳算法主要應用在機器學習 中。與此同時，理論方面同樣有大量工作 要做，例如：控制參數(shù)的選擇；交換和突變這兩類最重要的算子的確切作用；并行 GA 和分布式 GA 的研究。 圖 設備死鎖示意圖 在圖 中，分屬工件 1 和工件 2 的總共四個工序都處于循環(huán)等待其前面工序或前道工序結(jié)束加工的狀態(tài)之中，從而使設備 1 和設備 2 處于空轉(zhuǎn)狀態(tài)，即產(chǎn)生了所謂的死鎖現(xiàn)象。 圖 Gantte 圖 t 12 9 6 J3 J3 J3 J1 J1 J1 J2 J2 J2 t t 1 M1 10 7 3 4 M3 M2 遼寧科技大學本科生畢業(yè)設計 第 18 頁 （ jobbased representation） 將每個染色體用 n個代表工件的基因組成，是所有工件的一個排列。 前面兩種編碼方式比較復雜，下面我們用基于操作的編碼方式來解此車間調(diào)度問題： 把調(diào)度編碼為工序的序列，每個基因代表一道工序，給所有同一工件的工序指定相同的符號，其解碼原則是將染色體上得基因按照從左到右得順序解釋為任務相應順序的操作?？梢钥闯龉ぜ?j2 的所有工序都用相同的符號 2 來命名，并且根據(jù)它出 現(xiàn)在染色體中的順序加以解釋，工件的工序和加工機器的對應關(guān)系如下 所示。重復 STEP1， STEP2， STEP3， STEP4，直到種群滿