【正文】 首先提出來的［7］。它將問題域中的可能解看作是群體的一個個體或染色體，并將每一個體編碼成符號串形式，對群體反復(fù)進(jìn)行基于遺傳學(xué)的操作（遺傳，交叉和變異），根據(jù)預(yù)定的目標(biāo)適應(yīng)度函數(shù)對每個個體進(jìn)行評價，依據(jù)適者生存，優(yōu)勝劣汰的進(jìn)化規(guī)則，不斷得到更優(yōu)的群體，同時以全局并行搜索方式來搜索優(yōu)化群體中的最優(yōu)個體，求得滿足要求的最優(yōu)解。化石記錄表明我們所觀察的復(fù)雜結(jié)構(gòu)的生命是在相對短的時間進(jìn)化而來的，對這一點(diǎn)包括生物學(xué)家在內(nèi)的許多人都感到驚奇。進(jìn)化是發(fā)生在編碼染色體上，通過對染色體的譯碼部分生成生物體，但下面幾個關(guān)于進(jìn)化理論的一般特性已被廣大人們所接受。，哪些適應(yīng)性好地個體的染色體經(jīng)常比差的個體的染色體有更多的繁殖機(jī)會。大多數(shù)生物體是通過自然選擇和有性生殖這兩種基本過程進(jìn)行演化的。自然選擇決定了群體中那些個個體能存活并繁殖，有性生殖保證了后代基因中的混合與重組。 基本遺傳算法 遺傳算法的基本思路；，并從求解空間中任選N個點(diǎn)組成初始群體；。 遺傳算法的模式定理選擇操作是遺傳算法中體現(xiàn)“適者生存”的關(guān)鍵一環(huán)，它能控制高適應(yīng)度的模式成指數(shù)級增長。其傳統(tǒng)實現(xiàn)建立在逐項比較的基礎(chǔ)上，算法復(fù)雜度為O（n＾2）。交換操作是有規(guī)則的信息交換，它能創(chuàng)建新的模式結(jié)構(gòu)，但又最低限度地破壞選擇操作過程所選擇的高適應(yīng)度的模式。但是如果其中一方個體不具有模式H，則有可能會引起另一個個體模式的改變。通過變異操作對個體串中單個位置進(jìn)行代碼替換，替換的概率為變異概率Pm，則該位置不發(fā)生變異的概率為1Pm。綜合上面所述，考慮到選擇操作、交換操作和變異操作對模式的影響，則第t代種群P(t)經(jīng)過遺傳操作后下一代種群P(t+1)具有模式H的個體總數(shù)為: ()該式表示了下述的模式定理。模式定理保證了較優(yōu)的模式(遺傳算法的較優(yōu)解)的數(shù)目呈指數(shù)增長，為解釋遺傳算法機(jī)理提供了數(shù)學(xué)基礎(chǔ)。這些模式在遺傳中很重要，稱為基因塊。模式定理保證了較優(yōu)模式的樣本數(shù)呈指數(shù)增長，從而使遺傳算法找到全局最優(yōu)解的可能性存在。上述結(jié)論并沒有得到證明，因而被稱為假設(shè)。 遺傳算法的收斂性分析遺傳算法要實現(xiàn)全局收斂，首先要求任意初始種群經(jīng)有限步都能到達(dá)全局最優(yōu)解，其次算法必須由保優(yōu)操作來防止最優(yōu)解的遺失。通常，種群太小則不能提供足夠的采樣點(diǎn)，以致算法性能很差。選擇操作使高適應(yīng)度個體能夠以更大的概率生存，從而提高了遺傳算法的全局收斂性。交叉操作用于個體對，產(chǎn)生新的個體，實質(zhì)上是在解空間中進(jìn)行有效搜索。概率太小時，交叉操作很少進(jìn)行，從而會使搜索停滯不前，造成算法的不收斂。但是，變異概率太小則很難產(chǎn)生新模式，變異概率太大則會使遺傳算法成為隨機(jī)搜索算法。由馬爾可夫鏈推導(dǎo)出來的一些結(jié)論:基本遺傳算法收斂于最優(yōu)解的概率為1,使用保留最優(yōu)個體策略的遺傳算法收斂于最優(yōu)解的概率為1。從總體上來說，每代之間所處理的個體要遠(yuǎn)大于其表面的數(shù)目，這就是遺傳算法獨(dú)特的隱含并行性。隱含并行性為遺傳算法的高效性提供了理論依據(jù)。(population size)種群數(shù)目的多少直接影響到遺傳算法的優(yōu)化性能和效率，種群選擇太小時，不能提供足夠多的個體，致使算法性能較差，易產(chǎn)生早熟收斂，甚至不能得到可行解。(crossover rate)交換概率Pc用于控制交換操作的頻率。交換概率太小的時候又容易產(chǎn)生搜索停滯不前的現(xiàn)象。增加種群多樣性具有重要意義。如果變異概率太大的時，遺傳算法易變成隨機(jī)搜索，如果變異概率太小，則不能產(chǎn)生新個體，不利于種群的多樣性。(scaling window)該參數(shù)用于作出由目標(biāo)值到適應(yīng)度函數(shù)值的調(diào)整。另一種為保優(yōu)策略，首先進(jìn)行純選擇，把目前最優(yōu)個體直接加入下一代種群中，該策略是為了防止最優(yōu)解的丟失，但在實際應(yīng)用中往往采取這兩種選擇策略結(jié)合的方法，并做適當(dāng)?shù)淖冃?。這種機(jī)制意味著搜索過程可以跳出局部最優(yōu)點(diǎn)，能很好地將局部搜索和全局搜索協(xié)調(diào)起來，達(dá)到全局最優(yōu)點(diǎn)。，而不是對參數(shù)本身，因此遺傳算法具有靈活性高的特點(diǎn)。，容易形成通用算法程序。，在存在噪聲的情況下，對同一問題利用遺傳算法求解所得的結(jié)果是相似的。，用遺傳算法求最優(yōu)解比較困難，因為染色體種群很可能過早地斂，而對以后變化了的數(shù)據(jù)不再產(chǎn)生變化。其中一種是所謂觸發(fā)式超級突變，就是當(dāng)染色體群體的質(zhì)量下降(彼此的區(qū)別減少)時增加突變概率。，但交叉和變異的重要性存在爭議。而另一種觀點(diǎn)則認(rèn)為交叉過程的作用只不過是在種群中推廣變異過程所造成的更新，對于初期的種群來說，交叉幾乎等效于一個非常大的變異率，而這么大的變異很可能影響進(jìn)化過程。，優(yōu)化問題要具體情況具體分析。 遺傳算法的進(jìn)展地球上自出現(xiàn)生命至今已有30多億年的歷史，從低級生物到高級生命再至擁有智慧的人類，這是一個漫長的生物進(jìn)化過程。通過不斷的選擇，使有利于生存發(fā)展的變異遺傳下去，積累下來，使變異和遺傳向著適應(yīng)環(huán)境的方向發(fā)展。 遺傳算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經(jīng)過基因（gene）編碼的一定數(shù)目的個體(individual)組成。染色體作為遺傳物質(zhì)的主要載體，即多個基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個體的形狀的外部表現(xiàn)，如黑頭發(fā)的特征是由染色體中控制這一特征的某種基因組合決定的。由于仿照基因編碼的工作很復(fù)雜，我們往往進(jìn)行簡化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（generation）演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應(yīng)度（fitness）大小選擇（selection）個體，并借助于自然遺傳學(xué)的遺傳算子（genetic operators）進(jìn)行組合交叉（crossover）和變異（mutation），產(chǎn)生出代表新的解集的種群。隨著應(yīng)用領(lǐng)域的擴(kuò)展，遺傳算法的研究出現(xiàn)了幾個引人注目的新動向［9］：一是基于遺傳算法的機(jī)器學(xué)習(xí)，這一新的研究課題把遺傳算法從歷來離散的搜索空間的優(yōu)化搜索算法擴(kuò)展到具有獨(dú)特的規(guī)則生成功能的嶄新的機(jī)器學(xué)習(xí)算法［10］。二是遺傳算法正日益和神經(jīng)網(wǎng)絡(luò)［12］、模糊推理以及混沌理論等其它智能計算方法相互滲透和結(jié)合，這對開拓21世紀(jì)中新的智能計算技術(shù)將具有重要的意義。這一研究不僅對遺傳算法本身的發(fā)展，而且對于新一代智能計算機(jī)體系結(jié)構(gòu)的研究都是十分重要的。所謂人工生命即是用計算機(jī)模擬自然界豐富多彩的生命現(xiàn)象，其中生物的自適應(yīng)、進(jìn)化和免疫等現(xiàn)象是人工生命的重要研究對象，而遺傳算法在這方面將會發(fā)揮一定的作用，五是遺傳算法和進(jìn)化規(guī)劃（Evolution Programming,EP）以及進(jìn)化策略（Evolution Strategy,ES）等進(jìn)化計算理論日益結(jié)合。目前，這三者之間的比較研究和彼此結(jié)合的探討正形成熱點(diǎn)。 1996年，舉行了第1次遺傳程序設(shè)計國際會議，該領(lǐng)域己引起越來越多的相關(guān)學(xué)者們的興趣。此后，Holland指導(dǎo)學(xué)生完成了多篇有關(guān)遺傳算法研究的論文。1975年是遺傳算法研究歷史上十分重要的一年。Holland在該書中系統(tǒng)地闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法的理論研究和發(fā)展極其重要的模式理論（schema theory）。同年， Jong完成了他的博士論文《一類遺傳自適應(yīng)系統(tǒng)的行為分析》（An Analysis of the Behavior of a Class of Genetic Adaptive System）。盡管De Jong和Hollstien 一樣主要側(cè)重于函數(shù)優(yōu)化的應(yīng)用研究，但他將選擇、交叉和變異操作進(jìn)一步完善和系統(tǒng)化，同時又提出了諸如代溝（generation gap）等新的遺傳操作技術(shù)。進(jìn)入八十年代，遺傳算法迎來了興盛發(fā)展時期，無論是理論研究還是應(yīng)用研究都成了十分熱門的課題。1989年，《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法》（Genetic Algorithms in Search , Optimization, and Machine Learning）。同年，美國斯坦福大學(xué)的Koza基于自然選擇原則創(chuàng)造性地提出了用層次化的計算機(jī)程序來表達(dá)問題的遺傳程序設(shè)計( genetic programming, GP)方法，成功地解決了許多問題。此外，以遺傳算法的理論基礎(chǔ)為中心的學(xué)術(shù)會議還有Foundations of Genetic Algorithms，該會也是從1990年開始隔年召開一次。1991年，《遺傳算法手冊》（Handbook of Genetic Algorithms），其中包括了遺傳算法在工程技術(shù)和社會生活中的大量應(yīng)用實例。1994年，他又出版了《遺傳程序設(shè)計，第二冊:可重用程序的自動發(fā)現(xiàn)》深化了遺傳程序設(shè)計的研究，使程序設(shè)計自動化展現(xiàn)了新局面。1993年，MIT出版社創(chuàng)刊了新雜志《Evolutionary Computation》?！禔dvanced Computational Intelligence》雜志即將發(fā)刊。遺傳算法主要應(yīng)用在機(jī)器學(xué)習(xí)中。一般的學(xué)習(xí)系統(tǒng)要求具有隨時間推移逐步調(diào)整有關(guān)參數(shù)或者改變自身結(jié)構(gòu)以更加適應(yīng)環(huán)境，更好達(dá)到目標(biāo)的能力。除了機(jī)器學(xué)習(xí)之外遺傳算法所涉及的主要領(lǐng)域還有自動控制、規(guī)劃設(shè)計、組合優(yōu)化、圖象處理、信號處理、人工生命、模式識別，神經(jīng)網(wǎng)絡(luò)、自適應(yīng)控制、生物科學(xué)、系統(tǒng)工程、社會科學(xué)等。今后幾年，拓廣更加多樣的應(yīng)用領(lǐng)域，將是GA發(fā)展的主流。與此同時，理論方面同樣有大量工作要做，例如：控制參數(shù)的選擇；交換和突變這兩類最重要的算子的確切作用；并行GA和分布式GA的研究。這對GA的實際應(yīng)用關(guān)系重大。與自然界相似，遺傳算法對待求解問題本身一無所知，它所需要的僅是對算法所產(chǎn)生的每個染色體進(jìn)行評價，并基于適應(yīng)度值來評價染色體，使適用性好的染色體比適應(yīng)性差的染色體有更多的繁殖機(jī)會。 研究過程中的幾個關(guān)鍵問題 設(shè)備死鎖現(xiàn)象初始解群是問題的起點(diǎn)，解決設(shè)備死鎖問題必須從初始解群開始。 設(shè)備死鎖示意圖，分屬工件1和工件2的總共四個工序都處于循環(huán)等待其前面工序或前道工序結(jié)束加工的狀態(tài)之中，從而使設(shè)備1和設(shè)備2處于空轉(zhuǎn)狀態(tài)，即產(chǎn)生了所謂的死鎖現(xiàn)象。遺傳算法的工作基礎(chǔ)是選擇適當(dāng)?shù)姆椒ū硎緜€體和問題的解(作為進(jìn)化的個體)。由于遺傳算法不能直接處理空間解的數(shù)據(jù)，在解決此車間調(diào)度問題上把它們轉(zhuǎn)換成遺傳空間的基因按一定結(jié)構(gòu)組成的染色體或個體，也就是通過編碼將它們表示成遺傳空間的基因型串結(jié)構(gòu)數(shù)據(jù)。 加工時間和工藝約束項目工件操作序列123操作時間J1J2J3313352233機(jī)器J1J2J3M1M1M2M2M3M1M3M2M3，假設(shè)染色體為{2 1 2 3 1 1 3 2 3}，Oijk表示第i個工件的第j個工序在第k個機(jī)器上加工（以下同），則對機(jī)器加工順序的工藝約束，該染色體對應(yīng)的有序操作表為[O211 O111 O223 O312 O122 O133 O321 O232 O333]，即首先安排第二個工件的第一個操作步驟，然后安排第一個工件的第一個操作步驟，第二項任務(wù)的第二個操作步驟，…以次類推。t1296J3J3J3J1J1J1J2J2J2tt1M110734M3M2 Gantte圖（jobbased representation）將每個染色體用n個代表工件的基因組成，是所有工件的一個排列。其基本思想是只對任務(wù)進(jìn)行編碼，然后按照編碼在染色體中的順序來以相應(yīng)的優(yōu)先級別安排任務(wù)。對于有三項任務(wù)的調(diào)度問題，假設(shè)染色體為[2 3 1]，則可以解釋為首先安排第二項任務(wù)的所有操作，其次是第三項任務(wù)，最后才輪到第一項任務(wù)。用于表示機(jī)器上加工工件的一個排列順序。前面兩種編碼方式比較復(fù)雜，下面我們用基于操作的編碼方式來解此車間調(diào)度問題： 把調(diào)度編碼為工序的序列，每個基因代表一道工序，給所有同一工件的工序指定相同的符號，其解碼原則是將染色體上得基因按照從左到右得順序解釋為任務(wù)相應(yīng)順序的操作。顯然，這種解碼過程可產(chǎn)生活動調(diào)度。只需改變工序的順序，即可得到不同的調(diào)度結(jié)果，即不同的生產(chǎn)周期。因為每個工件有三道工序，所以每個工件在一個染色體中剛好出現(xiàn)三次?？梢钥闯龉ぜ2的所有工序都用相同的符號2來命名，并且根據(jù)它出現(xiàn)在染色體中的順序加以解釋，工件的工序和加工機(jī)器的對應(yīng)關(guān)系如下所示。 初始種群的生成在N個工件M臺機(jī)器的排序問題中，對每個機(jī)器的加工存在加工工藝順約束，這個工藝約束表示為工件的加工順序矩陣：M11 M12 … M1MM（J,M）= M21 M22 … M2M ： ： ： ： ()Mn1 Mn2