【正文】 自從達(dá)爾文的進(jìn)化論得到人們的接受之后，生物學(xué)家們就對(duì)進(jìn)化機(jī)制產(chǎn)生了極大的興趣。雖然目前人們對(duì)進(jìn)化機(jī)制在一些方面還沒(méi)有弄清楚，但它們的一些特征已為人所知。，而不是發(fā)生在它們所編碼地生物個(gè)體上。，變異可以使生物體子代的染色體不同于它們父代的染色體，通過(guò)結(jié)合兩個(gè)父代染色體的物質(zhì)，重組過(guò)程可以在子代中產(chǎn)生有很大差異的染色體。有關(guān)產(chǎn)生個(gè)體的信息包含在個(gè)體所攜帶的染色體的集合以及染色體編碼的結(jié)構(gòu)之中，這些個(gè)體會(huì)很好的適應(yīng)它們的環(huán)境。自然選擇的原則是適應(yīng)者生存，不適者淘汰。比起那些僅包含單個(gè)親本的基因拷貝和依靠偶然變異來(lái)改進(jìn)的后代，這種由基因重組產(chǎn)生的后代進(jìn)化要快得多。運(yùn)用選擇、交叉、變異算子產(chǎn)生新一代群體；，若找到滿(mǎn)足問(wèn)題的最優(yōu)解，結(jié)束；否則，轉(zhuǎn)步驟3。最常用的選擇方式是“輪盤(pán)賭”法。通過(guò)把各碼鏈適應(yīng)值轉(zhuǎn)換為一組具有線性序的區(qū)間，從而可利用二分查找法實(shí)現(xiàn)“輪盤(pán)賭”選擇操作的遞歸算法，使時(shí)間復(fù)雜度下降到O（nlog2n）。假設(shè)交換操作是采用的單點(diǎn)隨機(jī)雜交方式，隨機(jī)選取雜交的起始位置，交叉概率為Pc，兩個(gè)具有相同模式H的個(gè)體發(fā)生交換，即雜交操作，不會(huì)改變模式H。其中一方不具有模式H的概率為1 p(H, t)，當(dāng)兩個(gè)個(gè)體發(fā)生交換時(shí)，如果引起模式H的改變，只可能將交換的起始位置選擇在第一個(gè)模式位到最后一個(gè)模式位之間的任何一個(gè)位置上，此時(shí)，使模式H生存的概率Ps，為: ()在交換過(guò)程中，可能使兩個(gè)都不具備模式H的個(gè)體經(jīng)交換后產(chǎn)生模式H，故生存概率（）只是一個(gè)下界，則有： ()綜合考慮選擇操作，模式H在下一代中的數(shù)量可以用下式來(lái)綜合估計(jì): ()從上式可以看出，模式的平均適應(yīng)度高于群體平均適應(yīng)度，并且具有短定義距的模式，將在下一代中成指數(shù)級(jí)的增長(zhǎng)。要使一個(gè)模式H在變異操作過(guò)程中不被破壞，就要保證模式H中確定位必須保證不變，因此，模式H保持不變的概率為: ()上式中O(H)為該模式的階數(shù)。模式定理:在遺傳算子選擇、交換、變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式，在子代中將得以指數(shù)級(jí)增長(zhǎng)。由模式定理可知，具有低階、短定義距以及平均適應(yīng)度高于群體平均適應(yīng)度的模式在后代中呈指數(shù)級(jí)增長(zhǎng)?；驂K假設(shè):遺傳算法通過(guò)短定義距、低階以及高平均適應(yīng)度的模式(基因塊)，在遺傳操作下相互結(jié)合，最終接近全局最優(yōu)解。而基因塊假設(shè)則指出了在遺傳算子的作用下，算法具有生成全局最優(yōu)解的能力，即能生成高階、長(zhǎng)定義距、高平均適應(yīng)度的模式，最終生成全局最優(yōu)解。目前已經(jīng)有大量的實(shí)踐證據(jù)支持這一假設(shè)，盡管大量的證據(jù)并不等于理論證明，但是至少可以肯定的是對(duì)很多經(jīng)常碰到的問(wèn)題，遺傳算法都是適用的。與算法收斂性有關(guān)的因素主要包括種群規(guī)模、選擇操作、交叉概率和變異概率。種群太大，盡管可以增加優(yōu)化信息，阻止早熟收斂的發(fā)生，但無(wú)疑會(huì)增加計(jì)算量，造成收斂時(shí)間太長(zhǎng)，表現(xiàn)為收斂速度緩慢。如果在算法中采用最優(yōu)保存策略，即將父代群體中最佳個(gè)體保留下來(lái)，不參加交叉和變異操作，使之直接進(jìn)入下一代，最終可使遺傳算法以概率1收斂于全局最優(yōu)解。交叉概率太大時(shí)，種群中個(gè)體更新很快，會(huì)造成高適應(yīng)度值的個(gè)體很快被破壞掉。變異操作是對(duì)種群模式的擾動(dòng)，有利于增加種群的多樣性。遺傳操作對(duì)收斂性的影響，可利用馬爾可夫鏈對(duì)遺傳算法進(jìn)行分析，從而論證了遺傳算法在收斂性方面的一些重要性質(zhì)，有力地支持了遺傳算法的理論基礎(chǔ)。隱含并行性定理:遺傳算法所處理的模式總數(shù)與其群體規(guī)模N的立方成正比，即: m=O(N3) （）由該定理可知，雖然表面上每代處理的個(gè)體數(shù)目都是一定的，但是由于每個(gè)個(gè)體都隱含著多種不同的模式，所以每次參與遺傳算子操作的個(gè)體卻不僅僅是兩個(gè)。由隱含并行性定理可知，雖然表面上每代僅對(duì)N個(gè)個(gè)體處理操作，而事實(shí)上處理了O(N3)個(gè)模式，且無(wú)需額外存儲(chǔ)。 基本遺傳算法參數(shù)說(shuō)明對(duì)遺傳算法性能有影響的參數(shù)主要有:種群數(shù)目N、交換概率Pc、變異概率Pm、代溝G、尺度窗口W、和選擇策略S等。種群選擇過(guò)大時(shí)，雖然能避免早熟收斂，但是增加了計(jì)算量。交換概率太大的時(shí)，易產(chǎn)生更新過(guò)快，從而破壞掉高適應(yīng)度個(gè)體的現(xiàn)象。(mutation rate)變異概率Pm。通常選取一個(gè)較低的變異概率。(generation gap)代溝G用于控制每一代群體被替換的比例，每代有N(1G)個(gè)父代個(gè)體選中進(jìn)入下一代種群中，該參數(shù)和交換、變異概率以及選擇策略有很大關(guān)系，它并不是一個(gè)初始參數(shù)，而是評(píng)價(jià)遺傳算法的一個(gè)參數(shù)。(selection strategy)一般來(lái)說(shuō)有兩種選擇策略，一種為純選擇，種群中每個(gè)個(gè)體根據(jù)其適應(yīng)度值進(jìn)行比例選擇，即個(gè)體被選擇的概率與其適應(yīng)度值成正比。 遺傳算法的優(yōu)缺點(diǎn) 遺傳算法的優(yōu)點(diǎn)遺傳算法在解決優(yōu)化問(wèn)題過(guò)程中有如下優(yōu)點(diǎn):，而不是從單個(gè)解開(kāi)始。，遺傳算法的初始種群本身就帶有大量與最優(yōu)解甚遠(yuǎn)的信息，通過(guò)選擇、交換、變異操作，能迅速排除與最優(yōu)解相差極大的串，這是一個(gè)強(qiáng)烈的濾波過(guò)程，并且是一個(gè)并行濾波機(jī)制。，而非傳統(tǒng)方法的采用目標(biāo)函數(shù)的導(dǎo)數(shù)信息或者求解問(wèn)題域內(nèi)知識(shí)，因此具有普遍適應(yīng)性和可規(guī)?；奶攸c(diǎn)。由于遺傳算法使用適應(yīng)度值這一信息進(jìn)行搜索，并不需要問(wèn)題導(dǎo)數(shù)等與問(wèn)題直接相關(guān)的信息。 遺傳算法的缺點(diǎn)，而不能達(dá)到全局最優(yōu)。對(duì)于這個(gè)問(wèn)題，研究者提出了一些方法增加基因的多樣性，從而防止過(guò)早的收斂。另一種叫隨機(jī)外來(lái)染色體，是偶爾加入一些全新的隨機(jī)生成的染色體個(gè)體，從而增加染色體多樣性。一種觀點(diǎn)認(rèn)為交叉比變異更重要，因?yàn)樽儺悆H僅是保證不丟失某些可能的解。“大海撈針”的問(wèn)題，所謂“大海撈針”問(wèn)題就是沒(méi)有一個(gè)確切的適應(yīng)度函數(shù)表征個(gè)體好壞的問(wèn)題，遺傳算法對(duì)這類(lèi)問(wèn)題無(wú)法找到收斂的路。所以在使用遺傳算法的同時(shí)，也可以嘗試其它算法，互相補(bǔ)充，甚至根本不用遺傳算法。1859年，達(dá)爾文根據(jù)長(zhǎng)期對(duì)世界各地的考察以及人工選擇的實(shí)驗(yàn)，發(fā)表了《物種起源》，系統(tǒng)地提出并建立了以“優(yōu)勝劣汰”、“適者生存”的自然選擇為基礎(chǔ)的進(jìn)化論學(xué)說(shuō)，根據(jù)他的進(jìn)化論，生物發(fā)展進(jìn)化的原因主要有三個(gè)，就是遺傳、變異和選擇。經(jīng)過(guò)長(zhǎng)時(shí)間的遺傳、變異和選擇，生物便逐漸從簡(jiǎn)單到復(fù)雜，從低級(jí)到高級(jí)不斷地進(jìn)化和發(fā)展。每個(gè)個(gè)體實(shí)際上是染色體(chromosome)帶有特征的實(shí)體。因此，在一開(kāi)始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射即編碼工作。這個(gè)過(guò)程將導(dǎo)致種群像自然進(jìn)化一樣的后生代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過(guò)解碼（decoding），可以作為問(wèn)題近似最優(yōu)解。這一新的學(xué)習(xí)機(jī)制對(duì)于解決人工智能［11］中知識(shí)獲取和知識(shí)優(yōu)化精煉的瓶頸難題帶來(lái)了希望。三是并行處理的遺傳算法的研究十分活躍。四是遺傳算法和另一個(gè)稱(chēng)為人工生命的嶄新研究領(lǐng)域正不斷滲透。EP和ES幾乎是和遺傳算法同時(shí)獨(dú)立發(fā)展起來(lái)的，同遺傳算法一樣，它們也是模擬自然界生物進(jìn)化機(jī)制的智能計(jì)算方法，即同遺傳算法具有相同之處，也有各自的特點(diǎn)。近年來(lái)，遺傳程序設(shè)計(jì)運(yùn)用遺傳算法的思想自動(dòng)生成計(jì)算機(jī)程序解決了許多問(wèn)題，如預(yù)測(cè)、分類(lèi)、符號(hào)回歸和圖像處理等，作為一種新技術(shù)它己經(jīng)與遺傳算法并駕齊驅(qū)。1967年，“遺傳算法（Genetic Algorithms）”一詞。1971年。這一年Holland出版了他的著名專(zhuān)著《自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)》（Adaptation in Natural and Artificial Systems），這是第一本系統(tǒng)論述遺傳算法的專(zhuān)著，因此有人把1975年作為遺傳算法的誕生年。該理論首次確認(rèn)了結(jié)構(gòu)重組遺傳操作對(duì)于獲得隱并行性的重要性。該論文所做的研究工作，可看作是遺傳算法發(fā)展進(jìn)程中的一個(gè)里程碑，這是因?yàn)椋袶olland的模式理論與他的計(jì)算實(shí)驗(yàn)結(jié)合起來(lái)。可以認(rèn)為，De Jong的研究工作為遺傳算法及其應(yīng)用打下了堅(jiān)實(shí)的基礎(chǔ)，他所得出的許多結(jié)論，迄今仍具有普遍的指導(dǎo)意義。1985年，在美國(guó)召開(kāi)了第一屆遺傳算法國(guó)際會(huì)議（International Conference on Genetic Algorithms ，ICGA），并且成立國(guó)際遺傳算法學(xué)會(huì)（International Society of Genetic Algorithms ，ISGA），以后每?jī)赡昱e行一次。該書(shū)總結(jié)了遺傳算法研究的主要成果，對(duì)遺傳算法及其應(yīng)用作了全面而系統(tǒng)的論述。 在歐洲，從1990年開(kāi)始每隔一年舉辦一次Parallel Problem Solving from Nature 學(xué)術(shù)會(huì)議，其中遺傳算法是會(huì)議主要內(nèi)容之一。這些國(guó)際會(huì)議論文，集中反映了遺傳算法近些年來(lái)的最新發(fā)展和動(dòng)向。 1992年，Koza發(fā)表了他的專(zhuān)著《遺傳程序設(shè)計(jì):基于自然選擇法則的計(jì)算機(jī)程序設(shè)計(jì)》。有關(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ā)表。1997年，IEEE又創(chuàng)刊了《Transactions on Evolutionary Computation》。目前，關(guān)于遺傳算法研究的熱潮仍在持續(xù)，越來(lái)越多的從事不同領(lǐng)域的研究人員已經(jīng)或正在置身于有關(guān)遺傳算法的研究或應(yīng)用之中現(xiàn)在隨著科學(xué)技術(shù)的日益發(fā)展，遺傳算法有了突飛猛進(jìn)的發(fā)展，不僅理論研究十分活躍，而在越來(lái)越多的領(lǐng)域得到發(fā)展。遺傳算法適合于維數(shù)很高、體積很大、環(huán)境復(fù)雜、問(wèn)題結(jié)構(gòu)不十分清楚的場(chǎng)合，機(jī)器學(xué)習(xí)就屬于這類(lèi)情況。由于多樣性和復(fù)雜性，通常難以建立完善的理論以指導(dǎo)整個(gè)學(xué)習(xí)過(guò)程，從而使傳統(tǒng)尋優(yōu)技術(shù)的應(yīng)用受到限制，而這恰好是遺傳算法發(fā)揮的長(zhǎng)處。在人工智能研究中，現(xiàn)在還認(rèn)為人們認(rèn)為“遺傳算法、自適應(yīng)系統(tǒng)、細(xì)胞自動(dòng)機(jī)、混沌理論與人工智能一樣，都是對(duì)今后十年的計(jì)算技術(shù)有重大影響的關(guān)鍵技術(shù)”。這也是本世紀(jì)高新技術(shù)迅速發(fā)展帶有規(guī)律性的特點(diǎn)，即面向應(yīng)用。不論從理論還是應(yīng)用的角度看，最緊迫的應(yīng)是關(guān)于算法收斂性問(wèn)題的研究，特別是過(guò)早收斂的防止。 小結(jié)遺傳算法是一類(lèi)隨機(jī)化算法，但是它不是簡(jiǎn)單的隨機(jī)走動(dòng)，它可以有效地利用已經(jīng)有的信息處理來(lái)搜索那些有希望改善解質(zhì)量的串，類(lèi)似于自然進(jìn)化，遺傳算法通過(guò)作用于染色體上的基因，尋找好的染色體來(lái)求解問(wèn)題。3 用遺傳算法對(duì)具體問(wèn)題的解決與探討遺傳算法在解決作業(yè)車(chē)間調(diào)度問(wèn)題上比經(jīng)典的啟發(fā)式算法好，同時(shí)遺傳算法比傳統(tǒng)的搜索技術(shù)有更強(qiáng)的優(yōu)越性，因?yàn)樗粌H能解決某一特定問(wèn)題，而且可以適應(yīng)不同的問(wèn)題形式。本研究的設(shè)備死鎖不在同一臺(tái)機(jī)器上而是在不同的機(jī)器上產(chǎn)生死鎖現(xiàn)象，所謂的設(shè)備死鎖現(xiàn)象如圖所示，其中括號(hào)內(nèi)的兩個(gè)數(shù)據(jù)，意義為（工件號(hào)，工序號(hào)）。 參數(shù)編碼遺傳編碼技術(shù)是實(shí)施遺傳算法的核心。對(duì)于同一問(wèn)題可以有不同的編碼表示方法。目前，調(diào)度問(wèn)題中主要的遺傳算法編碼方式有以下幾種：（operationbased representation）其基本思想是將所有工件的操作進(jìn)行編碼，不同的工件用不同的編碼表示，而同一工件的所有操作在染色體中則用相同的編碼表示，其解碼原則是將染色體上的基因按照從左到右的順序解釋為相應(yīng)工件的操作順序，具有相同編碼的基因按照其在整個(gè)染色體中的位置解釋為工件相應(yīng)順序的操作。（我們用Gantte圖表示一個(gè)調(diào)度）。解碼過(guò)程是先加工第1號(hào)工件的所有操作，然后依次以最好允許加工時(shí)間加工后面所有操作。例如，對(duì)于上述3*3例子。（preferences listbeset representation）每個(gè)染色體用分別對(duì)應(yīng)于m臺(tái)不同機(jī)器的m個(gè)子串構(gòu)成，各子串是一個(gè)長(zhǎng)度為n的符號(hào)串。 ()對(duì)染色體的解釋為：在第一臺(tái)機(jī)器上首先應(yīng)該安排第二項(xiàng)工件的操作，其次是第一項(xiàng)工件的操作，第三項(xiàng)工件的操作；在第二臺(tái)機(jī)器上首先應(yīng)該安排第三項(xiàng)工件的操作，然后是第一、二項(xiàng)任務(wù)的操作，以此類(lèi)推。這是一種直接對(duì)調(diào)度方案進(jìn)行編碼的方式。對(duì)于n個(gè)工件m機(jī)器問(wèn)題，一個(gè)染色體包括個(gè)n*m個(gè)基因，每個(gè)個(gè)體出現(xiàn)在染色體中m次，每個(gè)基因不表明具體的工序，而是指上下依賴(lài)關(guān)系的工序。如果染色體位為[3 2 2 1 1 2 3 1 3 1]，其中1表示工件j1，2表示工件j2，3表示工件j3。例如，在以上給定的染色體中出現(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上加工。 染色體1 1 2 2 3 3 1 1 2 3 ↓ ↓ ↓ 機(jī)器 1 2 3一個(gè)好的調(diào)度方法（換句話說(shuō)就是染色體對(duì)應(yīng)的適應(yīng)度值高），可以有效提機(jī)器的利用率，降低機(jī)器空閑的時(shí)間長(zhǎng)度，從而達(dá)到優(yōu)化的目的，遺傳算法就是來(lái)尋找這樣的更優(yōu)的調(diào)度策略。相應(yīng)的每個(gè)加工操作有時(shí)間矩陣： T11 T12 … T1M T21 T22 … T2M T(J,M)= ： ： ： ： () TN