遺傳算法與蟻群算法簡介(參考版)
2024-08-27 02:06本頁面
【正文】 北京交通大學計算機與信息技術學院 43 2022/8/29 ? 最后，我們贊同“無免費午餐”的觀點，因此應盡可地了解問題的本身特點，針對問題給出算法設計，絕不能無目的的模擬計算 北京交通大學計算機與信息技術學院 44 2022/8/29 Beijing Jiaotong University, Beijing 100044, China 45 2022/8/29 謝謝！ 。 北京交通大學計算機與信息技術學院 41 2022/8/29 粒子群優(yōu)化算法 基本原理 (1)初始化：隨機生成一群規(guī)模為 m的微粒 ， 包括位置和速度 (2)評價：計算每個微粒的適應度 (3)更新 Pbest：對每個微粒 ， 將其適應值與其經歷過的最好位置做比較 ， 如果較好 ， 則將其位置作為該微粒的當前最好位置 Pbest (4)更新 gbest：對每個微粒 ， 將其適應值與全局最好位置做比較 ， 如果較好 ， 則將其記為 gbest (5)更新 vid和 xid：根據上述公式改變微粒的速度和位置 (6)如達到滿意的適應值或預設的最大代數 Gmax， 則結束 ， 否則轉 (2) 北京交通大學計算機與信息技術學院 42 2022/8/29 粒子群優(yōu)化算法 基本過程 粒子群優(yōu)化算法 參數設置 ? 最大速度 Vmax：決定了空間搜索的粒度 ， 通常設為每維變化范圍的 10%到 20% ? 慣性權重 w：使粒子保持運動慣性 ， 使其具有擴展搜索空間的趨勢 ， 有能力探索新的區(qū)域 。id = xid + vid 其中 w為慣性權重 ， c1和 c2為加速常數 ， rand1()和 rand2()為在 [0, 1]內選取的隨機函數 。rand1()(pid xid) + c2id = w 設 Vi =(vi1, vi2, … , viD)表示粒子 i的速度 。 北京交通大學計算機與信息技術學院 29 2022/8/29 ? 與基于梯度的優(yōu)化算法不同，群智能優(yōu)化算法依靠的是概率搜索，其優(yōu)點是： ? 無集中控制約束，不會因個別個體而影響整個問題的求解，確保了系統的魯棒性 ? 以非直接的信息交流方式確保了系統的擴展性 ? 并行分布式算法模型 ? 對問題定義的連續(xù)性無特殊要求 ? 算法實現簡單 北京交通大學計算機與信息技術學院 30 2022/8/29 主要內容 ? 智能優(yōu)化算法簡介 ?問題的 NP完全特性 ?常用的智能優(yōu)化算法 ? 遺傳算法 Geic Algorithm ? 群智能優(yōu)化算法 ?蟻群優(yōu)化算法 Ant Colony Optimization ?粒子群優(yōu)化算法 Particle Swarm Optimization ?… 北京交通大學計算機與信息技術學院 31 2022/8/29 蟻群優(yōu)化算法 (Ant Colony Optimization) ? 蟻群優(yōu)化算法（螞蟻算法），是一種分布式智能模擬算法 ? 由 M. Dorigo于 1992年在他的博士論文中提出，其靈感來源于螞蟻在尋找食物過程中發(fā)現路徑的行為 ? 基本思想是模擬螞蟻依賴信息素進行通信而顯示出的社會行為 ? 是一種隨機的通用試探法，可用于求解各種不同的組合優(yōu)化問題 ? 初始的蟻群優(yōu)化算法是基于圖的蟻群系統，過程如下（以求解對稱的 TSP問題為例）： 北京交通大學計算機與信息技術學院 32 2022/8/29 ? 問題的描述： n個城市 N = {1, 2, …, n}，任兩城市的邊 A = {(i, j) | i, j ∈ N}，城市間的距離為 D = (dij)n n ? 設有 m只螞蟻，其出發(fā)城市可隨機確定 ? 路徑的構造 ? 為 TSP圖中的每一條弧 (i, j)賦信息素初值 τij(0)，通常的做法是隨機生成一個解，設其目標值為 f0，則 τij(0) =1/f0 ? 設置城市間的啟發(fā)式信息 ηij ，通常 ηij = 1/dij ? 設第 k只螞蟻在城市 i，則其根據下面的概率選擇下一個城市： 其中 ? 另外，每一螞蟻有一個表 list，用于記錄其訪問過的城市；當訪問了所有的城市后，就可以在其經過的路徑上更新信息素 北京交通大學計算機與信息技術學院 33 2022/8/29 [ ( )] [ ]()[ ( )] [ ]kii j i jkiji l i llNtptt???????????kijN?α與 β表示信息素與啟發(fā)式信息的相對重要程度，通常 α = 1或 2， β = 2或 3 表示螞蟻 k可選的城市集合，即其還未訪問過的城市集合 kiN? 信息素更新策略 ? （局部更新）所有螞蟻周游完成后更新信息素：首先以一定的比例 (1 ρ)減少每條邊上的信息素（ 表示信息素的揮發(fā)），然后更新各自路徑上的信息素，即更新信息素的方式為 ? 其中信息素的揮發(fā)機制可以避免信息素大量積累，也體現了生物界的“遺忘”現象； 表示螞蟻 k在邊 (i, j)上留下的信息素，如果螞蟻沒有經過該邊，則其留下的信息素為 0，即 其中， 表示螞蟻 k構造的路徑的長度， Q是一常數（比如 1） ? 此機制體現了：構造的路徑越短，螞蟻留下的信息素越多；某邊經過的螞蟻越多，其上積累的信息素也就越多 北京交
黨政相關相關推薦
鄂ICP備17016276號-1