遺傳算法基本理論及實(shí)例

1、目錄_一、遺產(chǎn)算法的由來1二、遺傳算法的國(guó)內(nèi)外研究現(xiàn)狀2三、遺傳算法的特點(diǎn)3四、遺傳算法的流程5五、遺傳算法實(shí)例9六、遺傳算法編程13七、總結(jié)15附錄一：運(yùn)行程序16遺傳算法基本理論與實(shí)例一、遺產(chǎn)算法的由來遺傳算法（Genetic Algorithm，簡(jiǎn)稱GA）起源于對(duì)生物系統(tǒng)所進(jìn)行的計(jì)算機(jī)模擬研究。20世紀(jì)40年代以來，科學(xué)家不斷努力從生物學(xué)中尋求用于計(jì)算科學(xué)和人工系統(tǒng)的新思想、新方法。很多學(xué)者對(duì)關(guān)于從生物進(jìn)化和遺傳的激勵(lì)中開發(fā)出適合于現(xiàn)實(shí)世界復(fù)雜適應(yīng)系統(tǒng)研究的計(jì)算技術(shù)生物進(jìn)化系統(tǒng)的計(jì)算模型，以及模擬進(jìn)化過程的算法進(jìn)行了長(zhǎng)期的開拓性的探索和研究。John H.Holland教授及其學(xué)生首先提

2、出的遺傳算法就是一個(gè)重要的發(fā)展方向。遺傳算法借鑒了達(dá)爾文的進(jìn)化論和孟德爾、摩根的遺傳學(xué)說。按照達(dá)爾文的進(jìn)化論，地球上的每一物種從誕生開始就進(jìn)入了漫長(zhǎng)的進(jìn)化歷程。生物種群從低級(jí)、簡(jiǎn)單的類型逐漸發(fā)展成為高級(jí)復(fù)雜的類型。各種生物要生存下去及必須進(jìn)行生存斗爭(zhēng)，包括同一種群內(nèi)部的斗爭(zhēng)、不同種群之間的斗爭(zhēng)，以及生物與自然界無機(jī)環(huán)境之間的斗爭(zhēng)。具有較強(qiáng)生存能力的生物個(gè)體容易存活下來，并有較多的機(jī)會(huì)產(chǎn)生后代；具有較低生存能力的個(gè)體則被淘汰，或者產(chǎn)生后代的機(jī)會(huì)越來越少。，直至消亡。達(dá)爾文把這一過程和現(xiàn)象叫做“自然選擇，適者生存”。按照孟德爾和摩根的遺傳學(xué)理論，遺傳物質(zhì)是作為一種指令密碼封裝在每個(gè)細(xì)胞中，并以基因

3、的形式排列在染色體上，每個(gè)基因有特殊的位置并控制生物的某些特性。不同的基因組合產(chǎn)生的個(gè)體對(duì)環(huán)境的適應(yīng)性不一樣，通過基因雜交和突變可以產(chǎn)生對(duì)環(huán)境適應(yīng)性強(qiáng)的后代。經(jīng)過優(yōu)勝劣汰的自然選擇，適應(yīng)度值高的基因結(jié)構(gòu)就得以保存下來，從而逐漸形成了經(jīng)典的遺傳學(xué)染色體理論，揭示了遺傳和變異的基本規(guī)律。遺傳算法由美國(guó)的John H.Holland教授1975年首先提出，其主要特點(diǎn)是直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動(dòng)獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。遺傳算法的這些性質(zhì)，已被人們廣泛地應(yīng)用于組合優(yōu)化

4、、機(jī)器學(xué)習(xí)、信號(hào)處理、自適應(yīng)控制和人工生命等領(lǐng)域。它是現(xiàn)代有關(guān)智能計(jì)算中的關(guān)鍵技術(shù)。二、遺傳算法的國(guó)內(nèi)外研究現(xiàn)狀遺傳算法的鼻祖是美國(guó)Michigan大學(xué)的Holland教授及其學(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)行了研究，提出了遺傳算法的基本理論模式定理（Schema Theorem）并于19

5、57年出版了第一本系統(tǒng)論述遺傳算法和人工自適應(yīng)系統(tǒng)的專著Adaptation in Natural and Artificial Systems。20世紀(jì)80年代，Holland教授實(shí)現(xiàn)了第一個(gè)基于遺傳算法的機(jī)器學(xué)習(xí)系統(tǒng)，開創(chuàng)了遺傳算法的機(jī)器學(xué)習(xí)的新概念。1975年，De Jong基于遺傳算法的思想在計(jì)算機(jī)上進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化計(jì)算實(shí)驗(yàn)，建立了遺傳算法的工作框架，得到了一些重要且具有指導(dǎo)意義的結(jié)論。1989年，Goldberg出版了Genetic Algorithm in Search，Optimization and Machine Learning一書，系統(tǒng)地總結(jié)了遺傳算法的主要研究

6、成果，全面完整的論述了遺傳算法的基本原理及其應(yīng)用。1991年，David出版了Handbook of Genetic Algorithms一書，介紹了遺傳算法在科學(xué)計(jì)算、工程技術(shù)和社會(huì)經(jīng)濟(jì)中的大量實(shí)例。1992年，Koza將遺傳算法應(yīng)用于計(jì)算機(jī)程序的優(yōu)化設(shè)計(jì)及自動(dòng)生成，提出了遺傳編程（Genetic Programming，簡(jiǎn)稱GP）的概念。在控制系統(tǒng)的離線設(shè)計(jì)方面遺傳算法被眾多的使用者證明是有效的策略。例如，Krishnakumar和Goldberg以及Bramlette和Gusin已證明使用遺傳優(yōu)化方法在太空應(yīng)用中導(dǎo)出優(yōu)異的控制器結(jié)構(gòu)比使用傳統(tǒng)方法如LQR和Powell（鮑威爾）的增音機(jī)設(shè)

7、計(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é)者的高度重視。近些年來，國(guó)內(nèi)外很多學(xué)者在遺傳算法的編碼表示、適應(yīng)度函數(shù)、遺傳算子、參數(shù)選擇、收斂性分析、欺騙問題和并行遺傳算法上做出了大量的研究和改進(jìn)。還有很多學(xué)者將遺傳算法和其他只能算法結(jié)合，進(jìn)一步提高局部搜索能力。在遺傳算法

8、的應(yīng)用上也有很多改進(jìn)。由于遺傳算法具有全局并行搜索、簡(jiǎn)單通用、魯棒性強(qiáng)等優(yōu)點(diǎn)，使得遺傳算法廣泛地應(yīng)用于計(jì)算機(jī)科學(xué)、自動(dòng)控制、人工智能、工程設(shè)計(jì)、制造業(yè)、生物工程和社會(huì)科學(xué)等領(lǐng)域。針對(duì)遺傳算法的一些問題，還有一些問題需要進(jìn)一步的探究，將大大促進(jìn)遺傳算法理論和應(yīng)用的發(fā)展，遺傳算法必將在智能計(jì)算領(lǐng)域中展現(xiàn)出更加光明的前景。三、遺傳算法的特點(diǎn)遺傳算法是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法。它與傳統(tǒng)的算法不同，大多數(shù)古典的優(yōu)化算法是基于一個(gè)單一的度量函數(shù)（評(píng)估函數(shù)）的梯度和較高次統(tǒng)計(jì)，以產(chǎn)生一個(gè)確定性的試驗(yàn)解序列；遺傳算法不依賴梯度信息，而是通過模擬自然進(jìn)化進(jìn)程來搜索最優(yōu)解，它利用某種編碼

9、技術(shù)，作用于稱為染色體的數(shù)字串，模擬由這些串組成的群體的進(jìn)化過程。遺傳算法通過有組織的、隨機(jī)的信息交換來重新組合那些適應(yīng)性好的串，生成新的串的群體。遺傳算法有以下優(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ī)器

10、學(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ǔ)上盡心遺傳操作。更重要的是，遺傳算法的適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，

11、而且其定義域可以任意設(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)，即時(shí)在所定義的適應(yīng)度函數(shù)是不連續(xù)的、非規(guī)則的或有噪聲的情況下，也能以很大的概率找到全局最優(yōu)解。（6）遺傳算法采用自然進(jìn)化機(jī)制來表現(xiàn)復(fù)雜的現(xiàn)象，能夠快速可靠

12、地解決求解非常困難的問題。（7）遺傳算法具有固有的并行性和并行計(jì)算的能力。（8）遺傳算法具有可擴(kuò)展性，易于同別的技術(shù)混合使用。遺傳算法作為一種優(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ù)雜性等方面，還沒有有效的定量分析方法。遺傳算法的基本內(nèi)容如下：個(gè)體和種群。個(gè)體就是模擬生物個(gè)體而對(duì)問題中的對(duì)象（一般就是問題的解）的一種

13、稱呼，一個(gè)個(gè)體也就是搜索空間中的一個(gè)點(diǎn)。種群(population)就是模擬生物種群而由若干個(gè)體組成的群體，它一般是整個(gè)搜索空間的一個(gè)很小的子集。適應(yīng)度與適應(yīng)度函數(shù)。適應(yīng)度(fitness)就是借鑒生物個(gè)體對(duì)環(huán)境的適應(yīng)程度,而對(duì)問題中的個(gè)體對(duì)象所設(shè)計(jì)的表征其優(yōu)劣的一種測(cè)度。適應(yīng)度函數(shù)（fitness function）就是問題中的全體個(gè)體與其適應(yīng)度之間的一個(gè)對(duì)應(yīng)關(guān)系。它一般是一個(gè)實(shí)值函數(shù)。該函數(shù)就是遺傳算法中指導(dǎo)搜索的評(píng)價(jià)函數(shù)。染色體與基因。染色體（chromosome）就是問題中個(gè)體的某種字符串形式的編碼表示。字符串中的字符也就稱為基因（gene）。例如個(gè)體上9，染色體的表示形式是1001，

14、0和1是染色體上的基因。遺傳操作。也稱為遺傳算子，就是關(guān)于染色體的運(yùn)算。遺傳算法中有三種遺傳操作：選擇-復(fù)制，交叉和變異。四、遺傳算法的流程遺傳算法在整個(gè)進(jìn)化過程中的遺傳操作是隨機(jī)的，但它所呈現(xiàn)出的特性并不是完全搜索，它能有效地利用歷史信息來推測(cè)下一代期望性能有所提高的尋優(yōu)點(diǎn)集。這樣一代代的不斷進(jìn)化，最后收斂到一個(gè)最適應(yīng)環(huán)境的個(gè)體上，求得問題的最優(yōu)解。遺傳算法所涉及的五大要素是：參數(shù)編碼、初始種群的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作的設(shè)計(jì)和控制參數(shù)的設(shè)定。流程如圖1所示。圖1 遺傳算法基本流程簡(jiǎn)單遺傳算法的運(yùn)行過程為一個(gè)典型的迭代過程，其必須完成的工作內(nèi)容和基本步驟如下：1）選擇編碼策略，把參數(shù)

15、集合X和域轉(zhuǎn)換為位串結(jié)構(gòu)空間S。2）定義適應(yīng)度函數(shù) 。3）確定遺傳策略，包括選擇群體大小n，選擇、交叉、變異方法，以及確定交叉概率 、變異概率 等遺傳參數(shù)。4）隨機(jī)初始化生成種群P。5）計(jì)算群體中個(gè)體位串解碼后的適應(yīng)度值 。6）按照遺傳策略，運(yùn)用選擇、交叉和變異算子作用與群體，形成下一代群體。7）判斷群體性能是否滿足某一目標(biāo)，或者已完成預(yù)定迭代次數(shù)，不滿足則返回步驟6），或者修改遺傳策略再返回步驟6）。下面對(duì)基本步驟進(jìn)行分解，進(jìn)一步詳細(xì)介紹流程中一些細(xì)節(jié)。編碼表示。在許多問題求解中，編碼是遺傳算法中首要解決的問題，對(duì)算法的性能有很重要的影響。Holland提出的二進(jìn)制編碼是遺傳算法中最常用的一

16、種編碼方法，它采用最小字符編碼原則， 編/解碼操作簡(jiǎn)單易行，利于交叉、變異操作的實(shí)現(xiàn)，也可以采用模式定理對(duì)算法進(jìn)行理論分析。但二進(jìn)制編碼用于多維、高精度數(shù)值問題優(yōu)化時(shí)，不能很好地克服連續(xù)函數(shù)離散化時(shí)的映射誤差；不能直接反映問題的固有結(jié)構(gòu)，精度不高，并且個(gè)體長(zhǎng)度大、占用內(nèi)存多。針對(duì)二進(jìn)制編碼存在的不足，人們提出了多種改進(jìn)方法，比較典型的有以下幾種：（1）格雷碼編碼。為了克服二進(jìn)制編碼在連續(xù)函數(shù)離散化時(shí)存在的不足，人們提出了用格雷碼進(jìn)行編碼的方法，它是二進(jìn)制編碼的變形。格雷碼不僅具有二進(jìn)制編碼的一些優(yōu)點(diǎn)，而且能夠提高遺傳算法的局部搜索能力。假設(shè)有一個(gè)二進(jìn)制編碼為，其對(duì)應(yīng)的格雷碼為，則 （2）實(shí)數(shù)編

17、碼。該方法適合于遺傳算法中表示范圍較大的數(shù)，使遺傳算法更接近問題空間，避免了編碼和解碼的過程。它便于較大空間的遺傳搜索，提高了遺傳算法的精度要求；便于設(shè)計(jì)專門問題的遺傳算子；便于算法與經(jīng)典優(yōu)化方法的混合作用，改善了遺傳算法的計(jì)算復(fù)雜性，提高了運(yùn)算效率。（3）十進(jìn)制編碼。該方法利用十進(jìn)制編碼控制參數(shù)，緩解了“組合爆炸”和遺傳算法的早熟收斂問題。（4）非數(shù)值編碼。染色體編碼串中的基因值取一個(gè)僅有代碼含義而無數(shù)值含義的符號(hào)集，這些符號(hào)可以是數(shù)字也可以是字符。非數(shù)值編碼的優(yōu)點(diǎn)是在遺傳算法中可以利用所求問題的專門知識(shí)及相關(guān)算法。對(duì)于非數(shù)值編碼，問題的解和染色體的編碼要注意染色體的可行性、染色體的合法性和

18、映射的惟一性。適應(yīng)度函數(shù)。在遺傳算法中，適應(yīng)度是描述個(gè)體性能的主要指標(biāo)，根據(jù)適應(yīng)度的大小對(duì)個(gè)體進(jìn)行優(yōu)勝劣汰。對(duì)于求解有約束的優(yōu)化問題時(shí)，一般采用罰函數(shù)方法將目標(biāo)函數(shù)和約束條件建立成一個(gè)無約束的優(yōu)化目標(biāo)函數(shù)；然后再將目標(biāo)函數(shù)作適當(dāng)處理，建立適合遺傳算法的適應(yīng)度函數(shù)。將目標(biāo)函數(shù)轉(zhuǎn)換成適應(yīng)度函數(shù)一般應(yīng)遵循兩個(gè)原則：適應(yīng)度必須非負(fù)；優(yōu)化過程中目標(biāo)函數(shù)的變化方向應(yīng)與群體進(jìn)化過程中適應(yīng)度函數(shù)變化方向一致。在使用遺傳算法求解具體問題時(shí)，適應(yīng)度函數(shù)的選擇對(duì)算法的收斂性以及收斂速度的影響較大，針對(duì)不同的問題需根據(jù)經(jīng)驗(yàn)或算法來確定相應(yīng)的參數(shù)。遺傳算子。在遺傳算法中通過一系列算子來決定后代，算子對(duì)當(dāng)前群體中選定的成

19、員進(jìn)行重組和變異。（1）選擇算子 選擇操作通過適應(yīng)度選擇優(yōu)質(zhì)個(gè)體而拋棄劣質(zhì)個(gè)體，體現(xiàn)了“適者生存”的原理。常見的選擇操作主要有以下幾種：a）輪盤賭選擇。選擇某假設(shè)的概率是通過這個(gè)假設(shè)的適應(yīng)度與當(dāng)前群體中其他成員的適應(yīng)度的比值而得到。此方法是基于概率選擇的，存在統(tǒng)計(jì)誤差，因此可以結(jié)合最優(yōu)保存策略以保證當(dāng)前適應(yīng)度最優(yōu)的個(gè)體能夠進(jìn)化到下一代而不被遺傳操作的隨機(jī)性破壞，保證算法的收斂性。b）排序選擇。對(duì)個(gè)體適應(yīng)度取正值或負(fù)值以及個(gè)體適應(yīng)度之間的數(shù)值差異程度無特殊要求，對(duì)群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行排序，根據(jù)排序來分配各個(gè)體被選中的概率。c）最優(yōu)個(gè)體保存。父代群體中的最優(yōu)個(gè)體直接進(jìn)入子代群體中。該

20、方法可保證在遺傳過程中所得到的個(gè)體不會(huì)被交叉和變異操作所破壞，它是遺傳算法收斂性的一個(gè)重要保證條件；它也容易使得局部最優(yōu)個(gè)體不易被淘汰，從而使算法的全局搜索能力變強(qiáng)。d）隨機(jī)聯(lián)賽選擇。每次選取N個(gè)個(gè)體中適應(yīng)度最高的個(gè)體遺傳到下一代群體中。具體操作如下：從群體中隨機(jī)選取N個(gè)個(gè)體進(jìn)行適應(yīng)度大小比較，將其中適應(yīng)度最高的個(gè)體遺傳到下一代群體中；將上述過程重復(fù)執(zhí)行M（為群體大?。┐?，則可得到下一代群體。（2）交叉算子 交叉是指對(duì)兩個(gè)相互交叉的染色體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。它是產(chǎn)生新個(gè)體的主要方法，決定了遺傳算法的全局搜索能力，在遺傳算法中起關(guān)鍵作用。幾種常用的適用于二進(jìn)制編碼

21、或?qū)崝?shù)編碼方式的交叉算子如下：a）單點(diǎn)交叉。在個(gè)體編碼串中隨機(jī)設(shè)置一個(gè)交叉點(diǎn)后在該點(diǎn)相互交換兩個(gè)配對(duì)個(gè)體的部分基因。b）兩點(diǎn)交叉。在相互配對(duì)的兩個(gè)個(gè)體編碼串中隨機(jī)設(shè)置兩個(gè)交叉點(diǎn)，并交換兩個(gè)交叉點(diǎn)之間的部分基因。c）均勻交叉。兩個(gè)相互配對(duì)個(gè)體的每一位基因都以相同的概率進(jìn)行交換，從而形成兩個(gè)新個(gè)體。d）算術(shù)交叉。由兩個(gè)個(gè)體的線性組合而產(chǎn)生出新的個(gè)體。（3）變異算子 變異是指將個(gè)體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個(gè)新的個(gè)體。它是產(chǎn)生新個(gè)體的輔助方法，決定了遺傳算法的局部搜索能力。變異算子與交叉算子相互配合，可以共同完成對(duì)搜索空間的全局搜索和局部搜索，從而

22、使得遺傳算法以良好的搜索性能完成最優(yōu)化問題的尋優(yōu)過程。在遺傳算法中使用變異算子主要有以下兩個(gè)目的: 改善遺傳算法的局部搜索能力；維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。下面是幾種常用的變異操作：a）基本位變異。對(duì)個(gè)體編碼串以變異概率P隨機(jī)指定某一位或某幾位基因進(jìn)行變異操作。b）均勻變異（一致變異）。分別用符合某一范圍內(nèi)均勻分布的隨機(jī)數(shù)，以某一較小的概率來替換個(gè)體編碼串中各個(gè)基因座上的原有基因值。均勻變異操作特別適合應(yīng)用于遺傳算法的初期運(yùn)行階段，它使得搜索點(diǎn)可以在整個(gè)搜索空間內(nèi)自由地移動(dòng)，從而可以增加群體的多樣性，使算法能夠處理更多的模式。c）二元變異。需要兩條染色體參與，通過二元變異操作后生成兩條

23、新個(gè)體中的各個(gè)基因分別取原染色體對(duì)應(yīng)基因值的同或異或。它改變了傳統(tǒng)的變異方式，有效地克服了早熟收斂，提高了遺傳算法的優(yōu)化速度。d）高斯變異。在進(jìn)行變異時(shí)用一個(gè)均值為L(zhǎng)、方差為R2的正態(tài)分布的一個(gè)隨機(jī)數(shù)來替換原有基因值。其操作過程與均勻變異類似。五、遺傳算法實(shí)例例：利用遺傳算法，求解區(qū)間0，31上的二次函數(shù)的最大值。分析：原問題可轉(zhuǎn)化為在區(qū)間0，31中搜索能使y取最小值的點(diǎn)x的問題。那么，0，31中的點(diǎn)x就是個(gè)體，函數(shù)值f(x)恰好就可以作為x的適應(yīng)度，區(qū)間0，31就是一個(gè)（解）空間。這樣，只要能給出個(gè)體x的適當(dāng)染色體編碼，該問題就可以用遺傳算法來解決。二次函數(shù)的圖像如圖2所示。圖2 二次函數(shù)的

24、圖像（1）設(shè)定種群規(guī)模，編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4；用5位二進(jìn)制數(shù)編碼染色體；取下列個(gè)體組成初始種群： = 13（01101）， = 24（11000） = 8 （01000）， = 19（10011）（2）定義適應(yīng)度函數(shù)。取適應(yīng)度函數(shù)：f (x) = 。（3）計(jì)算各代種群中的各個(gè)體的適應(yīng)度，并對(duì)其染色體進(jìn)行遺傳操作，直到適應(yīng)度最高的個(gè)體（即31（11111）出現(xiàn)為止。首先計(jì)算種群S1中各個(gè)體的適應(yīng)度。容易求得， f (s1) = f(13) = 132 = 169 f (s2) = f(24) = 242 = 576 f (s3) = f(8) = 82 = 64 f (s

25、4) = f(19) = 192 = 361再計(jì)算種群中各個(gè)體的選擇概率。選擇概率的計(jì)算公式為 由此求得， P(s1) = P(13) = 0.14 P(s2) = P(24) = 0.49 P(s3) = P(8) = 0.06 P(s4) = P(19) = 0.31用賭輪選擇法可得圖3，圖3 賭輪選擇法示意圖設(shè)從區(qū)間0， 1中產(chǎn)生4個(gè)隨機(jī)數(shù)如下： r1 = 0.， r2 = 0. r3 = 0.， r4 = 0.98503表1 第一代選中次數(shù)表 染色體 適應(yīng)度選擇概率積累概率選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.0

26、60.690s4=100113610.3111于是，經(jīng)復(fù)制得群體：s1 =11000（24）， s2 =01101（13）s3 =11000（24）， s4 =10011（19） 設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運(yùn)算。設(shè)s1與s2配對(duì)，s3與s4配對(duì)。分別交換后兩位基因，得新染色體：s1=11001（25）， s2=01100（12） s3=11011（27）， s4=10000（16）設(shè)變異率pm=0.001。這樣，群體S1中共有540.001=0.02位基因可以變異。0.02位顯然不足1位，所以本輪遺傳操作不做變異。于是，得到第二代種群S2： s1=11001（25）

27、， s2=01100（12） s3=11011（27）， s4=10000（16）表2 第二代選中次數(shù)表 染色體 適應(yīng)度選擇概率積累概率 估計(jì)的選中次數(shù)s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.1511假設(shè)這一輪選擇-復(fù)制操作中，種群中的4個(gè)染色體都被選中，則得到群體：s1=11001（25）， s2= 01100（12）s3=11011（27）， s4= 10000（16） 做交叉運(yùn)算，讓s1與s2，s3與s4 分別交換后三位基因，得 s1 =11100（28）， s2 = 01001（9

28、） s3 =11000（24）， s4 = 10011（19） 這一輪仍然不會(huì)發(fā)生變異。于是，得第三代種群S3： s1=11100（28），s2=01001（9） s3=11000（24）， s4=10011（19） 表3 第三代選中次數(shù) 染色體 適應(yīng)度選擇概率積累概率 估計(jì)的選中次數(shù)s1=111007840.440.442s2=01001810.040.480s3=110005760.320.81s4=100113610.211設(shè)這一輪的選擇-復(fù)制結(jié)果為：s1=11100（28）， s2=11100（28）s3=11000（24）， s4=10011（19）做交叉運(yùn)算，讓s1與s4，s2與s

29、3 分別交換后兩位基因，得 s1=11111（31）， s2=11100（28）s3=11000（24）， s4=10000（16）這一輪仍然不會(huì)發(fā)生變異。于是，得第四代種群S4： s1=11111（31）， s2=11100（28） s3=11000（24）， s4=10000（16）顯然，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。于是，遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。然后，將染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。將31代入函數(shù)y=x2中，即得原問題的解，即函數(shù)y=x2的最大值為961。 六、遺傳算法編程MATLAB程序需要解決的問題是利用遺傳算法，求解區(qū)間0，31上的二次函數(shù)的最大值。使用的是matlabR2010A，在WIN7環(huán)境下運(yùn)行。鑒于此版本的軟件不含有遺傳算法工具箱，自行安裝至路徑“D:MATLABR2010atoolboxgeneticgatbx”，并在操作界面上添加路徑。程序見附錄一，程序界面如圖3所示。圖3 程序圖運(yùn)行結(jié)果如圖4所示。圖4 運(yùn)行結(jié)果圖由圖可知，經(jīng)過10代之后，遺傳算法找個(gè)了二次函數(shù)的最優(yōu)值。附錄一：運(yùn)行程序add