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