【文章內(nèi)容簡(jiǎn)介】 。Date48 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 ACO還在許多經(jīng)典組合優(yōu)化問題中獲得了成功的應(yīng)用，如二次規(guī)劃問題（ QAP）、 機(jī)器人路徑規(guī)劃、作業(yè)流程規(guī)劃、圖著色（ Graph Coloring） 等問題。 經(jīng)過多年的發(fā)展， ACO已成為能夠有效解決實(shí)際二次規(guī)劃問題的幾種重要算法之一。 AS在作業(yè)流程計(jì)劃（ Jobshop Scheduling） 問題中的應(yīng)用實(shí)例已經(jīng)出現(xiàn)，這說明了 AS在此領(lǐng)域的應(yīng)用潛力。利用 MAXMIN AS解決 PAQ也取得了比較理想的效果，并通過實(shí)驗(yàn)中的計(jì)算數(shù)據(jù)證明采用該方法處理 PAQ比較早的 SA算法更好，且與禁忌搜索算法性能相當(dāng)。利用 ACO實(shí)現(xiàn)對(duì)生產(chǎn)流程和特料管理的綜合優(yōu)化，并通過與遺傳、模擬退火和禁忌搜索算法的比較證明了 ACO的工程應(yīng)用價(jià)值。Date49 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 許多研究者將 ACO用于了武器攻擊目標(biāo)分配和優(yōu)化問題、車輛運(yùn)行路徑規(guī)劃、區(qū)域性無線電頻率自動(dòng)分配、 Bayesian works的訓(xùn)練和集合覆蓋等應(yīng)用優(yōu)化問題。 Costa和 Herz還提出了一種 AS在規(guī)劃問題方面的擴(kuò)展應(yīng)用 —— 圖著色問題，并取得了可與其他啟發(fā)式算法相比的效果。Date50 蟻群優(yōu)化算法概念 蟻群算法原理 簡(jiǎn)化的螞蟻尋食過程 自然蟻群與人工蟻群算法 蟻群算法與 TSP問題 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 一般蟻群算法的框架Date51 蟻群算法原理 蟻群算法是對(duì)自然界螞蟻的尋徑方式進(jìn)行模似而得出的一種仿生算法。螞蟻在運(yùn)動(dòng)過程中，能夠在它所經(jīng)過的路徑上留下一種稱之為外激素(pheromone)的物質(zhì)進(jìn)行信息傳遞，而且螞蟻在運(yùn)動(dòng)過程中能夠感知這種物質(zhì)，并以此指導(dǎo)自己的運(yùn)動(dòng)方向，因此由大量螞蟻組成的蟻群集體行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。 為了說明蟻群算法的原理，先簡(jiǎn)要介紹一下螞蟻搜尋食物的具體過程。在蟻群尋找食物時(shí)，它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因?yàn)槲浵佋趯ふ衣窂綍r(shí)會(huì)在路徑上釋放出一種特殊的信息素。當(dāng)它們碰到一個(gè)還沒有走過的路口時(shí)．就隨機(jī)地挑選一條路徑前行。與此同時(shí)釋放出與路徑長(zhǎng)度有關(guān)的信息素。路徑越長(zhǎng)，釋放的激索濃度越低 .當(dāng)后來的螞蟻再次碰到這個(gè)路口的時(shí)候．選擇激素濃度較高路徑概率就會(huì)相對(duì)較大。這樣形成一個(gè)正反饋。最優(yōu)路徑上的激索濃度越來越大．而其它的路徑上激素濃度卻會(huì)隨著時(shí)間的流逝而消減。最終整個(gè)蟻群會(huì)找出最優(yōu)路徑。Date52 簡(jiǎn)化的螞蟻尋食過程螞蟻從 A點(diǎn)出發(fā)，速度相同，食物在 D點(diǎn)，可能隨機(jī)選擇路線ABD或 ACD。 假設(shè)初始時(shí)每條分配路線一只螞蟻，每個(gè)時(shí)間單位行走一步，本圖為經(jīng)過 9個(gè)時(shí)間單位時(shí)的情形：走 ABD的螞蟻到達(dá)終點(diǎn)，而走 ACD的螞蟻剛好走到 C點(diǎn)，為一半路程。Date53 簡(jiǎn)化的螞蟻尋食過程本圖為從開始算起，經(jīng)過 18個(gè)時(shí)間單位時(shí)的情形：走 ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn) A， 而走 ACD的螞蟻剛好走到D點(diǎn)。Date54 簡(jiǎn)化的螞蟻尋食過程 假設(shè)螞蟻每經(jīng)過一處所留下的信息素為一個(gè)單位，則經(jīng)過 36個(gè)時(shí)間單位后，所有開始一起出發(fā)的螞蟻都經(jīng)過不同路徑從 D點(diǎn)取得了食物，此時(shí) ABD的路線往返了 2趟，每一處的信息素為 4個(gè)單位，而 ACD的路線往返了一趟，每一處的信息素為 2個(gè)單位，其比值為 2： 1。 尋找食物的過程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在 ABD路線上增派一只螞蟻（共 2只），而 ACD路線上仍然為一只螞蟻。再經(jīng)過 36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為 12和 4，比值為 3： 1。 若按以上規(guī)則繼續(xù)，蟻群在 ABD路線上再增派一只螞蟻（共 3只），而 ACD路線上仍然為一只螞蟻。再經(jīng)過 36個(gè)時(shí)間單位后，兩條線路上的信息素單位積累為 24和 6，比值為 4： 1。 若繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，最終所有的螞蟻會(huì)放棄 ACD路線，而都選擇ABD路線。這也就是前面所提到的正反饋效應(yīng)。Date55 自然蟻群與人工蟻群算法 基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問題，可以構(gòu)造人工蟻群，來解決最優(yōu)化問題，如 TSP問題。 人工蟻群中把具有簡(jiǎn)單功能的工作單元看作螞蟻。二者的相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。較短路徑的信息素濃度高，所以能夠最終被所有螞蟻選擇，也就是最終的優(yōu)化結(jié)果。 兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已經(jīng)訪問過的節(jié)點(diǎn)。同時(shí)，人工蟻群再選擇下一條路徑的時(shí)候是按一定算法規(guī)律有意識(shí)地尋找最短路徑，而不是盲目的。例如在 TSP問題中，可以預(yù)先知道當(dāng)前城市到下一個(gè)目的地的距離。Date56TSP問題表示為一個(gè) N個(gè)城市的有向圖 G=（ N， A），其中 城市之間距離目標(biāo)函數(shù)為 ，其中 為城市 1,2， …n 的一個(gè)排列， 。 蟻群算法與 TSP問題Date57 蟻群算法與 TSP問題 TSP問題的人工蟻群算法中，假設(shè) m只螞蟻在圖的相鄰節(jié)點(diǎn)間移動(dòng)，從而協(xié)作異步地得到問題的解。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類參數(shù)決定： 1 信息素值 也稱信息素痕跡。 2 可見度，即先驗(yàn)值。 信息素的更新方式有 2種，一是揮發(fā)，也就是所有路徑上的信息素以一定的比率進(jìn)行減少，模擬自然蟻群的信息素隨時(shí)間揮發(fā)的過程；二是增強(qiáng)，給評(píng)價(jià)值 “好 ”(有螞蟻?zhàn)哌^ )的邊增加信息素。Date58 蟻群算法 與 TSP問題 螞蟻向下一個(gè)目標(biāo)的運(yùn)動(dòng)是通過一個(gè)隨機(jī)原則來實(shí)現(xiàn)的，也就是運(yùn)用當(dāng)前所在節(jié)點(diǎn)存儲(chǔ)的信息，計(jì)算出下一步可達(dá)節(jié)點(diǎn)的概率，并按此概率實(shí)現(xiàn)一步移動(dòng)，逐此往復(fù)，越來越接近最優(yōu)解。 螞蟻在尋找過程中，或者找到一個(gè)解后，會(huì)評(píng)估該解或解的一部分的優(yōu)化程度，并把評(píng)價(jià)信息保存在相關(guān)連接的信息素中。Date59 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS）初始的蟻群算法是基于圖的蟻群算法， graphbased ant system,簡(jiǎn)稱為 GBAS， 是由 Gutjahr W J在 2022年的Future Generation Computing Systems提出的 .算法步驟如下：STEP 0 對(duì) n個(gè)城市的 TSP問題，城市間的距離矩陣為 ，給 TSP圖中的每一條弧 賦信息素初值 ，假設(shè) m只螞蟻在工作，所有螞蟻都從同一城市 出發(fā)。當(dāng)前最好解是 。Date60 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS）STEP 1 （ 外循環(huán)）如果滿足算法的停止規(guī)則，則停止計(jì)算并輸出計(jì)算得到的最好解。否則使螞蟻 s從起點(diǎn) 出發(fā)，用 表示螞蟻 s行走的城市集合，初始 為空集， 。STEP 2 (內(nèi)循環(huán) ) 按螞蟻 的順序分別計(jì)算。當(dāng)螞蟻在城市 i， 若 完成第 s只螞蟻的計(jì)算。否則，若，則以概率 ， 到達(dá) j， ；若則到達(dá) 重復(fù) STEP 2。Date61 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS）STRP 3 對(duì) ，若 ，按 中城市的順序計(jì)算路徑程度；若 ，路徑長(zhǎng)度置為一個(gè)無窮大值（即不可達(dá)）。比較 m只螞蟻中的路徑長(zhǎng)度，記走最短路徑的螞蟻為 t。若 ，則 。用如下公式對(duì) W路徑上的信息素痕跡加強(qiáng)，對(duì)其他路徑上的信息素進(jìn)行揮發(fā)。 得到新的 ，重復(fù)步驟 STEP 1。Date62 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS）在 STEP 3 中，揮發(fā)因子 對(duì)于一個(gè)固定的 ，滿足并且 經(jīng)過 k次揮發(fā)，非最優(yōu)路徑的信息素逐漸減少至消失。Date63 — 基于圖的蟻群系統(tǒng) （ GBAS） 以上算法中，在螞蟻的搜尋過程中，以信息素的概率分布來決定從城市i到城市 j的轉(zhuǎn)移。 算法中包括信息素更新的過程 1 信息素?fù)]發(fā)（ eva