數學建模遺傳算法與優化問題-文庫吧

【正文】 圖2 均衡搜索的具體實現圖示應該指出的是，遺傳算法雖然可以實現均衡的搜索，并且在許多復雜問題的求解中往往能得到滿意的結果，但是該算法的全局優化收斂性的理論分析尚待解決．目前普遍認為，標準遺傳算法并不保證全局最優收斂．但是，在一定的約束條件下，遺傳算法可以實現這一點．下面我們不加證明地羅列幾個定理或定義，供讀者參考（在這些定理的證明中，要用到許多概率論知識，特別是有關馬爾可夫鏈的理論，讀者可參閱有關文獻）．定理1 如果變異概率為，交叉概率為，同時采用比例選擇法（按個體適應度占群體適應度的比例進行復制），則標準遺傳算法的變換矩陣P是基本的．定理2 標準遺傳算法（參數如定理1）不能收斂至全局最優解．由定理2可以知道，具有變異概率，交叉概率為以及按比例選擇的標準遺傳算法是不能收斂至全局最最優解．我們在前面求解例1時所用的方法就是滿足定理1的條件的方法．這無疑是一個令人沮喪的結論．然而，慶幸的是，只要對標準遺傳算法作一些改進，就能夠保證其收斂性．具體如下：我們對標準遺傳算法作一定改進，即不按比例進行選擇，而是保留當前所得的最優解（稱作超個體）．該超個體不參與遺傳．最佳個體保存方法（elitist model）的思想是把群體中適應度最高的個體不進行配對交叉而直接復制到下一代中．此種選擇操作又稱復制（copy）．De Jong對此方法作了如下定義：定義 設到時刻t（第t代）時，群體中a*（t）為最佳個體．又設A（t＋1）為新一代群體，若A（t＋1）中不存在a*（t），則把a*(t)作為A（t＋1）中的第n+1個個體（其中，n為群體大?。∕atlab程序參見附錄11）．采用此選擇方法的優點是，進化過程中某一代的最優解可不被交叉和變異操作所破壞．但是，這也隱含了一種危機，即局部最優個體的遺傳基因會急速增加而使進化有可能限于局部解．也就是說，該方法的全局搜索能力差，它更適合單峰性質的搜索空間搜索，而不是多峰性質的空間搜索．所以此方法一般都與其他選擇方法結合使用．定理3 具有定理1所示參數，且在選擇后保留當前最優值的遺傳算法最終能收斂到全局最優解．當然，在選擇算子作用后保留當前最優解是一項比較復雜的工作，因為該解在選擇算子作用后可能丟失．但是定理3至少表明了這種改進的遺傳算法能夠收斂至全局最優解．有意思的是，實際上只要在選擇前保留當前最優解，就可以保證收斂，定理4描述了這種情況．定理4 具有定理1參數的，且在選擇前保留當前最優解的遺傳算法可收斂于全局最優解．例2：設，求 ，編碼長度為5，采用上述定理4所述的“在選擇前保留當前最優解的遺傳算法”進行．此略，留作練習．二、相關函數（命令）及簡介本實驗的程序中用到如下一些基本的Matlab函數：ones, zeros, sum, size, length, subs, double 等，以及 for, while 等基本程序結構語句，讀者可參考前面專門關于Matlab的介紹，也可參考其他數學實驗章節中的“相關函數（命令）及簡介”內容，此略．三、實驗內容上述例1的求解過程為：群體中包含六個染色體，每個染色體用22位0—1碼，變量區間為 ，取Fmin=，遺傳代數為50代，則運用第一種終止條件（指定遺傳代數）的Matlab程序為：[Count,Result,BestMember]=Genetic1(22,6,39。x*x+2*x+39。,1,2,2,50)執行結果為：Count = 50Result = BestMember = 圖2 例1的計算結果（注：上圖為遺傳進化過程中每一代的個體最大適應度；而下圖為目前為止的個體最大適應度——單調遞增）我們通過Matlab軟件實現了遺傳算法，得到了這題在第一種終止條件下的最優解：，．當然這個解和實際情況還有一點出入（應該是取1時，），但對于一個計算機算法來說已經很不錯了．我們也可以編制Matlab程序求在第二種終止條件下的最優解．此略，留作練習．實踐表明，此時的遺傳算法只要經過10代左右就可完成收斂，得到另一個“最優解”，與前面的最優解相差無幾．四、自己動手1． ，求例1的在第二種終止條件下的最優解．提示：一個可能的函數調用形式以及相應的結果為：[Count,Result,BestMember]=Genetic2(22,6,39。x*x+2*x+39。,1,2,2,)Count = 13Result = BestMember = 可以看到：兩組解都已經很接近實際結果，對于兩種方法所產生的最優解差異很?。梢娺@兩種終止算法都是可行的，而且可以知道對于例1的問題，遺傳算法只要經過10代左右就可以完成收斂，達到一個最優解．2． 按照例2的具體要求，用遺傳算法求上述例2的最優解．3． 附錄9子程序 ．若去掉前面的%號，則程序的算法思想有什么變化？4． 附錄9子程序 ，當Dim(1)=3時，將交換數組Population的最后兩行，即交換最后面的兩個個體．其目的是什么？5． ，修改附錄9子程序 ，使得交叉過程也有一個概率值（~）；，以便代入交叉概率．6． 設，求 ，要設定求解精度到15位小數．五、附錄附錄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)【程序說明】：(1) MumberLength： 表示一個染色體位串的二進制長度．（例1中取22）(2) MemberNumber： 表示群體中染色體的個數．（例1中取6個）(3) FunctionFitness： 表示目標函數，是個字符串，因此用表達式時，用單引號括出．（例1中是）(4) MinX： 變量區間的下限．（例1中是中的）(5) MaxX： 變量區間的上限．（例1中是中的 2）(6) Fmin： 定義適應函數過程中給出的一個目標函數的可能的最小值，由操作者自己給出．（例1中取Fmin=）(7) MutationProbability： 表示變異的概率，一般都很小．（）(8) Gen： 表示遺傳的代數，也就是終止程序時的代數．（例1中取50）另外，： Count 表示遺傳的代數；Result 表示計算的結果，也就是最優解；BestMember表示最優個體及其適應值．附錄2：子程序 function Population=PopulationInitialize(MumberLength,MemberNumber)Temporary=rand(MemberNumber,MumberLength)。Population=(Temporary=*ones(size(Temporary)))?！境绦蛘f明】子程序 ．這個初始群體含有MemberNumber個染色體，每個染色體有MumberLength個基因（二進制碼）．附錄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,