遺傳算法與蟻群算法簡介(編輯修改稿)
2025-09-12 02:06 本頁面
【文章內容簡介】 實數(shù)編碼 ? 采用擾動的方式： x‘ = x + ηξ，其中 η為擾動幅度， ξ為擾動變量 ? 組合優(yōu)化 ? 互換、逆序、插入等 北京交通大學計算機與信息技術學院 19 2022/8/29 遺傳算法 函數(shù)優(yōu)化示例 ? 求整數(shù)函數(shù) f(x) = x2在區(qū)間 [0, 31]上取最大值的點 ? 用基本遺傳算法求解 ? 問題是求最大值點，目標函數(shù)可取為 x2。 ? 用 5位的二進制位串表示個體，對應區(qū)間 [0, 31]上的 32個整數(shù)。隨機地選取 4個位串作為初始種群，位串與對應的整數(shù)如下： 01101 13 11000 24 01000 8 10011 19 北京交通大學計算機與信息技術學院 20 2022/8/29 ? 根據目標函數(shù) ， 對每個位串計算適值 ? 為每個位串指定一個與其適應值成正比的繁殖概率 ? 根據遺傳操作生成下一代種群 ? 假設選擇的兩對父代個體分別為 1和 2， 2和 4 北京交通大學計算機與信息技術學院 21 2022/8/29 編號 位串 參數(shù)值 目標函數(shù)值 選擇概率 1 01101 13 169 2 11000 24 576 3 01000 8 64 4 10011 19 361 總計 1170 ? 交叉過程 （ 假設使用單點交叉 ， 交叉概率 pc = ） 位串 2： 0 1 1 | 0 1 0 1 1 | 0 0 1 1 0 | 0 0 1 1 0 | 0 1 位串 4： 1 1 0 | 0 0 1 1 0 | 1 1 1 0 0 | 1 1 1 0 0 | 0 0 ? 變異過程 （ 假設變異概率 pm = ， 且此處無變異 ） ? 評價第二代種群 北京交通大學計算機與信息技術學院 22 2022/8/29 編號 位串 參數(shù)值 目標函數(shù)值 1 01100 12 144 2 11001 25 625 3 11011 27 729 4 10000 16 256 總計 1754 遺傳算法 數(shù)學解釋 ? Holland為解釋基于二進制編碼的基本遺傳算法建立了模式定理和隱含并行性定理 ? 模式定理的含義：在 SGA中，階次低、定義長度短且適配值超過平均適配值的模式在種群中的數(shù)目的期望值以指數(shù)級遞增（遺傳算法存在找到全局最優(yōu)解的可能性） ? 隱含并行性定理：遺傳算法所處理的有效模式的總數(shù)約與群體規(guī)模的三次方成正比 ? 積木塊假設的含義：通過短定義距、低階及高平均適應度的模式（積木塊），在遺傳操作下相互結合，最終接近全局最優(yōu)解（說明在遺傳算子的作用下能生成全局最優(yōu)解） 北京交通大學計算機與信息技術學院 23 2022/8/29 遺傳算法 改進 ? 編碼方式的改進 ? 二進制編碼使得個體串很長（特別是精度要求較高的時候） ? 根據需要采用格雷編碼、浮點數(shù)編碼、自然數(shù)編碼等 ? 對遺傳操作的改進 ? 改進選擇策略、交叉算子、變異算子 ? 對控制參數(shù)的自適應調整，如自適應調整交叉概率和變異概率等 ? 對執(zhí)行策略的改進 ? 混合遺傳算法、小生境技術、免疫遺傳算法、單親遺傳算法、并行遺傳算法 北京交通大學計算機與信息技術學院 24 2022/8/29 遺傳算法 欺騙問題 ? 完全欺騙問題 ? 一致欺騙問題 ? 序列欺騙問題 ? 基本欺騙問題 ? 具體請參考：李敏強 ,寇紀淞 . 遺傳算法的模式欺騙性分析 . 中國科學 (E輯 ), 2022, 32(1):95102. 北京交通大學計算機與信息技術學院 25 2022/8/29 遺傳算法 欺騙問題舉例 ? 設編碼空間 {0, 1}3上的最優(yōu)解位串為“ 11l”，若模式適應值滿足： f(0**) f(1**), f(00*) f(11*), f(01*), f(10*) f(*0*) f(*1*), f(0*0) f(1*1), f(0*1), f(1*0) f(**0) f(**1), f(*00) f(*11), f(*01), f(*10) 即競爭力強的低階模式的有效基因位為“ 0”，那么該類模式在群體中的數(shù)量將按指數(shù)增長，包含“ 0”的 1， 2階模式使 GA搜索偏離最優(yōu)解，就形成了 3階模式欺騙問題。 北京交通大學計算機與信息技術學院 26 2022/8/29 遺傳算法 主要特點 ? 處理參數(shù)集合的編碼，而不是參數(shù)本身 ? 始終保持整個種群而不是個體的進化；即使某個體在某時刻丟失了有用的特性，這種特性也會被其它個體保留并發(fā)展下去 ? 只需要知道問題本身所具有的目標函數(shù)的信息，且不受連續(xù)、可微等條件的約束，因而具有廣泛的適用性 ? 啟發(fā)式搜索，可適用于有噪聲和多峰值的復雜空間 北京交通大學計算機與信息技術學院 27 2022/8/29 主要內容 ? 智能優(yōu)化算法簡介 ?問題的 NP完全特性 ?常用的智能優(yōu)化算法 ? 遺傳算法 Geic Algorithm ? 群智能優(yōu)化算法 ?蟻群優(yōu)化算法 Ant Colony Optimization ?粒子群優(yōu)化算法 Particle Swarm Optimization ?… 北京交通大學計算機與信息技術學院 28 2022/8/29 群智能優(yōu)化算法 ? 群智能優(yōu)化算法是一種近年來新興的優(yōu)化方法，其模擬社會性動物的各種群體行為，利用群體中個體間的信息交互和合作來實現(xiàn)尋優(yōu)目的 ? 群智能優(yōu)
黨政相關相關推薦
鄂ICP備17016276號-1