【正文】 圖2 均衡搜索的具體實(shí)現(xiàn)圖示應(yīng)該指出的是，遺傳算法雖然可以實(shí)現(xiàn)均衡的搜索，并且在許多復(fù)雜問(wèn)題的求解中往往能得到滿(mǎn)意的結(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í)所用的方法就是滿(mǎn)足定理1的條件的方法．這無(wú)疑是一個(gè)令人沮喪的結(jié)論．然而，慶幸的是，只要對(duì)標(biāo)準(zhǔn)遺傳算法作一些改進(jìn)，就能夠保證其收斂性．具體如下：我們對(duì)標(biāo)準(zhǔn)遺傳算法作一定改進(jìn)，即不按比例進(jìn)行選擇，而是保留當(dāng)前所得的最優(yōu)解（稱(chēng)作超個(gè)體）．該超個(gè)體不參與遺傳．最佳個(gè)體保存方法（elitist model）的思想是把群體中適應(yīng)度最高的個(gè)體不進(jìn)行配對(duì)交叉而直接復(fù)制到下一代中．此種選擇操作又稱(chēng)復(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程序參見(jiàn)附錄11）．采用此選擇方法的優(yōu)點(diǎn)是，進(jìn)化過(guò)程中某一代的最優(yōu)解可不被交叉和變異操作所破壞．但是，這也隱含了一種危機(jī)，即局部最優(yōu)個(gè)體的遺傳基因會(huì)急速增加而使進(jìn)化有可能限于局部解．也就是說(shuō)，該方法的全局搜索能力差，它更適合單峰性質(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ù)（命令）及簡(jiǎn)介本實(shí)驗(yàn)的程序中用到如下一些基本的Matlab函數(shù)：ones, zeros, sum, size, length, subs, double 等，以及 for, while 等基本程序結(jié)構(gòu)語(yǔ)句，讀者可參考前面專(zhuān)門(mén)關(guān)于Matlab的介紹，也可參考其他數(shù)學(xué)實(shí)驗(yàn)章節(jié)中的“相關(guān)函數(shù)（命令）及簡(jiǎn)介”內(nèi)容，此略．三、實(shí)驗(yàn)內(nèi)容上述例1的求解過(guò)程為：群體中包含六個(gè)染色體，每個(gè)染色體用22位0—1碼，變量區(qū)間為 ，取Fmin=，遺傳代數(shù)為50代，則運(yùn)用第一種終止條件（指定遺傳代數(shù)）的Matlab程序?yàn)椋篬Count,Result,BestMember]=Genetic1(22,6,39。x*x+2*x+39。,1,2,2,50)執(zhí)行結(jié)果為：Count = 50Result = BestMember = 圖2 例1的計(jì)算結(jié)果（注：上圖為遺傳進(jìn)化過(guò)程中每一代的個(gè)體最大適應(yīng)度；而下圖為目前為止的個(gè)體最大適應(yīng)度——單調(diào)遞增）我們通過(guò)Matlab軟件實(shí)現(xiàn)了遺傳算法，得到了這題在第一種終止條件下的最優(yōu)解：，．當(dāng)然這個(gè)解和實(shí)際情況還有一點(diǎn)出入（應(yīng)該是取1時(shí)，），但對(duì)于一個(gè)計(jì)算機(jī)算法來(lái)說(shuō)已經(jīng)很不錯(cuò)了．我們也可以編制Matlab程序求在第二種終止條件下的最優(yōu)解．此略，留作練習(xí)．實(shí)踐表明，此時(shí)的遺傳算法只要經(jīng)過(guò)10代左右就可完成收斂，得到另一個(gè)“最優(yōu)解”，與前面的最優(yōu)解相差無(wú)幾．四、自己動(dòng)手1． ，求例1的在第二種終止條件下的最優(yōu)解．提示：一個(gè)可能的函數(shù)調(diào)用形式以及相應(yīng)的結(jié)果為：[Count,Result,BestMember]=Genetic2(22,6,39。x*x+2*x+39。,1,2,2,)Count = 13Result = BestMember = 可以看到：兩組解都已經(jīng)很接近實(shí)際結(jié)果，對(duì)于兩種方法所產(chǎn)生的最優(yōu)解差異很?。梢?jiàn)這兩種終止算法都是可行的，而且可以知道對(duì)于例1的問(wèn)題，遺傳算法只要經(jīng)過(guò)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子程序 ，使得交叉過(guò)程也有一個(gè)概率值（~）；，以便代入交叉概率．6． 設(shè)，求 ，要設(shè)定求解精度到15位小數(shù)．五、附錄附錄1：function [Count,Result,BestMember]=Genetic1(MumberLength,MemberNumber,FunctionFitness,MinX,MaxX,Fmin,MutationProbability,Gen)Population=PopulationInitialize(MumberLength,MemberNumber)。global Count。global CurrentBest。Count=1。PopulationCode=Population。PopulationFitness=Fitness(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength)。PopulationFitnessF=FitnessF(PopulationFitness,Fmin)。PopulationProbability=Probability(PopulationFitnessF)。[Population,CurrentBest,EachGenMaxFitness]=Elitist(PopulationCode,PopulationFitness,MumberLength)。EachMaxFitness(Count)=EachGenMaxFitness。MaxFitness(Count)=CurrentBest(length(CurrentBest))。while CountGen NewPopulation=Select(Population,PopulationProbability,MemberNumber)。 Population=NewPopulation。 NewPopulation=Crossing(Population,FunctionFitness,MinX,MaxX,MumberLength)。 Population=NewPopulation。 NewPopulation=Mutation(Population,MutationProbability)。 Population=NewPopulation。 PopulationFitness=Fitness(Population,FunctionFitness,MinX,MaxX,MumberLength)。 PopulationFitnessF=FitnessF(PopulationFitness,Fmin)。 PopulationProbability=Probability(PopulationFitnessF)。 Count=Count+1。 [NewPopulation,CurrentBest,EachGenMaxFitness]=Elitist(Population,PopulationFitness,MumberLength)。 EachMaxFitness(Count)=EachGenMaxFitness。 MaxFitness(Count)=CurrentBest(length(CurrentBest))。 Population=NewPopulation。endDim=size(Population)。Result=ones(2,Dim(1))。for i=1:Dim(1) Result(1,i)=Translate(Population(i,:),MinX,MaxX,MumberLength)。endResult(2,:)=PopulationFitness。BestMember(1,1)=Translate(CurrentBest(1:MumberLength),MinX,MaxX,MumberLength)。BestMember(2,1)=CurrentBest(MumberLength+1)。close allsubplot(211)plot(EachMaxFitness)subplot(212)plot(MaxFitness)【程序說(shuō)明】：(1) MumberLength： 表示一個(gè)染色體位串的二進(jìn)制長(zhǎng)度．（例1中取22）(2) MemberNumber： 表示群體中染色體的個(gè)數(shù)．（例1中取6個(gè)）(3) FunctionFitness： 表示目標(biāo)函數(shù)，是個(gè)字符串，因此用表達(dá)式時(shí)，用單引號(hào)括出．（例1中是）(4) MinX： 變量區(qū)間的下限．（例1中是中的）(5) MaxX： 變量區(qū)間的上限．（例1中是中的 2）(6) Fmin： 定義適應(yīng)函數(shù)過(guò)程中給出的一個(gè)目標(biāo)函數(shù)的可能的最小值，由操作者自己給出．（例1中取Fmin=）(7) MutationProbability： 表示變異的概率，一般都很小．（）(8) Gen： 表示遺傳的代數(shù)，也就是終止程序時(shí)的代數(shù)．（例1中取50）另外，： Count 表示遺傳的代數(shù)；Result 表示計(jì)算的結(jié)果，也就是最優(yōu)解；BestMember表示最優(yōu)個(gè)體及其適應(yīng)值．附錄2：子程序 function Population=PopulationInitialize(MumberLength,MemberNumber)Temporary=rand(MemberNumber,MumberLength)。Population=(Temporary=*ones(size(Temporary)))?！境绦蛘f(shuō)明】子程序 ．這個(gè)初始群體含有MemberNumber個(gè)染色體，每個(gè)染色體有MumberLength個(gè)基因（二進(jìn)制碼）．附錄3：function PopulationFitness=Fitness(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength)Dim=size(PopulationCode)。PopulationFitness=zeros(1,Dim(1))。for i=1:Dim(1)PopulationFitness(i)=Transfer(PopulationCode(i,:),FunctionFitness,