遺傳算法ppt課件-資料下載頁

　　

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