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