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