數學建模遺傳算法與優化問題-資料下載頁

　　

【正文】 為： 模式的適應值與群體平均適應值的比例為： 這就意味著如果模式保持在平均之上，那么它將在下一代中保持串數的幾何增長。特別地，在時刻，預計可以得到3*= （可能有4個或5個）被模式匹配；在時刻，有3*= ，即可能有6個串，等等。根據直覺，的模式定義了搜索空間中極有希望的一部分，并且它以幾何增長的方式被復制。可以用以前的實例檢驗對的預測。在時刻，新的群體見P5下方的。可見，模式在時刻匹配5個串：、和。 然而，選擇本身不能產生新的潛在解，只能從中間群體中復制一些串。所以在進化周期的第二步（重組）中向群體中引入了新個體。這是通過雜交和變異兩個算子完成的。以下依次討論兩個算子作用于群體中模式的效果。2． 雜交：考慮下面的例子：如在前面討論的，群體中一個單獨個體的串，設為：被233種模式匹配；該串同時被下面兩個模式匹配： 進一步假定上述串被選擇用來雜交。根據上一節的例子（個體和被選擇進行雜交），假定雜交位置為。很明顯，模式生存下來，即有一個后代仍然匹配。因為雜交在一個后代串上保存了第5，6，7位上的序列“111”。雜交前 雜交后 另一方面，模式遭破壞：子代不與它匹配。因為在模板開始的固定位“111”和結尾的固定位“10”分布在不同的子代上。 很明顯，模式的定義長度對其生存和損壞的概率起著很重要的作用。注意模式的定義長度為，而模式的定義長度為。 通常，雜交位是在中可能的位置上被唯一地選擇的。這就意味著模式的最大消亡概率為 因此，該模式的最小存活概率為實際上，我們的例子中的模式和的存活概率和消亡概率分別為：， ， 所以結果是可以預測的。注意實際上只有一些染色體經歷雜交，并且雜交的選擇性概率為。這說明一個模式的最小存活概率實際上為：再一次參考前面例子中的模式()： 注意，盡管雜交位置是在一個模式的固定位置之間選擇的，該模式仍然有機會存活。例如，如果串和都是以“111”開始，“10”結尾，模式將雜交存活，當然，這種可能性非常小。因此，模式的存活概率為 所以，選擇和雜交的結合給出了一個新的形式的復制模式生長公式： (2)公式(2)告訴我們在下一代中匹配模式的預測串數是實際匹配模式串數、模式的相對適應值及模式的定義長度的函數。顯然，在平均之上，短的定義長度的模式將按照幾何增長的速率被復制。對模式：這說明短的、平均值之上的模式將在下一代中出現幾何增長的串數：在時刻，預測有3*= ；在時刻，將有3*= 。3． 變異：變異算子以概率隨機地改變一個染色體中的某一位。其變化為從0到1或者相反。很明顯，如果模式經過變異還存活，該模式上的所有固定位應保持不變。再一次考慮群體中的一個串，設為： ()和模式。進一步假定串經歷變異，即至少有一位發生變異。根據前一節的結果，在第9位變異，其子代為仍然被模式匹配。如果被選擇變異的位置是從1到4，或者8到33，那么所生成的子代仍然被模式匹配。這里只有3位（第5，6和7位，即模式的固定位）是很重要的：變異其中之一將破壞模式。很明顯，這些重要位的數目等于模式的階，即固定位的數目。 因為單個位變異的概率為，所以單個位存活的概率為。單個變異是和其它變異相互獨立的，所以模式經過單點變異后的存活概率為由于，所以此概率可以被近似為再一次參考例子中的模式(): 選擇、雜交和變異的組合給出了復制生長公式的新形式： (3) 正如簡單公式(1)和(2)，公式(3)告訴我們在下一代中，預測匹配模式的串數是匹配模式的實際串數、模式的相對適應值和定義長度以及階的函數。很明顯，在平均值之上的、短的定義長度和低階的模式將按照幾何增長的速率被復制。 對模式：這就意味著短的、低階、平均之上的模式將在下一代中產生幾何增長的串數：在時刻預計有3*=（——只考慮選擇的結果，——值考慮選擇和雜交的結果），在時刻，有3*=（）。 注意，公式()是基于適應值函數返回正值的假定：當用遺傳算法優化可能返回負值的優化函數時，需要附加一些適應值函數和優化函數之間的映射。 概括起來，生長公式(1)顯示：選擇增加了平均之上的模式的復制率，并且這種變化是指數型的。復制本身并不能增加新的模式（初始時刻的復制除外）。這就是為什么要引入雜交算子的原因——能以結構化的方式隨機地交換信息。另外，變異算子向群體引入了較大的變化性。如果一個模式是短的且低階的，這些算子作用在該模式上的組合分裂效果是不大的。生長公式(3)的最終結果可以用下面的定理和假設表示：定理1 模式定理(Schema Theorem)： 短的、低階、平均之上的模式在遺傳算子的后續代中將按幾何級數增長。這一定理的直接結果是：遺傳算法通過短的、低階模式的雜交信息交換過程探求了搜索空間。假設1 基因塊假設(Building Block Hypothesis)： 遺傳算法是通過并列短的、低階、高效模式（稱之為基因塊）來尋求接近最優的執行效果。雖然已有一些研究來證明此假設，但是多數重要的應用還是依賴于實驗結果。遺傳算法在眾多問題領域中的應用支持基因塊假設。毫無疑問，基因塊假設說明遺傳算法的編碼問題對其執行效果來說是至關重要的，并且這種編碼應該符合短基因塊的思想。四、遺傳算法實現中的若干問題和討論：前面已給出了遺傳算法運行步驟的一般描述，通過一個實例具體地考察了它的運行步驟，并給出了遺傳算法的理論基礎。在具體實現過程中，仍有一些問題值得重視：1． 選擇策略：選擇策略是指復制算子按照什么方式進行操作。總的原則是讓適者生存，即適應值大的串生存概率要大。常用的選擇方法有以下幾種：(1). 確定性選擇方法：對群體中每個串計算生存概率（其中為總適應值），從而得到的期望拷貝數。按的整數部分值，分配給該串一個拷貝數。顯然，總的拷貝數小于。剩余部分的填充方法是：把每個串對應的的小數部分進行排隊，按從大到小的順序選擇對應的串，直到填滿。(2). 賭盤選擇方法：即前面采用的方法，此處不在贅述。由于賭盤選擇不能保證把最好的個體保留下來，因此又提出最優選擇：設是直到第代最好的個體，按賭盤產生后，若不在中，則把加入中，并隨機舍棄一個個體。(3). 有退還和無退還剩余隨機選擇：首先計算期望拷貝數，整數部分決定拷貝數。對余下的小數部分：a. 有退還剩余隨機選擇：把的小數部分作為賭盤選擇的權，利用賭盤選擇決定取舍；b. 無退還剩余隨機選擇：把的小數部分視為概率，一個一個地進行貝努利試驗，其中小數部分作為成功概率。2． 控制參數的選擇：在使用遺傳算法時，首先要給定一組控制參數，如群體規模，雜交率和變異率等，控制參數的不同選擇會對遺傳算法的性能產生很大的影響，要想發掘執行的最優性能，必須確定最優的參數設置。事實上，參數設置本身也是個優化問題。這里僅討論一些原則。遺傳算法的參數空間包括：群體規模、雜交率、變異率、代間隙、選擇策略和適應值變換等。● 群體規模：它影響到遺傳算法的最終性能和效率。規模太小，群體中所含的模式太少，對基因塊采樣增長速率小，且代表性差，最終解的質量不高；規模大的群體包含大量有廣泛代表性的基因塊，可以阻止算法過早地收斂到局部最優解。然而群體規模越大，每一代所需要的計算量就越大，這會導致收斂過程太慢；● 雜交率：雜交率控制雜交算子的應用頻率。雜交率越高，群體中的串的更新就越快，算法對解空間的搜索能力越強。若雜交率過高，高性能的串被破壞的速度也加快了；若雜交率過低，算法搜索解空間的能力下降，有蛻變成局部隨機搜索算法的危險。● 變異率：變異是增加群體多樣性的搜索算法。一個低水平的變異率足以防止整個群體中任一給定位保持永遠收斂于單一的值；高水平的變異率產生的實際上是隨機搜索。● 代間隙：它被引入算法中是允許出現群體重疊的情形，定義在0到1之間，控制每一代群體被替換的百分率。時，表示全部替換；時，表示部分替換。中有個個體被隨機地保留到下一代中。● 選擇策略：前面已經討論過，用的較多的是賭盤選擇。● 適應值變換：目的時提高算法對適應值變化的敏感度。因為適應值是算法唯一利用的信息，對適應值變化是否敏感是很重要的。3． 適應值變換：注意到賭盤選擇要求適應值是正的，而目標函數不一定為正，因此需要對目標函數做變換，即：其中選取一個適當大的數。 進行適應值比例變換的目的是調節遺傳算法執行過程中串的復制數目，以提高算法的性能。通俗地講就是希望放大串的適應值的間隔，不因適應值非常接近而無法選擇適應值更好的串。另外，還可壓制某些適應值非常大的串控制選擇過程。(1) 線性變換設原適應函數為，比例適應函數為，則 稱為線性比例變換。系數和的選擇必須滿足以下兩個條件：1. 平均比例適應值等于原平均適應值；2. 最大的比例適應值是平均適應值的指定倍數，即，一般取2，這兩個條件保證平均群體個體最好的個體的期望復制數分別為1和。(2) 冪比例變換冪比例變換是比例適應值取為原適應值的某個指定冪： ，值一般是依賴于具體問題的，在算法執行中需要變化以滿足要求的伸縮范圍，即是代的函數。(3) 指數比例變換指數比例滿足關系式：。指數比例既可讓非常好的串保持較多的復制機會，同時又限制了其復制數目，以免很快控制整個群體。同時對于適應值相近的串也提高了競爭性。參數的值決定了選擇的側重，越小，選擇強制越趨向于那些具有最高適應值的串，值隨著代的演化而增大。4． 遺傳算法的困難：(1). “編碼困難”：“表達是遺傳算法的主要問題。因為表達方案嚴重地限制了系統觀察世界的窗口。”(Koza, 1990)“在我看來有時確實如此，我們不能用二進制表達和只由二進制雜交和二進制變異組成的算子集來處理多數真實世界的問題。”(Davis, 1989)遺傳算法傳統上使用的二進制編碼當用于多維、高精度數值問題時會有一些障礙。例如，對于一個有100個變量、域區間[500, 500]、精度要求精確到小數點后第6位的問題，二進制解向量的長度是3000。這本身會產生一個大約是101000的搜索空間。對這樣的問題，遺傳算法執行得很不好。編碼應該具有這樣的性質：在表達空間里相互靠近的兩個點也必須在問題空間里靠近，反之亦然。而二進制方法并不總是這樣。一個可能的解決途徑是采用浮點編碼，目的是使遺傳算法更接近問題空間。通過利用真實空間的一些特征，這樣的移近強制算子更與問題的特殊性有關。(2). “有限困難”：遺傳算法理論解釋了為什么對一個給定的問題表達，能收斂到欲求的最優點。但不幸的是，實際的應用并不總遵循這一理論。主要的原因除了上面的“編碼困難”之外，還有“有限困難”，即：理論假定迭代次數是無限的，而實際上有限制；理論上也假定群體規模是無限的，實際上也有限制。這說明遺傳算法在某種條件下不能找到最優解：這種失敗是由于過早地收斂到局部最優造成的。過早收斂問題是所有優化算法共同的問題。如果收斂發生的太快，包含在群體中的有價值的信息常常會失去。而遺傳算法的執行趨向于在找到最優解之前過早地收斂。有一些避免過早收斂的策略，比如：(1) 配對策略(mating strategy)，又稱為近親預防(incest prevention)； (2) 使用均勻雜交(uniform crossover)；(3). 檢測群體中的重復串。參考文獻：Michalewicz, Z. (2000). 演化程序——遺傳算法和數據編碼的結合 (中譯本). 科學出版社.楊文采 (1997). 地球物理反演的理論與方法. 地質出版社.１７０