【正文】 以分布的形式做少量的計(jì)算來刷新全局路由選擇信息。該算法中，蟻群中螞蟻的先后出行順序沒有相關(guān)性，但是每次循環(huán)需要記憶 m只螞蟻的行走路徑，以進(jìn)行比較選擇最優(yōu)路徑。在 GBAS中， T集合表示滿足約束條件的候選集，在背包問題的蟻群算法中由判別條件 ， 來實(shí)現(xiàn)記 憶功能。 諸如車間作業(yè)及下料等問題，他們的共同特點(diǎn)是解以一個(gè)順序表示。假設(shè)第 K次外循環(huán)后得 到信息素矩陣 ，得到當(dāng)前最優(yōu)解 。這種方式可以實(shí)現(xiàn)由單個(gè)螞 蟻無法實(shí)現(xiàn)的集中行動(dòng)。當(dāng)前最好解是 。這也就是前面所提到的正反饋效應(yīng)。這是因?yàn)槲浵佋趯ふ衣窂綍r(shí)會(huì)在路徑上釋放出一種特殊的信息素。目前這方面的應(yīng)用研究仍在升溫，因?yàn)橥ㄐ啪W(wǎng)絡(luò)的分布式信息結(jié)構(gòu)、非穩(wěn)定隨機(jī)動(dòng)態(tài)特性以及網(wǎng)絡(luò)狀態(tài)的異步演化與 ACO的算法本質(zhì)和特性非常相似。為了避免搜索停滯，路徑上的信息素濃度被限制在 [MAX， MIN ]范圍內(nèi)，另外，信息素的初始值被設(shè)為其取值上限，這樣有助于增加算法初始階段的搜索能力。而且，取得了最佳結(jié)果的 ACO是通過引入局部搜索算法實(shí)現(xiàn)的，這實(shí)際上是一些結(jié)合了標(biāo)準(zhǔn)局域搜索算法的混合型概率搜索算法，有利于提高蟻群各級(jí)系統(tǒng)在優(yōu)化問題中的求解質(zhì)量。提出了許多用以解決復(fù)雜優(yōu)化問題的新方法，如進(jìn)化規(guī)劃、進(jìn)化策略、遺傳算法等，這些算法成功地解決了一些實(shí)際問題。 智能優(yōu)化計(jì)算 2022/8/27 9 蟻群優(yōu)化算法研究現(xiàn)狀 1/7 90年代 Dorigo最早提出了蟻群優(yōu)化算法 螞蟻系統(tǒng)（ Ant System, AS）并將其應(yīng)用于解決計(jì)算機(jī)算法學(xué)中經(jīng)典的旅行商問題（ TSP）。 智能優(yōu)化計(jì)算 2022/8/27 12 4/7 再次，還引入了負(fù)反饋機(jī)制，每當(dāng)一只螞蟻由一個(gè)節(jié)點(diǎn)移動(dòng)到另一個(gè)節(jié)點(diǎn)時(shí)，該路徑上的信息素都按照如下公式被相應(yīng)的消除一部分，從而實(shí)現(xiàn)一種信息素的局部調(diào)整，以減小已選擇過的路徑再次被選擇的概率。如果一只螞蟻因?yàn)榻?jīng)過了網(wǎng)絡(luò)中堵塞的路由而導(dǎo)致了比較大的延遲，那么就對該表項(xiàng)做較大的增強(qiáng)。螞蟻在運(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)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。 若按以上規(guī)則繼續(xù)，蟻群在 ABD路線上再增派一只螞蟻（共 3只），而ACD路線上仍然為一只螞蟻。 智能優(yōu)化計(jì)算 2022/8/27 29 蟻群算法與 TSP問題 3/3 螞蟻向下一個(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)解。 k?ln1,l n ( 1 )kk kKk? ? ? ??1K?1kk??????智能優(yōu)化計(jì)算 2022/8/27 34 — 基于圖的蟻群系統(tǒng)（ GBAS） 5/12 以上算法中，在螞蟻的搜尋過程中，以信息素的概率分布來決定從城市 i到城市 j的轉(zhuǎn)移。得到更新矩陣 這是第一次外循環(huán)結(jié)束的狀態(tài)。問題中 為先驗(yàn)知識(shí) 智能優(yōu)化計(jì)算 2022/8/27 56 其他算法及收斂性分析 4/4 ( 1 ) 1 .,( ) ( 1 ) ( ): ( 1 ) ( ), ( 0 , 1 )ijij ij ijijk k i jk k kk??? ? ???????? ? ? ???ij信息素痕跡 為 時(shí)刻連接城市 和 的路徑上的信息殘留濃度為避免過多的殘留信息會(huì)淹沒全局最優(yōu)解 需要在每只螞蟻完成一次循環(huán)后對殘留信息進(jìn)行更新,削弱舊信息,(i,j)弧上的信息素在第k1個(gè)循環(huán)的變化為 (k1),則保留的信息素為然后進(jìn)行信息素的揮發(fā)其中 為信息素的衰退系數(shù).智能優(yōu)化計(jì)算 2022/8/27 57 蟻群優(yōu)化算法 — 技術(shù)問題 解的表達(dá)形式與算法的實(shí)現(xiàn) 每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定 蟻群的規(guī)模和停止規(guī)則 信息素的更改 智能優(yōu)化計(jì)算 2022/8/27 58 解的表達(dá)形式與算法的實(shí)現(xiàn) 1/4 解的表達(dá)形式 解的表達(dá)形式 基于 TSP問題的蟻群優(yōu)化算法，其解的形式是所有城市的一個(gè)排列（閉圈，這種情況下誰在第一并不重要），信息素痕跡按每個(gè)弧記錄。 第一部分信息是存在每個(gè)節(jié)點(diǎn)的路由表數(shù)據(jù)結(jié)構(gòu) ，由此決定的的轉(zhuǎn)移概率為 其中 T可以看成節(jié)點(diǎn) i的鄰域。 ( ) ( 1 ) ( 1 )ij ij ijk k k? ? ?? ? ? ? ?()ij k?( 1 ) ( ) ( )ij ij ijs s s? ? ?? ? ? ?( 1)ij s? ?智能優(yōu)化計(jì)算 2022/8/27 68 信息素的更改 3/6 TSP問題中，蟻群優(yōu)化算法根據(jù)信息素痕跡更新方式不同可以分為 不同的算法，采用離線方式，并且 時(shí)，其中 W為 t循環(huán)中 m只螞蟻所行走的最佳路線或第 t只螞蟻所行走 的一條路徑。因此 ,近年來國內(nèi)外對RWA 并行的分布式算法表現(xiàn)出極大的興趣 ,此類算法建立的基礎(chǔ)是分層圖模型 。重復(fù)以上過程即可實(shí)現(xiàn)數(shù)據(jù)聚類。 智能優(yōu)化計(jì)算 2022/8/27 70 信息素的更改 5/6 與單螞蟻離線更新方式相比，信息量記憶更小的是信息素在線更新方式，即螞蟻每走一步，馬上回溯并且更新剛剛走過的路徑上的信息素，其規(guī)則為 其中， k為螞蟻行走的第 k步。 ??1 , 5 , ? ? ?? ? ?智能優(yōu)化計(jì)算 2022/8/27 65 蟻群的規(guī)模和停止規(guī)則 一、蟻群大小 一般情況下蟻群中螞蟻的個(gè)數(shù)不超過 TSP圖中節(jié)點(diǎn)的個(gè)數(shù)。設(shè)有一個(gè)容積為 b的背包， n個(gè)尺寸分別為 ，價(jià)值分別為 的物品， 01背包問題的數(shù)學(xué)模型為： 假設(shè)其解的順序表達(dá)形式為 ，其中 為 的一個(gè)排列。 ( ) ( ( ) | ( , ) )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)； 信息素的揮發(fā)； 信息素的增強(qiáng)； 主要體現(xiàn)在前面的算法中步驟 2和步驟 3中的轉(zhuǎn)移概率公式和信息素更新公式。 在 STEP 3中，蟻群永遠(yuǎn)記憶到目前為止的最優(yōu)解。 STEP 2 (內(nèi)循環(huán) ) 按螞蟻 的順序分別計(jì)算。二者的 相似之處在于都是優(yōu)先選擇信息素濃度大的路徑。路徑越長，釋放的激索濃度越低 .當(dāng)后來的螞蟻再次碰到這個(gè)路口的時(shí)候．選擇激素濃度較高路徑概率就會(huì)相對較大。其基本思想是將待聚類數(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)過程。 智能優(yōu)化計(jì)算 2022/8/27 15 7/7 這種算法求解 TSP的能力與 AS、精英策略 AS、遺傳算法和模擬退火算法進(jìn)行了比較。通過與其它各種通用的啟發(fā)式算法相比，在不大于 75城市的TSP中，這三種基本算法的求解能力還是比較理想的，但是當(dāng)問題規(guī)模擴(kuò)展時(shí)， AS的解題能力大幅度下降?，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)用問題提供了新的途徑 。已完成的群智能理論和應(yīng)用方法研究證明群智能方法是一種能夠有效解決大多數(shù)全局優(yōu)化問題的新方法。AntQ將螞蟻算法和一種增強(qiáng)型學(xué)習(xí)算法 Qlearning有機(jī)的結(jié)合了起來。 智能優(yōu)化計(jì)算 2022/8/27 17 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 2/5 蟻群算法在電信路由優(yōu)化中已取得了一定的應(yīng)用成果。 智能優(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)化問題。 智能優(yōu)化計(jì)算 2022/8/27 25 簡化的螞蟻尋食過程 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。每只螞蟻的一步轉(zhuǎn)移概率由圖中的每條邊上的兩類參數(shù)決定： 1 信息素值 也稱信息素痕跡。用如下公式對 W路徑 上的信息素痕跡加強(qiáng)，對其他路徑上的信息素進(jìn)行揮發(fā)。4 : , ( 4) 。智能優(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é)合。把 GBAS算法中步驟 3中的 改為 ，若滿足此條件則替換當(dāng)前最好解為 ， 對 W上的弧進(jìn)行信息素的加強(qiáng)，其他弧進(jìn)行信息素的揮發(fā)。 其中， 為第 k