第一章-遺傳算法簡(jiǎn)介-PPT幻燈片

第一節(jié)緒論1.1.1遺傳算法發(fā)展歷史

遺傳算法(GeneticAlgorithm，簡(jiǎn)稱GA)起源于對(duì)生物系統(tǒng)所進(jìn)行的計(jì)算機(jī)模擬研究。美國(guó)Michigan大學(xué)的Ho11and教授及其學(xué)生受到生物模擬技術(shù)的啟發(fā)，創(chuàng)造出了一種基于生物遺傳和進(jìn)化機(jī)制的適合于復(fù)雜系統(tǒng)優(yōu)化的自適應(yīng)概率優(yōu)化技術(shù)——遺傳算法。1967年，Holland的學(xué)生Bagley在其博士論文中首次提出了“遺傳算法”一詞，他發(fā)展了復(fù)制、交叉、變異、顯性、倒位等遺傳算子，在個(gè)體編碼上使用雙倍體的編碼方法。Holland教授用遺傳算法的思想對(duì)自然和人工自適應(yīng)系統(tǒng)進(jìn)行了研究，提出了遺傳算法的基本定理——模式定理(SchcmaTheorem)，并于1975年出版了第一本系統(tǒng)論述遺傳算法和人工自適應(yīng)系統(tǒng)的專著《AdaptationinNaturalandArtificialSystems》。

在控制系統(tǒng)的離線設(shè)計(jì)方面遺傳算法被眾多的使用者證明是有效的策略。例如，Krishnakumar和Goldberg以及Bramlette和Cusin已證明使用遺傳優(yōu)化方法在太空應(yīng)用中導(dǎo)出優(yōu)異的控制器結(jié)構(gòu)比使用傳統(tǒng)方法如LQR和Powell(鮑威爾)的增音機(jī)設(shè)計(jì)所用的時(shí)間要少(功能評(píng)估)。Porter和Mohamed展示了使用本質(zhì)結(jié)構(gòu)分派任務(wù)的多變量飛行控制系統(tǒng)的遺傳設(shè)計(jì)方案。與此同時(shí)，另一些人證明了遺傳算法如何在控制器結(jié)構(gòu)的選擇中使用。

從遺傳算法的整個(gè)發(fā)展過程來看，20世紀(jì)70年代是興起階段，20世紀(jì)80年代是發(fā)展階段，20世紀(jì)90年代是高潮階段。遺傳算法作為一種實(shí)用、高效、魯棒性強(qiáng)的優(yōu)化技術(shù)，發(fā)展極為迅速，已引起國(guó)內(nèi)外學(xué)者的高度重視。1．1．2遺傳算法的優(yōu)點(diǎn)遺傳算法具有如下優(yōu)點(diǎn)：(1)對(duì)可行解表示的廣泛性。遺傳算法的處理對(duì)象不是參數(shù)本身，而是針對(duì)那些通過參數(shù)集進(jìn)行編碼得到的基因個(gè)體。此編碼操作使得遺傳算法可以直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作。所謂結(jié)構(gòu)對(duì)象，泛指集合、序列、矩陣、樹、圖、鏈和表等各種一維或二維甚至多維結(jié)構(gòu)形式的對(duì)象。這一特點(diǎn)使得遺傳算法具有廣泛的應(yīng)用領(lǐng)域。比如：

①通過對(duì)連接矩陣的操作，遺傳算法可用來對(duì)神經(jīng)網(wǎng)絡(luò)或自動(dòng)機(jī)的結(jié)構(gòu)或參數(shù)加以優(yōu)化。②通過對(duì)集合的操作，遺傳算法可實(shí)現(xiàn)對(duì)規(guī)則集合和知識(shí)庫的精煉而達(dá)到高質(zhì)量的機(jī)器學(xué)習(xí)目的。③通過對(duì)樹結(jié)構(gòu)的操作，用遺傳算法可得到用于分類的最佳決策樹。④通過對(duì)任務(wù)序列的操作，遺傳算法可用于任務(wù)規(guī)劃，而通過對(duì)操作序列的處理，可自動(dòng)構(gòu)造順序控制系統(tǒng)。(2)群體搜索特性。許多傳統(tǒng)的搜索方法都是單點(diǎn)搜索，這種點(diǎn)對(duì)點(diǎn)的搜索方法，對(duì)于多峰分布的搜索空間常常會(huì)陷于局部的某個(gè)單峰的極值點(diǎn)。相反，遺傳算法采用的是同時(shí)處理群體中多個(gè)個(gè)體的方法，即同時(shí)對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估。這一特點(diǎn)使遺傳算法具有較好的全局搜索性能，也使得遺傳算法本身易于并行化。

(3)不需要輔助信息。遺傳算法僅用適應(yīng)度函數(shù)的數(shù)值來評(píng)估基因個(gè)體，并在此基礎(chǔ)上進(jìn)行遺傳操作。更重要的是，遺傳算法的適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。對(duì)適應(yīng)度函數(shù)的惟一要求是，編碼必須與可行解空間對(duì)應(yīng)，不能有死碼。由于限制條件的縮小，使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。(4)內(nèi)在啟發(fā)式隨機(jī)搜索特性。遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo)它的搜索方向。概率僅僅是作為一種工具來引導(dǎo)其搜索過程朝著搜索空間的更優(yōu)化的解區(qū)域移動(dòng)的。雖然看起來它是一種盲目搜索方法，實(shí)際上它有明確的搜索方向，具有內(nèi)在的并行搜索機(jī)制。

(5)遺傳算法在搜索過程中不容易陷入局部最優(yōu)，即使在所定義的適應(yīng)度函數(shù)是不連續(xù)的、非規(guī)則的或有噪聲的情況下，也能以很大的概率找到全局最優(yōu)解。(6)遺傳算法采用自然進(jìn)化機(jī)制來表現(xiàn)復(fù)雜的現(xiàn)象，能夠快速可靠地解決求解非常困難的問題。(7)遺傳算法具有固有的并行性和并行計(jì)算的能力。(8)遺傳算法具有可擴(kuò)展性，易于同別的技術(shù)混合。

應(yīng)重點(diǎn)注意的是，遺傳算法對(duì)給定問題給出了大量可能的解答，并挑選最終的解答給用戶。要是一個(gè)特定問題并沒有單個(gè)的解，例如Pareto最優(yōu)解系列中，就像多目標(biāo)優(yōu)化和日程安排的案例中，遺傳算法將盡可能地用于識(shí)別可同時(shí)替換的解。1．1．3遺傳算法的不足之處

遺傳算法作為一種優(yōu)化方法，它存在自身的局限性：(1)編碼不規(guī)范及編碼存在表示的不準(zhǔn)確性。(2)單一的遺傳算法編碼不能全面地將優(yōu)化問題的約束表示出來?？紤]約束的一個(gè)方法就是對(duì)不可行解采用閾值，這樣，計(jì)算的時(shí)間必然增加。(3)遺傳算法通常的效率比其他傳統(tǒng)的優(yōu)化方法低。

(4)遺傳算法容易出現(xiàn)過早收斂。(5)遺傳算法對(duì)算法的精度、可信度、計(jì)算復(fù)雜性等方面，還沒有有效的定量分析方法。1.1.4遺傳算法與傳統(tǒng)方法的比較

對(duì)于一個(gè)求函數(shù)最大值的優(yōu)化問題(求函數(shù)最小值也類似)，一般可描述為帶約束條件的數(shù)學(xué)規(guī)劃模型，目標(biāo)函數(shù)和約束條件種類繁多，有的是線性的，有的是非線性的；有的是連續(xù)的，有的是離散的；有的是單峰值的。有的是多峰值的。隨著研究的深入，人們逐漸認(rèn)識(shí)到在很多復(fù)雜情況下要想完全精確地求出其最優(yōu)解是不可能的，也是不現(xiàn)實(shí)的，因而求出其近似最優(yōu)解或滿意解是人們主要研究的問題之一。對(duì)于類似上述最優(yōu)化問題，求最優(yōu)解或近似最優(yōu)解的傳統(tǒng)方法主要有解析法、隨機(jī)法和窮舉法。解析法主要包括爬山法和間接法。隨機(jī)法主要包括導(dǎo)向隨機(jī)方法和盲目隨機(jī)方法。而窮舉法主要包括完全窮舉法、回溯法、動(dòng)態(tài)規(guī)劃法和限界剪枝法。此類問題可以利用遺傳算法求解。而對(duì)于求解此類問題，遺傳算法與一般傳統(tǒng)方法有著本質(zhì)的區(qū)別。1．遺傳算法與啟發(fā)式算法的比較

啟發(fā)式算法是指通過尋求一種能產(chǎn)生可行解的啟發(fā)式規(guī)則，找到問題的一個(gè)最優(yōu)解或近似最優(yōu)解。該方法求解問題的效率較高，但是它對(duì)每一個(gè)所求的問題必須找出其特有的啟發(fā)式規(guī)則，這個(gè)啟發(fā)式規(guī)則一般無通用性，不適用于其他問題。但遺傳算法采用的不是確定性規(guī)則，而是強(qiáng)調(diào)利用概率轉(zhuǎn)換規(guī)則來引導(dǎo)搜索過程。

2．遺傳算法與爬山法的比較

爬山法是直接法、梯度法和Hessian法的通稱。爬山法首先在最優(yōu)解可能存在的地方選擇一個(gè)初始點(diǎn)，然后通過分析目標(biāo)函數(shù)的特性，由初始點(diǎn)移到一個(gè)新的點(diǎn)，然后再繼續(xù)這個(gè)過程。爬山法的搜索過程是確定的，它通過產(chǎn)生一系列的點(diǎn)收斂到最優(yōu)解(有時(shí)是局部最優(yōu)解)，而遺傳算法的搜索過程是隨機(jī)的，它產(chǎn)生一系列隨機(jī)種群序列。二者的主要差異可以歸納為如下兩點(diǎn)：(1)爬山法的初始點(diǎn)僅有一個(gè)，由決策者給出；遺傳算法的初始點(diǎn)有多個(gè)，是隨機(jī)產(chǎn)生的。(2)通過分析目標(biāo)函數(shù)的特性可知，爬山法由上一點(diǎn)產(chǎn)生一個(gè)新的點(diǎn)；遺傳算法通過遺傳操作，在當(dāng)前的種群中經(jīng)過交叉、變異和選擇產(chǎn)生下一代種群。對(duì)同一優(yōu)化問題，遺傳算法所使用的機(jī)時(shí)比爬山法所花費(fèi)的機(jī)時(shí)要多。但遺傳算法可以處理一些爬山法所不能解決的復(fù)雜的優(yōu)化問題。3．遺傳算法與窮舉法的比較

窮舉法就是對(duì)解空間內(nèi)的所有可行解進(jìn)行搜索，但是通常的窮舉法并不是完全窮舉法，即不是對(duì)所有解進(jìn)行嘗試，而是有選擇地嘗試，如動(dòng)態(tài)規(guī)劃法、限界剪枝法。對(duì)于特定的問題，窮舉法有時(shí)也表現(xiàn)出很好的性能。但一般情況下，對(duì)于完全窮舉法，方法簡(jiǎn)單易行，但求解效率太低；對(duì)于動(dòng)態(tài)規(guī)劃法、限界剪枝法，則魯棒性不強(qiáng)。相比較而言，遺傳算法具有較高的搜索能力和極強(qiáng)的魯棒性。

4．遺傳算法與盲目隨機(jī)法的比較

與上述的搜索方法相比，盲目隨機(jī)搜索法有所改進(jìn)，但它的搜索效率仍然不高。一般而言，只有解在搜索空間中形成緊致分布時(shí)，它的搜索才有效。而遺傳算法作為導(dǎo)向隨機(jī)搜索方法，是對(duì)一個(gè)被編碼的參數(shù)空間進(jìn)行高效搜索。經(jīng)過上面的探討，能看到遺傳算法與更多的傳統(tǒng)優(yōu)化方法在本質(zhì)上有著不同之處，主要有四點(diǎn)不同：(1)遺傳算法搜索種群中的點(diǎn)是并行的，而不是單點(diǎn)。(2)遺傳算法并不需要輔助信息或輔助知識(shí)，只需要影響搜索方向的目標(biāo)函數(shù)和相對(duì)應(yīng)的適應(yīng)度。(3)遺傳算法使用概率變換規(guī)則，而不是確定的變換規(guī)則。(4)遺傳算法工作使用編碼參數(shù)集，而不是自身的參數(shù)集(除了在實(shí)值個(gè)體中使用)。1.1.5遺傳算法的特點(diǎn)

遺傳算法從問題解集中開始搜索，而不是從單個(gè)解開始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個(gè)初始值迭代求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優(yōu)。遺傳算法求解時(shí)使用特定問題的信息極少，容易形成通用算法程序。由于遺傳算法使用適應(yīng)值這一信息進(jìn)行搜索，并不需要問題導(dǎo)數(shù)等與問題直接相關(guān)的信息。遺傳算法只需適應(yīng)值和串碼等通用信息，故幾乎可處理任何問題。遺傳算法有極強(qiáng)的容錯(cuò)能力，遺傳算法的初始串集本身就帶有大量與最優(yōu)解甚遠(yuǎn)的信息；通過選擇，交叉，變異操作能迅速排除與最優(yōu)解相差極大的串；這是一個(gè)強(qiáng)烈的濾波過程；并且是一個(gè)并行濾波機(jī)制。故而，遺傳算法有極強(qiáng)的容錯(cuò)能力。遺傳算法中有選擇，交叉，變異都是隨機(jī)操作，而不是確定的精確規(guī)則。這說明遺傳算法是采用隨機(jī)方法進(jìn)行最優(yōu)解搜索，選擇體現(xiàn)了向最優(yōu)解逼近，交叉體現(xiàn)了最優(yōu)解的產(chǎn)生，變異體現(xiàn)了全局最優(yōu)解的覆蓋。遺傳算法具有隱含的并行性。第二節(jié)遺傳算法的研究方向及應(yīng)用1.2.1研究方向：遺傳算法是多學(xué)科結(jié)合與滲透的產(chǎn)物，它已經(jīng)發(fā)展成一種自組織、自適應(yīng)的綜合技術(shù)，其研究方向主要有下述幾個(gè)方面。

1．基礎(chǔ)理論

遺傳算法的數(shù)學(xué)理論并不完善，張鈴等對(duì)遺傳算法的“模式定理”和“隱性并行性”進(jìn)行了分析研究，指出其不足并指出遺傳算法本質(zhì)上是一個(gè)具有定向制導(dǎo)的隨機(jī)搜索技術(shù)。

在遺傳算法中，群體規(guī)模和遺傳算子的控制參數(shù)的選取非常困難，但它們又是必不可少的實(shí)驗(yàn)參數(shù)，在這方面，已有一些具有指導(dǎo)性的實(shí)驗(yàn)結(jié)果。遺傳算法還有一個(gè)過早收斂的問題，如何阻止過早收斂也是人們正在研究的問題之一。2．分布并行遺傳算法

遺傳算法在操作上具有高度的并行性，許多研究人員都在探索在并行機(jī)和分布式系統(tǒng)上高效執(zhí)行遺傳算法的策略。對(duì)分布遺傳算法的研究表明，只要通過保持多個(gè)群體和恰當(dāng)控制群體間的相互作用來模擬并發(fā)執(zhí)行過程，即使不使用并行計(jì)算機(jī)，也能提高算法的執(zhí)行效率。遺傳算法的并行性主要從三個(gè)方面考慮，即個(gè)體適應(yīng)度評(píng)價(jià)的并行性、整個(gè)群體各個(gè)個(gè)體適應(yīng)度評(píng)價(jià)的并行性及子代群體產(chǎn)生過程的并行性。3．分類系統(tǒng)

分類系統(tǒng)屬于基于遺傳算法的機(jī)器學(xué)習(xí)中的一類，包括一個(gè)簡(jiǎn)單的基于串規(guī)則的并行生成子系統(tǒng)、規(guī)則評(píng)價(jià)子系統(tǒng)和遺傳算法子系統(tǒng)。分類系統(tǒng)被人們?cè)絹碓蕉嗟貞?yīng)用在科學(xué)、工程和經(jīng)濟(jì)領(lǐng)域中，是目前遺傳算法研究中一個(gè)十分活躍的方向。4．遺傳神經(jīng)網(wǎng)絡(luò)

遺傳神經(jīng)網(wǎng)絡(luò)包括連接級(jí)、網(wǎng)絡(luò)結(jié)構(gòu)和學(xué)習(xí)規(guī)則的進(jìn)化。遺傳算法與神經(jīng)網(wǎng)絡(luò)相結(jié)合，成功地用于從分析時(shí)間序列來進(jìn)行財(cái)政預(yù)算。在這些系統(tǒng)中，訓(xùn)練信號(hào)是模糊的，數(shù)據(jù)是有噪聲的，一般很難正確給出每個(gè)執(zhí)行的定量評(píng)價(jià)，如果采用遺傳算法學(xué)習(xí)，就能克服這些困難，顯著提高系統(tǒng)性能。Muhlenbein分析了多層感知網(wǎng)絡(luò)的局限性，并猜想下一代神經(jīng)網(wǎng)絡(luò)將是遺傳神經(jīng)網(wǎng)絡(luò)。5．進(jìn)化算法

模擬自然進(jìn)化過程可以產(chǎn)生魯棒的計(jì)算機(jī)算法——進(jìn)化算法。遺傳算法是其三種典型的算法之一，其余兩種算法是進(jìn)化規(guī)劃和進(jìn)化策略，這三種算法是獨(dú)立發(fā)展起來的。6．人工生命與遺傳算法

近幾年來，通過計(jì)算機(jī)模擬再現(xiàn)種種生命現(xiàn)象，以達(dá)到對(duì)生命更深刻理解的人工生命的研究正在興起。已有不少學(xué)者對(duì)生態(tài)系統(tǒng)的演變、食物鏈的維持以及免疫系統(tǒng)的進(jìn)化等用遺傳算法做了生動(dòng)的模擬。但是實(shí)現(xiàn)人工生命的手段很多，遺傳算法在實(shí)現(xiàn)人工生命中的基本地位和能力究竟如何，這是值得研究的課題。1.2.2基于遺傳算法的應(yīng)用

遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題具體的領(lǐng)域，對(duì)問題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于許多學(xué)科。近十年來，遺傳算法得到了迅速發(fā)展。目前，遺傳算法在生物技術(shù)和生物學(xué)、化學(xué)和化學(xué)工程、計(jì)算機(jī)輔助設(shè)計(jì)、物理學(xué)和數(shù)據(jù)分析、動(dòng)態(tài)處理、建模與模擬、醫(yī)學(xué)與醫(yī)學(xué)工程、微電子學(xué)、模式識(shí)別、人工智能、生產(chǎn)調(diào)度、機(jī)器入學(xué)、開礦工程、電信學(xué)、售貨服務(wù)系統(tǒng)等領(lǐng)域都得到應(yīng)用，成為求解全局優(yōu)化問題的有力工具之一。下面列出遺傳算法一些主要的應(yīng)用領(lǐng)域。1．函數(shù)優(yōu)化

函數(shù)優(yōu)化(FunctionOptimization)是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對(duì)遺傳算法進(jìn)行性能評(píng)價(jià)的常用算例。可以用各種各樣的函數(shù)來驗(yàn)證遺傳算法的性能。對(duì)一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，使用遺傳算法可得到較好的結(jié)果。2．組合優(yōu)化

隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴(kuò)大，有時(shí)在目前的計(jì)算機(jī)上用枚舉法很難甚至不能求出問題的最優(yōu)解，對(duì)這類問題，人們已意識(shí)到應(yīng)把主要精力放在尋求其滿意解上，而遺傳算法就是尋求這種滿意解的最佳工具之一。實(shí)踐證明，遺傳算法對(duì)于組合優(yōu)化中的NP完全問題非常有效。3．生產(chǎn)調(diào)度問題

采用遺傳算法能夠解決復(fù)雜的生產(chǎn)調(diào)度問題。在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面，遺傳算法都得到了有效的應(yīng)用。4．自動(dòng)控制

在自動(dòng)控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問題需要求解，遺傳算法已在其中得到了初步應(yīng)用，并顯示出了良好的效果。例如，基于遺傳算法的模糊控制器優(yōu)化設(shè)計(jì)，用遺傳算法進(jìn)行航空控制系統(tǒng)的優(yōu)化，使用遺傳算法設(shè)計(jì)空間交會(huì)控制器等。5．機(jī)器人學(xué)

機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源來自于對(duì)人工自適應(yīng)系統(tǒng)的研究，所以機(jī)器入學(xué)理所當(dāng)然地成為遺傳算法的一個(gè)重要領(lǐng)域。例如，遺傳算法已經(jīng)在移動(dòng)機(jī)器人路徑規(guī)劃、機(jī)器人逆運(yùn)動(dòng)學(xué)求解等方面得到很好的應(yīng)用。6．圖像處理

圖像處理是計(jì)算機(jī)視覺中的一個(gè)重要領(lǐng)域，在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地會(huì)存在一些誤差，這些誤差會(huì)影響圖像處理的效果。如何使這些誤差最小是使計(jì)算機(jī)視覺達(dá)到實(shí)用化的重要要求，遺傳算法在這些圖像處理的優(yōu)化計(jì)算方面找到了用武之地。7．遺傳編程

Koza發(fā)展了遺傳程序設(shè)計(jì)的概念，他使用了以LISP語言所表示的編碼方法，算法基于對(duì)一種樹型結(jié)構(gòu)所進(jìn)行的遺傳操作來自動(dòng)生成計(jì)算機(jī)程序。