【正文】 31 參考文獻(xiàn) ................................................................................................................................ 32 附 錄 ....................................................................................................................................... 33 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 1 頁 1 緒論 課題來源 隨著加入 WTO，市場競爭越來越激烈，對制造企業(yè)來說，為了能夠在競爭中立于不敗，降低成本是不得不面臨的問題，而確保生產(chǎn)車間較高的生產(chǎn)能力和效率，是當(dāng)務(wù)之急。 當(dāng)前科學(xué)技術(shù)正進(jìn)入多學(xué)科互相交叉、互相滲透、互相影響的時代，生命科學(xué)與工程科學(xué)的交叉、滲透和相互促進(jìn)是其中一個 典型例子，也是近代科學(xué)技術(shù)發(fā)展的一個顯著特點(diǎn)。 所謂生產(chǎn)調(diào)度，即對生產(chǎn)過程進(jìn)行作業(yè)計(jì)劃，作為一個關(guān)鍵模塊，是整個先進(jìn)生產(chǎn)制造系統(tǒng)實(shí)現(xiàn)管理技術(shù)、運(yùn)籌方法、優(yōu)化技術(shù)、自動化與計(jì)算機(jī)技術(shù)發(fā)展的核心，有效的調(diào)度方法和優(yōu)化技術(shù)的研究與應(yīng)用，是實(shí)現(xiàn)先進(jìn)制造和提高生產(chǎn)效益的基礎(chǔ)和關(guān)鍵。目前的調(diào)度算法大多只關(guān)心工件的調(diào)度問題，而對其它資源分配問題則研究相對不多，將二者 結(jié)合起來研究應(yīng)該是值得注意的問題，目前已有不少學(xué)者開始關(guān)注該問題。由于遺傳算法是一種借鑒生物界自然選擇和進(jìn)化機(jī)制發(fā)展起來的高度并行、隨機(jī)、自適應(yīng)搜索算法 ［ 1］ 。一些學(xué)者們經(jīng)過大量的實(shí)踐證明了 遺傳算法在解決作業(yè)車間調(diào)度問題上 比經(jīng)典的啟發(fā)式算法好，同時遺傳算法比傳統(tǒng)的搜索技術(shù) 有更強(qiáng)的 優(yōu)越 性，因?yàn)樗粌H能解決某一特定問題，而且可以適應(yīng)不同的問 題形式 ［ 2］ 。 前提假設(shè) ［ 3］ ： 1. 每一臺機(jī)器每次只能加工一個工件，每一個工件在機(jī)器上的加工被成為一道工 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 2 頁 序。 求解調(diào)度問題的方法稱為調(diào)度優(yōu)化算法。其中精確求解方法包括解析方法、窮舉方法（包括分支定界）等；近似求解方法包括基于規(guī)則的構(gòu)造性方法、鄰域搜索算法（如進(jìn)化遺傳算法，模擬退火算法）以及人工智能方法（如神經(jīng)網(wǎng)絡(luò)） ［ 4］ 等。本文從實(shí)際和理論兩方面進(jìn)行研究和深入，重點(diǎn)研究了現(xiàn)代進(jìn)化算法中有代表性發(fā)展優(yōu)勢的遺傳算法 。在實(shí)際生產(chǎn)中，這項(xiàng)任務(wù)可能是裝配一種產(chǎn)品，也可能是完成一批工件的加工。在此基礎(chǔ)上，可對車間作業(yè)調(diào)度問題進(jìn)行一般性的描述 :假定有多個工件，要經(jīng)過多臺機(jī)器加工。用事先給定的“加工路線”表示工件加工時技術(shù)上的約束 ，即工件的加工工藝過程。車間作業(yè)調(diào)度問題中，每個工件都有獨(dú)特的加工路線 ［ 5］ 。 車間作業(yè)調(diào)度問題研究的假設(shè)條件及數(shù)學(xué)模型 車間作業(yè)調(diào)度問題研究的假設(shè)條件 在研究一般的車間作業(yè)調(diào)度問題中往往需要明確兩類重要假設(shè)條件 : :工件的任一工序必須在其前道工序完成后才能開始，并保證同一工件不會同時在兩臺機(jī)器上 加工，反映了工件不同工序間的時序關(guān)系 。 此外，還有一些輔助假設(shè)條件，如下 : 1. 各工件經(jīng)過其準(zhǔn)備時間后可開始加工 。 3. 工序允許等待，即前一個工序未完成，則后面工序需要等待 。 5. 工件的加工時間事先給定，且在整個加工過程中保持不變 。 車間作業(yè) 調(diào)度問題的數(shù)學(xué)模型 建立車間作業(yè)調(diào)度問題的數(shù)學(xué)模型，是我們研究該問題的出發(fā)點(diǎn)，同時也為其后的研 究奠定了基礎(chǔ)。我們定義以下基本數(shù)學(xué)符號 ［ 6］ ： J:所有工件的集合， 12{ , , }nJ J J J? ； M:所有機(jī)器的集合， 12{ , , }mM M M M? ； ijP： 工件 Ji 的工序集合， 12{ , , }i i i i ij j j j pP P P P?； P:所有工序的集合，此為 12m ax{ , , }nn P P P? 矩陣。 ( , )ijPi P??，表示 i 工件的所有工序按優(yōu)先順序的排列。 1 11 1 1 111121 2 ( 1 )110 0 000in n n n iiiP PPj j j Pj j j p j PPPPP P PPP P P P?????????????? （ ） MJ :機(jī)器順序陣， 此為 12m ax{ , , }nn P P P? 矩陣。注意 : 如果某工件的工序數(shù)不足 12max{ , , }nP P P，那么其空余的位置用 0填滿 。 T(i, j)表示工件 i的第 j 道工序在 MJ（ i， j） 上的加工時間。 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?矩陣。同上，如果某工件的工序數(shù)不足 12max{ , , }nP P P，那么其空余的位置用 0 填滿。 由此，我們可以給出一般性的車間作業(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? 。 生產(chǎn) 調(diào)度問題存在多種優(yōu)化目標(biāo)或者綜合優(yōu)化目標(biāo)，調(diào)度問題的優(yōu)化目標(biāo)通常從兩個方面來考慮 :生產(chǎn)成本和生產(chǎn)時間。從生產(chǎn)時間方面來考慮，其優(yōu)化目標(biāo)有 :最大程度滿足交貨期、最小完成時間、最小流動時間和最小等待時間等。 課題研究內(nèi)容及結(jié)構(gòu)安排 本文共分為三 章。并且以四個工件四個機(jī)器問題進(jìn)行舉例 ,說明了用遺傳算法解決車間調(diào)度問題的可行性 。它摒棄了 傳統(tǒng)的搜索方式，模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程 ［ 8］ 。 自然進(jìn)化與遺傳算法 自從達(dá)爾文的進(jìn)化論得到人們的接受之后，生物學(xué)家們就對進(jìn)化機(jī)制產(chǎn)生了極大的興趣。 雖然目前人們對進(jìn)化機(jī)制在一些方面還沒有弄清楚，但它們的一些特征已為人所知。 ，而不是發(fā)生在它們所編碼地生物個體上。 ，變異可以使生物體子代 的染色體不同于它們父代的染色體，通過結(jié)合兩個父代染色體的物質(zhì)，重組過程可以在子代中產(chǎn)生有很大差異的染色體。有關(guān)產(chǎn)生個體的信息包含在個體所攜帶的染色體的集合以及染色體編碼的結(jié)構(gòu)之中，這些個體會很好的適應(yīng)它們的環(huán)境。自然選擇的原則是適應(yīng)者生存，不適者淘汰。比起那些僅包 含 單個親本的基因拷貝和依靠偶然變異來改進(jìn)的后代，這種由基因重組產(chǎn)生的后代進(jìn)化要 快得多。運(yùn)用選擇、交叉、變異算子產(chǎn)生新一代群體； ，若找到滿足問題的最優(yōu)解，結(jié)束；否則，轉(zhuǎn)步驟 3。最常用的選擇方式是“輪盤 賭”法。通過把各碼鏈適應(yīng)值轉(zhuǎn)換為一組具有線性序的區(qū)間，從而可利用二分查找法實(shí)現(xiàn)“輪盤賭”選擇操作的遞歸算法，使時間復(fù)雜度下降到 O（ nlog2n）。假設(shè)交換操作是采用的單點(diǎn)隨機(jī)雜交方式，隨機(jī)選取雜交的起始位置，交叉概率為 Pc，兩個具有相同模式 H 的個體發(fā)生交換，即雜交操作，不會改變模式 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è)計(jì) 第 8 頁 ()11scHPPl??? ? () 綜合考慮選擇操作，模式 H 在下一代中的數(shù)量可以用下式來綜合估計(jì) : _( ) ( )( , 1 ) ( , ) ( 1 )1cf H Hm H t m H t p lf ?? ? ? ?? () 從上式可以看出，模式的平均適應(yīng)度高于群體平均適應(yīng)度，并且具有短 定義距的模式，將在下一代中成指數(shù)級的增長。要使一個模式 H 在變異操作過程中不被破壞，就要保證模式 H 中確定位必須保證不變，因此，模式 H 保持不變的概率為 : ()(1 ) 1 ( )OHs m mp p P o H? ? ? ? ? () 上式中 O(H)為該模式的階數(shù)。 模式定理 :在遺傳算子選擇、交換、變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式，在子代中將得以指數(shù)級增長。 由模式定理可知，具有低階、短定 義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式在后代中呈指數(shù)級增長。 基因塊假設(shè) :遺傳算法通過短定義距、低階以及高平均適應(yīng)度的模式 (基因塊 )，在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。而基因塊假設(shè)則指出了在遺傳算子的作用下，算法具有生成全局最優(yōu)解的能力，即能生成高階、長定義距、高平均適應(yīng)度的模式，最終生成全局最優(yōu)解。目前已經(jīng)有大量的實(shí)踐證據(jù)支持這一假 設(shè)，盡管大量的證據(jù)并不等于理論證明，但是至少可以肯定的是對很多經(jīng)常碰到的問題，遺傳算法都是適用的。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無疑會增加計(jì)算量，造成收斂時間太長，表現(xiàn)為收斂速度緩慢。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個體保留下來，不參加交叉和變異操作，使之直接進(jìn)入下一代，最終可使遺傳算法以概率 1 收斂于全局最優(yōu)解。交叉概率太大時，種群中個體更新很快，會造成高適應(yīng)度值的個體很快被破壞掉 。 變異操作是對種群 模式的擾動，有利于增加種群的多樣性。 遺傳操作對收斂性的影響，可利用馬爾可夫鏈對遺傳算法進(jìn)行分析，從而論證了遺傳算法在收斂性方面的一些重要性質(zhì)，有力地支持了遺傳算法的理論基礎(chǔ)。 隱含并行性定理 :遺傳算法所處理的模式總數(shù)與其群體規(guī)模 N 的立方成正比，即 : m=O(N3) （ ） 由該定理可知，雖然表面上每代處理的個體數(shù)目都是一定的，但是由于每個個體都 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 10 頁 隱含著多種不同的模式，所以每次參與遺傳算子操作的個體卻不僅僅是兩個。由隱含并行性定理可知，雖然表面上每代僅對 N 個個體處理操作，而事實(shí)上處理了O(N3)個模式，且無需額外存儲。 基本遺傳 算法參數(shù)說明 對遺傳算法性能有影響的參數(shù)主要有 :種群數(shù)目 N、交換概率 Pc、變異概率 Pm、代溝 G、尺度窗口 W、和選擇策略 S 等。種群選擇過大時，雖然能避免早熟收斂，但是增加了計(jì)算量。交換概率太大的時，易產(chǎn)生更新過快，從而破壞掉高適應(yīng)度個體的 現(xiàn)象。 (mutation rate) 變異概率 Pm。通常選取一個較低的變異概率。 (generation gap) 代溝 G 用于控制每一代群體被替換的比例，每代有 N (1G)個父代個體選中進(jìn)入下一代種群中，該參數(shù)和交換、變異概率以及選擇策略有很大關(guān)系，它并不是一個初始參數(shù)，而是評價遺傳算法的一個參數(shù)。 (selection strategy) 一般來說有兩種選擇策略，一種為純選擇，種群中每個個體根據(jù)其適應(yīng)度值進(jìn)行比例選擇，即個體被選擇的概率與其適應(yīng)度值成正比。 遼寧科技大學(xué)本科生畢業(yè)設(shè)計(jì) 第 11 頁 遺傳算法的優(yōu)缺點(diǎn) 遺傳算法的優(yōu)點(diǎn) 遺傳算法在解決優(yōu)化問題過程中有如 下優(yōu)點(diǎn) : ，而不是從單個解開始。 ，遺傳算法的初始種群本身就帶有大量與最優(yōu)解甚遠(yuǎn)的信息，通過選擇、交換、變異操作，能迅速排除與最優(yōu)解相差極大的串，這是一個強(qiáng)烈的濾波過程，