【正文】 gth)。global Count。x*x+2*x+39。,1,2,2,50)執(zhí)行結(jié)果為：Count = 50Result = BestMember = 圖2 例1的計算結(jié)果（注：上圖為遺傳進化過程中每一代的個體最大適應(yīng)度；而下圖為目前為止的個體最大適應(yīng)度——單調(diào)遞增）我們通過Matlab軟件實現(xiàn)了遺傳算法，得到了這題在第一種終止條件下的最優(yōu)解：，．當然這個解和實際情況還有一點出入（應(yīng)該是取1時，），但對于一個計算機算法來說已經(jīng)很不錯了．我們也可以編制Matlab程序求在第二種終止條件下的最優(yōu)解．此略，留作練習．實踐表明，此時的遺傳算法只要經(jīng)過10代左右就可完成收斂，得到另一個“最優(yōu)解”，與前面的最優(yōu)解相差無幾．四、自己動手1． ，求例1的在第二種終止條件下的最優(yōu)解．提示：一個可能的函數(shù)調(diào)用形式以及相應(yīng)的結(jié)果為：[Count,Result,BestMember]=Genetic2(22,6,39。global CurrentBest。PopulationFitnessF=FitnessF(PopulationFitness,Fmin)。MaxFitness(Count)=CurrentBest(length(CurrentBest))。 Population=NewPopulation。 PopulationFitnessF=FitnessF(PopulationFitness,Fmin)。 EachMaxFitness(Count)=EachGenMaxFitness。Result=ones(2,Dim(1))。BestMember(2,1)=CurrentBest(MumberLength+1)。PopulationFitness=zeros(1,Dim(1))。for i=1:Dim(2) PopulationData=PopulationData+PopulationCode(i)*(2^(MumberLengthi))。PopulationFitness=double(subs(FunctionFitness,39。PopulationFitnessF=zeros(1,Dim(2))。PopulationProbability=PopulationFitness/SumPopulationFitness。 Index=1。%%PopulationProbability=Probability(PopulationFitness)。if Dim(1)=3 Temp=Population(Dim(1),:)。 Site=SiteArray(1)。endNewPopulation=Population。 if ProbabilityMutationProbability if Population(i,Site(1))==1 Population(i,Site(1))=0。[MinFitness,MinSite]=min(PopulationFitness)。 CurrentBest(MumberLength+1)=PopulationFitness(MaxSite)。 endPopulation(MinSite,:)=CurrentBest(1:MumberLength)。遺傳算法(Genetic Algorithm)是這些技術(shù)中的一種，它是一類模擬生物進化過程而產(chǎn)生的由選擇算子、雜交算子和變異算子三個基本算子組成的全局尋優(yōu)算法。每個解用其“適應(yīng)值”評價。例如父代染色體為和，在第二個基因后雜交，產(chǎn)生的后代為和。 遺傳算法的特點：(1). 它不是直接作用于參變量集上，而是作用于參變量的某種編碼形成的數(shù)字串上。優(yōu)勢：(1). 不容易陷入局部極值，能以很大的概率找到全局最優(yōu)解。假設(shè)每個變量為域內(nèi)的一個值，且對所有的。這樣，對每個變量，由串長為的二進制編碼表達可以滿足精度要求。如果確實有一些關(guān)于最優(yōu)分布的知識，可以使用這些信息來設(shè)定初始潛在解的集合。4） 雜交(crossover)和變異(mutation)——決定新群體的性狀：設(shè)雜交概率為，此概率給出預計要進行雜交的染色體個數(shù)。兩個染色體 和 被他們的子代 和 所替代。隨著選擇、雜交和變異的進行，新群體就為下一次的評價做好了準備。假定對每個變量要求的精度是小數(shù)點后第4位。由于，因此染色體的第一部分需要15位。3） 根據(jù)適應(yīng)值評價解的適應(yīng)程度并據(jù)此生成新群體：現(xiàn)在系統(tǒng)為選擇過程建立一個輪盤。雜交按照下面的方法進行：對新群體中的每個染色體，產(chǎn)生一個在區(qū)間[0, 1]里的隨機數(shù)，如果，則選擇一個給定的染色體進行雜交。對這兩對中的每一對，產(chǎn)生區(qū)間[1, 32]（33為染色體總長度）里的一個隨機整數(shù)。這對染色體在第20位后的部分互換，生成的新的染色體對為：群體的當前版本為： 下一步操作——變異是在一位一位基礎(chǔ)上進行的。這說明我們必須產(chǎn)生660個隨機數(shù)。檢查一下新群體的評價過程，對每個染色體進行解碼，并計算解碼后的的適應(yīng)函數(shù)值，得到： 。例如。三、遺傳算法的理論基礎(chǔ)： 遺傳算法的理論基礎(chǔ)是遺傳算法解的二進制表達式及模式的含義。例如，考慮長度為10的串和模式。很明顯，每種模式精確地代表個串，這里為通配符(*)在模式模板中的個數(shù)。有兩個重要的模式性質(zhì)：階和定義長度。一個模式的階定義了模式的特殊性。 模式的定義長度（由表示），為第一個和最后一個固定串位之間的距離。模式的定義長度在計算模式雜交的存活概率時很有用，隨后討論。首先從運行一個例子開始來說明所有的定理。注意模式的階，其定義長度。如在先前的例子中看到的那樣，在一個單個串的選擇中，串被選擇的概率，其中為整個群體在時刻的總適應(yīng)值。如果假定模式高出平均，即，那么 ，且 ，其中，相應(yīng)于平均值之上的模式；相應(yīng)于平均值之下的模式。特別地，在時刻，預計可以得到3*= （可能有4個或5個）被模式匹配；在時刻，有3*= ，即可能有6個串，等等?？梢姡Ｊ皆跁r刻匹配5個串：、和。以下依次討論兩個算子作用于群體中模式的效果。因為雜交在一個后代串上保存了第5，6，7位上的序列“111”。注意模式的定義長度為，而模式的定義長度為。這說明一個模式的最小存活概率實際上為：再一次參考前面例子中的模式()： 注意，盡管雜交位置是在一個模式的固定位置之間選擇的，該模式仍然有機會存活。對模式：這說明短的、平均值之上的模式將在下一代中出現(xiàn)幾何增長的串數(shù)：在時刻，預測有3*= ；在時刻，將有3*= 。再一次考慮群體中的一個串，設(shè)為： ()和模式。這里只有3位（第5，6和7位，即模式的固定位）是很重要的：變異其中之一將破壞模式。很明顯，在平均值之上的、短的定義長度和低階的模式將按照幾何增長的速率被復制。復制本身并不能增加新的模式（初始時刻的復制除外）。生長公式(3)的最終結(jié)果可以用下面的定理和假設(shè)表示：定理1 模式定理(Schema Theorem)： 短的、低階、平均之上的模式在遺傳算子的后續(xù)代中將按幾何級數(shù)增長。遺傳算法在眾多問題領(lǐng)域中的應(yīng)用支持基因塊假設(shè)?？偟脑瓌t是讓適者生存，即適應(yīng)值大的串生存概率要大。剩余部分的填充方法是：把每個串對應(yīng)的的小數(shù)部分進行排隊，按從大到小的順序選擇對應(yīng)的串，直到填滿。對余下的小數(shù)部分：a. 有退還剩余隨機選擇：把的小數(shù)部分作為賭盤選擇的權(quán)，利用賭盤選擇決定取舍；b. 無退還剩余隨機選擇：把的小數(shù)部分視為概率，一個一個地進行貝努利試驗，其中小數(shù)部分作為成功概率。遺傳算法的參數(shù)空間包括：群體規(guī)模、雜交率、變異率、代間隙、選擇策略和適應(yīng)值變換等。雜交率越高，群體中的串的更新就越快，算法對解空間的搜索能力越強?！?代間隙：它被引入算法中是允許出現(xiàn)群體重疊的情形，定義在0到1之間，控制每一代群體被替換的百分率?！?適應(yīng)值變換：目的時提高算法對適應(yīng)值變化的敏感度。通俗地講就是希望放大串的適應(yīng)值的間隔，不因適應(yīng)值非常接近而無法選擇適應(yīng)值更好的串。(2) 冪比例變換冪比例變換是比例適應(yīng)值取為原適應(yīng)值的某個指定冪： ，值一般是依賴于具體問題的，在算法執(zhí)行中需要變化以滿足要求的伸縮范圍，即是代的函數(shù)。參數(shù)的值決定了選擇的側(cè)重，越小，選擇強制越趨向于那些具有最高適應(yīng)值的串，值隨著代的演化而增大?！?Davis, 1989)遺傳算法傳統(tǒng)上使用的二進制編碼當用于多維、高精度數(shù)值問題時會有一些障礙。編碼應(yīng)該具有這樣的性質(zhì)：在表達空間里相互靠近的兩個點也必須在問題空間里靠近，反之亦然。(2). “有限困難”：遺傳算法理論解釋了為什么對一個給定的問題表達，能收斂到欲求的最優(yōu)點。過早收斂問題是所有優(yōu)化算法共同的問題。參考文獻：Michalewicz, Z. (2000). 演化程序——遺傳算法和數(shù)據(jù)編碼的結(jié)合 (中譯本). 科學出版社.楊文采 (1997). 地球物理反演的理論與方法. 地質(zhì)出版社.１７０。而遺傳算法的執(zhí)行趨向于在找到最優(yōu)解之前過早地收斂。主要的原因除了上面的“編碼困難”之外，還有“有限困難”，即：理論假定迭代次數(shù)是無限的，而實際上有限制；理論上也假定群體規(guī)模是無限的，實際上也有限制。一個可能的解決途徑是采用浮點編碼，目的是使遺傳算法更接近問題空間。這本身會產(chǎn)生一個大約是101000的搜索空間。因為表達方案嚴重地限制了系統(tǒng)觀察世界的窗口。指數(shù)比例既可讓非常好的串保持較多的復制機會，同時又限制了其復制數(shù)目，以免很快控制整個群體。(1) 線性變換設(shè)原適應(yīng)函數(shù)為，比例適應(yīng)函數(shù)為，則 稱為線性比例變換。3． 適應(yīng)值變換：注意到賭盤選擇要求適應(yīng)值是正的，而目標函數(shù)不一定為正，因此需要對目標函數(shù)做變換，即：其中選取一個適當大的數(shù)。中有個個體被隨機地保留到下一代中?！?變異率：變異是增加群體多樣性的搜索算法。規(guī)模太小，群體中所含的模式太少，對基因塊采樣增長速率小，且代表性差，最終解的質(zhì)量不高；規(guī)模大的群體包含大量有廣泛代表性的基因塊，可以阻止算法過早地收斂到局部最優(yōu)解。事實上，參數(shù)設(shè)置本身也是個優(yōu)化問題。由于賭盤選擇不能保證把最好的個體保留下來，因此又提出最優(yōu)選擇：設(shè)是直到第代最好的個體，按賭盤產(chǎn)生后，若不在中，則把加入中，并隨機舍棄一個個體。按的整數(shù)部分值，分配給該串一個拷貝數(shù)。四、遺傳算法實現(xiàn)中的若干問題和討論：前面已給出了遺傳算法運行步驟的一般描述，通過一個實例具體地考察了它的運行步驟，并給出了遺傳算法的理論基礎(chǔ)。假設(shè)1 基因塊假設(shè)(Building Block Hypothesis)： 遺傳算法是通過并列短的、低階、高效模式（稱之為基因塊）來尋求接近最優(yōu)的執(zhí)行效果。另外，變異算子向群體引入了較大的變化性。 注意，公式()是基于適應(yīng)值函數(shù)返回正值的假定：當用遺傳算法優(yōu)化可能返回負值的優(yōu)化函數(shù)時，需要附加一些適應(yīng)值函數(shù)和優(yōu)化函數(shù)之間的映射。 因為單個位變異的概率為，所以單個位存活的概率為。根據(jù)前一節(jié)的結(jié)果，在第9位變異，其子代為仍然被模式匹配。其變化為從0到1或者相反。因此，模式的存活概率為 所以，選擇和雜交的結(jié)合給出了一個新的形式的復制模式生長公式： (2)公式(2)告訴我們在下一代中匹配模式