【正文】 ). 它不是從單個點(diǎn)，而是從一個解族開始搜索解空間，與傳統(tǒng)的“點(diǎn)對點(diǎn)”式的搜索方法不同。(4). 它利用概率轉(zhuǎn)移規(guī)則，而非確定性規(guī)則。(2). 由于其固有的并行性，適合于大規(guī)模并行計算。問題：求一個有個變量的函數(shù)的的最大值。假定以某個要求的精度優(yōu)化函數(shù)：這里取自變量小數(shù)點(diǎn)后第6位。用表示使成立的最小整數(shù)。以下的公式對應(yīng)于每個串的自變量的值： 其中表示二進(jìn)制串的十進(jìn)制值。2） 產(chǎn)生潛在解初始群體： 簡單地以位的方式隨機(jī)地設(shè)定個染色體。3） 根據(jù)適應(yīng)值評價解的適應(yīng)程度并據(jù)此生成新群體： 通常使用一個根據(jù)適應(yīng)值調(diào)節(jié)刻度寬度的輪盤。這樣做的效果是：好的染色體得到多個拷貝，中等染色體保持平穩(wěn)，最差染色體死亡。對于新群體中的每個染色體：● 產(chǎn)生一個在區(qū)間[0，1]里的隨機(jī)數(shù)；● 如果，則選擇給定的染色體進(jìn)行雜交。表示雜交點(diǎn)的位置。 下一步的變異，是在一位一位(bitbybit)的基礎(chǔ)上進(jìn)行的。整個群體中所有染色體的每一位都有均等的機(jī)會經(jīng)歷變異，即從0到1或者相反：● 產(chǎn)生一個在區(qū)間[0，1]里的隨機(jī)數(shù)；● 如果，變異此位。該評價是用來為下一次選擇過程建立概率分布的，即建立一個根據(jù)當(dāng)前適應(yīng)值構(gòu)造寬距的輪盤。2. 例子：問題：求下列函數(shù)的極大值：，其中及。圖2. 函數(shù)的圖按上面介紹的步驟求解此問題：1） 解碼和解碼：，所要求的精度意味著區(qū)間[, ]10000個等距區(qū)間。，所要求的精度意味著區(qū)間[, ]10000個等距區(qū)間。因此染色體的總長度為位，前18位為，后15位為。2） 產(chǎn)生潛在解初始群體：設(shè)，隨機(jī)產(chǎn)生一個初始化的20個染色體組成的群體，并計算相應(yīng)的適應(yīng)函數(shù)值： 很明顯，染色體是最好的，是最差的。群體的總適應(yīng)值為對每個染色體，選擇概率為：每個染色體的累計概率為： 現(xiàn)在，準(zhǔn)備轉(zhuǎn)動輪盤20次，每次為新群體選擇一個單個的染色體。最后，新群體由以下染色體組成：4） 雜交(crossover)和變異(mutation)——決定新群體的性狀：設(shè)雜交概率，所以預(yù)計染色體中平均有25%（即20個中的5個）將經(jīng)歷雜交。假定隨機(jī)序列為：這說明染色體、和被選擇雜交。對被選擇染色體隨機(jī)進(jìn)行配對：設(shè)為前兩個（即和）和后兩個（即和）被配對。數(shù)字表示雜交點(diǎn)的位置。這對染色體在第9位后的部分互換，生成新的一對染色體：第二對染色體是：產(chǎn)生的數(shù)為。變異概率，所以我們預(yù)計平均將有1%的位經(jīng)歷變異。因?yàn)槊恳晃欢加芯鹊臋C(jī)會被變異，所以對群體中的每一位可以產(chǎn)生區(qū)間[0, 1]里的一個隨機(jī)數(shù)，如果，則變異此位。在運(yùn)行的例子中，：：：這就意味著有四個染色體通過變異而改變；其中一個染色體（第13個）有兩位基因發(fā)生變化。對修正的染色體去掉撇號，最新的染色體群體如下： 這里只完成了圖1中的遺傳過程while循環(huán)中的一次迭代（即一代）。同時，當(dāng)前最好染色體的評價值()要好于先前群體的最好染色體的評價值()。經(jīng)過1000代后，群體及其適應(yīng)值為： 但是，仔細(xì)檢查整個運(yùn)行過程。這是由于取樣的隨機(jī)誤差造成的。在遺傳算法的實(shí)現(xiàn)中，通常在一獨(dú)立出來的位置保存“曾經(jīng)最好”的個體；用這種方法，算法將報告整個過程的最好值，而不只是最終群體的最好值。模式是能對染色體之間相似性進(jìn)行解釋的模板。一個模式代表所有的除“*”外與所有位置都匹配的所有串（搜索空間的子集）。模式(*11100100)與兩個串匹配：{(0111100100), (1111100100)}。顯然，模式(1001110001)只代表一個串，而模式(**********)代表所有長度為10的串。另一方面，每個長度為的串匹配個模式（每位上可以為原數(shù)碼和*兩種可能）。注意到：在一個模式中通配符*的數(shù)目決定了匹配該模式的串?dāng)?shù)。模式定理是在這些性質(zhì)的基礎(chǔ)上表達(dá)的。換句話說，它是模板長度減去通配符(*)的數(shù)目。如下面三個長度為10的模式：，的階為：，及。模式的階對計算變異操作種模式的存活概率時很有用的，隨后將討論。它定義了包含在模式中的信息的致密度。注意，只有單個固定點(diǎn)的模式的定義長度為零。 遺傳算法模擬進(jìn)化過程包括四個不斷重復(fù)的步驟： select from rebine evaluate 第一步（）簡單地將演化時鐘向前移動一個單位；最后一步（evaluate ）只是對當(dāng)前群體進(jìn)行評價。這里將討論這兩步作用在群體中預(yù)定數(shù)目的模式上的效果。1． 選擇： 仍然采用上一節(jié)的例子，群體規(guī)模，模式模板的長度。表示時刻時群體中匹配模式的串?dāng)?shù)，如對于一個給定模式：，因?yàn)橛?個串，和匹配模式。 模式在時刻的適應(yīng)值定義為群體中和模式匹配的所有串的平均適應(yīng)值。每個串根據(jù)其適應(yīng)值被拷貝零次、一次或多次。設(shè)經(jīng)過選擇步驟，有個串被模式匹配。 上述規(guī)則的長期效果是明顯的。 這是一個幾何級數(shù)方程：一個平均值之上的模式不僅在下一代中串?dāng)?shù)增長，而且是幾何增長。 回到模式，因?yàn)樵跁r刻有3個串，和匹配模式，模式的適應(yīng)值為： 同時，整個群體的平均適應(yīng)值為： 模式的適應(yīng)值與群體平均適應(yīng)值的比例為： 這就意味著如果模式保持在平均之上，那么它將在下一代中保持串?dāng)?shù)的幾何增長。根據(jù)直覺，的模式定義了搜索空間中極有希望的一部分，并且它以幾何增長的方式被復(fù)制。在時刻，新的群體見P5下方的。 然而，選擇本身不能產(chǎn)生新的潛在解，只能從中間群體中復(fù)制一些串。這是通過雜交和變異兩個算子完成的。2． 雜交：考慮下面的例子：如在前面討論的，群體中一個單獨(dú)個體的串，設(shè)為：被233種模式匹配；該串同時被下面兩個模式匹配： 進(jìn)一步假定上述串被選擇用來雜交。很明顯，模式生存下來，即有一個后代仍然匹配。雜交前 雜交后 另一方面，模式遭破壞：子代不與它匹配。 很明顯，模式的定義長度對其生存和損壞的概率起著很重要的作用。 通常，雜交位是在中可能的位置上被唯一地選擇的。注意實(shí)際上只有一些染色體經(jīng)歷雜交，并且雜交的選擇性概率為。例如，如果串和都是以“111”開始，“10”結(jié)尾，模式將雜交存活，當(dāng)然，這種可能性非常小。顯然，在平均之上，短的定義長度的模式將按照幾何增長的速率被復(fù)制。3． 變異：變異算子以概率隨機(jī)地改變一個染色體中的某一位。很明顯，如果模式經(jīng)過變異還存活，該模式上的所有固定位應(yīng)保持不變。進(jìn)一步假定串經(jīng)歷變異，即至少有一位發(fā)生變異。如果被選擇變異的位置是從1到4，或者8到33，那么所生成的子代仍然被模式匹配。很明顯，這些重要位的數(shù)目等于模式的階，即固定位的數(shù)目。單個變異是和其它變異相互獨(dú)立的，所以模式經(jīng)過單點(diǎn)變異后的存活概率為由于，所以此概率可以被近似為再一次參考例子中的模式(): 選擇、雜交和變異的組合給出了復(fù)制生長公式的新形式： (3) 正如簡單公式(1)和(2)，公式(3)告訴我們在下一代中，預(yù)測匹配模式的串?dāng)?shù)是匹配模式的實(shí)際串?dāng)?shù)、模式的相對適應(yīng)值和定義長度以及階的函數(shù)。 對模式：這就意味著短的、低階、平均之上的模式將在下一代中產(chǎn)生幾何增長的串?dāng)?shù)：在時刻預(yù)計有3*=（——只考慮選擇的結(jié)果，——值考慮選擇和雜交的結(jié)果），在時刻，有3*=（）。 概括起來，生長公式(1)顯示：選擇增加了平均之上的模式的復(fù)制率，并且這種變化是指數(shù)型的。這就是為什么要引入雜交算子的原因——能以結(jié)構(gòu)化的方式隨機(jī)地交換信息。如果一個模式是短的且低階的，這些算子作用在該模式上的組合分裂效果是不大的。這一定理的直接結(jié)果是：遺傳算法通過短的、低階模式的雜交信息交換過程探求了搜索空間。雖然已有一些研究來證明此假設(shè)，但是多數(shù)重要的應(yīng)用還是依賴于實(shí)驗(yàn)結(jié)果。毫無疑問，基因塊假設(shè)說明遺傳算法的編碼問題對其執(zhí)行效果來說是至關(guān)重要的，并且這種編碼應(yīng)該符合短基因塊的思想。在具體實(shí)現(xiàn)過程中，仍有一些問題值得重視：1． 選擇策略：選擇策略是指復(fù)制算子按照什么方式進(jìn)行操作。常用的選擇方法有以下幾種：(1). 確定性選擇方法：對群體中每個串計算生存概率（其中為總適應(yīng)值），從而得到的期望拷貝數(shù)。顯然，總的拷貝數(shù)小于。(2). 賭盤選擇方法：即前面采用的方法，此處不在贅述。(3). 有退還和無退還剩余隨機(jī)選擇：首先計算期望拷貝數(shù)，整數(shù)部分決定拷貝數(shù)。2． 控制參數(shù)的選擇：在使用遺傳算法時，首先要給定一組控制參數(shù)，如群體規(guī)模，雜交率和變異率等，控制參數(shù)的不同選擇會對遺傳算法的性能產(chǎn)生很大的影響，要想發(fā)掘執(zhí)行的最優(yōu)性能，必須確定最優(yōu)的參數(shù)設(shè)置。這里僅討論一些原則?！?群體規(guī)模：它影響到遺傳算法的最終性能和效率。然而群體規(guī)模越大，每一代所需要的計算量就越大，這會導(dǎo)致收斂過程太慢；● 雜交率：雜交率控制雜交算子的應(yīng)用頻率。若雜交率過高，高性能的串被破壞的速度也加快了；若雜交率過低，算法搜索解空間的能力下降，有蛻變成局部隨機(jī)搜索算法的危險。一個低水平的變異率足以防止整個群體中任一給定位保持永遠(yuǎn)收斂于單一的值；高水平的變異率產(chǎn)生的實(shí)際上是隨機(jī)搜索。時，表示全部替換；時，表示部分替換。● 選擇策略：前面已經(jīng)討論過，用的較多的是賭盤選擇。因?yàn)檫m應(yīng)值是算法唯一利用的信息，對適應(yīng)值變化是否敏感是很重要的。 進(jìn)行適應(yīng)值比例變換的目的是調(diào)節(jié)遺傳算法執(zhí)行過程中串的復(fù)制數(shù)目，以提高算法的性能。另外，還可壓制某些適應(yīng)值非常大的串控制選擇過程。系數(shù)和的選擇必須滿足以下兩個條件：1. 平均比例適應(yīng)值等于原平均適應(yīng)值；2. 最大的比例適應(yīng)值是平均適應(yīng)值的指定倍數(shù)，即，一般取2，這兩個條件保證平均群體個體最好的個體的期望復(fù)制數(shù)分別為1和。(3) 指數(shù)比例變換指數(shù)比例滿足關(guān)系式：。同時對于適應(yīng)值相近的串也提高了競爭性。4． 遺傳算法的困難：(1). “編碼困難”：“表達(dá)是遺傳算法的主要問題?！?Koza, 1990)“在我看來有時確實(shí)如此，我們不能用二進(jìn)制表達(dá)和只由二進(jìn)制雜交和二進(jìn)制變異組成的算子集來處理多數(shù)真實(shí)世界的問題。例如，對于一個有100個變量、域區(qū)間[500, 500]、精度要求精確到小數(shù)點(diǎn)后第6位的問題，二進(jìn)制解向量的長度是3000。對這樣的問題，遺傳算法執(zhí)行得很不好。而二進(jìn)制方法并不總是這樣。通過利用真實(shí)空間的一些特征，這樣的移近強(qiáng)制算子更與問題的特殊性有關(guān)。但不幸的是，實(shí)際的應(yīng)用并不總遵循這一理論。這說明遺傳算法在某種條件下不能找到最優(yōu)解：這種失敗是由于過早地收斂到局部最優(yōu)造成的。如果收斂發(fā)生的太快，包含在群體中的有價值的信息常常會失去。有一些避免過早收斂的策略，比如：(1) 配對策略(mating strategy)，又稱為近親預(yù)防(incest prevention)； (2) 使用均勻雜交(uniform crossover)；(3). 檢測群體中的