【正文】 誰在第一是很重要的。 定義 ：若一個馬爾可夫過程 ，對任意給定的 滿足 則稱馬爾可夫過程 依概率 1收斂到 。第 s只螞蟻在第 k輪轉(zhuǎn)移只由 決定，這個螞蟻行走的路徑和 一起，共同決定了 ，再通過信息素的更新原則可以進一步得到 。34 一般蟻群算法的框架一般蟻群算法的框架和 GBAS基本相同，有三個組成部分：n 蟻群的活動n 信息素的揮發(fā)n 信息素的增強主要體現(xiàn)在前面的算法中步驟 2和步驟 3中的轉(zhuǎn)移概率公式和信息素更新公式。第 K次循環(huán)前的信息素和最優(yōu)解為 ，經(jīng)過第 K次外循環(huán)后，得到 。第三次外循環(huán)后得到的信息素矩陣為：33 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 12/12 螞蟻以一定的概率從城市 i到城市 j進行轉(zhuǎn)移，信息素的更新在 STEP 3 完成，并隨 K而 變化。得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。 矩陣共有 12條弧，初始信息素記憶矩陣為：29 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 8/12執(zhí)行 GBAS算法的步驟 2，假設(shè)螞蟻的行走路線分別為：當前最優(yōu)解為 ，這個解是截止到當前的最優(yōu)解，碰巧是實際最優(yōu)解30 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 9/12按算法步驟 3的信息素更新規(guī)則，得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。四個城市的非對稱 TSP問題，距離矩陣和城市圖示如下：28 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng) （ GBAS） 7/12假設(shè)共 4只螞蟻，所有螞蟻都從城市 A出發(fā)，揮發(fā)因子 。 在 STEP 3中，蟻群永遠記憶到目前為止的最優(yōu)解。也就是說，增強過程體現(xiàn)在觀察蟻群（ m只螞蟻）中每只螞蟻所找到的路徑，并選擇 其中最優(yōu)路徑上的弧 進行信息素的增強，揮發(fā)過程是所有弧都進行的，不于螞蟻數(shù)量相關(guān)。 2 信息素增強（ reinforcement） 增強過程是蟻群優(yōu)化算法中可選的部分，稱為離線更新方式（還有在線更新方式）。26 — 基于圖的蟻群系統(tǒng) （ GBAS） 5/12 以上算法中，在螞蟻的搜尋過程中，以信息素的概率分布來決定從城市i到城市 j的轉(zhuǎn)移。 得到新的 ，重復(fù)步驟 STEP 1。若 ，則 。 24 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 3/12STRP 3 對 ， 若 按 中城市的順序計算路徑程度；若 ，路徑長度置為一個無窮大值（即不可達）。當螞蟻在城市 i， 若 完成第 s只螞蟻的計算。否則使螞蟻 s從起點 出發(fā)，用 表示螞蟻 s已經(jīng)過的城市集合，初始 為空， 。算法步驟如下：STEP 0 對 n個城市的 TSP問題，城市間的距離矩陣為 ，給 TSP圖中的每一條弧 賦信息素初值 ，假設(shè) m只螞蟻在工作，所有螞蟻都從同一城市 出發(fā)。螞蟻在尋找過程中，或者找到一個解后，會評估該解或解的一部分的優(yōu)化程度，并把評價信息保存在相關(guān)連接的信息素中。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類參數(shù)決定：1 信息素值 也稱信息素痕跡2 可見度，即先驗值信息素的更新方式：1 揮發(fā)，也就是所有路徑上的信息素以一定的比率進行減少，模擬自然蟻群的信息素隨時間揮發(fā)的過程；2 增強，給評價值 “好 ”(有螞蟻走過 )的邊增加信息素。19 蟻群算法與 TSP問題 1/3TSP問題表示為一個 N個城市的有向圖 G=（ N， A），其中 城市之間距離目標函數(shù)為 ，其中 為城市 1,2， …, n的一個排列， 。同時，人工蟻群再選擇下一條路徑的時候是按一定算法規(guī)律有意識地尋找最短路徑，而不是盲目的。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。人工蟻群中把具有簡單功能的工作單元看作螞蟻。再經(jīng)過 36個時間單位后，兩條線路上的信息素單位積累為 24和 6，比值為 4： 1。再經(jīng)過 36個時間單位后，兩條線路上的信息素單位積累為 12和 4，比值為 3： 1。17 簡化的螞蟻尋食過程 3/3假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個單位，則經(jīng)過36個時間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從 D點取得了食物，此時 ABD的路線往返了 2趟，每一處的信息素為4個單位，而 ACD的路線往返了一趟，每一處的信息素為 2個單位，其比值為 2： 1。 假設(shè)初始時每條分配路線一只螞蟻，每個時間單位行走一步，本圖為經(jīng)過 9個時間單位時的情形：走 ABD的螞蟻到達終點，而走 ACD的螞蟻剛好走到 C點，為一半路程。最終整個蟻群會找出最優(yōu)路徑。這樣形成一個正反饋。與此同時釋放出與路徑長度有關(guān)的信息素。螞蟻能夠在它所經(jīng)過的路徑上留下一種稱之為 外激素 (pheromone)的物質(zhì)進行信息傳遞，螞蟻在運動過程中能夠感知以此指導(dǎo)自己的運動方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。 Costa和 Herz還提出了一種 AS在規(guī)劃問題方面的擴展應(yīng)用 —— 圖著色問題，并取得了可與其他啟發(fā)式算法相比的效果。利用 ACO實現(xiàn)對生產(chǎn)流程和特料管理的綜合優(yōu)化，并通過與遺傳、模擬退火和禁忌搜索算法的比較證明了 ACO的工程應(yīng)用價值。 AS在作業(yè)流程計劃（Jobshop Scheduling） 問題中的應(yīng)用實例已經(jīng)出現(xiàn)，這說明了 AS在此領(lǐng)域的應(yīng)用潛力。11 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 4/5ACO還在許多經(jīng)典組合優(yōu)化問題中獲得了成功的應(yīng)用，如 二次規(guī)劃問題 （ QAP） 、 機器人路徑規(guī)劃 、 作業(yè)流程規(guī)劃 、 圖著色 （ Graph Coloring） 等問題。其基本思想是將待聚類數(shù)據(jù)隨機地散布到一個二維平面內(nèi)，然后將虛擬螞蟻分布到這個空間內(nèi)，并以隨機方式移動，當一只螞蟻遇到一個待聚類數(shù)據(jù)時即