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