【正文】 參考文獻：Michalewicz, Z. (2000). 演化程序——遺傳算法和數(shù)據(jù)編碼的結合 (中譯本). 科學出版社.楊文采 (1997). 地球物理反演的理論與方法. 地質出版社.１７０。而遺傳算法的執(zhí)行趨向于在找到最優(yōu)解之前過早地收斂。過早收斂問題是所有優(yōu)化算法共同的問題。主要的原因除了上面的“編碼困難”之外，還有“有限困難”，即：理論假定迭代次數(shù)是無限的，而實際上有限制；理論上也假定群體規(guī)模是無限的，實際上也有限制。(2). “有限困難”：遺傳算法理論解釋了為什么對一個給定的問題表達，能收斂到欲求的最優(yōu)點。一個可能的解決途徑是采用浮點編碼，目的是使遺傳算法更接近問題空間。編碼應該具有這樣的性質：在表達空間里相互靠近的兩個點也必須在問題空間里靠近，反之亦然。這本身會產(chǎn)生一個大約是101000的搜索空間。”(Davis, 1989)遺傳算法傳統(tǒng)上使用的二進制編碼當用于多維、高精度數(shù)值問題時會有一些障礙。因為表達方案嚴重地限制了系統(tǒng)觀察世界的窗口。參數(shù)的值決定了選擇的側重，越小，選擇強制越趨向于那些具有最高適應值的串，值隨著代的演化而增大。指數(shù)比例既可讓非常好的串保持較多的復制機會，同時又限制了其復制數(shù)目，以免很快控制整個群體。(2) 冪比例變換冪比例變換是比例適應值取為原適應值的某個指定冪： ，值一般是依賴于具體問題的，在算法執(zhí)行中需要變化以滿足要求的伸縮范圍，即是代的函數(shù)。(1) 線性變換設原適應函數(shù)為，比例適應函數(shù)為，則 稱為線性比例變換。通俗地講就是希望放大串的適應值的間隔，不因適應值非常接近而無法選擇適應值更好的串。3． 適應值變換：注意到賭盤選擇要求適應值是正的，而目標函數(shù)不一定為正，因此需要對目標函數(shù)做變換，即：其中選取一個適當大的數(shù)?！?適應值變換：目的時提高算法對適應值變化的敏感度。中有個個體被隨機地保留到下一代中?！?代間隙：它被引入算法中是允許出現(xiàn)群體重疊的情形，定義在0到1之間，控制每一代群體被替換的百分率?！?變異率：變異是增加群體多樣性的搜索算法。雜交率越高，群體中的串的更新就越快，算法對解空間的搜索能力越強。規(guī)模太小，群體中所含的模式太少，對基因塊采樣增長速率小，且代表性差，最終解的質量不高；規(guī)模大的群體包含大量有廣泛代表性的基因塊，可以阻止算法過早地收斂到局部最優(yōu)解。遺傳算法的參數(shù)空間包括：群體規(guī)模、雜交率、變異率、代間隙、選擇策略和適應值變換等。事實上，參數(shù)設置本身也是個優(yōu)化問題。對余下的小數(shù)部分：a. 有退還剩余隨機選擇：把的小數(shù)部分作為賭盤選擇的權，利用賭盤選擇決定取舍；b. 無退還剩余隨機選擇：把的小數(shù)部分視為概率，一個一個地進行貝努利試驗，其中小數(shù)部分作為成功概率。由于賭盤選擇不能保證把最好的個體保留下來，因此又提出最優(yōu)選擇：設是直到第代最好的個體，按賭盤產(chǎn)生后，若不在中，則把加入中，并隨機舍棄一個個體。剩余部分的填充方法是：把每個串對應的的小數(shù)部分進行排隊，按從大到小的順序選擇對應的串，直到填滿。按的整數(shù)部分值，分配給該串一個拷貝數(shù)?？偟脑瓌t是讓適者生存，即適應值大的串生存概率要大。四、遺傳算法實現(xiàn)中的若干問題和討論：前面已給出了遺傳算法運行步驟的一般描述，通過一個實例具體地考察了它的運行步驟，并給出了遺傳算法的理論基礎。遺傳算法在眾多問題領域中的應用支持基因塊假設。假設1 基因塊假設(Building Block Hypothesis)： 遺傳算法是通過并列短的、低階、高效模式（稱之為基因塊）來尋求接近最優(yōu)的執(zhí)行效果。生長公式(3)的最終結果可以用下面的定理和假設表示：定理1 模式定理(Schema Theorem)： 短的、低階、平均之上的模式在遺傳算子的后續(xù)代中將按幾何級數(shù)增長。另外，變異算子向群體引入了較大的變化性。復制本身并不能增加新的模式（初始時刻的復制除外）。 注意，公式()是基于適應值函數(shù)返回正值的假定：當用遺傳算法優(yōu)化可能返回負值的優(yōu)化函數(shù)時，需要附加一些適應值函數(shù)和優(yōu)化函數(shù)之間的映射。很明顯，在平均值之上的、短的定義長度和低階的模式將按照幾何增長的速率被復制。 因為單個位變異的概率為，所以單個位存活的概率為。這里只有3位（第5，6和7位，即模式的固定位）是很重要的：變異其中之一將破壞模式。根據(jù)前一節(jié)的結果，在第9位變異，其子代為仍然被模式匹配。再一次考慮群體中的一個串，設為： ()和模式。其變化為從0到1或者相反。對模式：這說明短的、平均值之上的模式將在下一代中出現(xiàn)幾何增長的串數(shù)：在時刻，預測有3*= ；在時刻，將有3*= 。因此，模式的存活概率為 所以，選擇和雜交的結合給出了一個新的形式的復制模式生長公式： (2)公式(2)告訴我們在下一代中匹配模式的預測串數(shù)是實際匹配模式串數(shù)、模式的相對適應值及模式的定義長度的函數(shù)。這說明一個模式的最小存活概率實際上為：再一次參考前面例子中的模式()： 注意，盡管雜交位置是在一個模式的固定位置之間選擇的，該模式仍然有機會存活。這就意味著模式的最大消亡概率為 因此，該模式的最小存活概率為實際上，我們的例子中的模式和的存活概率和消亡概率分別為：， ， 所以結果是可以預測的。注意模式的定義長度為，而模式的定義長度為。因為在模板開始的固定位“111”和結尾的固定位“10”分布在不同的子代上。因為雜交在一個后代串上保存了第5，6，7位上的序列“111”。根據(jù)上一節(jié)的例子（個體和被選擇進行雜交），假定雜交位置為。以下依次討論兩個算子作用于群體中模式的效果。所以在進化周期的第二步（重組）中向群體中引入了新個體。可見，模式在時刻匹配5個串：、和?？梢杂靡郧暗膶嵗龣z驗對的預測。特別地，在時刻，預計可以得到3*= （可能有4個或5個）被模式匹配；在時刻，有3*= ，即可能有6個串，等等。把方程（1）稱為復制模式增長方程。如果假定模式高出平均，即，那么 ，且 ，其中，相應于平均值之上的模式；相應于平均值之下的模式。因為：(1) 對一個被模式匹配的一般串，在一個單個串的選擇中，其選擇概率約等于；(2) 被模式匹配的串數(shù)為；(3) 單個串的選擇數(shù)目為，很明顯， 因為群體的平均適應值，所以上式可寫為 (1)這就意味著一個適應值在平均值之上的模式在下一代中的串數(shù)會增加，一個適應值低于平均的模式在下一代中的串數(shù)會減小，而一個中庸的模式將保持不變的水平。如在先前的例子中看到的那樣，在一個單個串的選擇中，串被選擇的概率，其中為整個群體在時刻的總適應值。假定在時刻，群體中匹配模式的串有個{}，則 在選擇過程中，中間群體是這樣產(chǎn)生的：對個單個串進行選擇。注意模式的階，其定義長度。假定在時刻，群體為原先初始化的結果（見P4的）。首先從運行一個例子開始來說明所有的定理。發(fā)生在進化周期其余兩個階段的主要現(xiàn)象是選擇和重組。模式的定義長度在計算模式雜交的存活概率時很有用，隨后討論。如，和。 模式的定義長度（由表示），為第一個和最后一個固定串位之間的距離。其中模式是最特殊的一個。一個模式的階定義了模式的特殊性。 模式的階（由表示），為串中0和1的數(shù)目，即固定位而非通配位的數(shù)目。有兩個重要的模式性質：階和定義長度。 不同的模式有不同的特性。很明顯，每種模式精確地代表個串，這里為通配符(*)在模式模板中的個數(shù)。而模式(*1*1100100)與四個串匹配：{(0101100100), (0111100100), (1101100100), (1111100100)}。例如，考慮長度為10的串和模式。一個模式是通過引入通配符(*)到基因字母表中來建立的。三、遺傳算法的理論基礎： 遺傳算法的理論基礎是遺傳算法解的二進制表達式及模式的含義。跟蹤進化過程中的最好個體是容易的。例如。 現(xiàn)在準備再運行以此選擇過程：應用遺傳算子及評價下一代等。檢查一下新群體的評價過程，對每個染色體進行解碼，并計算解碼后的的適應函數(shù)值，得到： 。 變異位以黑體表示。這說明我們必須產(chǎn)生660個隨機數(shù)。整個群體共有位；。這對染色體在第20位后的部分互換，生成的新的染色體對為：群體的當前版本為： 下一步操作——變異是在一位一位基礎上進行的。第一對染色體是：產(chǎn)生的數(shù)為。對這兩對中的每一對，產(chǎn)生區(qū)間[1, 32]（33為染色體總長度）里的一個隨機整數(shù)。這里很幸運，給選擇的染色體數(shù)是偶數(shù)，可以很容易地配對；如果選擇的染色體數(shù)為奇數(shù)，可以加入一額外的染色體或者移走一被選擇染色體，這種選擇同樣是隨機的。雜交按照下面的方法進行：對新群體中的每個染色體，產(chǎn)生一個在區(qū)間[0, 1]里的隨機數(shù)，如果，則選擇一個給定的染色體進行雜交。假定在區(qū)間[0, 1]里的20個數(shù)的一個隨機序列是： 第一個數(shù)大于而小于，意味著染色體被選擇；第二個數(shù)大于而小于，意味著染色體被選擇，等等。3） 根據(jù)適應值評價解的適應程度并據(jù)此生成新群體：現(xiàn)在系統(tǒng)為選擇過程建立一個輪盤。例如，染色體 (010001001011010000111110010100010)的前18位010001001011010000表示；后15位111110010100010表示 ；所以該染色體對應于，該染色體的適應值為。由于，因此染色體的第一部分需要15位。由于，因此染色體的第一部分需要18位。假定對每個變量要求的精度是小數(shù)點后第4位。其它的部分只是上述步驟的循環(huán)重復，見圖1。隨著選擇、雜交和變異的進行，新群體就為下一次的評價做好了準備。另一個遺傳系統(tǒng)參數(shù)，變異率，給出了我們預計的變異位數(shù)：。兩個染色體 和 被他們的子代 和 所替代。隨機地對被選擇的染色體配對：對染色體中的每一個，產(chǎn)生一個在區(qū)間[1, ]（為總長，即染色體位數(shù)）里的隨機整數(shù)。4） 雜交(crossover)和變異(mutation)——決定新群體的性狀：設雜交概率為，此概率給出預計要進行雜交的染色體個數(shù)。按照如下方法構造輪盤（假設這里的適應值時正值，否則可以使用一些比例機制調整）：● 計算每個染色體的適應值；● 計算群體的總適應值： ● 計算每個染色體的選擇概率： ● 計算每個染色體的累計概率： 對輪盤轉動次，每次按照下面的方法為新群體選擇一個單個的染色體：● 產(chǎn)生一個在區(qū)間[0，1]里的隨機數(shù)；● 如果，則選擇第一個染色體；否則選擇使成立的第個染色體()。如果確實有一些關于最優(yōu)分布的知識，可以使用這些信息來設定初始潛在解的集合。 代表一個潛在解的染色體被長度為的二進制串表達；前位對應區(qū)間[]里的一個值，隨后的位對應區(qū)間[]里的一個值，等等；最后的位對應區(qū)間[]里的一個值。這樣，對每個變量，由串長為的二進制編碼表達可以滿足精度要求。1） 編碼和解碼：要達到要求的精度，每個域應該被分割為個等尺寸的區(qū)間。假設每個變量為域內的一個值，且對所有的。二、遺傳算法的運行步驟：1. 一般性描述： 不失一般性，考慮求最大值的問題。優(yōu)勢：(1). 不容易陷入局部極值，能以很大的概率找到全局最優(yōu)解。(3). 它僅僅利用適應值信息評估個體的優(yōu)劣，無須