現(xiàn)代優(yōu)化算法-蟻群算法(完整版)
【正文】 ????????????,2,1,1,0,2,1,22,1,2,1,1,2,1,1..m i n,11????選擇 ij 路線(xiàn)為 1，否則為 0 避免產(chǎn)生回路 走入城市 j只有一次 從城市 i出發(fā)只有一次 蟻群優(yōu)化算法 — 算法提出 例子 ， 一般旅行商 TSP問(wèn)題的解 。 蟻群優(yōu)化算法 — 螞蟻生物行為 蟻群實(shí)現(xiàn)找到 蟻巢到食物源的最短路徑示意圖 障礙物 A B C D E H 15 15 15 15 初始時(shí) ， 各有 30只螞蟻在 B和 D點(diǎn)遇到障礙物 ， 開(kāi)始選擇路徑 。 I. 螞蟻個(gè)體通過(guò)在其所經(jīng)過(guò)的路上留下一種稱(chēng)之為“ 信息素 ”（ pheromone）或“跡”的物質(zhì)來(lái)實(shí)現(xiàn)與同伴之間的信息傳遞?，F(xiàn)代智能優(yōu)化算法 顏學(xué)峰 實(shí)驗(yàn)十六樓 415房間 Email： Tel:64253254(o)、 13671876906 華東理工大學(xué) 信息學(xué)院自動(dòng)化研究所 二○○八年 十 月 現(xiàn)代智能優(yōu)化算法 I. 模擬退火 II. 遺傳算法 III. 蟻群優(yōu)化算法 蟻群優(yōu)化算法 — 螞蟻生物行為 I. 螞蟻搬家，天要下雨。 II. 隨后的螞蟻遇到信息素時(shí)，不僅能檢測(cè)出該物質(zhì)的存在以及量的多少，而且可根據(jù)信息素的濃度來(lái)指導(dǎo)自己對(duì)前進(jìn)方向的選擇。 由于此時(shí)路徑上無(wú)跡 ， 螞蟻便以相同的概率隨機(jī)地走兩條路中的任意一條 ， 因而 15只選往 H， 15只選往 C（ 圖 2） 。 A B D E C 如圖所示 ， 從 A城市出發(fā)回到 A城市一個(gè) TSP問(wèn)題的解是 ABCEDA， 即圖中紅色線(xiàn)條路徑 。 蟻群優(yōu)化算法 — 算法提出 蟻群優(yōu)化算法的核心思想有三條： 第一，選擇機(jī)制：跡越多的路徑，被選中的概率越大； 第二，跡更新機(jī)制：路徑越短，跡增加越快； 第三，協(xié)作機(jī)制：個(gè)體之間通過(guò)跡進(jìn)行信息交流。 ??kiN??tPkij蟻群優(yōu)化算法 — 算法流程 跡更新機(jī)制， 為了避免殘留信息過(guò)多引起的殘留信息淹沒(méi)啟發(fā)信息的問(wèn)題，在每一只螞蟻完成對(duì)所有 n個(gè)城市的訪(fǎng)問(wèn)后（也即一個(gè)循環(huán)結(jié)束后）或每走一步（從一個(gè)城市到下一個(gè)城市后），必須對(duì)殘留信息進(jìn)行更新處理， Morigo介紹三種跡更新機(jī)制： 1） antcycle算法 2） antdensity算法 3） antquantity算法 蟻群優(yōu)化算法 — 算法流程 跡更新機(jī)制 —— antcycle算法， 在每一只螞蟻完成對(duì)所有 n個(gè)城市的訪(fǎng)問(wèn)后，對(duì)舊的信息進(jìn)行削弱，將最新的螞蟻訪(fǎng)問(wèn)路徑的信息加入 。 蟻群優(yōu)化算法 — 優(yōu)缺點(diǎn) 缺點(diǎn)： 1）算法有眾多參數(shù)（如 殘留信息的相對(duì)重要程度、啟發(fā)信息的相對(duì)重要程度、 Q常數(shù)、殘留信息的保留部分 ）需要確定，并且算法對(duì)參數(shù)敏感； 2）求解時(shí)間較長(zhǎng)，蟻群算法的復(fù)雜度可以反映這一點(diǎn)； 3）易出現(xiàn)停滯現(xiàn)象，即算法搜索進(jìn)行到一定程度后，所有個(gè)體發(fā)現(xiàn)的解都完全一致，不能對(duì)解空間進(jìn)一步進(jìn)行搜索。 解決：根據(jù)搜索進(jìn)展情況，動(dòng)態(tài)修改需要增加的信息素的方法。 ? ? ? ?kkij LtQt /?? ?Q（ t）時(shí)變函數(shù)幾個(gè)例子，針對(duì)不同情況使用 蟻群優(yōu)化算法 — 改進(jìn) 4）自適應(yīng)調(diào)整 （ 殘留信息的
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1