【文章內(nèi)容簡介】 MJ（ i， j） 上的加工時間。同樣地，如果某工件的工序數(shù)不足 12max{ , , }nP P P，那么其空余的位置用 0 填滿 。 1 11 2 1 1111 2 1 ( 1 )1 1100 000ijPjjjpj j n j Pn n n iiiP PPP P PP P P PPPPT T TTT T T T?????????????? （ ） jM ：工件排列陣，此為 12m ax{ , , }nP P P n?矩陣。 (, )jMi j 表示在 i機器上排在第 j位 加工的工件號， (, )jMi? 表示 i機器上依次加工的各工件的排列。同上，如果某工件的工序數(shù)不足 12max{ , , }nP P P，那么其空余的位置用 0 填滿。事實上，工件排列陣就是調(diào)度的一種表示形式。 由此，我們可以給出一般性的車間作業(yè)調(diào)度數(shù)學(xué)模型的 定義 : 如 果 對 應(yīng) 于 一 個確 定 的 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? 。即 jM? 使得目標(biāo)函數(shù) ()jfM 取值最小 (或最大 )，且與 MJ 相容，則稱 jM? 為車間作業(yè)調(diào)度問題在此目標(biāo)函數(shù)下的最優(yōu)解。 生產(chǎn) 調(diào)度問題存在多種優(yōu)化目標(biāo)或者綜合優(yōu)化目標(biāo)，調(diào)度問題的優(yōu)化目標(biāo)通常從兩個方面來考慮 :生產(chǎn)成本和生產(chǎn)時間。調(diào)度問題從生產(chǎn)成本方面來考慮，其優(yōu)化目標(biāo)有 :庫存最少、在制品最少、設(shè)備利用率最高等 。從生產(chǎn)時間方面來考慮，其優(yōu)化目標(biāo)有 :最大程度滿足交貨期、最小完成時間、最小流動時間和最小等待時間等。兩個方向的優(yōu)化目標(biāo)之間彼此不是相互孤立的，其中的許多具體目標(biāo)之間的聯(lián)系很密切，有的相互促進(jìn)，有的相互沖突，也有的毫無聯(lián)系。 課題研究內(nèi)容及結(jié)構(gòu)安排 本文共分為三 章。第一章簡要介紹了車間調(diào)度問題和求解調(diào)度問題的基本方法 ；第 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 5 頁 二章介紹了遺傳算法的基本理論；第三章用遺傳算法來解決車間調(diào)度問題 ,其中介紹了常用的幾種編碼方式 ,在比較的情況下提出本文主要用基于操作的編碼方式 .還有提出了幾種主要的遺傳算子。并且以四個工件四個機器問題進(jìn)行舉例 ,說明了用遺傳算法解決車間調(diào)度問題的可行性 。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 6 頁 2 遺傳算法相關(guān)理論與實現(xiàn)技術(shù) 遺傳算法 (Geic Algorithm, GA)是一種基于自然群體遺傳演化機制的高效探索算法，它是美國學(xué)者 Holland 于 1975 年首先提出來的 ［ 7］ 。它摒棄了 傳統(tǒng)的搜索方式，模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程 ［ 8］ 。它將問題域中的可能解看作是群體的一個個體或染色體，并將每一個體編碼成符號串形式，對群體反復(fù)進(jìn)行基于遺傳學(xué)的操作（遺傳，交叉和變異），根據(jù)預(yù)定的目標(biāo)適應(yīng)度函數(shù)對每個個體進(jìn)行評價，依據(jù)適者生存，優(yōu)勝劣汰的進(jìn)化規(guī)則，不斷得到更優(yōu)的群體，同時以全局并行搜索方式來搜索優(yōu)化群體中的最優(yōu)個體，求得滿足要求的最優(yōu)解。 自然進(jìn)化與遺傳算法 自從達(dá)爾文的進(jìn)化論得到人們的接受之后，生物學(xué)家們就對進(jìn)化機制產(chǎn)生了極大的興趣?；涗洷砻魑覀兯^察的復(fù)雜結(jié)構(gòu) 的生命是在相對短的時間進(jìn)化而來的，對這一點包括生物學(xué)家在內(nèi)的許多人都感到驚奇。 雖然目前人們對進(jìn)化機制在一些方面還沒有弄清楚，但它們的一些特征已為人所知。進(jìn)化是發(fā)生在編碼染色體上，通過對染色體的譯碼部分生成生物體，但下面幾個關(guān)于進(jìn)化理論的一般特性已被廣大人們所接受。 ，而不是發(fā)生在它們所編碼地生物個體上。 ，哪些適應(yīng)性好地個體的染色體經(jīng)常比差的個體的染色體有更多的繁殖機會。 ，變異可以使生物體子代 的染色體不同于它們父代的染色體，通過結(jié)合兩個父代染色體的物質(zhì)，重組過程可以在子代中產(chǎn)生有很大差異的染色體。 。有關(guān)產(chǎn)生個體的信息包含在個體所攜帶的染色體的集合以及染色體編碼的結(jié)構(gòu)之中，這些個體會很好的適應(yīng)它們的環(huán)境。 大多數(shù)生物體是通過自然選擇和有性生殖這兩種基本過程進(jìn)行演化的。自然選擇的原則是適應(yīng)者生存，不適者淘汰。自然選擇決定了群體中那些個個體能存活并繁殖，有性生殖保證了后代基因中的混合與重組。比起那些僅包 含 單個親本的基因拷貝和依靠偶然變異來改進(jìn)的后代，這種由基因重組產(chǎn)生的后代進(jìn)化要 快得多。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 7 頁 基本 遺傳算法 遺傳算法的基本思路 ； 將求解空間中的每一個點進(jìn)行編碼，并從求解空間中任選 N個點組成初始群體； 。運用選擇、交叉、變異算子產(chǎn)生新一代群體； ，若找到滿足問題的最優(yōu)解，結(jié)束；否則，轉(zhuǎn)步驟 3。 遺傳算法的 模式定理 選擇操作是遺傳算法中體現(xiàn)“適者生存”的關(guān)鍵一環(huán)，它能控制高適應(yīng)度的模式成指數(shù)級增長。最常用的選擇方式是“輪盤 賭”法。其傳統(tǒng)實現(xiàn)建立在逐項比較的基礎(chǔ)上，算法復(fù)雜度為 O（ n＾ 2） 。通過把各碼鏈適應(yīng)值轉(zhuǎn)換為一組具有線性序的區(qū)間，從而可利用二分查找法實現(xiàn)“輪盤賭”選擇操作的遞歸算法，使時間復(fù)雜度下降到 O（ nlog2n）。 交換操作是有規(guī)則的信息交換，它能創(chuàng)建新的模式結(jié)構(gòu)，但又最低限度地破壞選擇操作過程所選擇的高適應(yīng)度的模式。假設(shè)交換操作是采用的單點隨機雜交方式，隨機選取雜交的起始位置，交叉概率為 Pc，兩個具有相同模式 H 的個體發(fā)生交換，即雜交操作，不會改變模式 H。但是如果其中一方個體不具有模式 H， 則有可能會引起另一個個體模式的改變。其中一方不具有模式 H 的概率為 1 p(H, t)，當(dāng)兩個個體發(fā)生交換時，如果引起模式 H 的改變，只可能將交換的起始位置選擇在第一個模式位到最后一個模式位之間的任何一個位置上，此時，使模式 H 生存的概率 Ps，為 : ()1 1scHPPl??? ? () 在交換過程中，可能使兩個都不具備模式 H 的個體經(jīng)交換后產(chǎn)生模式 H，故生存概率（ ()1 1c HP l?? ?）只是一個下界，則有： 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 8 頁 ()11scHPPl??? ? () 綜合考慮選擇操作，模式 H 在下一代中的數(shù)量可以用下式來綜合估計 : _( ) ( )( , 1 ) ( , ) ( 1 )1cf H Hm H t m H t p lf ?? ? ? ?? () 從上式可以看出，模式的平均適應(yīng)度高于群體平均適應(yīng)度，并且具有短 定義距的模式，將在下一代中成指數(shù)級的增長。 通過變異操作對個體串中單個位置進(jìn)行代碼替換，替換的概率為變異概率 Pm，則該位置不發(fā)生變異的概率為 1Pm。要使一個模式 H 在變異操作過程中不被破壞，就要保證模式 H 中確定位必須保證不變，因此，模式 H 保持不變的概率為 : ()(1 ) 1 ( )OHs m mp p P o H? ? ? ? ? () 上式中 O(H)為該模式的階數(shù)。 綜合上面所述，考慮到選擇操作、交換操作和 變異操作對模式的影響，則第 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?? ? ? ??? () 該式表示了下述的模式定理。 模式定理 :在遺傳算子選擇、交換、變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式，在子代中將得以指數(shù)級增長。 模式定理保證了較優(yōu)的模式 (遺傳算法的較優(yōu)解 )的數(shù)目呈指數(shù)增長，為解釋遺傳算法機理提供了數(shù)學(xué)基礎(chǔ)。 由模式定理可知，具有低階、短定 義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式在后代中呈指數(shù)級增長。這些模式在遺傳中很重要，稱為基因塊。 基因塊假設(shè) :遺傳算法通過短定義距、低階以及高平均適應(yīng)度的模式 (基因塊 )，在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。 模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在 。而基因塊假設(shè)則指出了在遺傳算子的作用下，算法具有生成全局最優(yōu)解的能力，即能生成高階、長定義距、高平均適應(yīng)度的模式，最終生成全局最優(yōu)解。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 9 頁 上述結(jié)論并沒有得到證明，因而被稱為假設(shè)。目前已經(jīng)有大量的實踐證據(jù)支持這一假 設(shè)，盡管大量的證據(jù)并不等于理論證明，但是至少可以肯定的是對很多經(jīng)常碰到的問題，遺傳算法都是適用的。 遺傳算法的收斂性分析 遺傳算法要實現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達(dá)全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。 通常，種群太小則不能提供足夠的采樣點，以致算法性能很差 。種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會增加計算量，造成收斂時間太長，表現(xiàn)為收斂速度緩慢。 影響 選擇操作使高適應(yīng)度個體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個體保留下來，不參加交叉和變異操作，使之直接進(jìn)入下一代，最終可使遺傳算法以概率 1 收斂于全局最優(yōu)解。 交叉操作用于個體對，產(chǎn)生新的個體，實質(zhì)上是在解空間中進(jìn)行有效搜索。交叉概率太大時，種群中個體更新很快，會造成高適應(yīng)度值的個體很快被破壞掉 。概率太小時，交叉操作很少進(jìn)行，從而會使搜索停滯不前，造成算法的不收斂。 變異操作是對種群 模式的擾動，有利于增加種群的多樣性。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會使遺傳算法成為隨機搜索算法。 遺傳操作對收斂性的影響，可利用馬爾可夫鏈對遺傳算法進(jìn)行分析，從而論證了遺傳算法在收斂性方面的一些重要性質(zhì)，有力地支持了遺傳算法的理論基礎(chǔ)。由馬爾可夫鏈推導(dǎo)出來的一些結(jié)論 :基本遺傳算法收斂于最優(yōu)解的概率為 1,使用保留最優(yōu)個體策略的遺傳算法收斂于最優(yōu)解的概率為 1。 隱含并行性定理 :遺傳算法所處理的模式總數(shù)與其群體規(guī)模 N 的立方成正比，即 : m=O(N3) （ ） 由該定理可知，雖然表面上每代處理的個體數(shù)目都是一定的，但是由于每個個體都 遼寧科技大學(xué)本科生畢業(yè)設(shè)計 第 10 頁 隱含著多種不同的模式，所以每次參與遺傳算子操作的個體卻不僅僅是兩個。從總體上來說，每代之間所處理的個體要遠(yuǎn)大于其表面的數(shù)目，這就是遺傳算法獨特的隱含并行性。由隱含并行性定理可知，雖然表面上每代僅對 N 個個體處理操作，而事實上處理了O(N3)個模式，且無需額外存儲。隱含并行性為遺傳算法的高效性提供了理論依據(jù)。 基本遺傳 算法參數(shù)說明 對遺傳算法性能有影響的參數(shù)主要有 :種群數(shù)目 N、交換概率 Pc、變異概率 Pm、代溝 G、尺度窗口 W、和選擇策略 S 等。 (population size) 種群數(shù)目的多少直接影響到遺傳算法的優(yōu)化性能和效率，種群選擇太小時，不能提供足夠多的個體，致使算法性能較差，易產(chǎn)生早熟收斂，甚至不能得到可行解。種群選擇過大時，雖然能避免早熟收斂，但是增加了計算量。 (crossover rate) 交換概率 Pc 用于控制交換操作的頻率。交換概率太大的時，易產(chǎn)生更新過快，從而破壞掉高適應(yīng)度個體的 現(xiàn)象。交換概率太小的時候又容易產(chǎn)生搜索停滯不前的現(xiàn)象。 (mutation rate) 變異概率 Pm。增加種群多樣性具有重要意義。通常選取一個較低的變異概率。如果變異概率太大的時，遺傳算法易變成隨機搜索，如果變異概率太小，則不能產(chǎn)生新個體，不利于種群的多樣性。 (