【正文】 的預(yù)測(cè)串?dāng)?shù)是實(shí)際匹配模式串?dāng)?shù)、模式的相對(duì)適應(yīng)值及模式的定義長度的函數(shù)。這就意味著模式的最大消亡概率為 因此，該模式的最小存活概率為實(shí)際上，我們的例子中的模式和的存活概率和消亡概率分別為：， ， 所以結(jié)果是可以預(yù)測(cè)的。因?yàn)樵谀０彘_始的固定位“111”和結(jié)尾的固定位“10”分布在不同的子代上。根據(jù)上一節(jié)的例子（個(gè)體和被選擇進(jìn)行雜交），假定雜交位置為。所以在進(jìn)化周期的第二步（重組）中向群體中引入了新個(gè)體。可以用以前的實(shí)例檢驗(yàn)對(duì)的預(yù)測(cè)。把方程（1）稱為復(fù)制模式增長方程。因?yàn)椋?1) 對(duì)一個(gè)被模式匹配的一般串，在一個(gè)單個(gè)串的選擇中，其選擇概率約等于；(2) 被模式匹配的串?dāng)?shù)為；(3) 單個(gè)串的選擇數(shù)目為，很明顯， 因?yàn)槿后w的平均適應(yīng)值，所以上式可寫為 (1)這就意味著一個(gè)適應(yīng)值在平均值之上的模式在下一代中的串?dāng)?shù)會(huì)增加，一個(gè)適應(yīng)值低于平均的模式在下一代中的串?dāng)?shù)會(huì)減小，而一個(gè)中庸的模式將保持不變的水平。假定在時(shí)刻，群體中匹配模式的串有個(gè){}，則 在選擇過程中，中間群體是這樣產(chǎn)生的：對(duì)個(gè)單個(gè)串進(jìn)行選擇。假定在時(shí)刻，群體為原先初始化的結(jié)果（見P4的）。發(fā)生在進(jìn)化周期其余兩個(gè)階段的主要現(xiàn)象是選擇和重組。如，和。其中模式是最特殊的一個(gè)。 模式的階（由表示），為串中0和1的數(shù)目，即固定位而非通配位的數(shù)目。 不同的模式有不同的特性。而模式(*1*1100100)與四個(gè)串匹配：{(0101100100), (0111100100), (1101100100), (1111100100)}。一個(gè)模式是通過引入通配符(*)到基因字母表中來建立的。跟蹤進(jìn)化過程中的最好個(gè)體是容易的。 現(xiàn)在準(zhǔn)備再運(yùn)行以此選擇過程：應(yīng)用遺傳算子及評(píng)價(jià)下一代等。 變異位以黑體表示。整個(gè)群體共有位；。第一對(duì)染色體是：產(chǎn)生的數(shù)為。這里很幸運(yùn)，給選擇的染色體數(shù)是偶數(shù)，可以很容易地配對(duì)；如果選擇的染色體數(shù)為奇數(shù)，可以加入一額外的染色體或者移走一被選擇染色體，這種選擇同樣是隨機(jī)的。假定在區(qū)間[0, 1]里的20個(gè)數(shù)的一個(gè)隨機(jī)序列是： 第一個(gè)數(shù)大于而小于，意味著染色體被選擇；第二個(gè)數(shù)大于而小于，意味著染色體被選擇，等等。例如，染色體 (010001001011010000111110010100010)的前18位010001001011010000表示；后15位111110010100010表示 ；所以該染色體對(duì)應(yīng)于，該染色體的適應(yīng)值為。由于，因此染色體的第一部分需要18位。其它的部分只是上述步驟的循環(huán)重復(fù)，見圖1。另一個(gè)遺傳系統(tǒng)參數(shù)，變異率，給出了我們預(yù)計(jì)的變異位數(shù)：。隨機(jī)地對(duì)被選擇的染色體配對(duì)：對(duì)染色體中的每一個(gè)，產(chǎn)生一個(gè)在區(qū)間[1, ]（為總長，即染色體位數(shù)）里的隨機(jī)整數(shù)。按照如下方法構(gòu)造輪盤（假設(shè)這里的適應(yīng)值時(shí)正值，否則可以使用一些比例機(jī)制調(diào)整）：● 計(jì)算每個(gè)染色體的適應(yīng)值；● 計(jì)算群體的總適應(yīng)值： ● 計(jì)算每個(gè)染色體的選擇概率： ● 計(jì)算每個(gè)染色體的累計(jì)概率： 對(duì)輪盤轉(zhuǎn)動(dòng)次，每次按照下面的方法為新群體選擇一個(gè)單個(gè)的染色體：● 產(chǎn)生一個(gè)在區(qū)間[0，1]里的隨機(jī)數(shù)；● 如果，則選擇第一個(gè)染色體；否則選擇使成立的第個(gè)染色體()。 代表一個(gè)潛在解的染色體被長度為的二進(jìn)制串表達(dá)；前位對(duì)應(yīng)區(qū)間[]里的一個(gè)值，隨后的位對(duì)應(yīng)區(qū)間[]里的一個(gè)值，等等；最后的位對(duì)應(yīng)區(qū)間[]里的一個(gè)值。1） 編碼和解碼：要達(dá)到要求的精度，每個(gè)域應(yīng)該被分割為個(gè)等尺寸的區(qū)間。二、遺傳算法的運(yùn)行步驟：1. 一般性描述： 不失一般性，考慮求最大值的問題。(3). 它僅僅利用適應(yīng)值信息評(píng)估個(gè)體的優(yōu)劣，無須求導(dǎo)數(shù)或其它輔助信息。變異是通過用一個(gè)等于變異率的概率隨機(jī)地改變被選擇染色體上的一個(gè)或多個(gè)基因（染色體中的一個(gè)二進(jìn)制位）。新的群體的成員通過雜交和變異進(jìn)行變換，形成新的解。一代代進(jìn)化，直到最終解族對(duì)應(yīng)的誤差泛函值達(dá)到設(shè)定的要求?！境绦蛘f明】（“優(yōu)勝劣汰”思想）．輸入?yún)?shù)為：群體Population, 目標(biāo)函數(shù)值PopulationFitness和染色體個(gè)數(shù)MumberLength．“遺傳算法”專題一、遺傳算法的主要特征： 我們的目的是獲得“最好解”，可以把這種任務(wù)看成是一個(gè)優(yōu)化過程。 CurrentBest(1:MumberLength)=Population(MaxSite,:)。EachGenMaxFitness=MaxFitness。 end endendNewPopulation=Population。for i=1:Dim(1) Probability=rand(1)。 Population(i,1:Site)=Population(i+1,1:Site)。 Population(Dim(1)1,:)=Temp。%%Population=Population(SortSite,:)。 end NewPopulation(i,:)=Population(Index,:)。for i=2:MemberNumber CProbability(i)=CProbability(i1)+PopulationProbability(i)。endif PopulationFitness(i)=Fmin PopulationFitnessF(i)=0。,sym(PopulationData)))?！境绦蛘f明】子程序 ．含有4個(gè)輸入?yún)?shù)，PopulationCode, MinX, MaxX, MumberLength．附錄5：function PopulationFitness=Transfer(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength)PopulationFitness=0。end【程序說明】．子程序中含有5個(gè)輸入?yún)?shù)：PopulationCode表示用0—1代碼表示的群體，F(xiàn)unctionFitness 表示目標(biāo)函數(shù)，它是一個(gè)字符串，因此寫入調(diào)用程序時(shí)，應(yīng)該用單引號(hào)括出，MumberLength表示染色體位串的二進(jìn)制長度．MinX和MaxX 分別指變量區(qū)間的上下限．附錄4：子程序 function PopulationData=Translate(PopulationCode,MinX,MaxX,MumberLength)PopulationData=0。Population=(Temporary=*ones(size(Temporary)))。endResult(2,:)=PopulationFitness。 Population=NewPopulation。 Count=Count+1。 Population=NewPopulation。 Population=NewPopulation。[Population,CurrentBest,EachGenMaxFitness]=Elitist(PopulationCode,PopulationFitness,MumberLength)。PopulationCode=Population。,1,2,2,)Count = 13Result = BestMember = 可以看到：兩組解都已經(jīng)很接近實(shí)際結(jié)果，對(duì)于兩種方法所產(chǎn)生的最優(yōu)解差異很?。梢娺@兩種終止算法都是可行的，而且可以知道對(duì)于例1的問題，遺傳算法只要經(jīng)過10代左右就可以完成收斂，達(dá)到一個(gè)最優(yōu)解．2． 按照例2的具體要求，用遺傳算法求上述例2的最優(yōu)解．3． 附錄9子程序 ．若去掉前面的%號(hào)，則程序的算法思想有什么變化？4． 附錄9子程序 ，當(dāng)Dim(1)=3時(shí)，將交換數(shù)組Population的最后兩行，即交換最后面的兩個(gè)個(gè)體．其目的是什么？5． ，修改附錄9子程序 ，使得交叉過程也有一個(gè)概率值（~）；，以便代入交叉概率．6． 設(shè)，求 ，要設(shè)定求解精度到15位小數(shù)．五、附錄附錄1：function [Count,Result,BestMember]=Genetic1(MumberLength,MemberNumber,FunctionFitness,MinX,MaxX,Fmin,MutationProbability,Gen)Population=PopulationInitialize(MumberLength,MemberNumber)。實(shí)驗(yàn)十 遺傳算法與優(yōu)化問題一、問題背景與實(shí)驗(yàn)?zāi)康倪z傳算法（Genetic Algorithm—GA），是模擬達(dá)爾文的遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì)算模型，．遺傳算法作為一種新的全局優(yōu)化搜索算法，以其簡單通用、魯棒性強(qiáng)、適于并行處理及應(yīng)用范圍廣等顯著特點(diǎn)，奠定了它作為21世紀(jì)關(guān)鍵智能計(jì)算之一的地位．本實(shí)驗(yàn)將首先介紹一下遺傳算法的基本理論，然后用其解決幾個(gè)簡單的函數(shù)最值問題，使讀者能夠?qū)W會(huì)利用遺傳算法進(jìn)行初步的優(yōu)化計(jì)算．1．遺傳算法的基本原理遺傳算法的基本思想正是基于模仿生物界遺傳學(xué)的遺傳過程．它把問題的參數(shù)用基因代表，把問題的解用染色體代表（在計(jì)算機(jī)里用二進(jìn)制碼表示），從而得到一個(gè)由具有不同染色體的個(gè)體組成的群體．這個(gè)群體在問題特定的環(huán)境里生存競(jìng)爭，適者有最好的機(jī)會(huì)生存和產(chǎn)生后代．后代隨機(jī)化地繼承了父代的最好特征，并也在生存環(huán)境的控制支配下繼續(xù)這一過程．群體的染色體都將逐漸適應(yīng)環(huán)境，不斷進(jìn)化，最后收斂到一族最適應(yīng)環(huán)境的類似個(gè)體，即得到問題最優(yōu)的解．值得注意的一點(diǎn)是，現(xiàn)在的遺傳算法是受生物進(jìn)化論學(xué)說的啟發(fā)提出的，這種學(xué)說對(duì)我們用計(jì)算機(jī)解決復(fù)雜問題很有用，而它本身是否完全正確并不重要（目前生物界對(duì)此學(xué)說尚有爭議）．（1）遺傳算法中的生物遺傳學(xué)概念由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的直接搜索優(yōu)化方法；故而在這個(gè)算法中要用到各種進(jìn)化和遺傳學(xué)的概念．首先給出遺傳學(xué)概念、遺傳算法概念和相應(yīng)的數(shù)學(xué)概念三者之間的對(duì)應(yīng)關(guān)系．這些概念如下：序號(hào)遺傳學(xué)概念遺傳算法概念數(shù)學(xué)概念1個(gè)體要處理的基本對(duì)象、結(jié)構(gòu)也就是可行解2群體個(gè)體的集合被選定的一組可行解3染色體個(gè)體的表現(xiàn)形式可行解的編碼4基因染色體中的元素編碼中的元素5基因位某一基因在染色體中的位置元素在編碼中的位置6適應(yīng)值個(gè)體對(duì)于環(huán)境的適應(yīng)程度，或在環(huán)境壓力下的生存能力可行解所對(duì)應(yīng)的適應(yīng)函數(shù)值7種群被選定的一組染色體或個(gè)體根據(jù)入選概率定出的一組可行解8選擇從群體中選擇優(yōu)勝的個(gè)體，淘汰劣質(zhì)個(gè)體的操作保留或復(fù)制適應(yīng)值大的可行解，去掉小的可行解9交叉一組染色體上對(duì)應(yīng)基因段的交換根據(jù)交叉原則產(chǎn)生的一組新解10交叉概率染色體對(duì)應(yīng)基因段交換的概率（可能性大?。╅]區(qū)間[0,1]上的一個(gè)值，~11變異染色體水平上基因變化編碼的某些元素被改變12變異概率染色體上基因變化的概率（可能性大?。╅_區(qū)間(0,1)內(nèi)的一個(gè)值, ~13進(jìn)化、適者生存?zhèn)€體進(jìn)行優(yōu)勝劣汰的進(jìn)化，一代又一