【正文】 取為每次迭代的最小值的絕對(duì)值加上目標(biāo)函數(shù)值，即有： 第六步：設(shè)計(jì)遺傳算子。選擇運(yùn)算使用比例選擇算子；交叉運(yùn)算使用單點(diǎn)交叉算子；變異運(yùn)算使用基本位變異算子。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 93 第七步：確定遺傳算法的運(yùn)行參數(shù)。 對(duì)于本例，設(shè)定基本遺傳算法的運(yùn)行參數(shù)如下： 群體大小 : N＝ 50 終止代數(shù) : ger＝ 100 交叉概率： pc＝ 變異概率： pm＝ 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 94 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 95 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 96 由該組圖我們可以看出，隨著進(jìn)化過(guò)程的進(jìn)行，群體中適應(yīng)度較低的一些個(gè)體被逐漸淘汰掉，而適應(yīng)度較高的一些個(gè)體會(huì)越來(lái)越多．并且它們都集中在所求問(wèn)題的最優(yōu)點(diǎn)附近，從而最終就可搜索到問(wèn)題的最優(yōu)解。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 97 小結(jié) 遺傳算法描述了從第 0代產(chǎn)生第 1代的過(guò)程，然后遺傳算法迭代地執(zhí)行這個(gè)過(guò)程，直到滿足某個(gè)停止準(zhǔn)則。在每一代中，算法首先計(jì)算群體中每個(gè)個(gè)體地適應(yīng)值，然后利用適應(yīng)值信息，遺傳算法分別以概率 pc 、 pr 和pm 執(zhí)行雜交、復(fù)制和變異操作，從而產(chǎn)生新的群體。 應(yīng)用遺傳算法求解問(wèn)題需完成四個(gè)主要步驟： 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 98 四、基本遺傳算法的構(gòu)成要素 最常用的是二進(jìn)制編碼，對(duì)于離散性變量直接編碼，對(duì)于連續(xù)性變量先離散化后再編碼 評(píng)估函數(shù) —— 用來(lái)評(píng)估一個(gè)染色體的優(yōu)劣的絕對(duì)值 適應(yīng)度函數(shù) —— 評(píng)估一個(gè)染色體相對(duì)整個(gè)群體的優(yōu)劣的相對(duì)值的大小 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 99 基本遺傳算法一般采用下面兩種方法之一將目標(biāo)函數(shù)值 f(x)變換為個(gè)體的適應(yīng)度 F(x)： 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 100 其中， Cmax是一個(gè)適當(dāng)?shù)叵鄬?duì)比較大的數(shù)，它可用下面幾種方法求得： ?預(yù)先指定的一個(gè)較大的數(shù)。 ?進(jìn)化到當(dāng)前代為止的最大目標(biāo)函數(shù)值。 ?當(dāng)前代或最近幾代群體中的最大目標(biāo)函數(shù)值。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 101 復(fù)制算子、交叉算子、變異算子 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 102 ?N：群體大小 ， 即群體中所含個(gè)體的數(shù)量 ，一般取 20～ 100 ?T：遺傳算法的終止進(jìn)化代數(shù) ， 一般取100～ 500 ? pc：雜交概率 ， 一般取 ～ ? pm ：變異概率 ， 一般取 ～ ? pr ：復(fù)制概率 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 103 四、基本遺傳算法的一般框架 算法過(guò)程： （ i）和步（ ii），直到滿足停止準(zhǔn)則： （ i）計(jì)算群體中每個(gè)個(gè)體的適應(yīng)值 （ ii）應(yīng)用復(fù)制、雜交和變異算子產(chǎn)生下一代群體 執(zhí)行結(jié)果，這個(gè)結(jié)果可以表示問(wèn)題的一個(gè)解（或近似解） 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 104 GEN＝ 0 產(chǎn)生初始群體 是否滿足停止準(zhǔn)則 指定結(jié)果 結(jié) 束 計(jì)算每個(gè)個(gè)體的適應(yīng)值 i＝ 0 i＝ N ？ 以概率選擇遺傳算子 GEN＝ GEN＋ 1 選擇一個(gè)個(gè)體 選擇兩個(gè)個(gè)體 選擇一個(gè)個(gè)體 執(zhí)行復(fù)制 i＝ i＋ 1 執(zhí)行變異 復(fù)制到新群體 執(zhí)行雜交 插入到新群體 將兩個(gè)子代串插入到新群體 i＝ i＋ 1 是 否 是 否 pr pc pm GEN— 當(dāng)前代數(shù) N— 群體規(guī)模 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 105 五、遺傳算法的數(shù)學(xué)理論 幾個(gè)相關(guān)的定義： 模式 —— 是一個(gè)相同的構(gòu)形，它描述的是一個(gè)串的子集，這個(gè)集合中串之間在某些位上相同。 例如，添加符號(hào) *表示不確定字母，即 0或 1，考慮串長(zhǎng)為 7的模式H＝ *11*0**，則串 A＝ 0111000是模式 H的一個(gè)表示，對(duì)于基數(shù)為 k的字母表，每一個(gè)串有（ k＋ 1） l 個(gè)模式。 模式的階 —— 出現(xiàn)在模式中確定位置的數(shù)目。在二進(jìn)制中，一個(gè)模式的階就是所有的 1或 0的數(shù)目。 例如，模式 H＝ *11*0**的階為 3 模式的定義長(zhǎng)度 —— 模式中第一個(gè)確定位置與最后一個(gè)確定位置之間的距離 例如，模式 H＝ *11*0**的定義長(zhǎng)度 r＝ 5－ 2＝ 3 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 106 定理 1（模式定理）：具有短的定義長(zhǎng)度、低階并且適應(yīng)值在群體平均適應(yīng)值以上的模式在遺傳算法迭代過(guò)程中將按指數(shù)增長(zhǎng)率被采樣。 模式定理揭示了遺傳算法為什么有效！ 定理 2（隱并行性）： ns ? n3, 其中 ns —— 有效模式數(shù) n—— 群體規(guī)模 該定理表明，每一代中除了僅對(duì) n個(gè)串的處理外，遺傳算法實(shí)際上處理大約 O（ n3）個(gè)模式，從而每代只執(zhí)行與群體規(guī)模成比例的計(jì)算量，就可以同時(shí)收到并行地對(duì)大約 O（ n3）個(gè)模式進(jìn)行有效處理的目的，并且無(wú)須額外的存儲(chǔ)。 定理 3（積木塊假設(shè)） ：低階、短距、高平均適應(yīng)值的模式（積木塊）在遺傳算子的作用下，相互結(jié)合，能生成高階、長(zhǎng)距、高平均適應(yīng)值的模式，可最終生成全局最優(yōu)解 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 107 定理 4（收斂性定理） ：如果在代的演化過(guò)程中，遺傳算法保留最好的解，并且算法以雜交和變異作為隨機(jī)化算子，則對(duì)于一個(gè)全局優(yōu)化問(wèn)題，隨著演化代數(shù)趨向于無(wú)窮，遺傳算法將以概率 1找到全局最有解 遺傳算法極限特性的分析表明算法能夠?qū)λ阉骺臻g進(jìn)行持續(xù)的搜索，因此遺傳算法特別適合于在全局優(yōu)化問(wèn)題中應(yīng)用 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 108 六、遺傳算法的基本實(shí)現(xiàn)技術(shù) ： 二進(jìn)制編碼、格雷編碼等 編碼規(guī)則： i）應(yīng)使用能易于產(chǎn)生與所求問(wèn)題相關(guān)的且具有低階、短定義長(zhǎng)度模式的編碼方案 ii）應(yīng)使用能使問(wèn)題得到自然表示或描述的具有最小編碼字符集的編碼方案 適應(yīng)值函數(shù)必須是正數(shù)，出現(xiàn)負(fù)數(shù)時(shí)應(yīng)進(jìn)行變換，常用變換方式有三種： 線性比例法： g（ x）＝ a f（ x）＋ b ( b 大于 0) 指數(shù)比例法： g（ x）＝ exp(a f(x))， (a不等于 0) 冪指數(shù)比例法： g（ x）＝ (f(x))a (a為偶數(shù) ) ： 賭盤選擇、余數(shù)隨機(jī)選擇、全局隨機(jī)選擇 ： 一點(diǎn)雜交、兩點(diǎn)雜交、一致雜交 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 109 七、遺傳算法的特點(diǎn) ?，不存在求導(dǎo)和函數(shù)連續(xù)性的限定； ?，而是從一個(gè)點(diǎn)的群體開始搜索； ?； ?，能自動(dòng)獲取搜索過(guò)程中的有關(guān)知識(shí)并用于指導(dǎo)優(yōu)化，自適應(yīng)地調(diào)整搜索方向，不需要確定地規(guī)則； ? 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 110 八、遺傳算法的應(yīng)用 ，優(yōu)化網(wǎng)絡(luò)連接權(quán) 、結(jié)構(gòu)和學(xué)習(xí)參數(shù) 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 111 遺傳算法的困難 (1). “編碼困難 ” ： “ 表達(dá)是遺傳算法的主要問(wèn)題 。 因?yàn)楸磉_(dá)方案嚴(yán)重地限制了系統(tǒng)觀察世界的窗口 。 ” (Koza, 1990) “我們不能用二進(jìn)制表達(dá)和只由二進(jìn)制雜交和二進(jìn)制變異組成的算子集來(lái)處理多數(shù)真實(shí)世界問(wèn)題 。 ” (Davis, 1989) 遺傳算法傳統(tǒng)上使用的二進(jìn)制編碼當(dāng)用于多維 、 高精度數(shù)值問(wèn)題時(shí)會(huì)有一些障礙 。 例如 ， 對(duì)于一個(gè)有 100個(gè)變量 、 域區(qū)間 [500, 500]、 精度要求精確到小數(shù)點(diǎn)后第 6位的問(wèn)題 ， 二進(jìn)制解向量的長(zhǎng)度是3000。 這本身會(huì)產(chǎn)生一個(gè)大約是 101000的搜索空間 。 對(duì)這樣的問(wèn)題 ， 遺傳算法執(zhí)行得很不好 。 編碼應(yīng)該具有這樣的性質(zhì)：在表達(dá)空間里相互靠近的兩個(gè)點(diǎn)也必須在問(wèn)題空間里靠近 ， 反之亦然 。 而二進(jìn)制方法并不總是這樣 。 一個(gè)可能的解決途徑是采用浮點(diǎn)編碼 ， 目的是使遺傳算法更接近問(wèn)題空間 。 通過(guò)利用真實(shí)空間的一些特征 ， 這樣的移近強(qiáng)制算子更與問(wèn)題的特殊性有關(guān) 。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 112 (2). “有限困難 ” ： 遺傳算法理論解釋了為什么對(duì)一個(gè)給定的問(wèn)題表達(dá) ， 能收斂到欲求的最優(yōu)點(diǎn) 。 但不幸的是 ， 實(shí)際的應(yīng)用并不總遵循這一理論 。 主要的原因除了上面的 “ 編碼困難 ” 之外 ， 還有 “ 有限困難 ” ，即：理論假定迭代次數(shù)是無(wú)限的 ， 而實(shí)際上有限制；理論上也假定群體規(guī)模是無(wú)限的 ， 實(shí)際上也有限制 。 這說(shuō)明遺傳算法在某種條件下不能找到最優(yōu)解： 這種失敗是由于過(guò)早地收斂到局部最優(yōu)造成的 。 過(guò)早收斂問(wèn)題是所有優(yōu)化算法共同的問(wèn)題 。 如果收斂發(fā)生的太快 ， 包含在群體中的有價(jià)值的信息常常會(huì)失去 。 而遺傳算法的執(zhí)行趨向于在找到最優(yōu)解之前過(guò)早地收斂 。 有一些避免過(guò)早收斂的策略 ， 比如： (1) 配對(duì)策略 (mating strategy)， 又稱為近親預(yù)防 (incest prevention)； (2) 使用均勻雜交 (uniform crossover)； (3). 檢測(cè)群體中的重復(fù)串 。 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 113 Thank you! 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 114 練習(xí) 說(shuō)說(shuō)遺傳算法的基本思想和算法流程 。 求下面加權(quán)有向圖中從 A到 G的最短路： A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 6 5 8 3 3 3 8 4 2 2 2 1 3 3 3 5 5 2 6 6 4 3 2022/6/1 華中農(nóng)業(yè)大學(xué)理學(xué)院 115 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 5 3 1 3 6 8 7 6 6 5 8 3 3 3 8 4 2 2 2 1 3 3 3 5 5 2 6 6 4 3