基于遺傳算法求解作業車間調度問題本科畢業設計論文(編輯修改稿)

　

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