【正文】 遺傳算法實(shí)現(xiàn)中的若干問題和討論：前面已給出了遺傳算法運(yùn)行步驟的一般描述，通過一個(gè)實(shí)例具體地考察了它的運(yùn)行步驟，并給出了遺傳算法的理論基礎(chǔ)。由于賭盤選擇不能保證把最好的個(gè)體保留下來，因此又提出最優(yōu)選擇：設(shè)是直到第代最好的個(gè)體，按賭盤產(chǎn)生后，若不在中，則把加入中，并隨機(jī)舍棄一個(gè)個(gè)體。規(guī)模太小，群體中所含的模式太少，對(duì)基因塊采樣增長速率小，且代表性差，最終解的質(zhì)量不高；規(guī)模大的群體包含大量有廣泛代表性的基因塊，可以阻止算法過早地收斂到局部最優(yōu)解。中有個(gè)個(gè)體被隨機(jī)地保留到下一代中。(1) 線性變換設(shè)原適應(yīng)函數(shù)為，比例適應(yīng)函數(shù)為，則 稱為線性比例變換。因?yàn)楸磉_(dá)方案嚴(yán)重地限制了系統(tǒng)觀察世界的窗口。一個(gè)可能的解決途徑是采用浮點(diǎn)編碼，目的是使遺傳算法更接近問題空間。而遺傳算法的執(zhí)行趨向于在找到最優(yōu)解之前過早地收斂。過早收斂問題是所有優(yōu)化算法共同的問題。編碼應(yīng)該具有這樣的性質(zhì)：在表達(dá)空間里相互靠近的兩個(gè)點(diǎn)也必須在問題空間里靠近，反之亦然。參數(shù)的值決定了選擇的側(cè)重，越小，選擇強(qiáng)制越趨向于那些具有最高適應(yīng)值的串，值隨著代的演化而增大。通俗地講就是希望放大串的適應(yīng)值的間隔，不因適應(yīng)值非常接近而無法選擇適應(yīng)值更好的串?！?代間隙：它被引入算法中是允許出現(xiàn)群體重疊的情形，定義在0到1之間，控制每一代群體被替換的百分率。遺傳算法的參數(shù)空間包括：群體規(guī)模、雜交率、變異率、代間隙、選擇策略和適應(yīng)值變換等。剩余部分的填充方法是：把每個(gè)串對(duì)應(yīng)的的小數(shù)部分進(jìn)行排隊(duì)，按從大到小的順序選擇對(duì)應(yīng)的串，直到填滿。遺傳算法在眾多問題領(lǐng)域中的應(yīng)用支持基因塊假設(shè)。復(fù)制本身并不能增加新的模式（初始時(shí)刻的復(fù)制除外）。這里只有3位（第5，6和7位，即模式的固定位）是很重要的：變異其中之一將破壞模式。對(duì)模式：這說明短的、平均值之上的模式將在下一代中出現(xiàn)幾何增長的串?dāng)?shù)：在時(shí)刻，預(yù)測(cè)有3*= ；在時(shí)刻，將有3*= 。注意模式的定義長度為，而模式的定義長度為。以下依次討論兩個(gè)算子作用于群體中模式的效果。特別地，在時(shí)刻，預(yù)計(jì)可以得到3*= （可能有4個(gè)或5個(gè)）被模式匹配；在時(shí)刻，有3*= ，即可能有6個(gè)串，等等。如在先前的例子中看到的那樣，在一個(gè)單個(gè)串的選擇中，串被選擇的概率，其中為整個(gè)群體在時(shí)刻的總適應(yīng)值。首先從運(yùn)行一個(gè)例子開始來說明所有的定理。 模式的定義長度（由表示），為第一個(gè)和最后一個(gè)固定串位之間的距離。有兩個(gè)重要的模式性質(zhì)：階和定義長度。例如，考慮長度為10的串和模式。例如。這說明我們必須產(chǎn)生660個(gè)隨機(jī)數(shù)。對(duì)這兩對(duì)中的每一對(duì)，產(chǎn)生區(qū)間[1, 32]（33為染色體總長度）里的一個(gè)隨機(jī)整數(shù)。3） 根據(jù)適應(yīng)值評(píng)價(jià)解的適應(yīng)程度并據(jù)此生成新群體：現(xiàn)在系統(tǒng)為選擇過程建立一個(gè)輪盤。假定對(duì)每個(gè)變量要求的精度是小數(shù)點(diǎn)后第4位。兩個(gè)染色體 和 被他們的子代 和 所替代。如果確實(shí)有一些關(guān)于最優(yōu)分布的知識(shí)，可以使用這些信息來設(shè)定初始潛在解的集合。假設(shè)每個(gè)變量為域內(nèi)的一個(gè)值，且對(duì)所有的。 遺傳算法的特點(diǎn)：(1). 它不是直接作用于參變量集上，而是作用于參變量的某種編碼形成的數(shù)字串上。每個(gè)解用其“適應(yīng)值”評(píng)價(jià)。 endPopulation(MinSite,:)=CurrentBest(1:MumberLength)。[MinFitness,MinSite]=min(PopulationFitness)。endNewPopulation=Population。if Dim(1)=3 Temp=Population(Dim(1),:)。 Index=1。PopulationFitnessF=zeros(1,Dim(2))。for i=1:Dim(2) PopulationData=PopulationData+PopulationCode(i)*(2^(MumberLengthi))。BestMember(2,1)=CurrentBest(MumberLength+1)。 EachMaxFitness(Count)=EachGenMaxFitness。 Population=NewPopulation。PopulationFitnessF=FitnessF(PopulationFitness,Fmin)。,1,2,2,50)執(zhí)行結(jié)果為：Count = 50Result = BestMember = 圖2 例1的計(jì)算結(jié)果（注：上圖為遺傳進(jìn)化過程中每一代的個(gè)體最大適應(yīng)度；而下圖為目前為止的個(gè)體最大適應(yīng)度——單調(diào)遞增）我們通過Matlab軟件實(shí)現(xiàn)了遺傳算法，得到了這題在第一種終止條件下的最優(yōu)解：，．當(dāng)然這個(gè)解和實(shí)際情況還有一點(diǎn)出入（應(yīng)該是取1時(shí)，），但對(duì)于一個(gè)計(jì)算機(jī)算法來說已經(jīng)很不錯(cuò)了．我們也可以編制Matlab程序求在第二種終止條件下的最優(yōu)解．此略，留作練習(xí)．實(shí)踐表明，此時(shí)的遺傳算法只要經(jīng)過10代左右就可完成收斂，得到另一個(gè)“最優(yōu)解”，與前面的最優(yōu)解相差無幾．四、自己動(dòng)手1． ，求例1的在第二種終止條件下的最優(yōu)解．提示：一個(gè)可能的函數(shù)調(diào)用形式以及相應(yīng)的結(jié)果為：[Count,Result,BestMember]=Genetic2(22,6,39。global Count。EachMaxFitness(Count)=EachGenMaxFitness。 PopulationFitness=Fitness(Population,FunctionFitness,MinX,MaxX,MumberLength)。endDim=size(Population)?！境绦蛘f明】子程序 ．這個(gè)初始群體含有MemberNumber個(gè)染色體，每個(gè)染色體有MumberLength個(gè)基因（二進(jìn)制碼）．附錄3：function PopulationFitness=Fitness(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength)Dim=size(PopulationCode)。PopulationData=Translate(PopulationCode,MinX,MaxX,MumberLength)。endend【程序說明】．其輸入?yún)?shù)如下：PopulationFitness 為群體中染色體的目標(biāo)函數(shù)值，F(xiàn)min為定義適應(yīng)函數(shù)過程中給出的一個(gè)目標(biāo)函數(shù)的可能的最小值．附錄7：子程序 function PopulationProbability=Probability(PopulationFitness)SumPopulationFitness=sum(PopulationFitness)。end【程序說明】子程序 根據(jù)入選概率（計(jì)算累計(jì)概率）在群體中按比例選擇部分染色體組成種群，該子程序的3個(gè)輸入?yún)?shù)分別為：群體Population，入選概率PopulationProbability，群體中染色體的個(gè)數(shù)MemberNumber．附錄9：子程序 function NewPopulation=Crossing(Population,FunctionFitness,MinX,MaxX,MumberLength)%%PopulationFitness=%% Fitness(Population,FunctionFitness,MinX,MaxX,MumberLength)。endfor i=1:2:Dim(1)1 SiteArray=randperm(Dim(2))。 Site=randperm(Dim(2))。if Count==1 CurrentBest(1:MumberLength)=Population(MaxSite,:)。對(duì)于小空間，經(jīng)典的窮舉法就足夠了；而對(duì)大空間，則需要使用特殊的人工智能技術(shù)。雜交組合了兩個(gè)親體染色體（即待求參數(shù)的二進(jìn)制編碼串）的特征，通過交換父代相應(yīng)的片斷形成了兩個(gè)相似的后代。(4). 它利用概率轉(zhuǎn)移規(guī)則，而非確定性規(guī)則。用表示使成立的最小整數(shù)。這樣做的效果是：好的染色體得到多個(gè)拷貝，中等染色體保持平穩(wěn)，最差染色體死亡。整個(gè)群體中所有染色體的每一位都有均等的機(jī)會(huì)經(jīng)歷變異，即從0到1或者相反：● 產(chǎn)生一個(gè)在區(qū)間[0，1]里的隨機(jī)數(shù)；● 如果，變異此位。，所要求的精度意味著區(qū)間[, ]10000個(gè)等距區(qū)間。最后，新群體由以下染色體組成：4） 雜交(crossover)和變異(mutation)——決定新群體的性狀：設(shè)雜交概率，所以預(yù)計(jì)染色體中平均有25%（即20個(gè)中的5個(gè)）將經(jīng)歷雜交。這對(duì)染色體在第9位后的部分互換，生成新的一對(duì)染色體：第二對(duì)染色體是：產(chǎn)生的數(shù)為。對(duì)修正的染色體去掉撇號(hào)，最新的染色體群體如下： 這里只完成了圖1中的遺傳過程while循環(huán)中的一次迭代（即一代）。在遺傳算法的實(shí)現(xiàn)中，通常在一獨(dú)立出來的位置保存“曾經(jīng)最好”的個(gè)體；用這種方法，算法將報(bào)告整個(gè)過程的最好值，而不只是最終群體的最好值。顯然，模式(1001110001)只代表一個(gè)串，而模式(**********)代表所有長度為10的串。換句話說，它是模板長度減去通配符(*)的數(shù)目。注意，只有單個(gè)固定點(diǎn)的模式的定義長度為零。表示時(shí)刻時(shí)群體中匹配模式的串?dāng)?shù)，如對(duì)于一個(gè)給定模式：，因?yàn)橛?個(gè)串，和匹配模式。 上述規(guī)則的長期效果是明顯的。在時(shí)刻，新的群體見P5下方的。很明顯，模式生存下來，即有一個(gè)后代仍然匹配。注意實(shí)際上只有一些染色體經(jīng)歷雜交，并且雜交的選擇性概率為。很明顯，如果模式經(jīng)過變異還存活，該模式上的所有固定位應(yīng)保持不變。單個(gè)變異是和其它變異相互獨(dú)立的，所以模式經(jīng)過單點(diǎn)變異后的存活概率為由于，所以此概率可以被近似為再一次參考例子中的模式(): 選擇、雜交和變異的組合給出了復(fù)制生長公式的新形式： (3) 正如簡單公式(1)和(2)，公式(3)告訴我們?cè)谙乱淮?，預(yù)測(cè)匹配模式的串?dāng)?shù)是匹配模式的實(shí)際串?dāng)?shù)、模式的相對(duì)適應(yīng)值和定義長度以及階的函數(shù)。如果一個(gè)模式是短的且低階的，這些算子作用在該模式上的組合分裂效果是不大的。在具體實(shí)現(xiàn)過程中，仍有一些問題值得重視：1． 選擇策略：選擇策略是指復(fù)制算子按照什么方式進(jìn)行操作。(3). 有退還和無退還剩余隨機(jī)選擇：首先計(jì)算期望拷貝數(shù)，整數(shù)部分決定拷貝數(shù)。然而群體規(guī)模越大，每一代所需要的計(jì)算量就越大，這會(huì)導(dǎo)致收斂過程太慢；● 雜交率：雜交率控制雜交算子的應(yīng)用頻率?！?選擇策略：前面已經(jīng)討論過，用的較多的是賭盤選擇。系數(shù)和的選擇必須滿足以下兩個(gè)條件：1. 平均比例適應(yīng)值等于原平均適應(yīng)值；2. 最大的比例適應(yīng)值是平均適應(yīng)值的指定倍數(shù)，即，一般取2，這兩個(gè)條件保證平均群體個(gè)體最好的個(gè)體的期望復(fù)制數(shù)分別為1和?！?Koza, 1990)“在我看來有時(shí)確實(shí)如此，我們不能用二進(jìn)制表達(dá)和只由二進(jìn)制雜交和二進(jìn)制變異組成的算子集來處理多數(shù)真實(shí)世界的問題。通過利用真實(shí)空間的一些特征，這樣的移近強(qiáng)制算子更與問題的特殊性有關(guān)。有一些避免過早收斂的策略，比如：(1) 配對(duì)策略(mating strategy)，又稱為近親預(yù)防(incest prevention)； (2) 使用均勻雜交(uniform crossover)；(3). 檢測(cè)群體中的重復(fù)串。這說明遺傳算法在某種條件下不能找到最優(yōu)解：這種失敗是由于過早地收斂到局部最優(yōu)造成的。對(duì)這樣的問題，遺傳算法執(zhí)行得很不好。同時(shí)對(duì)于適