【文章內(nèi)容簡介】 。29 蟻群算法與 TSP問題 2/3 TSP問題的人工蟻群算法中，假設(shè) m只螞蟻在圖的相鄰節(jié)點間移動，從而協(xié)作異步地得到問題的解。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類參數(shù)決定： 1 信息素值 也稱信息素痕跡。 2 可見度，即先驗值。 信息素的更新方式有 2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進行減少，模擬自然蟻群的信息素隨時間揮發(fā)的過程；二是增強，給評價值 “好 ”(有螞蟻走過 )的邊增加信息素。30 蟻群算法與 TSP問題 3/3 螞蟻向下一個目標(biāo)的運動是通過一個隨機原則來實現(xiàn)的，也就是運用當(dāng)前所在節(jié)點存儲的信息，計算出下一步可達節(jié)點的概率，并按此概率實現(xiàn)一步移動，逐此往復(fù)，越來越接近最優(yōu)解。 螞蟻在尋找過程中，或者找到一個解后，會評估該解或解的一部分的優(yōu)化程度，并把評價信息保存在相關(guān)連接的信息素中。31 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 1/12初始的蟻群算法是基于圖的蟻群算法， graphbased ant system,簡稱為 GBAS，是由 Gutjahr W J在 2022年的Future Generation Computing Systems提出的，課本的參考文獻 2。算法步驟如下：STEP 0 對 n個城市的 TSP問題，城市間的距離矩陣為 ，給 TSP圖中的每一條弧 賦信息素初值 ，假設(shè) m只螞蟻在工作，所有螞蟻都從同一城市 出發(fā)。當(dāng)前最好解是 。32 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 2/12STEP 1 （外循環(huán)）如果滿足算法的停止規(guī)則，則停止計算并輸出計算得到的最好解。否則使螞蟻 s從起點 出發(fā)，用 表示螞蟻 s行走的城市集合，初始 為空集， 。STEP 2 (內(nèi)循環(huán) ) 按螞蟻 的順序分別計算。當(dāng)螞蟻在城市 i，若 完成第 s只螞蟻的計算。否則，若，則以概率 ， 到達 j， ；若則到達 重復(fù) STEP 2。33 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 3/12STRP 3 對 ，若 ，按 中城市的順序計算路徑程度；若 ，路徑長度置為一個無窮大值（即不可達）。比較 m只螞蟻中的路徑長度，記走最短路徑的螞蟻為 t。若 ，則 。用如下公式對 W路徑上的信息素痕跡加強，對其他路徑上的信息素進行揮發(fā)。 得到新的 ，重復(fù)步驟 STEP 1。34 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 4/12在 STEP 3 中，揮發(fā)因子 對于一個固定的 ，滿足并且 經(jīng)過 k次揮發(fā)，非最優(yōu)路徑的信息素逐漸減少至消失。35 — 基于圖的蟻群系統(tǒng)（ GBAS） 5/12 以上算法中，在螞蟻的搜尋過程中，以信息素的概率分布來決定從城市i到城市 j的轉(zhuǎn)移。 算法中包括信息素更新的過程 1 信息素揮發(fā)（ evaporation） 信息素痕跡的揮發(fā)過程是每個連接上的信息素痕跡的濃度自動逐漸減弱的過程，由 表示，這個揮發(fā)過程主要用于避免算法過快地向局部最優(yōu)區(qū)域集中，有助于搜索區(qū)域的擴展。 2 信息素增強（ reinforcement）增強過程是蟻群優(yōu)化算法中可選的部分，稱為離線更新方式（還有在線更新方式）。這種方式可以實現(xiàn)由單個螞蟻無法實現(xiàn)的集中行動。也就是說，增強過程體現(xiàn)在觀察蟻群（ m只螞蟻）中每只螞蟻所找到的路徑，并選擇其中最優(yōu)路徑上的弧進行信息素的增強，揮發(fā)過程是所有弧都進行的，不于螞蟻數(shù)量相關(guān)。這種增強過程中進行的信息素更新稱為離線的信息素更新。 在 STEP 3中，蟻群永遠記憶到目前為止的最優(yōu)解。36圖的蟻群系統(tǒng)（ GBAS） 6/12可以驗證，下式滿足：即 是一個隨機矩陣。四個城市的非對稱 TSP問題，距離矩陣和城市圖示如下：37 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 7/12假設(shè)共 4只螞蟻，所有螞蟻都從城市 A出發(fā)，揮發(fā)因子 。此時，觀察 GBAS的計算過程。 矩陣共有 12條弧，初始信息素記憶矩陣為：38 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 8/12執(zhí)行 GBAS算法的步驟 2，假設(shè)螞蟻的行走路線分別為：當(dāng)前最優(yōu)解為，這個解是截止到當(dāng)前的最優(yōu)解，碰巧是實際最優(yōu)解39 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 9/12按算法步驟 3的信息素更新規(guī)則，得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。40 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 10/12重復(fù)外循環(huán)，由于上一次得到的 W2已經(jīng)是全局最優(yōu)解，因此按算法步驟 3的信息素更新規(guī)則，無論螞蟻如何行走，都只是對 W2路線上的城市信息素進行增強，其他的城市信息素進行揮發(fā)。得到更新矩陣這是第一次外循環(huán)結(jié)束的狀態(tài)。41 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 11/12重復(fù)外循環(huán)，由于 W2全局最優(yōu)解， GBAS只記錄第一個最優(yōu)解，因此一但得到了全局最優(yōu)解，信息素的更新將不再依賴于以群的行走路線，而只是不斷增強最優(yōu)路線的信息素，同時進行揮發(fā)。第三次外循環(huán)后得到的信息素矩陣為：42 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 12/12 螞蟻以一定的概率從城市 i到城市 j進行轉(zhuǎn)移，信息素的更新在 STEP 3 完成，并隨 K而變化。假設(shè)第 K次外循環(huán)后得到信息素矩陣 ，得到當(dāng)前最優(yōu)解 。第 K次循環(huán)前的信息素和最優(yōu)解為 ，經(jīng)過第 K次外循環(huán)后，得到 。由于螞蟻的一步轉(zhuǎn)移概率是隨機的，從 到 也是隨機的，是一個馬爾可夫過程。43 一般蟻群算法的框架一般蟻群算法的框架和 GBAS基本相同，有三個組成部分： 蟻群的活動； 信息素的揮發(fā)； 信息素的增強；主要體現(xiàn)在前面的算法中步驟 2和步驟 3中的轉(zhuǎn)移概率公式和信息素更新公式。44 蟻群優(yōu)化算法 — 算法模型和收斂性分析 馬氏過程的收斂定義 GBAS算法的