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