人工智能07蟻群算法及其應用PPT學習課件

第七章蟻群算法及其應用 1 2 蟻群算法的背景 20世紀50年代中期創(chuàng)立了仿生學 人們從生物進化的機理中受到啟發(fā) 提出了許多用以解決復雜優(yōu)化問題的新方法 如進化規(guī)劃 進化策略 遺傳算法等 這些算法成功地解決了一些實際問題 蟻群算法從螞蟻覓食得到啟發(fā) 2 2020 4 19 蟻群算法的背景 仿生算法集群智能算法概率型算法遺傳算法 進化算法粒子群算法 課程論文2 蟻群算法用來解決眾多NP hard問題 3 2020 4 19 蟻群算法的背景 自然蟻群的自組織行為特征高度結構化的組織 雖然螞蟻的個體行為極其簡單 但由個體組成的蟻群卻構成高度結構化的社會組織 螞蟻社會的成員有分工 有相互的通信和信息傳遞 自然優(yōu)化 蟻群在覓食過程中 在沒有任何提示下總能找到從蟻巢到食物源之間的最短路徑 當經過的路線上出現障礙物時 還能迅速找到新的最優(yōu)路徑 信息正反饋 螞蟻在尋找食物時 在其經過的路徑上釋放信息素 外激素 螞蟻基本沒有視覺 但能在小范圍內察覺同類散發(fā)的信息素的軌跡 由此來決定何去何從 并傾向于朝著信息素強度高的方向移動 自催化行為 某條路徑上走過的螞蟻越多 留下的信息素也越多 隨時間蒸發(fā)一部分 后來螞蟻選擇該路徑的概率也越高 4 2020 4 19 蟻群算法的背景 概念原型各個螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物 當一只找到食物以后 它會向環(huán)境釋放一種揮發(fā)性分泌物pheromone 稱為信息素 該物質隨著時間的推移會逐漸揮發(fā)消失 信息素濃度的大小表征路徑的遠近 來實現的 吸引其他的螞蟻過來 這樣越來越多的螞蟻會找到食物 有些螞蟻并沒有像其它螞蟻一樣總重復同樣的路 他們會另辟蹊徑 如果另開辟的道路比原來的其他道路更短 那么 漸漸地 更多的螞蟻被吸引到這條較短的路上來 最后 經過一段時間運行 就可能會出現一條最短的路徑被大多數螞蟻重復著 5 2020 4 19 蟻群算法的提出 算法的提出蟻群算法 AntColonyOptimization ACO 又稱螞蟻算法 一種用來在圖中尋找優(yōu)化路徑的機率型算法 它由MarcoDorigo于1992年在他的博士論文 Antsystem optimizationbyacolonyofcooperatingagents 中提出 其靈感來源于螞蟻在尋找食物過程中發(fā)現路徑的行為 最早用于解決著名的旅行商問題 TSP travelingsalesmanproblem 6 2020 4 19 蟻群算法的提出 基本原理蟻群算法是對自然界螞蟻的尋徑方式進行模似而得出的一種仿生算法 螞蟻在運動過程中 能夠在它所經過的路徑上留下一種稱之為信息素 pheromone 的物質進行信息傳遞 而且螞蟻在運動過程中能夠感知這種物質 并以此指導自己的運動方向 因此由大量螞蟻組成的蟻群集體行為便表現出一種信息正反饋現象 某一路徑上走過的螞蟻越多 則后來者選擇該路徑的概率就越大 7 2020 4 19 蟻群算法的提出 簡化的螞蟻尋食正反饋過程螞蟻從A點出發(fā) 速度相同 食物在D點 可能隨機選擇路線ABD或ACD 假設初始時每條路線分配一只螞蟻 每個時間單位行走一步 本圖為經過9個時間單位時的情形 走ABD的螞蟻到達終點 而走ACD的螞蟻剛好走到C點 為一半路程 8 2020 4 19 蟻群算法的提出 本圖為從開始算起 經過18個時間單位時的情形 走ABD的螞蟻到達終點后得到食物又返回了起點A 而走ACD的螞蟻剛好走到D點 9 2020 4 19 蟻群算法的提出 假設螞蟻每經過一處所留下的信息素為一個單位 則經過36個時間單位后 所有開始一起出發(fā)的螞蟻都經過不同路徑從D點取得了食物 此時ABD的路線往返了2趟 每一處的信息素為4個單位 而ACD的路線往返了一趟 每一處的信息素為2個單位 其比值為2 1 尋找食物的過程繼續(xù)進行 則按信息素的指導 蟻群在ABD路線上增派一只螞蟻 共2只 而ACD路線上仍然為一只螞蟻 再經過36個時間單位后 兩條線路上的信息素單位積累為12和4 比值為3 1 若按以上規(guī)則繼續(xù) 蟻群在ABD路線上再增派一只螞蟻 共3只 而ACD路線上仍然為一只螞蟻 再經過36個時間單位后 兩條線路上的信息素單位積累為24和6 比值為4 1 若繼續(xù)進行 則按信息素的指導 最終所有的螞蟻會放棄ACD路線 而都選擇ABD路線 這也就是前面所提到的正反饋效應 10 2020 4 19 蟻群算法的提出 人工蟻群算法基于以上蟻群尋找食物時的最優(yōu)路徑選擇問題 可以構造人工蟻群 來解決最優(yōu)化問題 如TSP問題 人工蟻群中把具有簡單功能的工作單元看作螞蟻 二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑 較短路徑的信息素濃度高 所以能夠最終被所有螞蟻選擇 也就是最終的優(yōu)化結果 兩者的區(qū)別在于人工蟻群有一定的記憶能力 能夠記憶已經訪問過的節(jié)點 同時 人工蟻群在選擇下一條路徑的時候是按一定算法規(guī)律有意識地尋找最短路徑 而不是盲目的 例如在TSP問題中 可以預先知道當前城市到下一個目的地的距離 人工蟻群VS自然蟻群 11 2020 4 19 蟻群算法的特征 蟻群算法采用了分布式正反饋并行計算機制 易于與其他方法結合 并具有較強的魯棒性 1 其原理是一種正反饋機制或稱增強型學習系統(tǒng) 它通過信息素的不斷更新達到最終收斂于近似最優(yōu)路徑上 2 它是一種通用型隨機優(yōu)化方法 但人工螞蟻決不是對實際螞蟻的一種簡單模擬 它融進了人類的智能 3 它是一種分布式的優(yōu)化方法 不僅適合目前的串行計算機 而且適合未來的并行計算機 4 它是一種全局優(yōu)化的方法 不僅可用于求解單目標優(yōu)化問題 而且可用于求解多目標優(yōu)化問題 5 它是一種啟發(fā)式算法 計算復雜性為O NC m n2 其中NC是迭代次數 m是螞蟻數目 n是目的節(jié)點數目 12 2020 4 19 蟻群算法的特征 算法優(yōu)點 1 求解問題的快速性 由正反饋機制決定 2 全局優(yōu)化性 由分布式計算決定 避免蟻群在尋優(yōu)空間中過早收斂 3 有限時間內答案的合理性 由貪婪式搜索模式決定 使能在搜索過程的早期就找到可以接受的較好解 13 2020 4 19 蟻群算法的基本思想 算法流程圖 14 2020 4 19 蟻群算法的基本思想 以TSP問題為例 1 根據具體問題設置多只螞蟻 分頭并行搜索 2 每只螞蟻完成一次周游后 在行進的路上釋放信息素 信息素量與解的質量成正比 3 螞蟻路徑的選擇根據信息素強度大小 初始信息素量設為相等 同時考慮兩點之間的距離 采用隨機的局部搜索策略 這使得距離較短的邊 其上的信息素量較大 后來的螞蟻選擇該邊的概率也較大 15 2020 4 19 蟻群算法的基本思想 4 每只螞蟻只能走合法路線 經過每個城市1次且僅1次 為此設置禁忌表來控制 5 所有螞蟻都搜索完一次就是迭代一次 每迭代一次就對所有的邊做一次信息素更新 原來的螞蟻死掉 新的螞蟻進行新一輪搜索 6 更新信息素包括原有信息素的蒸發(fā)和經過的路徑上信息素的增加 7 達到預定的迭代步數 或出現停滯現象 所有螞蟻都選擇同樣的路徑 解不再變化 則算法結束 以當前最優(yōu)解作為問題的解輸出 16 2020 4 19 蟻群算法的數學模型 TSP算例分析 旅行商問題 TSP 給定n個城市和兩個兩個城市之間的距離 要求確定一條經過所有城市僅一次的最短路徑 第一步 初始化將m只螞蟻隨機放到n個城市 每只螞蟻的禁忌表為螞蟻當前所在城市 各邊信息素初始化為c 禁忌表體現了人工螞蟻的記憶性 使得螞蟻不會走重復道路 提高了效率 17 2020 4 19 蟻群算法的數學模型 第二步 選擇路徑路徑在t時刻 螞蟻k從城市i轉移到城市j的概率為 18 2020 4 19 蟻群算法的數學模型 19 2020 4 19 蟻群算法的數學模型 蟻群的規(guī)模和停止規(guī)則蟻群大小 一般情況下蟻群中螞蟻的個數不超過TSP圖中節(jié)點的個數 終止條件 1給定一個外循環(huán)的最大數目 表明已經有足夠的螞蟻工作 2當前最優(yōu)解連續(xù)K次相同而停止 其中K是一個給定的整數 表示算法已經收斂 不再需要繼續(xù) 3目標值控制規(guī)則 給定優(yōu)化問題 目標最小化 的一個下界和一個誤差值 當算法得到的目標值同下界之差小于給定的誤差值時 算法終止 第四步 輸出結果若未達到終止條件則轉步驟二 否則 輸出目前的最優(yōu)解 20 2020 4 19 TSP應用舉例 21 2020 4 19 TSP應用舉例 22 2020 4 19 TSP應用舉例 23 2020 4 19 TSP應用舉例 24 2020 4 19 TSP應用舉例 25 2020 4 19 TSP應用舉例 26 2020 4 19 改進的蟻群優(yōu)化算法 27 2020 4 19 一般蟻群算法的框架主要有三個組成部分 蟻群的活動 信息素的揮發(fā) 信息素的增強 主要體現在轉移概率公式和信息素更新公式 28 2020 4 19 一 帶精英策略的螞蟻系統(tǒng) 特點 在信息素更新時給予當前最優(yōu)解以額外的信息素量 使最優(yōu)解得到更好的利用 找到全局最優(yōu)解的螞蟻稱為 精英螞蟻 29 2020 4 19 二 蟻群系統(tǒng) 規(guī)則 和 都是為了使搜索過程更具有指導性 即使螞蟻的搜索主要集中在當前找出的最好解鄰域內 規(guī)則 則是為了使已選的邊對后來的螞蟻具有較小的影響力 以避免螞蟻收斂到同一路徑 30 2020 4 19 三 最大最小螞蟻系統(tǒng) 關于的取值 沒有確定的方法 有的書例子中取為0 01 10 有的書提出一個在最大值給定的情況下計算最小值的公式 四 基于優(yōu)化排序的螞蟻系統(tǒng) 特點 每次迭代完成后 螞蟻所經路徑由小到大排序 并根據路徑長度賦予不同的權重 路徑越短權重越大 信息素更新時對考慮權重的影響 31 2020 4 19 六 一種新的自適應蟻群算法 特點 將ACS中的狀態(tài)轉移規(guī)則改為自適應偽隨機比率規(guī)則 動態(tài)調整轉移概率 以避免出現停滯現象 說明 在ACS的狀態(tài)轉移公式中 是給定的常數 在AACA中 是隨平均節(jié)點分支數ANB而變化的變量 ANB較大 意味著下一步可選的城市較多 也變大 表示選擇信息素和距離最好的邊的可能性增大 反之減小 32 2020 4 19 七 基于混合行為的蟻群算法 特點 按螞蟻的行為特征將螞蟻分成4類 稱為4個子蟻群 各子蟻群按各自的轉移規(guī)則行動 搜索路徑 每迭代一次 更新當前最優(yōu)解 按最優(yōu)路徑長度更新各條邊上的信息素 如此直至算法結束 螞蟻行為 螞蟻在前進過程中 用以決定其下一步移動到哪個狀態(tài)的規(guī)則集合 33 2020 4 19 蟻群算法與遺傳 模擬退火算法的比較 實驗結果表明 1 蟻群算法所找出的解的質量最高 遺傳算法次之 模擬退火算法最低 2 蟻群算法的收斂速度最快 遺傳算法次之 模擬退火算法最慢 蟻群算法之所以能夠快速收斂到全局最優(yōu)解 是因為該算法的個體之間不斷進行信息交流和傳遞 單個個體容易收斂于局部最優(yōu) 多個個體通過合作可以很快地收斂于解空間的最優(yōu)解的附近 34 2020 4 19 蟻群算法的應用 應用領域蟻群算法能夠被用于解決大多數優(yōu)化問題或者能夠轉化為優(yōu)化求解的問題 現在其應用領域已擴展到多目標優(yōu)化 數據分類 數據聚類 模式識別 電信QoS管理 生物系統(tǒng)建模 流程規(guī)劃 信號處理 機器人控制 決策支持以及仿真和系統(tǒng)辯識等方面 群智能理論和方法為解決這類應用問題提供了新的途徑 35 2020 4 19 蟻群算法的應用 蟻群算法在電信路由優(yōu)化中已取得了一定的應用成果 HP公司和英國電信公司在90年代中后期都開展了這方面的研究 設計了蟻群路由算法 AntColonyRouting ACR 每只螞蟻就像蟻群優(yōu)化算法中一樣 根據它在網絡上的經驗與性能 動態(tài)更新路由表項 如果一只螞蟻因為經過了網絡中堵塞的路由而導致了比較大的延遲 那么就對該表項做較大的增強 同時根據信息素揮發(fā)機制實現系統(tǒng)的信息更新 從而拋棄過期的路由信息 這樣 在當前最優(yōu)路由出現擁堵現象時 ACR算法就能迅速的搜尋另一條可替代的最優(yōu)路徑 從而提高網絡的均衡性 負荷量和利用率 目前這方面的應用研究仍在升溫 因為通信網絡的分布式信息結構 非穩(wěn)定隨機動態(tài)特性以及網絡狀態(tài)的異步演化與ACO的算法本質和特性非常相似 36 2020 4 19 蟻群算法的應用 基于群智能的聚類算法起源于對蟻群蟻卵的分類研究 Lumer和Faieta將Deneubourg提出將蟻巢分類模型應用于數據聚類分析 其基本思想是將待聚類數據隨機地散布到一個二維平面內 然后將虛擬螞蟻分布到這個空間內 并以隨機方式移動 當一只螞蟻遇到一個待聚類數據時即將之拾起并繼續(xù)隨機運動 若運動路徑附近的數據與背負的數據相似性高于設置的標準則將其放置在該位置 然后繼續(xù)移動 重復上述數據搬運過程 按照這樣的方法可實現對相似數據的聚類 37 2020 4 19 蟻群算法的應用 ACO還在許多經典組合優(yōu)化問題中獲得了成功的應用 如二次規(guī)劃問題 QAP 機器人路徑規(guī)劃 作業(yè)流程規(guī)劃 圖著色 GraphColoring 等問題 經過多年的發(fā)展 ACO已成為能夠有效解決實際二次規(guī)劃問題的幾種重要算法之一 AS在作業(yè)流程計劃 Job shopScheduling 問題中的應用實例已經出現 這說明了AS在此領域的應用潛力 利用MAX MINAS解決PAQ也取得了比較理想的效果 并通過實驗中的計算數據證明采用該方法處理PAQ比較早的SA算法更好 且與禁忌搜索算法性能相當 利用ACO實現對生產流程和特料管理的綜合優(yōu)化 并通過與遺傳 模擬退火和禁忌搜索算法的比較證明了ACO的工程應用價值 38 2020 4 19 蟻群算法的應