蟻群算法ppt課件(2)(已修改)

　

【正文】 第五章第五章 蟻群算法蟻群算法智能優(yōu)化方法智能優(yōu)化方法 信息系統(tǒng)與管理學院 1蟻群優(yōu)化算法n 蟻群優(yōu)化算法概述n 蟻群優(yōu)化算法概念n 算法模型和收斂性分析n 算法實現(xiàn)的技術(shù)問題n 應用2 蟻群優(yōu)化算法概述 起源 應用領(lǐng)域 研究背景 應用現(xiàn)狀3 蟻群優(yōu)化算法起源 20世紀 50年代中期創(chuàng)立了仿生學，人們從生物進化的機理中受到啟發(fā)。提出了許多用以解決復雜優(yōu)化問題的新方法，如 進化規(guī)劃、進化策略、遺傳算法 等。 20世紀 90年代意大利學者 M． Dorigo， V． Maniezzo，A． Colorni等從生物進化的機制中受到啟發(fā)，通過模擬自然界螞蟻搜索路徑的行為，提出來一種新型的 模擬進化算法 —— 蟻群算法 。 該方法求解 TSP問題 、 分配問題 、 jobshop調(diào)度 問題，取得了較好的試驗結(jié)果．雖然研究時間不長，但是現(xiàn)在的研究顯示出，蟻群算法在求解復雜優(yōu)化問題（特別是 離散優(yōu)化問題 ）方面有一定優(yōu)勢。4 蟻群優(yōu)化算法應用領(lǐng)域 這種方法能夠被用于解決大多數(shù)優(yōu)化問題或者能夠轉(zhuǎn)化為優(yōu)化求解的問題。 目前其應用領(lǐng)域已擴展到 多目標優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識別、電信 QoS管理、生物系統(tǒng)建模、流程規(guī)劃、信號處理、機器人控制、決策支持以及仿真和系統(tǒng)辯識 等方面，群智能理論和方法為解決這類應用問題提供了新的途徑 。5 蟻群優(yōu)化算法研究背景 1/3群體智能理論研究領(lǐng)域有兩種主要的算法：u 蟻群算法 (Ant Colony Optimization, ACO)– 對螞蟻群落食物采集過程的模擬，已成功應用于許多離散優(yōu)化問題。u 粒子群算法 （ Particle Swarm Optimization, PSO）– 起源于對簡單社會系統(tǒng)的模擬，最初是模擬鳥群覓食的過程，但后來發(fā)現(xiàn)它是一種很好的優(yōu)化工具。 6 蟻群優(yōu)化算法研究背景 2/3與大多數(shù) 基于梯度 的應用優(yōu)化算法不同，群智能依靠的是 概率搜索算法 。雖然概率搜索算法通常要采用較多的評價函數(shù)，其優(yōu)點主要表現(xiàn)在： ，不會因個別個體的故障影響整個問題的求解，確保了系統(tǒng)具備更強的魯棒性 ，可充分利用多處理器 7 蟻群優(yōu)化算法研究背景 3/3群智能方法易于實現(xiàn)，算法中僅涉及各種基本的數(shù)學操作，其數(shù)據(jù)處理過程對 CPU和內(nèi)存的要求也不高。而且，這種方法只需目標函數(shù)的輸出值，而無需其梯度信息。已完成的群智能理論和應用方法研究證明群智能方法是一種能夠有效解決大多數(shù)全局優(yōu)化問題的新方法。更為重要是，群智能潛在的 并行性 和 分布式 特點為處理大量的以數(shù)據(jù)庫形式存在的數(shù)據(jù)提供了技術(shù)保證。無論是從理論研究還是應用研究的角度分析，群智能理論及其應用研究都是具有重要學術(shù)意義和現(xiàn)實價值的。 8 蟻群優(yōu)化算法應用現(xiàn)狀 1/5隨著群智能理論和應用算法研究的不斷發(fā)展，研究者已嘗試著將其用于各種工程優(yōu)化問題，并取得了意想不到的收獲。多種研究表明，群智能在 離散求解空間 和 連續(xù)求解空間 中均表現(xiàn)出良好的搜索效果，并在組合優(yōu)化問題中表現(xiàn)突出。蟻群優(yōu)化算法并不是旅行商問題的最佳解決方法，但是它卻為解決組合優(yōu)化問題提供了新思路，并很快被應用到其它組合優(yōu)化問題中。比較典型的應用研究包括：u 網(wǎng)絡(luò)路由優(yōu)化u 數(shù)據(jù)挖掘以u 一些經(jīng)典的組合優(yōu)化問題9 蟻群優(yōu)化算法應用現(xiàn)狀 2/5蟻群算法在電信路由優(yōu)化中已取得了一定的應用成果。 HP公司和 英國電信公司 在 90年代中后期都開展了這方面的研究，設(shè)計了蟻群路由算法（ Ant Colony Routing, ACR）。每只螞蟻就像蟻群優(yōu)化算法中一樣，根據(jù)它在網(wǎng)絡(luò)上的經(jīng)驗與性能，動態(tài)更新路由表項。如果一只螞蟻因為經(jīng)過了網(wǎng)絡(luò)中堵塞的路由而導致了比較大的延遲，那么就對該表項做較大的增強。同時根據(jù)信息素揮發(fā)機制實現(xiàn)系統(tǒng)的信息更新，從而拋棄過期的路由信息。這樣，在當前最優(yōu)路由出現(xiàn)擁堵現(xiàn)象時， ACR算法就能迅速的搜尋另一條可替代的最優(yōu)路徑，從而提高網(wǎng)絡(luò)的均衡性、負荷量和利用率。目前這方面的應用研究仍在升溫，因為通信網(wǎng)絡(luò)的分布式信息結(jié)構(gòu)、非穩(wěn)定隨機動態(tài)特性以及網(wǎng)絡(luò)狀態(tài)的異步演化與 ACO的算法本質(zhì)和特性非常相似。 10 蟻群優(yōu)化算法應用現(xiàn)狀 3/5基于群智能的 聚類算法 起源于對 蟻群蟻卵 的分類研究。 Lumer和 Faieta將 Deneubourg提出將蟻巢分類模型應用于數(shù)據(jù)聚類分析。其基本思想是將待聚類數(shù)據(jù)隨機地散布到一個二維平面內(nèi)，然后將虛擬螞蟻分布到這個空間內(nèi)，并以隨機方式移動，當一只螞蟻遇到一個待聚類數(shù)據(jù)時即將之拾起并繼續(xù)隨機運動，若運動路徑附近的數(shù)據(jù)與背負的數(shù)據(jù)相似性高于設(shè)置的標準則將其放置在該位置，然后繼續(xù)移動，重復上述數(shù)據(jù)搬運過程。按照這樣的方法可實現(xiàn)對相似數(shù)據(jù)的聚類。11 蟻群優(yōu)化算法應用現(xiàn)狀 4/5ACO還在許多經(jīng)典組合優(yōu)化問題中獲得了成功的應用，如 二次規(guī)劃問題 （ QAP） 、 機器人路徑規(guī)劃 、 作業(yè)流程規(guī)劃 、 圖著色 （ Graph Coloring） 等問題。經(jīng)過多年的發(fā)展， ACO已成為能夠有效解決實際二次規(guī)劃問題的幾種重要算法之一。 AS在作業(yè)流程計劃（Jobshop Scheduling） 問題中的應用實例已經(jīng)出現(xiàn)，這說明了 AS在此領(lǐng)域的應用潛力。利用 MAXMIN AS解決PAQ也取得了比較理想的效果，并通過實驗中的計算數(shù)據(jù)證明采用該方法處理 PAQ比較早的 SA算法更好，且與禁忌搜索算法性能相當。利用 ACO實現(xiàn)對生產(chǎn)流程和特料管理的綜合優(yōu)化，并通過與遺傳、模擬退火和禁忌搜索算法的比較證明了 ACO的工程應用價值。12 蟻群優(yōu)化算法應用現(xiàn)狀 5/5許多 研究者將 ACO用于了 武器攻擊目標分配和優(yōu)化問題、 車輛運行路徑規(guī)劃 、 區(qū)域性無線電頻率自動分配 、 Bayesian works的訓練和 集合覆蓋 等應用優(yōu)化問題。 Costa和 Herz還提出了一種 AS在規(guī)劃問題方面的擴展應用 —— 圖著色問題，并取得了可與其他啟發(fā)式算法相比的效果。13 蟻群優(yōu)化算法概念 蟻群算法原理 簡化的螞蟻尋食過程 自然蟻群與人工蟻群算法 蟻群算法與 TSP問題 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 一般蟻群算法的框架14 蟻群算法原理蟻群算法是對自然界螞蟻的尋徑方式進行模似而得出的一種仿生算法。螞蟻能夠在它所經(jīng)過的路徑上留下一種稱之為 外激素 (pheromone)的物質(zhì)進行信息傳遞，螞蟻在運動過程中能夠感知以此指導自己的運動方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。螞蟻搜尋食物的具體過程：當碰到一個還