【正文】 .............. 10 遺傳算法的優(yōu)缺點 ................................................................................................... 11 遺傳算法的優(yōu)點 ............................................................................................. 11 遺傳算法的缺點 ............................................................................................. 11 遺傳算法的進展 ....................................................................................................... 12 小結(jié) ........................................................................................................................... 15 3 用遺傳算法對具體問題的解決與探討 .................................................................. 16 研究過程中的幾個關(guān)鍵問題 ................................................................................... 16 設(shè)備死鎖現(xiàn)象 ................................................................................................. 16 參數(shù)編碼 ......................................................................................................... 16 初始種群的生成 ............................................................................................. 19 個體的適應(yīng)度函數(shù) ......................................................................................... 20 遼寧科技大學本科生畢業(yè)設(shè)計 第 VI 頁 算法參數(shù) ......................................................................................................... 20 遺傳算子的設(shè)計 ............................................................................................. 21 遺傳算法終止條件 ................................................................................................... 24 遺傳算法解決車間調(diào)度問題的改進 ....................................................................... 24 系統(tǒng)仿真 ................................................................................................................... 24 小結(jié) ........................................................................................................................... 29 結(jié) 論 ....................................................................................................................................... 30 致 謝 ....................................................................................................................................... 31 參考文獻 ................................................................................................................................ 32 附 錄 ....................................................................................................................................... 33 遼寧科技大學本科生畢業(yè)設(shè)計 第 1 頁 1 緒論 課題來源 隨著加入 WTO，市場競爭越來越激烈，對制造企業(yè)來說，為了能夠在競爭中立于不敗，降低成本是不得不面臨的問題，而確保生產(chǎn)車間較高的生產(chǎn)能力和效率，是當務(wù)之急。由于遺傳算法是一種借鑒生物界自然選擇和進化機制發(fā)展起來的高度并行、隨機、自適應(yīng)搜索算法 ［ 1］ 。其中精確求解方法包括解析方法、窮舉方法（包括分支定界）等；近似求解方法包括基于規(guī)則的構(gòu)造性方法、鄰域搜索算法（如進化遺傳算法，模擬退火算法）以及人工智能方法（如神經(jīng)網(wǎng)絡(luò)） ［ 4］ 等。用事先給定的“加工路線”表示工件加工時技術(shù)上的約束 ，即工件的加工工藝過程。 3. 工序允許等待，即前一個工序未完成，則后面工序需要等待 。 ( , )ijPi P??，表示 i 工件的所有工序按優(yōu)先順序的排列。 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?矩陣。從生產(chǎn)時間方面來考慮，其優(yōu)化目標有 :最大程度滿足交貨期、最小完成時間、最小流動時間和最小等待時間等。 自然進化與遺傳算法 自從達爾文的進化論得到人們的接受之后，生物學家們就對進化機制產(chǎn)生了極大的興趣。有關(guān)產(chǎn)生個體的信息包含在個體所攜帶的染色體的集合以及染色體編碼的結(jié)構(gòu)之中，這些個體會很好的適應(yīng)它們的環(huán)境。最常用的選擇方式是“輪盤 賭”法。要使一個模式 H 在變異操作過程中不被破壞，就要保證模式 H 中確定位必須保證不變，因此，模式 H 保持不變的概率為 : ()(1 ) 1 ( )OHs m mp p P o H? ? ? ? ? () 上式中 O(H)為該模式的階數(shù)。而基因塊假設(shè)則指出了在遺傳算子的作用下，算法具有生成全局最優(yōu)解的能力，即能生成高階、長定義距、高平均適應(yīng)度的模式，最終生成全局最優(yōu)解。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個體保留下來，不參加交叉和變異操作，使之直接進入下一代，最終可使遺傳算法以概率 1 收斂于全局最優(yōu)解。 隱含并行性定理 :遺傳算法所處理的模式總數(shù)與其群體規(guī)模 N 的立方成正比，即 : m=O(N3) （ ） 由該定理可知，雖然表面上每代處理的個體數(shù)目都是一定的，但是由于每個個體都 遼寧科技大學本科生畢業(yè)設(shè)計 第 10 頁 隱含著多種不同的模式，所以每次參與遺傳算子操作的個體卻不僅僅是兩個。交換概率太大的時，易產(chǎn)生更新過快，從而破壞掉高適應(yīng)度個體的 現(xiàn)象。 (selection strategy) 一般來說有兩種選擇策略，一種為純選擇，種群中每個個體根據(jù)其適應(yīng)度值進行比例選擇，即個體被選擇的概率與其適應(yīng)度值成正比。由于遺傳算法使用適應(yīng)度值這一信息進行搜索，并不需要問題導數(shù)等與問題直接相關(guān)的信息。一種觀點認為交叉比變異更重要，因為變異僅僅是保證不丟失某些可能的解 。經(jīng)過長時間的遺傳、變異和選擇，生物便逐漸從簡單到復(fù)雜，從低級到高級不斷地進化和發(fā)展。這 遼寧科技大學本科生畢業(yè)設(shè)計 第 13 頁 一新的學習機制對于解決人工智能 ［ 11］ 中知識獲取和知識優(yōu)化精煉的瓶頸難題帶來了希望。 近年來，遺傳程序設(shè)計運用 遺傳算法的思想自動生成計算機程序解決了許多問題，如預(yù)測、分類、符號回歸和圖像處理等，作為一種新技術(shù)它己經(jīng)與遺傳算法并駕齊驅(qū)。該理論首次確認了結(jié)構(gòu)重組遺傳操作對于獲得隱并行性的重要性。該書總結(jié)了遺傳算法研究的主要成果，對 遺傳算法及其應(yīng)用作了全面而系統(tǒng)的論述 。有關(guān)遺傳算法的學術(shù)論文也不斷在《 Artificial Intelligence》、《 Machine Learning》、《 Information science》、《 Parallel Computing》、《 Geic Programming and Evoluable Machines》《 IEEE Transactions on Neural Networks》 ,《 IEEE Transactions on Signal Processing》等雜志上發(fā)表。由于多樣性和復(fù)雜性，通常難以建立完善的理論以指導整個學習過程，從而使傳統(tǒng)尋 優(yōu)技術(shù)的應(yīng)用受到限制，而這恰好是遺傳算法發(fā)揮的長處。 小結(jié) 遺傳算法是一類隨機化算法，但是它不是簡單的隨機走動，它可以有效地利用已經(jīng)有的信息處理來搜索那些有希望改善解質(zhì)量的串，類似于自然進化，遺傳算法通過作用于染色體上的基因，尋找好的染色體來求解問題。對于同一問題可以有不同的編碼表示方法。例如，對于上述 3*3 例子。 對于 n 個工件 m 機器問題，一個染色體 包括個 n*m 個基因，每個個體出現(xiàn)在染色體中 m次，每個基因不表明具體的工序，而是指上下依賴關(guān)系的工序。 相應(yīng)的每個加工操作有時間矩陣： T11 T12 ? T1M T21 T22 ? T2M T(J,M)= ： ： ： ： () TN1 TN2 ? TNM 其中第 J 行表示第 J 個工件的機器加工時間 ,時間為零表示工件不在機器上加工 . 因為每個個體由 N 個工件號重復(fù) M 次組成的 .所以產(chǎn)生一個 1,2.. .. ..N(每個重復(fù)有N*M 個操作 )的全排列即是一個初始個體 ,算法如下： STEP1：用行號 1 代替機器順序矩陣 M(j,m)的第 j 行的所有元素 ,零元素保持不變 , 遼寧科技大學本科生畢業(yè)設(shè)計 第 20 頁 若產(chǎn)生的矩陣為 GEN。 個體的適應(yīng)度函數(shù) 在遺傳算法中 ,適應(yīng)度是描述個體 性能的主要指標。 算法參數(shù) 標準 GA 有 4 個關(guān)鍵參數(shù)，包括種群數(shù)目 （ population size,記作 M） 、交叉概率 遼寧科技大學本科生畢業(yè)設(shè)計 第 21 頁 （ crossover rate,記作 pc） 、變異概率 （ mutation rate,記作 pm） 和代溝 （ generation gap,記作 （ G） 。通常一個較低的變異概率足以防止整個群體中任一位置的基因一直保持不