【正文】 來完成局部信息的刷新計(jì)算。重復(fù)以上過程即可實(shí)現(xiàn)數(shù)據(jù)聚類。 智能優(yōu)化計(jì)算 2022/8/27 79 蟻群優(yōu)化算法 — 參考文獻(xiàn) ? 題目：群智能理論及應(yīng)用 ? 電子學(xué)報(bào) , 2022年 S1期 【 作者 】 彭喜元 彭宇 戴毓豐 ? 【 關(guān)鍵詞 】 群智能 微粒群算法 蟻群算法 優(yōu)化算法 。主要內(nèi)容有蟻群算法的由來、研究成果、應(yīng)用綜述、算法的具體描述及改進(jìn)、算法的典型優(yōu)化問題求解模式、算法的典型應(yīng)用及拓展應(yīng)用。 參考文獻(xiàn)： 基于蟻群系統(tǒng)的分布式 RWA 算法研究 孫海金 , 朱 娜 , 周乃富 2022 年 第 2 期 光通信研究 智能優(yōu)化計(jì)算 2022/8/27 74 3/5 蟻群算法用于計(jì)算機(jī)網(wǎng)絡(luò)路由 參考文獻(xiàn)：計(jì)算機(jī)網(wǎng)絡(luò)中的組播路由算法 謝銀祥 智能優(yōu)化計(jì)算 2022/8/27 75 應(yīng)用 4/5 智能優(yōu)化計(jì)算 2022/8/27 76 5/5 蟻群算法用于聚類（蟻群蟻卵分類） 思想：把待聚類的數(shù)據(jù)隨機(jī)散布在一個(gè)平面上，放置若干只虛擬螞蟻使其在平面上隨機(jī)運(yùn)動(dòng)。因此 ,近年來國內(nèi)外對RWA 并行的分布式算法表現(xiàn)出極大的興趣 ,此類算法建立的基礎(chǔ)是分層圖模型 。研究 RWA 問題的目的是盡可能減少所需要的波長數(shù)和降低光路連接請求的阻塞率。 蟻密算法（ antdensity algorithm ）信息素更新為 。相對而言，單螞蟻離線更新方式記憶信息少，只需要記憶第s只螞蟻的路徑，并通過信息素更新后，釋放該螞蟻的所有記錄信息。 ( ) ( 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只螞蟻所行走 的一條路徑。 蟻群離線更新方式是在蟻群中的 m只螞蟻全部完成 n城市的訪問（第 k1次蟻群循環(huán)）后，統(tǒng)一對殘留信息進(jìn)行更新處理。 智能優(yōu)化計(jì)算 2022/8/27 66 信息素的更改 1/6 信息素的更新分為離線和在線兩種方式。 ()Ls11 jkijab???? 1 2 1( ) ( 0 , , , .. .. , , )kkL s i i i i ??智能優(yōu)化計(jì)算 2022/8/27 64 每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定 系數(shù)的確定 3/3 殘留信息的相對重要程度 和預(yù)見值的相對重要程度 體現(xiàn)了相關(guān)信息痕跡和預(yù)見度對螞蟻決策的相對影響。 第一部分信息是存在每個(gè)節(jié)點(diǎn)的路由表數(shù)據(jù)結(jié)構(gòu) ，由此決定的的轉(zhuǎn)移概率為 其中 T可以看成節(jié)點(diǎn) i的鄰域。 ( , )G V A? ? ?0 , 1 , 2 , .. .. , , {( , ) | , }V n A i j i j V? ? ? ?( 1)nn? 1 ( 1 )ij nn? ??12( ) ( 0 , , , ...., )kL s i i i?12, , ...., ki i i 1k?1ki?11 jkijab????1 2 1( ) ( 0 , , , .. .. , , )kkL s i i i i ??智能優(yōu)化計(jì)算 2022/8/27 61 解的表達(dá)形式與算法的實(shí)現(xiàn) 4/4 算法的實(shí)現(xiàn) 對蟻群重復(fù)以上過程，比較 m只螞蟻的裝包值 并記憶具有最大裝包值的螞蟻為 t。初始信息素痕跡定義為 。 TSP問題尋找的是最短回路，而一般優(yōu)化問題中， STEP 3 中的判斷條件 需要根據(jù)實(shí)際問題進(jìn)行修改。問題中 為先驗(yàn)知識 智能優(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è)弧記錄。 （9）m in( ) , 1l n( 1 )l im 0kkkckkkc???????令：其中 ，則定理5. 2. 1的 結(jié)論也成立。第 s只螞蟻在第 k輪轉(zhuǎn)移只由 決定，這個(gè)螞蟻行走的路徑和 一起，共同決定了 ，再通過信息素的更新原則可以進(jìn)一步得到 。 第 K次循環(huán)前的信息素和最優(yōu)解為 ，經(jīng)過 第 K次外循環(huán)后，得到 。得到更新矩陣 這是第一次外循環(huán)結(jié)束的狀態(tài)。3 : , ( 3 ) 8 。 ()k?( , )( ) 1 , 0iji j Akk??? ? ??四個(gè)城市的非對稱 TSP問題，距離矩陣和城市圖示如下： 0 1 0 .5 11 0 1 1()1 .5 5 0 11 1 1 0ijDd??????????智能優(yōu)化計(jì)算 2022/8/27 36 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 7/12 假設(shè)共 4只螞蟻，所有螞蟻都從城市 A出發(fā)，揮發(fā)因子 。也就是說，增強(qiáng)過程體現(xiàn)在觀察蟻群（ m只螞蟻） 中每只螞蟻所找到的路徑，并選擇其中最優(yōu)路徑上的弧進(jìn)行信息素的增強(qiáng)， 揮發(fā)過程是所有弧都進(jìn)行的，不于螞蟻數(shù)量相關(guān)。 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)移。 若 ，則 。否則，若 ，則以概率 ， 到達(dá) j， ；若 則到達(dá) 重復(fù) STEP 2。 }, |j), { ( iA n}{ 1 , 2 , . . . ,N Nji ???nnijd ?)(),( ji ||1)0( Aij ??0i),2,1( nw ?? 初始的蟻群優(yōu)化算法 — 基于圖的蟻群系統(tǒng)（ GBAS） 2/12 STEP 1 （外循環(huán)）如果滿足算法的停止規(guī)則，則停止計(jì)算并輸出計(jì)算得到的最好解。 智能優(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)解。 }, |j), { ( iA n}{ 1 , 2 , . . . ,N Nji ???nnijd ?)(?? ??nlii lldwf1 1)(),( 21 niiiw ??11 iin ??智能優(yōu)化計(jì)算 2022/8/27 28 蟻群算法與 TSP問題 2/3 TSP問題的人工蟻群算法中，假設(shè) m只螞蟻在圖的相鄰節(jié)點(diǎn)間移動(dòng)，從而協(xié)作異步地得到問題的解。 兩者的區(qū)別在于人工蟻群有一定的記憶能力，能夠記憶已 經(jīng)訪問過的節(jié)點(diǎn)。 智能優(yōu)化計(jì)算 2022/8/27 26 自然蟻群與人工蟻群算法 基于以上蟻群尋找食物時(shí)的最優(yōu)路徑選擇問題，可以構(gòu)造 人工蟻群，來解決最優(yōu)化問題，如 TSP問題。 若按以上規(guī)則繼續(xù)，蟻群在 ABD路線上再增派一只螞蟻（共 3只），而ACD路線上仍然為一只螞蟻。 智能優(yōu)化計(jì)算 2022/8/27 24 簡化的螞蟻尋食過程 2/3 本圖為從開始算起，經(jīng)過 18個(gè)時(shí)間單位時(shí)的情形：走 ABD的螞蟻到達(dá)終點(diǎn)后得到食物又返回了起點(diǎn) A，而走 ACD的螞蟻剛好走到 D點(diǎn)。最優(yōu)路徑上的激索濃度越來越大．而其它的路徑上激素濃度卻會(huì)隨著時(shí)間的流逝而消減。當(dāng)它們碰到一個(gè)還沒有走過的路口時(shí)．就隨機(jī)地挑選一條路徑前行。螞蟻在運(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)象：某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。利用 ACO實(shí)現(xiàn)對生產(chǎn)流程和特料管理的綜合優(yōu)化，并通過與遺傳、模擬退火和禁忌搜索算法的比較證明了 ACO的工程應(yīng)用價(jià)值。 智能優(yōu)化計(jì)算 2022/8/27 19 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 4/5 ACO還在許多經(jīng)典組合優(yōu)化問題中獲得了成功的應(yīng)用，如二次規(guī)劃問題（ QAP）、機(jī)器人路徑規(guī)劃、作業(yè)流程規(guī)劃、圖著色（ Graph Coloring）等問題。 智能優(yōu)化計(jì)算 2022/8/27 18 蟻群優(yōu)化算法應(yīng)用現(xiàn)狀 3/5 基于群智能的聚類算法起源于對蟻群蟻卵的分類研究。如果一只螞蟻因?yàn)榻?jīng)過了網(wǎng)絡(luò)中堵塞的路由而導(dǎo)致了比較大的延遲，那么就對該表項(xiàng)做較大的增強(qiáng)。比較典型的應(yīng)用研究