【正文】 上。所以在進(jìn)化周期的第二步（重組）中向群體中引入了新個(gè)體。把方程（1）稱為復(fù)制模式增長方程。假定在時(shí)刻，群體中匹配模式的串有個(gè){}，則 在選擇過程中，中間群體是這樣產(chǎn)生的：對個(gè)單個(gè)串進(jìn)行選擇。發(fā)生在進(jìn)化周期其余兩個(gè)階段的主要現(xiàn)象是選擇和重組。其中模式是最特殊的一個(gè)。 不同的模式有不同的特性。一個(gè)模式是通過引入通配符(*)到基因字母表中來建立的。 現(xiàn)在準(zhǔn)備再運(yùn)行以此選擇過程：應(yīng)用遺傳算子及評價(jià)下一代等。整個(gè)群體共有位；。這里很幸運(yùn)，給選擇的染色體數(shù)是偶數(shù)，可以很容易地配對；如果選擇的染色體數(shù)為奇數(shù)，可以加入一額外的染色體或者移走一被選擇染色體，這種選擇同樣是隨機(jī)的。例如，染色體 (010001001011010000111110010100010)的前18位010001001011010000表示；后15位111110010100010表示 ；所以該染色體對應(yīng)于，該染色體的適應(yīng)值為。其它的部分只是上述步驟的循環(huán)重復(fù)，見圖1。隨機(jī)地對被選擇的染色體配對：對染色體中的每一個(gè)，產(chǎn)生一個(gè)在區(qū)間[1, ]（為總長，即染色體位數(shù)）里的隨機(jī)整數(shù)。 代表一個(gè)潛在解的染色體被長度為的二進(jìn)制串表達(dá)；前位對應(yīng)區(qū)間[]里的一個(gè)值，隨后的位對應(yīng)區(qū)間[]里的一個(gè)值，等等；最后的位對應(yīng)區(qū)間[]里的一個(gè)值。二、遺傳算法的運(yùn)行步驟：1. 一般性描述： 不失一般性，考慮求最大值的問題。變異是通過用一個(gè)等于變異率的概率隨機(jī)地改變被選擇染色體上的一個(gè)或多個(gè)基因（染色體中的一個(gè)二進(jìn)制位）。一代代進(jìn)化，直到最終解族對應(yīng)的誤差泛函值達(dá)到設(shè)定的要求。 CurrentBest(1:MumberLength)=Population(MaxSite,:)。 end endendNewPopulation=Population。 Population(i,1:Site)=Population(i+1,1:Site)。%%Population=Population(SortSite,:)。for i=2:MemberNumber CProbability(i)=CProbability(i1)+PopulationProbability(i)。,sym(PopulationData)))。end【程序說明】．子程序中含有5個(gè)輸入?yún)?shù)：PopulationCode表示用0—1代碼表示的群體，F(xiàn)unctionFitness 表示目標(biāo)函數(shù)，它是一個(gè)字符串，因此寫入調(diào)用程序時(shí)，應(yīng)該用單引號括出，MumberLength表示染色體位串的二進(jìn)制長度．MinX和MaxX 分別指變量區(qū)間的上下限．附錄4：子程序 function PopulationData=Translate(PopulationCode,MinX,MaxX,MumberLength)PopulationData=0。endResult(2,:)=PopulationFitness。 Count=Count+1。 Population=NewPopulation。PopulationCode=Population。實(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ī)會(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é)說對我們用計(jì)算機(jī)解決復(fù)雜問題很有用，而它本身是否完全正確并不重要（目前生物界對此學(xué)說尚有爭議）．（1）遺傳算法中的生物遺傳學(xué)概念由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的直接搜索優(yōu)化方法；故而在這個(gè)算法中要用到各種進(jìn)化和遺傳學(xué)的概念．首先給出遺傳學(xué)概念、遺傳算法概念和相應(yīng)的數(shù)學(xué)概念三者之間的對應(yīng)關(guān)系．這些概念如下：序號遺傳學(xué)概念遺傳算法概念數(shù)學(xué)概念1個(gè)體要處理的基本對象、結(jié)構(gòu)也就是可行解2群體個(gè)體的集合被選定的一組可行解3染色體個(gè)體的表現(xiàn)形式可行解的編碼4基因染色體中的元素編碼中的元素5基因位某一基因在染色體中的位置元素在編碼中的位置6適應(yīng)值個(gè)體對于環(huán)境的適應(yīng)程度，或在環(huán)境壓力下的生存能力可行解所對應(yīng)的適應(yīng)函數(shù)值7種群被選定的一組染色體或個(gè)體根據(jù)入選概率定出的一組可行解8選擇從群體中選擇優(yōu)勝的個(gè)體，淘汰劣質(zhì)個(gè)體的操作保留或復(fù)制適應(yīng)值大的可行解，去掉小的可行解9交叉一組染色體上對應(yīng)基因段的交換根據(jù)交叉原則產(chǎn)生的一組新解10交叉概率染色體對應(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)化，一代又一代地優(yōu)化目標(biāo)函數(shù)取到最大值，最優(yōu)的可行解（2）遺傳算法的步驟遺傳算法計(jì)算優(yōu)化的操作過程就如同生物學(xué)上生物遺傳進(jìn)化的過程，主要有三個(gè)基本操作（或稱為算子）：選擇（Selection）、交叉（Crossover）、變異（Mutation）．遺傳算法基本步驟主要是：先把問題的解表示成“染色體”，在算法中也就是以二進(jìn)制編碼的串，在執(zhí)行遺傳算法之前，給出一群“染色體”，也就是假設(shè)的可行解．然后，把這些假設(shè)的可行解置于問題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，再通過交叉、變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群．經(jīng)過這樣的一代一代地進(jìn)化，最后就會(huì)收斂到最適應(yīng)環(huán)境的一個(gè)“染色體”上，它就是問題的最優(yōu)解．下面給出遺傳算法的具體步驟，流程圖參見圖1：第一步：選擇編碼策略，把參數(shù)集合（可行解集合）轉(zhuǎn)換染色體結(jié)構(gòu)空間；第二步：定義適應(yīng)函數(shù)，便于計(jì)算適應(yīng)值；第三步：確定遺傳策略，包括選擇群體大小，選擇、交叉、變異方法以及確定交叉概率、變異概率等遺傳參數(shù)；第四步：隨機(jī)產(chǎn)生初始化群體；第五步：計(jì)算群體中的個(gè)體或染色體解碼后的適應(yīng)值；第六步：按照遺傳策略，運(yùn)用選擇、交叉和變異算子作用于群體，形成下一代群體；第七步：判斷群體性能是否滿足某一指標(biāo)、或者是否已完成預(yù)定的迭代次數(shù)，不滿足則返回第五步、或者修改遺傳策略再返回第六步．產(chǎn)生初始群體是否滿足終止條件得到結(jié)果結(jié)束程序是否計(jì)算每個(gè)個(gè)體的適應(yīng)值以概率選擇遺傳算子選擇一個(gè)個(gè)體復(fù)制到新群體選擇兩個(gè)個(gè)體進(jìn)行交叉插入到新群體選擇一個(gè)個(gè)體進(jìn)行變異插入到新群體得到新群體圖1 一個(gè)遺傳算法的具體步驟遺傳算法有很多種具體的不同實(shí)現(xiàn)過程，以上介紹的是標(biāo)準(zhǔn)遺傳算法的主要步驟，此算法會(huì)一直運(yùn)行直到找到滿足條件的最優(yōu)解為止．2．遺傳算法的實(shí)際應(yīng)用例1：設(shè)，求 ．注：這是一個(gè)非常簡單的二次函數(shù)求極值的問題，相信大家都會(huì)做．在此我們要研究的不是問題本身，而是借此來說明如何通過遺傳算法分析和解決問題．在此將細(xì)化地給出遺傳算法的整個(gè)過程．（1）編碼和產(chǎn)生初始群體首先第一步要確定編碼的策略，也就是說如何把到2這個(gè)區(qū)間內(nèi)的數(shù)用計(jì)算機(jī)語言表示出來．編碼就是表現(xiàn)型到基因型的映射，編碼時(shí)要注意以下三個(gè)原則：完備性：問題空間中所有點(diǎn)（潛在解）都能成為GA編碼空間中的點(diǎn)（染色體位串）的表現(xiàn)型；健全性：GA編碼空間中的染色體位串必須對應(yīng)問題空間中的某一潛在解；非冗余性：染色體和潛在解必須一一對應(yīng)．這里我們通過采用二進(jìn)制的形式來解決編碼問題，將某個(gè)變量值代表的個(gè)體表示為一個(gè){0，1}二進(jìn)制串．當(dāng)然，串長取決于求解的精度．如果要設(shè)定求解精度到六位小數(shù)，由于區(qū)間長度為，則必須將閉區(qū)間 分為等分．因?yàn)?所以編碼的二進(jìn)制串至少需要22位．將一個(gè)二進(jìn)制串（b21b20b19…b1b0）轉(zhuǎn)化為區(qū)間內(nèi)對應(yīng)的實(shí)數(shù)值很簡單，只需采取以下兩步（Matlab程序參見附錄4）：1）將一個(gè)二進(jìn)制串（b21b20b19…b1b0）代表的二進(jìn)制數(shù)化為10進(jìn)制數(shù)：2） 對應(yīng)的區(qū)間內(nèi)的實(shí)數(shù)：例如，一個(gè)二進(jìn)制串a(chǎn)=1000101110110101000111．=(1000101110110101000111)2=2288967二進(jìn)制串0000000000000000000000，1111111111111111111111，則分別表示區(qū)間的兩個(gè)端點(diǎn)值1和2．利用這種方法我們就完成了遺傳算法的第一步——編碼，這種二進(jìn)制編碼的方法完全符合上述的編碼的三個(gè)原則．首先我們來隨機(jī)的產(chǎn)生一個(gè)個(gè)體數(shù)為4個(gè)的初始群體如下：pop(1)={1101011101001100011110， %% a11000011001010001000010， %% a20001100111010110000000， %% a30110101001101110010101} %% a4（Matlab程序參見附錄2）化成十進(jìn)制的數(shù)分別為：pop(1)={ ， ， ， }接下來我們就要解決每個(gè)染色體個(gè)體的適應(yīng)值問題了．（2）定義適應(yīng)函數(shù)和適應(yīng)值由于給定的目標(biāo)函數(shù)在內(nèi)的值有正有負(fù)，所以必須通過建立適應(yīng)函數(shù)與目標(biāo)函數(shù)的映射關(guān)系，保證映射后的適應(yīng)值非負(fù)，而且目標(biāo)函數(shù)的優(yōu)化方向應(yīng)對應(yīng)于適應(yīng)值增大的方向，也為以后計(jì)算各個(gè)體的入選概率打下基礎(chǔ)．對于本題中的最大化問題，定義適應(yīng)函數(shù)，采用下述方法：式中既可以是特定的輸入值，也可以是當(dāng)前所有代或最近K代中的最小值，這里為了便于計(jì)算，將采用了一個(gè)特定的輸入值．若取，則當(dāng)時(shí)適應(yīng)函數(shù)；當(dāng)時(shí)適應(yīng)函數(shù)．由上述所隨機(jī)產(chǎn)生的初始群體，我們可以先計(jì)算出目標(biāo)函數(shù)值分別如下（Matlab程序參見附錄3）：f [pop(1)]={ , , , }然后通過適應(yīng)函數(shù)計(jì)算出適應(yīng)值分別如下（Matlab程序參見附錄附錄6）：取，g[pop(1)]= { , , 0 , }（3）確定選擇標(biāo)準(zhǔn)這里我們用到了適應(yīng)值的比例來作為選擇的標(biāo)準(zhǔn)，得到的每個(gè)個(gè)體的適應(yīng)值比例叫作入選概率．其計(jì)算公式如下：對于給定的規(guī)模為n的群體pop={}，個(gè)體的適應(yīng)值為，則其入選概率為由上述給出的群體，我們可以計(jì)算出各個(gè)個(gè)體的入選概率．首先可得 ，然后分別用四個(gè)個(gè)體的適應(yīng)值去除以，得：P(a1)= / = %% a1P(a2)= / = %% a2P(a3)= 0 / = 0 %% a3P(a4)= / = %% a4（Matlab程序參見附錄7）（4）產(chǎn)生種群計(jì)算完了入選概率后，就將入選概率大的個(gè)體選入種群，淘汰概率小的個(gè)體，并用入選概率最大的個(gè)體補(bǔ)入種群，得到與原群體大小同樣的種群（Matlab程序參見附錄附錄11）．要說明的是：附錄11的算法與這里不完全相同．為保證收斂性，附錄11的算法作了