【正文】 代地優(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è)非常簡(jiǎn)單的二次函數(shù)求極值的問題，相信大家都會(huì)做．在此我們要研究的不是問題本身，而是借此來說明如何通過遺傳算法分析和解決問題．在此將細(xì)化地給出遺傳算法的整個(gè)過程．（1）編碼和產(chǎn)生初始群體首先第一步要確定編碼的策略，也就是說如何把到2這個(gè)區(qū)間內(nèi)的數(shù)用計(jì)算機(jī)語(yǔ)言表示出來．編碼就是表現(xiàn)型到基因型的映射，編碼時(shí)要注意以下三個(gè)原則：完備性：?jiǎn)栴}空間中所有點(diǎn)（潛在解）都能成為GA編碼空間中的點(diǎn)（染色體位串）的表現(xiàn)型；健全性：GA編碼空間中的染色體位串必須對(duì)應(yīng)問題空間中的某一潛在解；非冗余性：染色體和潛在解必須一一對(duì)應(yīng)．這里我們通過采用二進(jìn)制的形式來解決編碼問題，將某個(gè)變量值代表的個(gè)體表示為一個(gè){0，1}二進(jìn)制串．當(dāng)然，串長(zhǎng)取決于求解的精度．如果要設(shè)定求解精度到六位小數(shù)，由于區(qū)間長(zhǎng)度為，則必須將閉區(qū)間 分為等分．因?yàn)?所以編碼的二進(jìn)制串至少需要22位．將一個(gè)二進(jìn)制串（b21b20b19…b1b0）轉(zhuǎn)化為區(qū)間內(nèi)對(duì)應(yīng)的實(shí)數(shù)值很簡(jiǎn)單，只需采取以下兩步（Matlab程序參見附錄4）：1）將一個(gè)二進(jìn)制串（b21b20b19…b1b0）代表的二進(jìn)制數(shù)化為10進(jìn)制數(shù)：2） 對(duì)應(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)對(duì)應(yīng)于適應(yīng)值增大的方向，也為以后計(jì)算各個(gè)體的入選概率打下基礎(chǔ)．對(duì)于本題中的最大化問題，定義適應(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ì)算公式如下：對(duì)于給定的規(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的算法作了修正，采用了最佳個(gè)體保存方法（elitist model），具體內(nèi)容將在后面給出介紹．由初始群體的入選概率我們淘汰掉a3，再加入a2補(bǔ)足成與群體同樣大小的種群得到newpop(1)如下：newpop(1)={1101011101001100011110， %% a11000011001010001000010， %% a21000011001010001000010， %% a20110101001101110010101} %% a4（5）交叉交叉也就是將一組染色體上對(duì)應(yīng)基因段的交換得到新的染色體，然后得到新的染色體組，組成新的群體（Matlab程序參見附錄9）．我們把之前得到的newpop(1)的四個(gè)個(gè)體兩兩組成一對(duì)，重復(fù)的不配對(duì)，進(jìn)行交叉．（可以在任一位進(jìn)行交叉）110101110 1001100011110， 1101011101010001000010 交叉得：100001100 1010001000010， 100001100100110001111010000110010100 01000010， 1000011001010010010101 交叉得：01101010011011 10010101， 0110101001101101000010通過交叉得到了四個(gè)新個(gè)體，得到新的群體jchpop (1)如下：jchpop(1)={1101011101010001000010，1000011001001100011110，1000011001010010010101，0110101001101101000010}這里采用的是單點(diǎn)交叉的方法，當(dāng)然還有多點(diǎn)交叉的方法，不過有些煩瑣，這里就不著重介紹了．（6）變異變異也就是通過一個(gè)小概率改變?nèi)旧w位串上的某個(gè)基因（Matlab程序參見附錄10）．現(xiàn)把剛得到的jchpop(1)中第3個(gè)個(gè)體中的第9位改變，就產(chǎn)生了變異，得到了新的群體pop(2)如下：pop(2)= {1101011101010001000010，1000011001001100011110，1000011011010010010101，0110101001101101000010 }然后重復(fù)上述的選擇、交叉、變異直到滿足終止條件為止．（7）終止條件遺傳算法的終止條件有兩類常見條件：（1）采用設(shè)定最大（遺傳）代數(shù)的方法，一般可設(shè)定為50代，此時(shí)就可能得出最優(yōu)解．此種方法簡(jiǎn)單易行，但可能不是很精確（Matlab程序參見附錄1）；（2）根據(jù)個(gè)體的差異來判斷，通過計(jì)算種群中基因多樣性測(cè)度，即所有基因位相似程度來進(jìn)行控制．3．遺傳算法的收斂性前面我們已經(jīng)就遺傳算法中的編碼、適應(yīng)度函數(shù)、選擇、交叉和變異等主要操作的基本內(nèi)容及設(shè)計(jì)進(jìn)行了詳細(xì)的介紹．作為一種搜索算法，遺傳算法通過對(duì)這些操作的適當(dāng)設(shè)計(jì)和運(yùn)行，可以實(shí)現(xiàn)兼顧全局搜索和局部搜索的所謂均衡搜索，具體實(shí)現(xiàn)見下圖2所示．圖2 均衡搜索的具體實(shí)現(xiàn)圖示應(yīng)該指出的是，遺傳算法雖然可以實(shí)現(xiàn)均衡的搜索，并且在許多復(fù)雜問題的求解中往往能得到滿意的結(jié)果，但是該算法的全局優(yōu)化收斂性的理論分析尚待解決．目前普遍認(rèn)為，標(biāo)準(zhǔn)遺傳算法并不保證全局最優(yōu)收斂．但是，在一定的約束條件下，遺傳算法可以實(shí)現(xiàn)這一點(diǎn)．下面我們不加證明地羅列幾個(gè)定理或定義，供讀者參考（在這些定理的證明中，要用到許多概率論知識(shí)，特別是有關(guān)馬爾可夫鏈的理論，讀者可參閱有關(guān)文獻(xiàn)）．定理1 如果變異概率為，交叉概率為，同時(shí)采用比例選擇法（按個(gè)體適應(yīng)度占群體適應(yīng)度的比例進(jìn)行復(fù)制），則標(biāo)準(zhǔn)遺傳算法的變換矩陣P是基本的．定理2 標(biāo)準(zhǔn)遺傳算法（參數(shù)如定理1）不能收斂至全局最優(yōu)解．由定理2可以知道，具有變異概率，交叉概率為以及按比例選擇的標(biāo)準(zhǔn)遺傳算法是不能收斂至全局最最優(yōu)解．我們?cè)谇懊媲蠼饫?時(shí)所用的方法就是滿足定理1的條件的方法．這無疑是一個(gè)令人沮喪的結(jié)論．然而，慶幸的是，只要對(duì)標(biāo)準(zhǔn)遺傳算法作一些改進(jìn)，就能夠保證其收斂性．具體如下：我們對(duì)標(biāo)準(zhǔn)遺傳算法作一定改進(jìn)，即不按比例進(jìn)行選擇，而是保留當(dāng)前所得的最優(yōu)解（稱作超個(gè)體）．該超個(gè)體不參與遺傳．最佳個(gè)體保存方法（elitist model）的思想是把群體中適應(yīng)度最高的個(gè)體不進(jìn)行配對(duì)交叉而直接復(fù)制到下一代中．此種選擇操作又稱復(fù)制（copy）．De Jong對(duì)此方法作了如下定義：定義 設(shè)到時(shí)刻t（第t代）時(shí)，群體中a*（t）為最佳個(gè)體．又設(shè)A（t＋1）為新一代群體，若A（t＋1）中不存在a*（t），則把a(bǔ)*(t)作為A（t＋1）中的第n+1個(gè)個(gè)體（其中，n為群體大?。∕atlab程序參見附錄11）．采用此選擇方法的優(yōu)點(diǎn)是，進(jìn)化過程中某一代的最優(yōu)解可不被交叉和變異操作所破壞．但是，這也隱含了一種危機(jī)，即局部最優(yōu)個(gè)體的遺傳基因會(huì)急速增加而使進(jìn)化有可能限于局部解．也就是說，該方法的全局搜索能力差，它更適合單峰性質(zhì)的搜索空間搜索，而不是多峰性質(zhì)的空間搜索．所以此方法一般都與其他選擇方法結(jié)合使用．定理3 具有定理1所示參數(shù)，且在選擇后保留當(dāng)前最優(yōu)值的遺傳算法最終能收斂到全局最優(yōu)解．當(dāng)然，在選擇算子作用后保留當(dāng)前最優(yōu)解是一項(xiàng)比較復(fù)雜的工作，因?yàn)樵摻庠谶x擇算子作用后可能丟失．但是定理3至少表明了這種改進(jìn)的遺傳算法能夠收斂至全局最優(yōu)解．有意思的是，實(shí)際上只要在選擇前保留當(dāng)前最優(yōu)解，就可以保證收斂，定理4描述了這種情況．定理4 具有定理1參數(shù)的，且在選擇前保留當(dāng)前最優(yōu)解的遺傳算法可收斂于全局最優(yōu)解．例2：設(shè)，求 ，編碼長(zhǎng)度為5，采用上述定理4所述的“在選擇前保留當(dāng)前最優(yōu)解的遺傳算法”進(jìn)行．此略，留作練習(xí)．二、相關(guān)函數(shù)（