人工智能07蟻群算法及其應(yīng)用(ppt51頁)-文庫吧資料
2025-02-23 12:43本頁面
【正文】 確定的方法，有的 書例子中取為 ， 10；有的書提出一個(gè)在最大 值給定的情況下計(jì)算最小值的公式。 （二）蟻群系統(tǒng) ACS 規(guī)則１和２都是為了使搜索過程更具有指導(dǎo)性，即使螞蟻的搜索主要集中在當(dāng)前找出的最好解鄰域內(nèi)。 ３、局部更新規(guī)則 ——螞蟻每次從城市 轉(zhuǎn)移到 城市 后，邊 上的信息素適當(dāng)減少。 特點(diǎn) １、狀態(tài)轉(zhuǎn)移規(guī)則 ——偽隨機(jī)比率規(guī)則 )1,0(0?qq 0q? 設(shè) 為常數(shù)， 為隨機(jī)數(shù)， 如果 ，則螞蟻轉(zhuǎn)移的下一座城市是使 取最大值的城市；若 ， 仍按轉(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)移概率公式和信息素更新公式。 ? 終止條件 : 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)化問題（目標(biāo)最小化）的一個(gè)下界和一個(gè)誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時(shí)，算法終止。 禁忌表體現(xiàn)了人工螞蟻的記憶性，使得螞蟻不會走重復(fù)道路，提高了效率。 蟻群算法的數(shù)學(xué)模型 ? TSP算例分析 旅行商問題（ TSP） 給定 n個(gè)城市和兩個(gè)兩個(gè)城市之間的距離 ，要求確定一條經(jīng)過所有城市僅一次的最短路徑 。 ? 更新信息素包括原有信息素的蒸發(fā)和經(jīng)過的路徑上信息素的增加。 蟻群算法的基本思想 ? 每只螞蟻只能走合法路線（經(jīng)過每個(gè)城市 1次且僅 1次），為此設(shè)置禁忌表來控制。 ? 螞蟻路徑的選擇根據(jù)信息素強(qiáng)度大?。ǔ跏夹畔⑺亓吭O(shè)為相等），同時(shí)考慮兩點(diǎn)之間的距離，采用隨機(jī)的局部搜索策略。 蟻群算法的特征 算法優(yōu)點(diǎn)： ? （ 1） 求解問題的快速性 ——由正反饋機(jī)制決定 ? （ 2） 全局優(yōu)化性 ——由分布式計(jì)算決定，避免蟻群在尋優(yōu)空間中過早收斂 ? （ 3） 有限時(shí)間內(nèi)答案的合理性 ——由貪婪式搜索模式?jīng)Q定，使能在搜索過程的早期就找到可以接受的較好解 蟻群算法的基本思想 算法流程圖： 開始 初始化 迭代次數(shù)Nc=Nc+1 螞蟻 k=1 螞蟻 k=k+1 按照狀態(tài)轉(zhuǎn)移概率公式選擇下一個(gè)元素 修改禁忌表 K=螞蟻總數(shù) m？ 按照公式進(jìn)行信息量更新 滿足結(jié)束條件？ 輸出程序計(jì)算結(jié)果 結(jié)束 Y Y N N 蟻群算法的基本思想 以 TSP問題為例： ? 根據(jù)具體問題設(shè)置多只螞蟻，分頭并行搜索。 人工蟻群 VS 自然蟻群 蟻群算法的特征 蟻群算法 采用了分布式正反饋并行計(jì)算機(jī)制 , 易于與其他方法結(jié)合 , 并具有較強(qiáng)的 魯棒性 。同時(shí)，人工蟻群
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1