「遺傳算法基本理論及實例」.doc

目錄_一、遺產(chǎn)算法的由來1二、遺傳算法的國內(nèi)外研究現(xiàn)狀2三、遺傳算法的特點3四、遺傳算法的流程5五、遺傳算法實例9六、遺傳算法編程13七、總結(jié)15附錄一：運行程序16內(nèi)容作參考遺傳算法基本理論與實例一、遺產(chǎn)算法的由來遺傳算法（Genetic Algorithm，簡稱GA）起源于對生物系統(tǒng)所進(jìn)行的計算機(jī)模擬研究。20世紀(jì)40年代以來，科學(xué)家不斷努力從生物學(xué)中尋求用于計算科學(xué)和人工系統(tǒng)的新思想、新方法。很多學(xué)者對關(guān)于從生物進(jìn)化和遺傳的激勵中開發(fā)出適合于現(xiàn)實世界復(fù)雜適應(yīng)系統(tǒng)研究的計算技術(shù)生物進(jìn)化系統(tǒng)的計算模型，以及模擬進(jìn)化過程的算法進(jìn)行了長期的開拓性的探索和研究。John H.Holland教授及其學(xué)生首先提出的遺傳算法就是一個重要的發(fā)展方向。遺傳算法借鑒了達(dá)爾文的進(jìn)化論和孟德爾、摩根的遺傳學(xué)說。按照達(dá)爾文的進(jìn)化論，地球上的每一物種從誕生開始就進(jìn)入了漫長的進(jìn)化歷程。生物種群從低級、簡單的類型逐漸發(fā)展成為高級復(fù)雜的類型。各種生物要生存下去及必須進(jìn)行生存斗爭，包括同一種群內(nèi)部的斗爭、不同種群之間的斗爭，以及生物與自然界無機(jī)環(huán)境之間的斗爭。具有較強(qiáng)生存能力的生物個體容易存活下來，并有較多的機(jī)會產(chǎn)生后代；具有較低生存能力的個體則被淘汰，或者產(chǎn)生后代的機(jī)會越來越少。，直至消亡。達(dá)爾文把這一過程和現(xiàn)象叫做“自然選擇，適者生存”。按照孟德爾和摩根的遺傳學(xué)理論，遺傳物質(zhì)是作為一種指令密碼封裝在每個細(xì)胞中，并以基因的形式排列在染色體上，每個基因有特殊的位置并控制生物的某些特性。不同的基因組合產(chǎn)生的個體對環(huán)境的適應(yīng)性不一樣，通過基因雜交和突變可以產(chǎn)生對環(huán)境適應(yīng)性強(qiáng)的后代。經(jīng)過優(yōu)勝劣汰的自然選擇，適應(yīng)度值高的基因結(jié)構(gòu)就得以保存下來，從而逐漸形成了經(jīng)典的遺傳學(xué)染色體理論，揭示了遺傳和變異的基本規(guī)律。遺傳算法由美國的John H.Holland教授1975年首先提出，其主要特點是直接對結(jié)構(gòu)對象進(jìn)行操作，不存在求導(dǎo)和函數(shù)連續(xù)性的限定；具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；采用概率化的尋優(yōu)方法，能自動獲取和指導(dǎo)優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。遺傳算法的這些性質(zhì)，已被人們廣泛地應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、信號處理、自適應(yīng)控制和人工生命等領(lǐng)域。它是現(xiàn)代有關(guān)智能計算中的關(guān)鍵技術(shù)。二、遺傳算法的國內(nèi)外研究現(xiàn)狀遺傳算法的鼻祖是美國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ù)制、交叉、變異、顯性、倒位等遺傳算子，在個體編碼上使用雙倍體的編碼方法。Holland教授用遺傳算法的思想對自然和人工自適應(yīng)系統(tǒng)進(jìn)行了研究，提出了遺傳算法的基本理論模式定理（Schema Theorem）并于1957年出版了第一本系統(tǒng)論述遺傳算法和人工自適應(yīng)系統(tǒng)的專著Adaptation in Natural and Artificial Systems。20世紀(jì)80年代，Holland教授實現(xiàn)了第一個基于遺傳算法的機(jī)器學(xué)習(xí)系統(tǒng)，開創(chuàng)了遺傳算法的機(jī)器學(xué)習(xí)的新概念。1975年，De Jong基于遺傳算法的思想在計算機(jī)上進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化計算實驗，建立了遺傳算法的工作框架，得到了一些重要且具有指導(dǎo)意義的結(jié)論。1989年，Goldberg出版了Genetic Algorithm in Search，Optimization and Machine Learning一書，系統(tǒng)地總結(jié)了遺傳算法的主要研究成果，全面完整的論述了遺傳算法的基本原理及其應(yīng)用。1991年，David出版了Handbook of Genetic Algorithms一書，介紹了遺傳算法在科學(xué)計算、工程技術(shù)和社會經(jīng)濟(jì)中的大量實例。1992年，Koza將遺傳算法應(yīng)用于計算機(jī)程序的優(yōu)化設(shè)計及自動生成，提出了遺傳編程（Genetic Programming，簡稱GP）的概念。在控制系統(tǒng)的離線設(shè)計方面遺傳算法被眾多的使用者證明是有效的策略。例如，Krishnakumar和Goldberg以及Bramlette和Gusin已證明使用遺傳優(yōu)化方法在太空應(yīng)用中導(dǎo)出優(yōu)異的控制器結(jié)構(gòu)比使用傳統(tǒng)方法如LQR和Powell（鮑威爾）的增音機(jī)設(shè)計所用的時間要少（功能評估）。Porter和Mohamed展示了使用本質(zhì)結(jié)構(gòu)分派任務(wù)的多變量飛行控制系統(tǒng)的遺傳設(shè)計方案。與此同時，另一些人證明了遺傳算法如何在控制器結(jié)構(gòu)的選擇中使用。從遺傳算法的整個發(fā)展過程來看，20世紀(jì)70年代是興起階段，20世紀(jì)80年代是發(fā)展階段，20世紀(jì)90年代是高潮階段。遺傳算法作為一種實用、高效、魯棒性強(qiáng)的優(yōu)化技術(shù)，發(fā)展極為迅速，已引起國內(nèi)外學(xué)者的高度重視。近些年來，國內(nèi)外很多學(xué)者在遺傳算法的編碼表示、適應(yīng)度函數(shù)、遺傳算子、參數(shù)選擇、收斂性分析、欺騙問題和并行遺傳算法上做出了大量的研究和改進(jìn)。還有很多學(xué)者將遺傳算法和其他只能算法結(jié)合，進(jìn)一步提高局部搜索能力。在遺傳算法的應(yīng)用上也有很多改進(jìn)。由于遺傳算法具有全局并行搜索、簡單通用、魯棒性強(qiáng)等優(yōu)點，使得遺傳算法廣泛地應(yīng)用于計算機(jī)科學(xué)、自動控制、人工智能、工程設(shè)計、制造業(yè)、生物工程和社會科學(xué)等領(lǐng)域。針對遺傳算法的一些問題，還有一些問題需要進(jìn)一步的探究，將大大促進(jìn)遺傳算法理論和應(yīng)用的發(fā)展，遺傳算法必將在智能計算領(lǐng)域中展現(xiàn)出更加光明的前景。三、遺傳算法的特點遺傳算法是一種借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī)搜索算法。它與傳統(tǒng)的算法不同，大多數(shù)古典的優(yōu)化算法是基于一個單一的度量函數(shù)（評估函數(shù)）的梯度和較高次統(tǒng)計，以產(chǎn)生一個確定性的試驗解序列；遺傳算法不依賴梯度信息，而是通過模擬自然進(jìn)化進(jìn)程來搜索最優(yōu)解，它利用某種編碼技術(shù)，作用于稱為染色體的數(shù)字串，模擬由這些串組成的群體的進(jìn)化過程。遺傳算法通過有組織的、隨機(jī)的信息交換來重新組合那些適應(yīng)性好的串，生成新的串的群體。遺傳算法有以下優(yōu)點：（1）對可行解表示的廣泛性。遺傳算法的處理對象不是參數(shù)本身，而是針對那些通過參數(shù)集進(jìn)行編碼的基因個體，此編碼操作使得遺傳算法可以直接對結(jié)構(gòu)對象進(jìn)行操作。所謂結(jié)構(gòu)對象，泛指集合、序列、矩陣、樹、鏈、表等各種一維或二維甚至多維結(jié)構(gòu)形式的對象。這一特點使得遺傳算法具有廣泛的應(yīng)用領(lǐng)域。比如通過對連接矩陣的操作，遺傳算法可用來對神經(jīng)網(wǎng)絡(luò)或自動機(jī)的結(jié)構(gòu)或參數(shù)加以優(yōu)化；通過對集合的操作，遺傳算法可實現(xiàn)對規(guī)則集合和知識庫的精煉而達(dá)到高質(zhì)量的機(jī)器學(xué)習(xí)目的；通過對樹結(jié)構(gòu)的操作，用遺傳算法可得到用于分類的最佳決策樹；通過對任務(wù)序列的操作，遺傳算法可用于任務(wù)規(guī)劃，而通過對操作序列的處理，可自動構(gòu)造順序控制系統(tǒng)。（2）群體搜索特性。許多傳統(tǒng)的搜索方法都是單點搜索，這種點對點的搜索方法，對于多峰分布的搜索空間常常會陷于局部的某個單峰的極值點。相反，遺傳算法采用的是同時處理群體中多個個體的方法，即同時對搜索空間中的多個解進(jìn)行評估。這一特點使遺傳算法具有較好的全局搜索性能，也使得算法本身易于并行化。 （3）不需要輔助信息。遺傳算法僅用適應(yīng)度函數(shù)來的數(shù)值來評估基因個體，并在此基礎(chǔ)上盡心遺傳操作。更重要的是，遺傳算法的適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。對適應(yīng)度函數(shù)的唯一要求是，編碼必須與可行解空間對應(yīng)，不能有死碼。由于限制條件的縮小，使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。（4）內(nèi)在啟發(fā)式隨機(jī)搜索特性。遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo)它的搜索方向。概率不僅僅是作為一種工具來引導(dǎo)其搜索過程朝著搜索空間的更優(yōu)化的解區(qū)域移動的。雖然看起來它是一種盲目搜索方法，實際上它有明確的搜索方向，具有內(nèi)在的并行搜索機(jī)制。（5）遺傳算法在搜索過程中不容易陷入局部最優(yōu)，即時在所定義的適應(yīng)度函數(shù)是不連續(xù)的、非規(guī)則的或有噪聲的情況下，也能以很大的概率找到全局最優(yōu)解。（6）遺傳算法采用自然進(jìn)化機(jī)制來表現(xiàn)復(fù)雜的現(xiàn)象，能夠快速可靠地解決求解非常困難的問題。（7）遺傳算法具有固有的并行性和并行計算的能力。（8）遺傳算法具有可擴(kuò)展性，易于同別的技術(shù)混合使用。遺傳算法作為一種優(yōu)化算法，也有它自身的局限性：（1）編碼不規(guī)范及編碼存在表示的不準(zhǔn)確性。（2）單一的遺傳算法編碼不能全面地將優(yōu)化問題的約束表示出來。考慮約束的一個方法就是對不可行解采用閾值，這樣，計算的時間必然增加。（3）遺傳算法通常的效率比其他傳統(tǒng)的優(yōu)化方法低。（4）遺傳算法容易出現(xiàn)過早收斂。（5）遺傳算法對算法的精度、可信度、計算復(fù)雜性等方面，還沒有有效的定量分析方法。遺傳算法的基本內(nèi)容如下：個體和種群。個體就是模擬生物個體而對問題中的對象（一般就是問題的解）的一種稱呼，一個個體也就是搜索空間中的一個點。種群(population)就是模擬生物種群而由若干個體組成的群體，它一般是整個搜索空間的一個很小的子集。適應(yīng)度與適應(yīng)度函數(shù)。適應(yīng)度(fitness)就是借鑒生物個體對環(huán)境的適應(yīng)程度,而對問題中的個體對象所設(shè)計的表征其優(yōu)劣的一種測度。適應(yīng)度函數(shù)（fitness function）就是問題中的全體個體與其適應(yīng)度之間的一個對應(yīng)關(guān)系。它一般是一個實值函數(shù)。該函數(shù)就是遺傳算法中指導(dǎo)搜索的評價函數(shù)。染色體與基因。染色體（chromosome）就是問題中個體的某種字符串形式的編碼表示。字符串中的字符也就稱為基因（gene）。例如個體上9，染色體的表示形式是1001，0和1是染色體上的基因。遺傳操作。也稱為遺傳算子，就是關(guān)于染色體的運算。遺傳算法中有三種遺傳操作：選擇-復(fù)制，交叉和變異。四、遺傳算法的流程遺傳算法在整個進(jìn)化過程中的遺傳操作是隨機(jī)的，但它所呈現(xiàn)出的特性并不是完全搜索，它能有效地利用歷史信息來推測下一代期望性能有所提高的尋優(yōu)點集。這樣一代代的不斷進(jìn)化，最后收斂到一個最適應(yīng)環(huán)境的個體上，求得問題的最優(yōu)解。遺傳算法所涉及的五大要素是：參數(shù)編碼、初始種群的設(shè)定、適應(yīng)度函數(shù)的設(shè)計、遺傳操作的設(shè)計和控制參數(shù)的設(shè)定。流程如圖1所示。圖1 遺傳算法基本流程簡單遺傳算法的運行過程為一個典型的迭代過程，其必須完成的工作內(nèi)容和基本步驟如下：1）選擇編碼策略，把參數(shù)集合X和域轉(zhuǎn)換為位串結(jié)構(gòu)空間S。2）定義適應(yīng)度函數(shù) 。3）確定遺傳策略，包括選擇群體大小n，選擇、交叉、變異方法，以及確定交叉概率 、變異概率 等遺傳參數(shù)。4）隨機(jī)初始化生成種群P。5）計算群體中個體位串解碼后的適應(yīng)度值 。6）按照遺傳策略，運用選擇、交叉和變異算子作用與群體，形成下一代群體。7）判斷群體性能是否滿足某一目標(biāo)，或者已完成預(yù)定迭代次數(shù)，不滿足則返回步驟6），或者修改遺傳策略再返回步驟6）。下面對基本步驟進(jìn)行分解，進(jìn)一步詳細(xì)介紹流程中一些細(xì)節(jié)。編碼表示。在許多問題求解中，編碼是遺傳算法中首要解決的問題，對算法的性能有很重要的影響。Holland提出的二進(jìn)制編碼是遺傳算法中最常用的一種編碼方法，它采用最小字符編碼原則， 編/解碼操作簡單易行，利于交叉、變異操作的實現(xiàn)，也可以采用模式定理對算法進(jìn)行理論分析。但二進(jìn)制編碼用于多維、高精度數(shù)值問題優(yōu)化時，不能很好地克服連續(xù)函數(shù)離散化時的映射誤差；不能直接反映問題的固有結(jié)構(gòu)，精度不高，并且個體長度大、占用內(nèi)存多。針對二進(jìn)制編碼存在的不足，人們提出了多種改進(jìn)方法，比較典型的有以下幾種：（1）格雷碼編碼。為了克服二進(jìn)制編碼在連續(xù)函數(shù)離散化時存在的不足，人們提出了用格雷碼進(jìn)行編碼的方法，它是二進(jìn)制編碼的變形。格雷碼不僅具有二進(jìn)制編碼的一些優(yōu)點，而且能夠提高遺傳算法的局部搜索能力。假設(shè)有一個二進(jìn)制編碼為，其對應(yīng)的格雷碼為，則 （2）實數(shù)編碼。該方法適合于遺傳算法中表示范圍較大的數(shù)，使遺傳算法更接近問題空間，避免了編碼和解碼的過程。它便于較大空間的遺傳搜索，提高了遺傳算法的精度要求；便于設(shè)計專門問題的遺傳算子；便于算法與經(jīng)典優(yōu)化方法的混合作用，改善了遺傳算法的計算復(fù)雜性，提高了運算效率。（3）十進(jìn)制編碼。該方法利用十進(jìn)制編碼控制參數(shù)，緩解了“組合爆炸”和遺傳算法的早熟收斂問題。（4）非數(shù)值編碼。染色體編碼串中的基因值取一個僅有代碼含義而無數(shù)值含義的符號集，這些符號可以是數(shù)字也可以是字符。非數(shù)值編碼的優(yōu)點是在遺傳算法中可以利用所求問題的專門知識及相關(guān)算法。對于非數(shù)值編碼，問題的解和染色體的編碼要注意染色體的可行性、染色體的合法性和映射的惟一性。適應(yīng)度函數(shù)。在遺傳算法中，適應(yīng)度是描述個體性能的主要指標(biāo)，根據(jù)適應(yīng)度的大小對個體進(jìn)行優(yōu)勝劣汰。對于求解有約束的優(yōu)化問題時，一般采用罰函數(shù)方法將目標(biāo)函數(shù)和約束條件建立成一個無約束的優(yōu)化目標(biāo)函數(shù)；然后再將目標(biāo)函數(shù)作適當(dāng)處理，建立適合遺傳算法的適應(yīng)度函數(shù)。將目標(biāo)函數(shù)轉(zhuǎn)換成適應(yīng)度函數(shù)一般應(yīng)遵循兩個原則：適應(yīng)度必須非負(fù)；優(yōu)化過程中目標(biāo)函數(shù)的變化方向應(yīng)與群體進(jìn)化過程中適應(yīng)度函數(shù)變化方向一致。在使用遺傳算法求解具體問題時，適應(yīng)度函數(shù)的選擇對算法的收斂性以及收斂速度的影響較大，針對不同的問題需根據(jù)經(jīng)驗或算法來確定相應(yīng)的參數(shù)。遺傳算子。在遺傳算法中通過一系列算子來決定后代，算子對當(dāng)前群體中選定的成員進(jìn)行重組和變異。（1）選擇算子 選擇操作通過適應(yīng)度選擇優(yōu)質(zhì)個體而拋棄劣質(zhì)個體，體現(xiàn)了“適者生存”的原理。常見的選擇操作主要有以下幾種：a）輪盤賭選擇。選擇某假設(shè)的概率是通過這個假設(shè)的適應(yīng)度與當(dāng)前群體中其他成員的適應(yīng)度的比值而得到。此方法是基于概率選擇的，存在統(tǒng)計誤差，因此可以結(jié)合最優(yōu)保存策略以保證當(dāng)前適應(yīng)度最優(yōu)的個體能夠進(jìn)化到下一代而不被遺傳操作的隨機(jī)性破壞，保證算法的收斂性。b）排序選擇。對個體適應(yīng)度取正值或負(fù)值以及個體適應(yīng)度之間的數(shù)值差異程度無特殊要求，對群體中的所有個體按其適應(yīng)度大小進(jìn)行排序，根據(jù)排序來分配各個體被選中的概率。c）最優(yōu)個體保存。父代群體中的最優(yōu)個體直接進(jìn)入子代群體中。該方法可保證在遺傳過程中所得到的個體不會被交叉和變異操作所破壞，它是遺傳算法收斂性的一個重要保證條件；它也容易使得局部最優(yōu)個體不易被淘汰，從而使算法的全局搜索能力變強(qiáng)。d）隨機(jī)聯(lián)賽選擇。每次選取N個個體中適應(yīng)度最高的個體遺傳到下一代群體中。具體操作如下：從群體中隨機(jī)選取N個個體進(jìn)行適應(yīng)度大小比較，將其中適應(yīng)度最高的個體遺傳到下一代群體中；將上述過程重復(fù)執(zhí)行M（為群體大小）次，則可得到下一代群體。（2）交叉算子 交叉是指對兩個相互交叉的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。它是產(chǎn)生新個體的主要方法，決定了遺傳算法的全局搜索能力，在遺傳算法中起關(guān)鍵作用。幾種常用的適用于二進(jìn)制編碼或?qū)崝?shù)編碼方式的交叉算子如下：a）單點交叉。在個體編碼串中隨機(jī)設(shè)置一個交叉點后在該點相互交換兩個配對個體的部分基因。b）兩點交叉。在相互配對的兩個個體編碼串中隨機(jī)設(shè)置兩個交叉點，并交換兩個交叉點之間的部分基因。c）均勻交叉。兩個相互配對個體的每一位基因都以相同的概率進(jìn)行交換，從而形成兩個新個體。d）算術(shù)交叉。由兩個個體的線性組合而產(chǎn)生出新的個體。（3）變異算子 變異是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個新的個體。它是產(chǎn)生新個體的輔助方法，決定了遺傳算法的局部搜索能力。變異算子與交叉算子相互配合，可以共同完成對搜索空間的全局搜索和局部搜索，從而使得遺傳算法以良好的搜索性能完成最優(yōu)化問題的尋優(yōu)過程。在遺傳算法中使用變異算子主要有以下兩個目的: 改善遺傳算法的局部搜索能力；維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。下面是幾種常用的變異操作：a）基本位變異。對個體編碼串以變異概率P隨機(jī)指定某一位或某幾位基因進(jìn)行變異操作。b）均勻變異（一致變異）。分別用符合某一范圍內(nèi)均勻分布的隨機(jī)數(shù)，以某一較小的概率來替換個體編碼串中各個基因座上的原有基因值。均勻變異操作特別適合應(yīng)用于遺傳算法的初期運行階段，它使得搜索點可以在整個搜索空間內(nèi)自由地移動，從而可以增加群體的多樣性，使算法能夠處理更多的模式。c）二元變異。需要兩條染色體參與，通過二元變異操作后生成兩條新個體中的各個基因分別取原染色體對應(yīng)基因值的同或異或。它改變了傳統(tǒng)的變異方式，有效地克服了早熟收斂，提高了遺傳算法的優(yōu)化速度。d）高斯變異。在進(jìn)行變異時用一個均值為L、方差為R2的正態(tài)分布的一個隨機(jī)數(shù)來替換原有基因值。其操作過程與均勻變異類似。五、遺傳算法實例例：利用遺傳算法，求解區(qū)間0，31上的二次函數(shù)的最大值。分析：原問題可轉(zhuǎn)化為在區(qū)間0，31中搜索能使y取最小值的點x的問題。那么，0，31中的點x就是個體，函數(shù)值f(x)恰好就可以作為x的適應(yīng)度，區(qū)間0，31就是一個（解）空間。這樣，只要能給出個體x的適當(dāng)染色體編碼，該問題就可以用遺傳算法來解決。二次函數(shù)的圖像如圖2所示。圖2 二次函數(shù)的圖像（1）設(shè)定種群規(guī)模，編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4；用5位二進(jìn)制數(shù)編碼染色體；取下列個體組成初始種群： = 13（01101）， = 24（11000） = 8 （01000）， = 19（10011）（2）定義適應(yīng)度函數(shù)。取適應(yīng)度函數(shù)：f (x) = 。（3）計算各代種群中的各個體的適應(yīng)度，并對其染色體進(jìn)行遺傳操作，直到適應(yīng)度最高的個體（即31（11111）出現(xiàn)為止。首先計算種群S1中各個體的適應(yīng)度。容易求得， f (s1) = f(13) = 132 = 169 f (s2) = f(24) = 242 = 576 f (s3) = f(8) = 82 = 64 f (s4) = f(19) = 192 = 361再計算種群中各個體的選擇概率。選擇概率的計算公式為 由此求得， 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個隨機(jī)數(shù)如下： r1 = 0.450126， r2 = 0.110347 r3 = 0.572496， r4 = 0.98503表1 第一代選中次數(shù)表 染色體 適應(yīng)度選擇概率積累概率選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.3111于是，經(jīng)復(fù)制得群體：s1 =11000（24）， s2 =01101（13）s3 =11000（24）， s4 =10011（19） 設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運算。設(shè)s1與s2配對，s3與s4配對。分別交換后兩位基因，得新染色體：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）， s2=01100（12） s3=11011（27）， s4=10000（16）表2 第二代選中次數(shù)表 染色體 適應(yīng)度選擇概率積累概率 估計的選中次數(shù)s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.1511假設(shè)這一輪選擇-復(fù)制操作中，種群中的4個染色體都被選中，則得到群體：s1=11001（25）， s2= 01100（12）s3=11011（27）， s4= 10000（16） 做交叉運算，讓s1與s2，s3與s4 分別交換后三位基因，得 s1 =11100（28）， s2 = 01001（9） s3 =11000（24）， s4 = 10011（19） 這一輪仍然不會發(fā)生變異。于是，得第三代種群S3： s1=11100（28），s2=01001（9） s3=11000（24）， s4=10011（19） 表3 第三代選中次數(shù) 染色體 適應(yīng)度選擇概率積累概率 估計的選中次數(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）做交叉運算，讓s1與s4，s2與s3 分別交換后兩位基因，得 s1=11111（31）， s2=11100（28）s3=11000（24）， s4=10000（16）這一輪仍然不會發(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)境下運行。鑒于此版本的軟件不含有遺傳算法工具箱，自行安裝至路徑“D:MATLABR2010atoolboxgeneticgatbx”，并在操作界面上添加路徑。程序見附錄一，程序界面如圖3所示。圖3 程序圖運行結(jié)果如圖4所示。圖4 運行結(jié)果圖由圖可知，經(jīng)過10代之后，遺傳算法找個了二次函數(shù)的最優(yōu)值。附錄一：運行程序a