【正文】 ，用遺傳算法求最優(yōu)解比較困難，因為染色體種群很可能過 早地 斂，而對以后變化了的數(shù)據(jù)不再產(chǎn)生變化。其中一種是所謂觸發(fā)式超級突變，就是當染色體群體的質(zhì)量下降 (彼此的區(qū)別減少 )時增加突變概率 。 ，但交叉和變異的重要性存在爭議。而另一種觀點則認為交叉過程的作用只不過是在種群中推廣變異過程所造成的更新，對于初期的種群來說，交叉幾乎等效于 遼寧科技大學本科生畢業(yè)設計 第 12 頁 一個非常大的變異率，而這么大的變異很可能影響進化過程。 ，優(yōu)化問題要具體情況具 體分析。 遺傳算法的 進展 地球上自出現(xiàn)生命至今已有 30 多億年的歷史，從低級生物到高級生命再至擁有智慧的人類，這是一個漫長的生物進化過程。通過不斷的選擇，使有利于生存發(fā)展的變異遺傳下去，積累下來，使變 異和遺傳向著適應環(huán)境的方向發(fā)展。 遺傳 算法 是從代表問題可能潛在的解集的一個種群 （ population） 開始的，而一個種群則由經(jīng)過基因 （ gene） 編碼的一定數(shù)目的個體 (individual)組成。染色體作為遺傳物質(zhì)的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn) （ 即基因型 ） 是某種基因組合，它決定了個體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因 組合決定的。由于仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代 （ generation） 演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應度 （ fitness） 大小選擇 （ selection）個體，并借助于自然遺傳學的遺傳算子（ geic operators） 進行組合交叉 （ crossover）和變異 （ mutation） ，產(chǎn)生出代表新的解集的種群。 隨著應用領域的擴展，遺傳算法的研究出現(xiàn)了幾個引人注目的新動向 ［ 9］ ：一是基于遺傳算法的機器學習，這一新的研究課題把遺傳算法從歷來離散的搜索空間的優(yōu)化搜索算法擴展到具有獨特的規(guī)則生成功能的嶄新的機器學習算法 ［ 10］ 。二是遺傳算法正日益和神經(jīng)網(wǎng)絡 ［ 12］ 、模糊推理以及混沌理論等其它智能計算方法相互滲透和結合，這對開拓 21 世 紀中新的智能計算技術將具有重要的意義。這一研究不僅對遺傳算法本身的發(fā)展，而且對于新一代智能計算機體系結構的研究都是十分重要的。所謂人工生命即是用計算機模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應、進化和免疫等現(xiàn)象是人工生命的重要研究對象，而遺傳算法在這方面將會發(fā)揮一定的作用，五是遺傳算法和進化規(guī)劃 （ Evolution Programming,EP） 以及進化策略 （ Evolution Strategy,ES）等進化 計算理論日益結合。目前，這三者之間的比較研究和彼此結合的探討正形成熱點。 1996 年，舉行了第 1 次遺傳程序設計國際會議，該領域己引起越來越多的相關學者們的興趣。此后， Holland 指導學生完成了多篇有關遺傳算法研究的論文。 1975 年是遺傳算法研究歷史上十分重要的一年。 Holland 在該書中系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法的理論研究和發(fā)展極其重要的模式理論 （ schema theory） 。同年， Jong 完成了他的博士論文《一類遺傳自適應系統(tǒng)的行為分析》 （ An Analysis of the Behavior of a Class of Geic Adaptive System） 。盡管 De Jong 和 Hollstien 一樣主要側重于函數(shù)優(yōu)化的應用研究，但他將 遼寧科技大學本科生畢業(yè)設計 第 14 頁 選擇、交叉和變異操作進一步完善和系統(tǒng)化，同時又提出了諸如代溝 （ generation gap）等新的遺傳操作技術。 進入八十年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應用研究都成了十分熱門的課題。 1989 年， Holland 的學生 出版了專著《搜索、優(yōu)化和機器學習中的遺傳算法》 （ Geic Algorithms in Search , Optimization, and Machine Learning） 。同年，美國斯坦福大學的 Koza 基于自然選擇原則創(chuàng)造性地提出了用層次化的計算機程序來表達問題的遺傳程序設計 ( geic programming, GP)方法，成功地解決了許多問題。此外，以遺傳算法的理論基礎為中心的學術會議還有 Foundations of Geic Algorithms，該會也是從 1990 年開始隔年召開一 次。 1991 年， 編輯出版了《遺傳算法手冊》 （ Handbook of Geic Algorithms） ，其中包括了遺傳算法在工程技術和社會生活中的大量應用實例。 1994 年，他又出版了《遺傳程序設計，第二冊 :可重用程序的自動發(fā)現(xiàn)》深化了遺傳程序設計的研究，使程序設計自動化展現(xiàn)了新局面。 1993 年，MIT 出版社創(chuàng)刊了新雜志《 Evolutionary Computation》?！?Advanced Computational Intelligence》雜志即將發(fā)刊，由模糊集合創(chuàng)始人 教授為名譽主編。 遺傳算法主要應用在機器學習 中。一般的學習系統(tǒng)要求具有隨時間推移逐步調(diào)整有關參數(shù)或者改變自身結構以更加適應環(huán)境，更好達到目標的能力。 除了機器學習之外遺傳算法所涉及的主要領域還有自動控制、規(guī)劃設計、組合優(yōu)化、圖象處理、信號處理、人工生命、 模式識別，神經(jīng)網(wǎng)絡、自適應控制、生物科學、系統(tǒng)工程、社會科學等。 今后幾年，拓廣更加多樣的應用領域，將是 GA 發(fā)展的主流。與此同時，理論方面同樣有大量工作要做，例如：控制參數(shù)的選擇；交換和突變這兩類最重要的算子的確切作用；并行 GA 和分布式 GA 的研究。這對 GA 的實際應用關系重大 。與自然界相似，遺傳算法對待求解問題本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個染色體進行評價，并基于適應度值來評價染色體，使適用性好的染色體比適應性差的染色體有更多的繁殖機會。 研究過程中的幾個關鍵問題 設備死鎖現(xiàn)象 初始解群是問題的起點，解決設備死鎖問題必須從初始解群開始。 圖 設備死鎖示意圖 在圖 中，分屬工件 1 和工件 2 的總共四個工序都處于循環(huán)等待其前面工序或前道工序結束加工的狀態(tài)之中，從而使設備 1 和設備 2 處于空轉 狀態(tài)，即產(chǎn)生了所謂的死鎖現(xiàn)象。遺傳算法的工作基礎是選擇適當?shù)姆椒ū硎緜€體和問題的解 (作為進化的個體 )。由于遺傳算法不能直接處理空間解的數(shù)據(jù)，在解決此車間調(diào)度問題上把它們轉換成遺傳空間的基因按一定結構組成的染色體或個體，也就是通過編碼將它們表示成遺傳空間的基因型串結構數(shù)據(jù)。 表 加工時間和工藝約束 項目 工件 操作序列 1 2 3 操作時間 J1 J2 J3 3 1 3 3 5 2 2 3 3 機器 J1 J2 J3 M1 M1 M2 M2 M3 M1 M3 M2 M3 對于上表 3個工件在 3個 機器上加工的例子，假設染色體為 {2 1 2 3 1 1 3 2 3}， Oijk 表示第 i個工件的第 j 個工序在第 k 個機器上加工（以下同），則對機器加工順序的工藝約束，該染色體對應的有序操作表為 [O211 O111 O223 O312 O122 O133 O321 O232 O333]，即首先安排第二個工件的第一個操作步驟，然后安排第一個工件的第一個操作步驟，第二項任務的第二個操作步驟， ? 以次類推。 圖 Gantte 圖 t 12 9 6 J3 J3 J3 J1 J1 J1 J2 J2 J2 t t 1 M1 10 7 3 4 M3 M2 遼寧科技大學本科生畢業(yè)設計 第 18 頁 （ jobbased representation） 將每個染色體用 n個代表工件的基因組成，是所有工件的一個排列。其基本思想是只對任務進行編碼，然后按照編碼在染色體中的順序來以相應的優(yōu)先級別安排任務。對于有三項任務的調(diào)度問題，假設染色體為 [2 3 1]，則可以解釋為首先安排第二項任務的所有操作，其次是第三項任務，最后才輪到第一項任務。用于表示機器上加工工件的一個排列順序。 前面兩種編碼方式比較復雜，下面我們用基于操作的編碼方式來解此車間調(diào)度問題： 把調(diào)度編碼為工 序的序列，每個基因代表一道工序，給所有同一工件的工序指定相同的符號，其解碼原則是將染色體上得基因按照從左到右得順序解釋為任務相應順序的操作。顯然，這種解碼過程可產(chǎn)生活動調(diào)度。只需改變工序的順序，即可得到不同的調(diào)度結果，即不同的生產(chǎn)周期。因為每個工件有三道工序，所以每個工件在一個染色體中剛好出現(xiàn)三次?？梢钥闯龉ぜ?j2 的所有工序都用相同的符號 2 來命名，并且根據(jù)它出 現(xiàn)在染色體中的順序加以解釋，工件的工序和加工機器的對應關系如下 所示。 初始種群的生成 在 N 個工件 M臺機器的排序問題中，對每個機器的加工存在加工工藝順約束，這個工藝約束表示為工件的加工順序矩陣： M11 M12 ? M1M M（ J,M） = M21 M22 ? M2M ： ： ： ： () Mn1 Mn2 ? MnM 其中第 J行表示第 J個工件的機器順序 .機器號為零表示工件加工結束。 STEP2：產(chǎn)生一個整數(shù)隨機數(shù) 1=p=N。 STEP4：重復 STIP2， STEP3，直到 GEN 的所有元素為零。重復 STEP1， STEP2， STEP3， STEP4，直到種群滿。 初始種群的生成也可以用隨機方法產(chǎn)生，這是因為群體中的個體都是由工件的符號組成的，而且工件任意排列總能產(chǎn)生可行調(diào)度 .在下文的舉例驗證過程中我們運用了隨機的方法產(chǎn)生初始種群。根據(jù)適應度的大小 ,對個體進行優(yōu)勝劣汰。從生物學角度講 ,適應度相當于“生存競爭 ,適者生存”的生物生存能力 ,在遺傳過程中具有重要意義。 STEP2:chrom（ i） 對應相應工序的加工機器為 machiner（ i）。 STEP4:求出適應度函數(shù) F=ti(chorm(n))。目前，如何確定 GA 的最優(yōu)參數(shù)仍舊是一個公開的問題，也是研究 GA 的重要課題之一。通常，種群太小 時，不能提供足夠的采樣點，以致算法性能很差，甚至得不到問題得可行解；種群太大時，盡管可增加優(yōu)化信息以阻止早熟收斂的發(fā)生，但無疑會增加計算量，從而使收斂時間太長。 pc 交叉概率用于控制交叉操作的頻率。 pm 變異概率是加大種群多樣性的重要因素。但是，變異概率太小則不會產(chǎn)生新個體，抑制早熟現(xiàn)象的能力較差，概率太大則會破壞掉很多較好的模式，使 GA 成為隨機搜索。評價值 (目標函數(shù) )較小的個體有較高的概率生存 ,即在下一代群體中再次出現(xiàn)。 其中 ,∑fi 表示指所有個體適應值之和。 第一種交叉算子 遼寧科技大學本科生畢業(yè)設計 第 22 頁 在用遺傳算法解決作業(yè)車間調(diào)度問題中 ,在對工序編碼的排序問題中 ,交叉算子不能簡單交換兩個個體的相應位置的基因段 ,因為這樣得到的后代個體可能不能滿足每個工件號重復 M次的要求。所以為了滿足我們的工序編碼的要求 ,本文采用另一種交叉 算子。 例如 :對于一個 4 個工件 4 個機器問題 ,假如父母個體為 : Parent1:1 3 4 2 4 2 3 3 1 4 3 2 1 4 2 1 Parent2:3 2 4 1 1 2 3 4 4 2 3 1 2 4 1 3 假設隨機選擇工件 1， 2，則從 parent1 得到的新串為： New1:1 h h 2 h 2 h h 1 h h 2 1 h 2 1 Part1:1 2 2 1 2 1 2 1 Part2:3 4 4 3 3 4 3 4 同樣從 Parent2 得到的新串為 New2:h 2 h 1 1 2 h h h 2 h 1 2 h 1 h Part1: 2 1 1 2 2 1 2 1 Part2: 3 4 3 4 4 3 4 3 然后用 Parent2 個體的 part2： 3 4 3 4 4 3 4 3 按照原來的相對順序逐個替換第一個父母個體 Parent1 產(chǎn)生的新串 New1： 1 h h 2 h 2 h h 1 h h 2 1 h 2 1 中的 h，得到的后代個體為： Parent1＇ :1 3 4 2 3 2 4 4 1 3 4 2 1 3 2 1 同理用 Parent1 個體的 part2： 3 4 4 3 3 4 3 4 按照原來的相對順序逐個替換第二個父 遼寧科技