資源描述：
《《蟻群算法發(fā)展》PPT課件》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、蟻群算法螞蟻的生物學(xué)特征螞蟻是一種既渺小而又平常的社會性昆蟲。生物學(xué)家通過對螞蟻的長期觀察研究發(fā)現(xiàn)，每只螞蟻的智能并不高，但它們卻能協(xié)同工作，集中食物，建筑蟻穴并撫養(yǎng)后代，依靠群體能力發(fā)揮出超出個體的智能。螞蟻有復(fù)雜的社會體制，“螞蟻”城市往往有5000萬個成員。螞蟻有四種不同的蟻型：蟻后、雄蟻、工蟻和兵蟻。螞蟻的生物學(xué)特征尋找食物螞蟻尋找食物過程中總會自動找到一條最短路徑。蟻群算法起源蟻群優(yōu)化（antcolonyoptimization,ACO）是20世紀(jì)90年代初由意大利學(xué)者M.Dorigo等通過模擬螞蟻的行為而
2、提出的一種隨機優(yōu)化技術(shù)。ACO算法最初用于求解旅行商問題，現(xiàn)在已經(jīng)成功用于許多組合優(yōu)化問題。MacroDorigo蟻群算法的基本原理蟻群算法是對自然界螞蟻的尋徑方式進行模似而得出的一種仿生算法。螞蟻在運動過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為信息素(pheromone)的物質(zhì)進行信息傳遞，而且螞蟻在運動過程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運動方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。蟻群算法的基本原理在蟻群尋找食物時，它們總能
3、找到一條從食物到巢穴之間的最優(yōu)路徑。這是因為螞蟻在尋找路徑時會在路徑上釋放出一種特殊的信息素。當(dāng)它們碰到一個還沒有走過的路口時，就隨機地挑選一條路徑前行。與此同時釋放出與路徑長度有關(guān)的信息素。路徑越長，釋放的激索濃度越低。當(dāng)后來的螞蟻再次碰到這個路口的時候，選擇激素濃度較高路徑概率就會相對較大。這樣形成一個正反饋。最優(yōu)路徑上的激索濃度越來越大。而其它的路徑上激素濃度卻會隨著時間的流逝而消減。最終整個蟻群會找出最優(yōu)路徑。簡化螞蟻的尋食過程螞蟻從A點出發(fā)，速度相同，食物在D點，可能隨機選擇路線ABD或ACD。假設(shè)初始時每
4、條分配路線一只螞蟻，每個時間單位行走一步，本圖為經(jīng)過9個時間單位時的情形：走ABD的螞蟻到達(dá)終點，而走ACD的螞蟻剛好走到C點，為一半路程。簡化螞蟻的尋食過程本圖為從開始算起，經(jīng)過18個時間單位時的情形：走ABD的螞蟻到達(dá)終點后得到食物又返回了起點A，而走ACD的螞蟻剛好走到D點。簡化螞蟻的尋食過程假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個單位，則經(jīng)過36個時間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從D點取得了食物，此時ABD的路線往返了2趟，每一處的信息素為4個單位，而ACD的路線往返了一趟，每一處的信息素為2個
5、單位，其比值為2：1。尋找食物的過程繼續(xù)進行，則按信息素的指導(dǎo)，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個時間單位后，兩條線路上的信息素單位積累為12和4，比值為3：1。若按以上規(guī)則繼續(xù)，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經(jīng)過36個時間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。若繼續(xù)進行，則按信息素的指導(dǎo)，最終所有的螞蟻會放棄ACD路線，而都選擇ABD路線。這也就是前面所提到的正反饋效應(yīng)。蟻群算法模型的建立對螞蟻個體
6、的抽象蟻群算法是對自然界真實螞蟻覓食行為的一種模擬，因此首先必須對真實螞蟻進行抽象，而不可能也沒必要對螞蟻個體進行完全再現(xiàn)。把螞蟻能夠有效刻畫出真實蟻群中能為算法所借鑒的特征抽象出來，同時建立與算法模型無關(guān)的因素。蟻群算法模型的建立問題空間的描述蟻群算法所求解的問題空間可用一個重要的數(shù)學(xué)工具——圖（graph）來描述。尋找路徑的抽象把覓食過程抽象成算法中解的構(gòu)造過程，將信息素抽象為存在于圖的邊上的軌跡。在每一節(jié)點上人工螞蟻感知相鄰節(jié)點邊上的信息素濃度。蟻群算法模型的建立信息素?fù)]發(fā)的抽象自然界中，螞蟻留下的信息素會隨著
7、時間的推移而連續(xù)不斷的揮發(fā)。因此使算法中的信息素?fù)]發(fā)方式與螞蟻覓食過程機理相符，要使螞蟻完成一個節(jié)點的移動后，經(jīng)過一個單位時間，進行一次信息素的揮發(fā)。蟻群算法模型的建立啟發(fā)因子的引入蟻群算法的自組織性，似的系統(tǒng)的演化需要耗費較長的時間，而實際應(yīng)用時對算法運行時間的要求也是必不可少的。因此引入一個啟發(fā)因子，給蟻群算法一個初始的引導(dǎo)，增加算法的時間有效性。蟻群算法的基本步驟基本蟻群算法的優(yōu)缺點優(yōu)點較強的魯棒性、全局性、普遍性分布式計算易于與其它方法結(jié)合缺點需要較長的計算時間，容易停滯所有路徑的信息素增量，會導(dǎo)致錯誤的引導(dǎo)
8、信息素的均勻分配策略未體現(xiàn)出路段的重要性蟻群優(yōu)化算法研究進展最初的蟻群算法是螞蟻系統(tǒng),由于信息素更新方式的不同還可以細(xì)分為蟻周、蟻密、蟻量三種算法模型。但是螞蟻系統(tǒng)只能解決小規(guī)模的問題,比如說TSP問題。但是當(dāng)問題的規(guī)模增大時,比如說TSP中的城市規(guī)模增大時,算法的反應(yīng)比較遲鈍,所以產(chǎn)生了后來的蟻群系統(tǒng),優(yōu)化了螞蟻系統(tǒng)在全局的更新以及螞蟻的狀態(tài)
