人工智能07蟻群算法及其應用(ppt51頁)(編輯修改稿)
2025-03-09 12:43 本頁面
【文章內(nèi)容簡介】 控制。 ? 所有螞蟻都搜索完一次就是迭代一次，每迭代一次就對所有的邊做一次信息素更新，原來的螞蟻死掉，新的螞蟻進行新一輪搜索。 ? 更新信息素包括原有信息素的蒸發(fā)和經(jīng)過的路徑上信息素的增加。 ? 達到預定的迭代步數(shù)，或出現(xiàn) 停滯現(xiàn)象 （所有螞蟻都選擇同樣的路徑，解不再變化），則算法結束，以當前最優(yōu)解作為問題的解輸出。 蟻群算法的數(shù)學模型 ? TSP算例分析 旅行商問題（ TSP） 給定 n個城市和兩個兩個城市之間的距離 ，要求確定一條經(jīng)過所有城市僅一次的最短路徑 。 第一步 :初始化 將 m只螞蟻隨機放到 n個城市，每只螞蟻的禁忌表為螞蟻當前所在城市，各邊信息素初始化為 c。 禁忌表體現(xiàn)了人工螞蟻的記憶性，使得螞蟻不會走重復道路，提高了效率。 蟻群算法的數(shù)學模型 第二步 :選擇路徑路徑 在 t時刻，螞蟻 k從城市 i轉移到城市 j的概率為： 蟻群算法的數(shù)學模型 蟻群算法的數(shù)學模型 蟻群的規(guī)模和停止規(guī)則 ? 蟻群大小 : 一般情況下蟻群中螞蟻的個數(shù)不超過 TSP圖中節(jié)點的個數(shù)。 ? 終止條件 : 1 給定一個外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作； 2 當前最優(yōu)解連續(xù) K次相同而停止，其中 K是一個給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)； 3 目標值控制規(guī)則，給定優(yōu)化問題（目標最小化）的一個下界和一個誤差值，當算法得到的目標值同下界之差小于給定的誤差值時，算法終止。 第四步：輸出結果 若未達到終止條件則轉步驟二，否則，輸出目前的最優(yōu)解。 TSP應用舉例 TSP應用舉例 TSP應用舉例 TSP應用舉例 TSP應用舉例 TSP應用舉例 改進的蟻群優(yōu)化算法 ▲ 最優(yōu)解保留策略螞蟻系統(tǒng) （帶精英策略的螞蟻系統(tǒng) ASelite） ▲ 蟻群系統(tǒng) （ ACS） ▲ 最大 最小螞蟻系統(tǒng) （ MMAS） ▲ 基于優(yōu)化排序的螞蟻系統(tǒng)（ ASrank） ▲ 最優(yōu)最差螞蟻系統(tǒng)（ BWAS） ▲ 一種新的自適應蟻群算法（ AACA） ▲ 基于混合行為的蟻群算法（ HBACA） 改 進 的 蟻群算法 ? 一般蟻群算法的框架主要有三個組成部分： 1. 蟻群的活動； 2. 信息素的揮發(fā)； 3. 信息素的增強； ? 主要體現(xiàn)在轉移概率公式和信息素更新公式。 （一）帶精英策略的螞蟻系統(tǒng) eliteAS特點 —— 在信息素更新時給予當前最優(yōu)解以額外的信息素量，使最優(yōu)解得到更好的利用。找到全局最優(yōu)解的螞蟻稱為“精英螞蟻”。 ? ?? ??? ????????? ijijijij tnt ????? 1????? ???否則是當前最優(yōu)解的一部分若邊,0,Δ ijLQτ gbij??ijτΔ?gbL——精英螞蟻在邊 上增加的信息素量； ij——精英螞蟻個數(shù)； ——當前全局最優(yōu)解路徑長度。 特點 １、狀態(tài)轉移規(guī)則 ——偽隨機比率規(guī)則 )1,0(0?qq 0q? 設 為常數(shù)， 為隨機數(shù)， 如果 ，則螞蟻轉移的下一座城市是使 取最大值的城市；若 ， 仍按轉移概率確定。 βijαij tηtτ )]([)]([ ?0qq?２、全局更新規(guī)則 ——只有精英螞蟻才允許釋放 信息素，即只有全局最優(yōu)解所屬的邊才增加 信息素。 ３、局部更新規(guī)則 ——螞蟻每次從城市 轉移到
規(guī)章制度相關推薦
鄂ICP備17016276號-1