遺傳算法與蟻群算法簡介-wenkub.com
2025-08-13 02:06 本頁面
【正文】 為了使算法在前期有較高的搜索能力 ， 在后期有較快的收斂速度 ， 可令 w隨時間線性減小 ， 如由 0， 由 ， 由 ? 加速常數(shù) c1和 c2：通?？晒潭?2。rand2()(pgd xid) x39。 在每一代 ， 粒子 i的第 d維 (1 ? d ? D)根據(jù)如下方程變化： v39。也有人將遺傳算法和差分演化算法（ Differential Evolution Algorithm）歸入群智能優(yōu)化算法中。 ? 循環(huán)交叉（ CX） 北京交通大學計算機與信息技術(shù)學院 18 2022/8/29 遺傳算法 變異 ? 二進制或十進制 ? 用另一種基因替換某一位置或某些位置上的基因 ? 實數(shù)編碼 ? 采用擾動的方式： x‘ = x + ηξ，其中 η為擾動幅度， ξ為擾動變量 ? 組合優(yōu)化 ? 互換、逆序、插入等 北京交通大學計算機與信息技術(shù)學院 19 2022/8/29 遺傳算法 函數(shù)優(yōu)化示例 ? 求整數(shù)函數(shù) f(x) = x2在區(qū)間 [0, 31]上取最大值的點 ? 用基本遺傳算法求解 ? 問題是求最大值點，目標函數(shù)可取為 x2。 = [4 2 1 | 7 3 5 8 | 6 9] 北京交通大學計算機與信息技術(shù)學院 17 2022/8/29 遺傳算法 交叉（續(xù)） ? 基于位置的交叉（ PX） ? 與 OX類似，只是它不再選取連續(xù)的基因片段，而是隨機選取一些位置，然后交換被選中位置上的基因，并在原先父代個體中刪除從另一父代個體交換過來的基因，接著從第一個基因位置起依次在未選中位置填入剩余基因。 =[2 6 4 7 | 5 1 8 9 3]， p239。 = [4 3 5 | 1 8 7 6 | 9 2] p239。[i] = p2[p1[i]] p1 = [2 6 4 7 3 5 8 9 1] p139。 = α1x1 + α2x2 + … + αnxn ? 組合優(yōu)化中的置換編碼 GA通常采用 ? 部分映射交叉 (partially mapping crossover, PMX)：隨機選擇兩個交叉點，交換交叉點之間的片段；對于其他基因，若它不與換過來的片段沖突則保留，若沖突則通過部分映射來確定最后的基因 p1 = [2 6 4 | 7 3 5 8 | 9 1] p139。兩點交叉： 北京交通大學計算機與信息技術(shù)學院 14 2022/8/29 1 0 1 1 0 0 1 0 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 1 0 1 0 1 遺傳算法 交叉（續(xù)） ? 實數(shù)編碼的 GA通常采用算術(shù)交叉： ? 雙個體算術(shù)交叉： x x2為父代個體， α ∈ (0, 1)為隨機數(shù) x139。 ? 常用的選擇方法有： ?比例選擇（輪盤選擇） ?基于排名的選擇：由好到壞排序，然后以一定方式給每一個體分配選擇概率（線性、非線性等方式，要求好的個體被選擇的概率大，所有個體所分配的概率之和為 1） ?錦標賽選擇：在父代個體隨機選 k個，然后選最好的。遺傳算法與群智能優(yōu)化算法簡介 主要內(nèi)容 ? 智能優(yōu)化算法簡介 ?問題的 NP完全特性 ?常用的智能優(yōu)化算法 ? 遺傳算法 Geic Algorithm ? 群智能優(yōu)化算法 ?蟻群優(yōu)化算法 Ant Colony Optimization ?粒子群優(yōu)化算法 Particle Swarm Optimization ? ... 北京交通大學計算機與信息技術(shù)學院 2 2022/8/29 智能優(yōu)化算法簡介 ? 20世紀 80年代以來，一些優(yōu)化算法得到發(fā)展 ? GA、 EP、 ACO、 PSO、 SA、 TS、 ANN及混合的優(yōu)化策略等 ? 基本思想：模擬或揭示某些自然現(xiàn)象或過程 ? 為用傳統(tǒng)的優(yōu)化方法難以解決的 NP完全問題提供了有效的解決途徑 ? 由于算法構(gòu)造的直觀性與自然機理，因而通常被稱作 智能優(yōu)化算法 （ intelligent optimization algorithms），或 現(xiàn)代啟發(fā)式算法 （ metaheuristic algorithms） ? [智能優(yōu)化算法及其應(yīng)用，王凌，清華大學出版社， 2022] 北京交通大學計算機與信息技術(shù)學院 3 2022/8/29 智能優(yōu)化算法簡介 問題的 NP完全特性 ? 求解 n個城市的 TSP問題。 北京交通大學計算機與信息技術(shù)學院 13 2022/8/29 ?適應(yīng)值： ?第 i個個體的選擇概率： ?產(chǎn)生隨機數(shù)： ?選擇滿足下式的第 i個個體： ()()iijjfxpfx??[ 0 ,1]? ?111iijjjjpp????????()ifx遺傳算法 交叉 ? 用于組合出新的個體，在解空間中進行有效搜索，同時降低對有效模式的破壞概率 ? 二進制編碼的 GA通常采用單點交叉和多點交叉。 = αx1 + (1 α)x2 x239。 = [2 3 4 | 1 8 7 6 | 9 5] p2 = [4 5 2 | 1 8 7 6 | 9 3] p239。 = [7 3 6 2 9 8 5 1 4] p2 = [4 5 2 1 8 7 6 9 3] p239。 = [2 1 6 | 7 3 5 8 | 9 4] 遺傳算法 交叉（續(xù)） ? 單位置次序交叉（ C1） ? 類
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1