【文章內容簡介】 程序來表達問題的遺傳程序設計( genetic programming, GP)方法，成功地解決了許多問題。 在歐洲，從1990年開始每隔一年舉辦一次Parallel Problem Solving from Nature 學術會議，其中遺傳算法是會議主要內容之一。此外，以遺傳算法的理論基礎為中心的學術會議還有Foundations of Genetic Algorithms，該會也是從1990年開始隔年召開一次。這些國際會議論文，集中反映了遺傳算法近些年來的最新發(fā)展和動向。1991年，《遺傳算法手冊》（Handbook of Genetic Algorithms），其中包括了遺傳算法在工程技術和社會生活中的大量應用實例。 1992年，Koza發(fā)表了他的專著《遺傳程序設計:基于自然選擇法則的計算機程序設計》。1994年，他又出版了《遺傳程序設計，第二冊:可重用程序的自動發(fā)現(xiàn)》深化了遺傳程序設計的研究，使程序設計自動化展現(xiàn)了新局面。有關遺傳算法的學術論文也不斷在《Artificial Intelligence》、《Machine Learning》、《Information science》、《Parallel Computing》、《Genetic Programming and Evoluable Machines》《IEEE Transactions on Neural Networks》,《IEEE Transactions on Signal Processing》等雜志上發(fā)表。1993年，MIT出版社創(chuàng)刊了新雜志《Evolutionary Computation》。1997年，IEEE又創(chuàng)刊了《Transactions on Evolutionary Computation》?！禔dvanced Computational Intelligence》雜志即將發(fā)刊。目前，關于遺傳算法研究的熱潮仍在持續(xù)，越來越多的從事不同領域的研究人員已經或正在置身于有關遺傳算法的研究或應用之中現(xiàn)在隨著科學技術的日益發(fā)展，遺傳算法有了突飛猛進的發(fā)展，不僅理論研究十分活躍，而在越來越多的領域得到發(fā)展。遺傳算法主要應用在機器學習中。遺傳算法適合于維數(shù)很高、體積很大、環(huán)境復雜、問題結構不十分清楚的場合，機器學習就屬于這類情況。一般的學習系統(tǒng)要求具有隨時間推移逐步調整有關參數(shù)或者改變自身結構以更加適應環(huán)境，更好達到目標的能力。由于多樣性和復雜性，通常難以建立完善的理論以指導整個學習過程，從而使傳統(tǒng)尋優(yōu)技術的應用受到限制，而這恰好是遺傳算法發(fā)揮的長處。除了機器學習之外遺傳算法所涉及的主要領域還有自動控制、規(guī)劃設計、組合優(yōu)化、圖象處理、信號處理、人工生命、模式識別，神經網絡、自適應控制、生物科學、系統(tǒng)工程、社會科學等。在人工智能研究中，現(xiàn)在還認為人們認為“遺傳算法、自適應系統(tǒng)、細胞自動機、混沌理論與人工智能一樣，都是對今后十年的計算技術有重大影響的關鍵技術”。今后幾年，拓廣更加多樣的應用領域，將是GA發(fā)展的主流。這也是本世紀高新技術迅速發(fā)展帶有規(guī)律性的特點，即面向應用。與此同時，理論方面同樣有大量工作要做，例如：控制參數(shù)的選擇；交換和突變這兩類最重要的算子的確切作用；并行GA和分布式GA的研究。不論從理論還是應用的角度看，最緊迫的應是關于算法收斂性問題的研究，特別是過早收斂的防止。這對GA的實際應用關系重大。 小結遺傳算法是一類隨機化算法，但是它不是簡單的隨機走動，它可以有效地利用已經有的信息處理來搜索那些有希望改善解質量的串，類似于自然進化，遺傳算法通過作用于染色體上的基因，尋找好的染色體來求解問題。與自然界相似，遺傳算法對待求解問題本身一無所知，它所需要的僅是對算法所產生的每個染色體進行評價，并基于適應度值來評價染色體，使適用性好的染色體比適應性差的染色體有更多的繁殖機會。3 用遺傳算法對具體問題的解決與探討遺傳算法在解決作業(yè)車間調度問題上比經典的啟發(fā)式算法好，同時遺傳算法比傳統(tǒng)的搜索技術有更強的優(yōu)越性，因為它不僅能解決某一特定問題，而且可以適應不同的問題形式。 研究過程中的幾個關鍵問題 設備死鎖現(xiàn)象初始解群是問題的起點，解決設備死鎖問題必須從初始解群開始。本研究的設備死鎖不在同一臺機器上而是在不同的機器上產生死鎖現(xiàn)象，所謂的設備死鎖現(xiàn)象如圖所示，其中括號內的兩個數(shù)據，意義為（工件號，工序號）。 設備死鎖示意圖，分屬工件1和工件2的總共四個工序都處于循環(huán)等待其前面工序或前道工序結束加工的狀態(tài)之中，從而使設備1和設備2處于空轉狀態(tài)，即產生了所謂的死鎖現(xiàn)象。 參數(shù)編碼遺傳編碼技術是實施遺傳算法的核心。遺傳算法的工作基礎是選擇適當?shù)姆椒ū硎緜€體和問題的解(作為進化的個體)。對于同一問題可以有不同的編碼表示方法。由于遺傳算法不能直接處理空間解的數(shù)據，在解決此車間調度問題上把它們轉換成遺傳空間的基因按一定結構組成的染色體或個體，也就是通過編碼將它們表示成遺傳空間的基因型串結構數(shù)據。目前，調度問題中主要的遺傳算法編碼方式有以下幾種：（operationbased representation）其基本思想是將所有工件的操作進行編碼，不同的工件用不同的編碼表示，而同一工件的所有操作在染色體中則用相同的編碼表示，其解碼原則是將染色體上的基因按照從左到右的順序解釋為相應工件的操作順序，具有相同編碼的基因按照其在整個染色體中的位置解釋為工件相應順序的操作。 加工時間和工藝約束項目工件操作序列123操作時間J1J2J3313352233機器J1J2J3M1M1M2M2M3M1M3M2M3，假設染色體為{2 1 2 3 1 1 3 2 3}，Oijk表示第i個工件的第j個工序在第k個機器上加工（以下同），則對機器加工順序的工藝約束，該染色體對應的有序操作表為[O211 O111 O223 O312 O122 O133 O321 O232 O333]，即首先安排第二個工件的第一個操作步驟，然后安排第一個工件的第一個操作步驟，第二項任務的第二個操作步驟，…以次類推。（我們用Gantte圖表示一個調度）。t1296J3J3J3J1J1J1J2J2J2tt1M110734M3M2 Gantte圖（jobbased representation）將每個染色體用n個代表工件的基因組成，是所有工件的一個排列。解碼過程是先加工第1號工件的所有操作，然后依次以最好允許加工時間加工后面所有操作。其基本思想是只對任務進行編碼，然后按照編碼在染色體中的順序來以相應的優(yōu)先級別安排任務。例如，對于上述3*3例子。對于有三項任務的調度問題，假設染色體為[2 3 1]，則可以解釋為首先安排第二項任務的所有操作，其次是第三項任務，最后才輪到第一項任務。（preferences listbeset representation）每個染色體用分別對應于m臺不同機器的m個子串構成，各子串是一個長度為n的符號串。用于表示機器上加工工件的一個排列順序。 ()對染色體的解釋為：在第一臺機器上首先應該安排第二項工件的操作，其次是第一項工件的操作，第三項工件的操作；在第二臺機器上首先應該安排第三項工件的操作，然后是第一、二項任務的操作，以此類推。前面兩種編碼方式比較復雜，下面我們用基于操作的編碼方式來解此車間調度問題： 把調度編碼為工序的序列，每個基因代表一道工序，給所有同一工件的工序指定相同的符號，其解碼原則是將染色體上得基因按照從左到右得順序解釋為任務相應順序的操作。這是一種直接對調度方案進行編碼的方式。顯然，這種解碼過程可產生活動調度。對于n個工件m機器問題，一個染色體包括個n*m個基因，每個個體出現(xiàn)在染色體中m次，每個基因不表明具體的工序，而是指上下依賴關系的工序。只需改變工序的順序，即可得到不同的調度結果，即不同的生產周期。如果染色體位為[3 2 2 1 1 2 3 1 3 1]，其中1表示工件j1，2表示工件j2，3表示工件j3。因為每個工件有三道工序，所以每個工件在一個染色體中剛好出現(xiàn)三次。例如，在以上給定的染色體中出現(xiàn)三個2表示工件j2的三道工序，第一個2對應工件j2的第一道工序在機器1上加工，第二個2對應工件j2的第二道工序在機器2上加工，第三個2對應工件j2的第三道工序在機器3上加工?？梢钥闯龉ぜ2的所有工序都用相同的符號2來命名，并且根據它出現(xiàn)在染色體中的順序加以解釋，工件的工序和加工機器的對應關系如下所示。 染色體1 1 2 2 3 3 1 1 2 3 ↓ ↓ ↓ 機器 1 2 3一個好的調度方法（換句話說就是染色體對應的適應度值高），可以有效提機器的利用率，降低機器空閑的時間長度，從而達到優(yōu)化的目的，遺傳算法就是來尋找這樣的更優(yōu)的調度策略。 初始種群的生成在N個工件M臺機器的排序問題中，對每個機器的加工存在加工工藝順約束，這個工藝約束表示為工件的加工順序矩陣：M11 M12 … M1MM（J,M）= M21 M22 … M2M ： ： ： ： ()Mn1 Mn2 … MnM。相應的每個加工操作有時間矩陣： T11 T12 … T1M T21 T22 … T2M T(J,M)= ： ： ： ： () TN1 TN2 … TNM 其中第J行表示第J個工件的機器加工時間,時間為零表示工件不在機器上加工.,2.. .. ..N(每個重復有N*M個操作)的全排列即是一個初始個體,算法如下：STEP1：用行號1代替機器順序矩陣M(j,m)的第j行的所有元素,零元素保持不變,若產生的矩陣為GEN。STEP2：產生一個整數(shù)隨機數(shù)1=p=N。STEP3：令chrom（i）=p，并且將矩陣GEN的p行GEN（p，：）左移一個元素，此行移出的最后一個元素用零代替。STEP4：重復STIP2，STEP3，直到GEN的所有元素為零。產生的chrom為一個個體。重復STEP1，STEP2，STEP3，STEP4，直到種群滿。這是用遺傳算法解決車間調度問題的一種初始化群體方法［13］，但是它并不適用于基于操作的編碼方式。初始種群的生成也可以用隨機方法產生，這是因為群體中的個體都是由工件的符號組成的。 個體的適應度函數(shù)在遺傳算法中,適應度是描述個體性能的主要指標。根據適應度的大小,對個體進行優(yōu)勝劣汰。適應度是驅動遺傳算法的動力。從生物學角度講,適應度相當于“生存競爭,適者生存”的生物生存能力,在遺傳過程中具有重要意義。適應度函數(shù)就是目標函數(shù)，在用遺傳算法解決車間調度問題里，定義個體的適應度函數(shù)為在M臺機器上排序加工完N個工件所需的時間，根據染色體編碼的思想提出的適應度算法如下：STEP1:定義ti(n)為每個工件的可加工時間，初始化向量為零向量。STEP2:chrom（i）對應相應工序的加工機器為machiner（i）。 ti(chrom(1))=ti(chrom(1),machine(1))STEP3:for i=2 to n For k=1 to nti(chrom(i))=ti(chrom(i1))+max(ti(chrom(ik),machine(ik)+k)) 其中若當ik=0,則ti(chrom(ik),machine(ik))=0,還有要判斷chorm(i)所對應的工件在以前是否加工過，若加工過，則ti(chrom(i))=ti(chorm(i1))。STEP4:求出適應度函數(shù)F=ti(chorm(n))。 算法參數(shù)標準GA有4個關鍵參數(shù)，包括種群數(shù)目（population size,記作M）、交叉概率（crossover rate,記作pc）、變異概率（mutation rate,記作pm）和代溝（generation gap,記作（G）。目前，如何確定GA的最優(yōu)參數(shù)仍舊是一個公開的問題，也是研究GA