1、 蟻群算法Ant Colony Algorithm 1精選PPT1 蟻群優化算法概念1.1 蟻群算法原理1.2 簡化的螞蟻尋食過程1.3 蟻群現象1.4 螞蟻簡單規則的兩個方面1.4 蟻群算法與TSP問題1.5 初始的蟻群優化算法基于圖的蟻群系統（GBAS）2精選PPT1.1 蟻群算法原理 蟻群算法是對自然界螞蟻的尋徑方式進行模似而得出的一種仿生算法。螞蟻在運動過程中，能夠在它所經過的路徑上留下一種稱之為外激素(pheromone)的物質進行信息傳遞，而且螞蟻在運動過程中能夠感知這種物質，并以此指導自己的運動方向，因此由大量螞蟻組成的蟻群集體行為便表現出一種信息正反饋現象：某一路徑上走過的螞蟻

2、越多，則后來者選擇該路徑的概率就越大。3精選PPT為了說明蟻群算法的原理，先簡要介紹一下螞 蟻搜尋食物的具體過程： 在蟻群尋找食物時，它們總能找到一條從食物到巢穴之間的最優路徑。這是因為螞蟻在尋找路徑時會在路徑上釋放出一種特殊的信息素。當它們碰到一個還沒有走過的路口時就隨機地挑選一條路徑前行。與此同時釋放出與路徑長度有關的信息素。路徑越長，釋放的激索濃度越低.當后來的螞蟻再次碰到這個路口的時候選擇激素濃度較高路徑概率就會相對較大。這樣形成一個正反饋。最優路徑上的激索濃度越來越大而其它的路徑上激素濃度卻會隨著時間的流逝而消減。最終整個蟻群會找出最優路徑。4精選PPT1.2 簡化的螞蟻尋食過程螞蟻

3、從A點出發，速度相同，食物在D點，可能隨機選 擇路線ABD或ACD。假設初始時每條分配路線一只螞 蟻，每個時間單位行走一步，本圖為經過9個時間單位 時的情形：走ABD的螞蟻到達終點，而走ACD的螞蟻 剛好走到C點，為一半路程。5精選PPT本圖為從開始算起，經過18個時間單位時的情形：走 ABD的螞蟻到達終點后得到食物又返回了起點A，而 走ACD的螞蟻剛好走到D點。6精選PPT 假設螞蟻每經過一處所留下的信息素為一個單位，則經過36個時間單位后，所有開始一起出發的螞蟻都經過不同路徑從D點取得了食物，此時ABD的路線往返了2趟，每一處的信息素為4個單位，而 ACD的路線往返了一趟，每一處的信息素為

4、2個單位，其比值為2：1。 尋找食物的過程繼續進行，則按信息素的指導，蟻群在ABD路線上增派一只螞蟻（共2只），而ACD路線上仍然為一只螞蟻。再經過36個時間單位后，兩條線路上的信息素單位積累為12和4，比值為3：1。7精選PPT 若按以上規則繼續，蟻群在ABD路線上再增派一只螞蟻（共3只），而ACD路線上仍然為一只螞蟻。再經過36個時間單位后，兩條線路上的信息素單位積累為24和6，比值為4：1。 若繼續進行，則按信息素的指導，最終所有的螞蟻會放棄ACD路線，而都選擇ABD路線。這是正反饋效應。8精選PPT信息素的更新方式有2種： 一是揮發：也就是所有路徑上的信息素以一定的比率進行減少，模擬自

5、然蟻群的信息素隨時間揮發的過程； 二是增強：給評價值“好”(有螞蟻走過)的邊增加信息素。9精選PPT1.3 蟻群現象螞蟻正常行進，突然環境變化，增加了障礙物10精選PPT蟻群現象：螞蟻以同等概率選擇各條路徑，緊接著，隨著時間的增 加較短路徑信息濃度高，選擇該路徑的螞蟻逐漸增多。11精選PPT蟻群現象：螞蟻最終繞過障礙物找到最優路徑12精選PPT1.4 螞蟻簡單規則的兩個方面：1多樣性：螞蟻在覓食的時候路線不一，隨 機性的向著某個方向行走，打破常規，進行創新。2正反饋：優化的路線不斷被保存并加大自身概率，保證了相對優良的信息能夠被保存下來。 多樣性保證了系統的創新能力，正反饋保證了優良特性能夠得

6、到強化，兩者要恰到好處的結合。 13精選PPT1.5 蟻群算法在TSP問題中的應用旅行商問題，即TSP問題又譯為旅行推銷員問題、貨郎擔問題，是數學領域中著名問題之一。假設有一個旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路經的限制是每個城市只能拜訪一次，而且最后要回到原來出發的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。 14精選PPT算法步驟如下：15精選PPT16精選PPT17精選PPT18精選PPT按 的不同取法，可形成三種類型的螞蟻算法模型：（1）Ant-Circle System模型，有式中，Q為常量， 為第k只螞蟻在本次循環中所走路徑的長度。（2）Ant-Quantity System模型19精選PPT（3）Ant-Density System模型 很明顯在后兩種模型中，利用的都是局部信息，而第一種模型利用的是整體信息。這三種模型在求解不同問題時各有優勢。20精選PPT21精選PPT22精選PPT23精選PPT24精選PPT這樣循環，最終得到了最優路線。25精選PPT實際的概率公式：定義 為他