【正文】 擴(kuò)展。此時(shí)，觀察 GBAS的計(jì)算過程。 0 1 48 5 24 1 485 24 0 1 48 1 48( 2) ( ( 2) )1 48 1 48 0 5 241 48 5 24 1 48 0ij????????????智能優(yōu)化計(jì)算 2022/8/27 40 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 11/12 重復(fù)外循環(huán)，由于 W2全局最優(yōu)解， GBAS只記錄第一個(gè)最優(yōu)解，因此一但得到了全局最優(yōu)解，信息素的更新將不再依賴于以群的行走路線，而只是不斷增強(qiáng)最優(yōu)路線的信息素，同時(shí)進(jìn)行揮發(fā)。 的變化僅由 決定，而與先前的狀態(tài)無關(guān)，這是一個(gè)典型的馬爾可夫過程。而對(duì)于一般以順序作為解的優(yōu)化問題，誰在第一是很重要的。 設(shè)第 s只螞蟻第 k步所走的路線為 ， 表示螞蟻從 0點(diǎn)出發(fā)，順序到達(dá) 。 ? ?| ( , )i ijA a i j A??( 1 ) { ( 1 ) | ( , ) }i ijA k a k i j A? ? ? ?( 1 )( 1 ) ,0ijilijlTakjTakPjT???? ?? ?? ???? ??( 1 ) ( 1 )( 1 ) ( 1 )( 1 ) ,0ij ijil ilijlTkkkka k j TjT?????????? ??????? ? ??? ????智能優(yōu)化計(jì)算 2022/8/27 63 每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定 需要記憶的信息 2/3 第二部分需要記憶的信息是每個(gè)螞蟻的記憶表中存儲(chǔ)著的自身的歷史信息，這一部分主要由算法的中的 記憶，表示螞蟻已經(jīng)行走過的節(jié)點(diǎn)。離線方式（同步更新方式）的主要思想是在若干只螞蟻完成 n個(gè)城市的訪問后，統(tǒng)一對(duì)殘留信息進(jìn)行更新處理。 Q為一個(gè)常數(shù)，該算法名為蟻環(huán)算法（ antcycle algotithm） ,特點(diǎn)是行走的路徑越短對(duì)應(yīng)保存的信息素的值就越大。 以上三種算法中，蟻環(huán)算法效果最好，因?yàn)樗玫氖侨中畔?，而其余兩種算法用的是局部信息。 用蟻群算法在分層圖模型的基礎(chǔ)上求解動(dòng)態(tài) RWA 問題。 智能優(yōu)化計(jì)算 2022/8/27 78 蟻群優(yōu)化算法 — 參考書 2 ? 蟻群算法及其應(yīng)用 李士勇 哈工大出版社 國(guó)內(nèi)首部蟻群算法的專著，系統(tǒng)地闡述蟻群算法的基本原理、基本蟻群算法及改進(jìn)算法，蟻群算法與遺傳、免疫算法的融合，自適應(yīng)蟻群算法，并行蟻群算法，蟻群算法的收斂性與理論模型及其在優(yōu)化問題中的應(yīng)用。當(dāng)一只螞蟻遇到一個(gè)數(shù)據(jù)時(shí)即拾起并繼續(xù)行走，在行走過程中，如果遇到附近的數(shù)據(jù)與背負(fù)的數(shù)據(jù)相似性高于設(shè)置的標(biāo)準(zhǔn)時(shí)則將數(shù)據(jù)放置在該位置，繼續(xù)移動(dòng)。由于 RWA 問題是 NPC 問題 ,文獻(xiàn)中大多將 RWA 問題拆分成路由和波長(zhǎng)分配兩個(gè)子問題分別加以解決。實(shí)際上這種方式等價(jià)于蟻群離線方式中只有一只螞蟻。 其中， 為第 k1次循環(huán)后的的信息素的痕跡值。 Dorigo在求解 TSP問題時(shí)，推薦參數(shù)的最佳設(shè)置為： 。把 GBAS算法中步驟 3中的 改為 ，若滿足此條件則替換當(dāng)前最好解為 ， 對(duì) W上的弧進(jìn)行信息素的加強(qiáng)，其他弧進(jìn)行信息素的揮發(fā)。 ()L s N?智能優(yōu)化計(jì)算 2022/8/27 59 解的表達(dá)形式與算法的實(shí)現(xiàn) 2/4 算法的實(shí)現(xiàn) 例： 01背包問題的解順序表達(dá)形式與算法實(shí)現(xiàn)。智能優(yōu)化計(jì)算 2022/8/27 54 其他算法及收斂性分析 2/4 ij( 1 )( 1 )p0( 1 ) { ( 1 ) | ( , ) }( 1 ) ( 1 )1.ijillTi ijij ijakjTakjTA k a k i j Akk??????????? ?????? ? ? ????i ij式螞蟻轉(zhuǎn)移概率更一般的規(guī)則由存儲(chǔ)在每個(gè)節(jié)點(diǎn)的路由表數(shù)據(jù)結(jié)構(gòu)A ={a |(i ,j) A} 決定，即轉(zhuǎn)移概率為其中， 取決于三部分因素，T 是從i可 以直接到達(dá)的節(jié)點(diǎn)結(jié)合。由于螞蟻的一步轉(zhuǎn)移 概率是隨機(jī)的，從 到 也是隨機(jī)的，是一個(gè)馬爾可夫過程。4 : , ( 4) 。這種增強(qiáng)過程中進(jìn)行的 信息素更新稱為離線的信息素更新。用如下公式對(duì) W路徑 上的信息素痕跡加強(qiáng)，對(duì)其他路徑上的信息素進(jìn)行揮發(fā)。否則使螞蟻 s從起點(diǎn) 出發(fā)，用 表示螞蟻 s行走的城市集合，初始 為空集， 。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類參數(shù)決定： 1 信息素值 也稱信息素痕跡。 人工蟻群中把具有簡(jiǎn)單功能的工作單元看作螞蟻。 智能優(yōu)化計(jì)算 2022/8/27 25 簡(jiǎn)化的螞蟻尋食過程 3/3 假設(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。與此同時(shí)釋放出與路徑長(zhǎng)度有關(guān)的信息素。 智能優(yōu)化計(jì)算 2022/8/27 20 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 5/5 許多研究者將 ACO用于了武器攻擊目標(biāo)分配和優(yōu)化問題、車輛運(yùn)行路徑規(guī)劃、區(qū)域性無線電頻率自動(dòng)分配、 Bayesian works的訓(xùn)練和集合覆蓋等應(yīng)用優(yōu)化問題。Lumer和 Faieta將 Deneubourg提出將蟻巢分類模型應(yīng)用于數(shù)據(jù)聚類分析。 智能優(yōu)化計(jì)算 2022/8/27 17 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 2/5 蟻群算法在電信路由優(yōu)化中已取得了一定的應(yīng)用成果。與“精英策略”相似，在此算法中總是更新更好進(jìn)程上的信息素，選擇的標(biāo)準(zhǔn)是其行程長(zhǎng)度 決定的排序，且每個(gè)螞蟻放置信息素的強(qiáng)度通過下式中的排序加權(quán)處理確定，其中，ｗ為每次迭代后放置信息素的螞蟻總數(shù)。AntQ將螞蟻算法和一種增強(qiáng)型學(xué)習(xí)算法 Qlearning有機(jī)的結(jié)合了起來。在 Antdensity和 Antquantity中螞蟻在兩個(gè)位置節(jié)點(diǎn)間每移動(dòng)一次后即更新信息素，而在 Antcycle中當(dāng)所有的螞蟻都完成了自己的行程后才對(duì)信息素進(jìn)行更新，而且每個(gè)螞蟻所釋放的信息素被表達(dá)為反映相應(yīng)行程質(zhì)量的函數(shù)。已完成的群智能理論和應(yīng)用方法研究證明群智能方法是一種能夠有效解決大多數(shù)全局優(yōu)化問題的新方法。用該方法求解 TSP問題、分配問題、 jobshop調(diào)度問題，取得了較好的試驗(yàn)結(jié)果．雖然研究時(shí)間不長(zhǎng)，但是現(xiàn)在的研究顯示出，蟻群算法在求解復(fù)雜優(yōu)化問題（特別是離散優(yōu)化問題）方面有一定優(yōu)勢(shì)，表明它是一種有發(fā)展前景的算法． 智能優(yōu)化計(jì)算 2022/8/27 5 蟻群優(yōu)化算法應(yīng)用領(lǐng)域 這種方法能夠被用于解決大多數(shù)優(yōu)化問題或者能夠轉(zhuǎn)化為優(yōu)化求解的問題?，F(xiàn)在其應(yīng)用領(lǐng)域已擴(kuò)展到多目標(biāo)優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識(shí)別、電信 QoS管理、生物系統(tǒng)建模、流程規(guī)劃、信號(hào)處理、機(jī)器人控制、決策支持以及仿真和系統(tǒng)辯識(shí)等方面，群智能理論和方法為解決這類應(yīng)用問題提供了新的途徑 。更為重要是，群智能潛在的并行性和分布式特點(diǎn)為處理大量的以數(shù)據(jù)庫(kù)形式存在的數(shù)據(jù)提供了技術(shù)保證。通過與其它各種通用的啟發(fā)式算法相比，在不大于 75城市的TSP中，這三種基本算法的求解能力還是比較理想的，但是當(dāng)問題規(guī)模擴(kuò)展時(shí)， AS的解題能力大幅度下降。 ACS與 AS之間存在三方面的主要差異：首先， ACS采用了更為大膽的行為選擇規(guī)則；其次，只增強(qiáng)屬于全局最優(yōu)解的路徑上的信息素。 智能優(yōu)化計(jì)算 2022/8/27 15 7/7 這種算法求解 TSP的能力與 AS、精英策略 AS、遺傳算法和模擬退火算法進(jìn)行了比較。 HP公司和英國(guó)電信公司在 90年代中后期都開展了這方面的研究，設(shè)計(jì)了蟻群路由算法（ Ant Colony Routing, ACR）。其基本思想是將待聚類數(shù)據(jù)隨機(jī)地散布到一個(gè)二維平面內(nèi)，然后將虛擬螞蟻分布到這個(gè)空間內(nèi)，并以隨機(jī)方式移動(dòng)，當(dāng)一只螞蟻遇到一個(gè)待聚類數(shù)據(jù)時(shí)即將之拾起并繼續(xù)隨機(jī)運(yùn)動(dòng)，若運(yùn)動(dòng)路徑附近的數(shù)據(jù)與背負(fù)的數(shù)據(jù)相似性高于設(shè)置的標(biāo)準(zhǔn)則將其放置在該位置，然后繼續(xù)移動(dòng)，重復(fù)上述數(shù)據(jù)搬運(yùn)過程。 Costa和 Herz還提出了一種 AS在規(guī)劃問題方面的擴(kuò)展應(yīng)用 ——圖著色問題，并取得了可與其他啟發(fā)式算法相比的效果。路徑越長(zhǎng)，釋放的激索濃度越低 .當(dāng)后來的螞蟻再次碰到這個(gè)路口的時(shí)候．選擇激素濃度較高路徑概率就會(huì)相對(duì)較大。 尋找食物的過程繼續(xù)進(jìn)行，則按信息素的指導(dǎo)，蟻群在 ABD路線上增派一只螞蟻（共 2只），而 ACD路線上仍然為一只螞蟻。二者的 相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。 2 可見度，即先驗(yàn)值。 STEP 2 (內(nèi)循環(huán) ) 按螞蟻 的順序分別計(jì)算。 得到新的 ，重復(fù)步驟 STEP 1。 在 STEP 3中，蟻群永遠(yuǎn)記憶到目前為止的最優(yōu)解。W A B C D A f WW A C D B A f WW A D C B A f WW A B D C A f W? ? ? ? ?? ? ? ? ?? ? ? ? ?? ? ? ? ?第一只第二只第三只第四只智能優(yōu)化計(jì)算 2022/8/27 38 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 9/12 按算法步驟 3的信息素更新規(guī)則，得到更新矩陣 這是第一次外循環(huán)結(jié)束的狀態(tài)。 ( ) ( ( ) | ( , ) )ijk k i j A???? ()Wk? ?( 1 ) , ( 1 )k W k? ??? ?( ) , ( )k W k?? ?( 1 ) , ( 1 )k W k? ?? ? ?( ) , ( )k W k?智能優(yōu)化計(jì)算 2022/8/27 42 一般蟻群算法的框架 一般蟻群算法的框架和 GBAS基本相同，有三個(gè)組成部分： 蟻群的活動(dòng)