【正文】 本 書(shū) 可供人工智能、 計(jì) 算機(jī)科學(xué)、信息科學(xué)、控制工程、管理工程、交通工程、網(wǎng) 絡(luò) 工程、智能 優(yōu)化算法及智能自 動(dòng) 化等 領(lǐng) 域的廣大 師 生和科技人 員 學(xué)習(xí) 及參考。主要內(nèi)容有蟻群算法的由來(lái)、研究成果、應(yīng)用綜述、算法的具體描述及改進(jìn)、算法的典型優(yōu)化問(wèn)題求解模式、算法的典型應(yīng)用及拓展應(yīng)用。重復(fù)以上過(guò)程即可實(shí)現(xiàn)數(shù)據(jù)聚類(lèi)。 參考文獻(xiàn)： 基于蟻群系統(tǒng)的分布式 RWA 算法研究 孫海金 , 朱　娜 , 周乃富 2022 年　第 2 期 光通信研究104 3/5 蟻群算法用于計(jì)算機(jī)網(wǎng)絡(luò)路由參考文獻(xiàn)：計(jì)算機(jī)網(wǎng)絡(luò)中的組播路由算法 謝銀祥 105 應(yīng)用 4/5106 5/5 蟻群算法用于聚類(lèi)（蟻群蟻卵分類(lèi)） 思想：把待聚類(lèi)的數(shù)據(jù)隨機(jī)散布在一個(gè)平面上，放置若干只虛擬螞蟻使其在平面上隨機(jī)運(yùn)動(dòng)?；谖浵仭靶畔⑺乇?”來(lái)完成局部信息的刷新計(jì)算。因此 ,近年來(lái)國(guó)內(nèi)外對(duì)RWA 并行的分布式算法表現(xiàn)出極大的興趣 ,此類(lèi)算法建立的基礎(chǔ)是分層圖模型 。但是 ,由于 RWA 問(wèn)題本身是一個(gè)不可分割的整體 ,把 RWA 分開(kāi)考慮必然造成難以得到全局最優(yōu)解的后果。研究 RWA 問(wèn)題的目的是盡可能減少所需要的波長(zhǎng)數(shù)和降低光路連接請(qǐng)求的阻塞率。蟻環(huán)離線更新方法很好地保證了殘留信息不至于無(wú)限積累，非最優(yōu)路徑會(huì)逐漸隨時(shí)間推移被忘記。蟻密算法（ antdensity algorithm ）信息素更新為 。100 信息素的更改 5/6 與單螞蟻離線更新方式相比，信息量記憶更小的是信息素在線更新方式，即螞蟻每走一步，馬上回溯并且更新剛剛走過(guò)的路徑上的信息素，其規(guī)則為 其中， k為螞蟻行走的第 k步。相對(duì)而言，單螞蟻離線更新方式記憶信息少，只需要記憶第 s只螞蟻的路徑，并通過(guò)信息素更新后，釋放該螞蟻的所有記錄信息。99 信息素的更改 4/6 GBAS算法是典型的離線信息素更新方式。 98 信息素的更改 3/6TSP問(wèn)題中，蟻群優(yōu)化算法根據(jù)信息素痕跡更新方式不同可以分為不同的算法，采用離線方式，并且時(shí)，其中 W為 t循環(huán)中 m只螞蟻所行走的最佳路線或第 t只螞蟻所行走的一條路徑。 單螞蟻離線更新是在第 s只螞蟻完成對(duì)所有 n個(gè)城市的訪問(wèn)后，進(jìn)行路徑回溯，更新行走路徑上的信息素，同時(shí)釋放分配給它的資源。 蟻群離線更新方式是在蟻群中的 m只螞蟻全部完成 n城市的訪問(wèn)（第 k1次蟻群循環(huán)）后，統(tǒng)一對(duì)殘留信息進(jìn)行更新處理。 信息素的在線更新（異步更新方式）即螞蟻每行走一步，立即回溯并且更新行走路徑上的信息素。96 信息素的更改 1/6 信息素的更新分為離線和在線兩種方式。95 蟻群的規(guī)模和停止規(guī)則一、蟻群大小 一般情況下蟻群中螞蟻的個(gè)數(shù)不超過(guò) TSP圖中節(jié)點(diǎn)的個(gè)數(shù)。94 每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定 系數(shù)的確定 3/3 殘留信息的相對(duì)重要程度 和預(yù)見(jiàn)值的相對(duì)重要程度 體現(xiàn)了相關(guān)信息痕跡和預(yù)見(jiàn)度對(duì)螞蟻決策的相對(duì)影響。 第三部分為問(wèn)題的約束條件。第一部分信息是存在每個(gè)節(jié)點(diǎn)的路由表數(shù)據(jù)結(jié)構(gòu) ，由此決定的的轉(zhuǎn)移概率為其中 T可以看成節(jié)點(diǎn) i的鄰域。 算法中記錄了三個(gè)信息：信息素痕跡 ；行走路線 ；和問(wèn)題的約束條件 ，以確定是否將 加入。91 解的表達(dá)形式與算法的實(shí)現(xiàn) 4/4 算法的實(shí)現(xiàn) 對(duì)蟻群重復(fù)以上過(guò)程，比較 m只螞蟻的裝包值 并記憶具有最大裝包值的螞蟻為 t。第 步按 TSP算法的轉(zhuǎn)移概率公式行走選擇 。初始信息素痕跡定義為 。設(shè)有一個(gè)容積為 b的背包， n個(gè)尺寸分別為 ，價(jià)值分別為 的物品， 01背包問(wèn)題的數(shù)學(xué)模型為：假設(shè)其解的順序表達(dá)形式為　　　　　　　　，其中　　　為　　　　　　的一個(gè)排列。 TSP問(wèn)題尋找的是最短回路，而一般優(yōu)化問(wèn)題中， STEP 3 中的判斷條件 需要根據(jù)實(shí)際問(wèn)題進(jìn)行修改。蟻群算法在解決這類(lèi)問(wèn)題時(shí)，只需要建立一個(gè)虛擬的始終點(diǎn)，就可以把 TSP問(wèn)題的解法推廣，用于諸多的優(yōu)化問(wèn)題。75 GBAS算法的收斂性分析 1/8 定理 滿足 指定條件 的馬爾可夫過(guò)程 依概率 1收斂到 ,其中 為一條最優(yōu)路徑 , 定義為 : 證明分析 : 蟻群算法中 ,一但達(dá)到全局最優(yōu) ,由 只記錄第一個(gè)最優(yōu)解 .證明分三部分 :n 證明以概率 1達(dá)到一個(gè)最優(yōu)路徑n 證明 (1)上式成立n 證明以概率 1收斂到一個(gè)最優(yōu)路徑76 GBAS算法的收斂性分析 2/8證明以概率 1到達(dá)一個(gè)最優(yōu)路徑 對(duì)于最優(yōu)路徑 ,令 為蟻群中的一個(gè)螞蟻在第 k次外循環(huán)后第一次走到最優(yōu)路徑 的事件 . 表示僅第 k次外循環(huán)沒(méi)有走到 的事件 ,但前 k1次可能走到過(guò)這條最優(yōu)路徑 . 永遠(yuǎn)不會(huì)被走到的事件為 ,其概率為 :77 GBAS算法的收斂性分析 3/8 任意給定的固定弧 (i,j),在第 k次循環(huán)后 ,其信息素值的下界可以計(jì)算出 .78 GBAS算法的收斂性分析 4/8令 ,任何一個(gè)固定節(jié)點(diǎn)最多有 (n1)后續(xù)節(jié)點(diǎn) ,并且其弧上的信息素值都小于 1或者等于 :蟻群中的一只螞蟻在第 次循環(huán)走到路徑 W* 的概率為一個(gè)蟻群中至少有一只螞蟻，因此這是一個(gè)蟻群到達(dá)最優(yōu)路徑的一個(gè)下界 . 上式右側(cè)與 k無(wú)關(guān) ,79 GBAS算法的收斂性分析 5/8 則取對(duì)數(shù)有從而得到80 GBAS算法的收斂性分析 6/8 證明右式成立 隨機(jī)過(guò)程 以概率 1達(dá)到一條最優(yōu)路徑 .當(dāng)某條最優(yōu)路徑 Z在第 k次循環(huán)被首次走到后 ,在第 k+1輪循環(huán)按信息素的更新原則 ,可以用歸納法證明 ,對(duì)于任意81 GBAS算法的收斂性分析 7/8由于級(jí)數(shù) 是發(fā)散的 ,可知 .因此 ,當(dāng) 時(shí) ,在第 K輪迭代之后 ,該弧永遠(yuǎn)不再被加強(qiáng) ,從而有 也既 弧上的信息素之和將趨于 0.對(duì)于信息素的更新公式 (2),可以歸納證明(6)式的第二項(xiàng)與 (i,j)弧無(wú)關(guān) ,結(jié)合 (7)式可得 的極限存在 ,且所有的極限之和為 82 GBAS算法的收斂性分析 8/8 結(jié)合前兩部分討論 ,當(dāng) Xn首次到達(dá)最優(yōu)路徑后 ,對(duì)于任何最優(yōu)路徑上的弧 ,(1)式的轉(zhuǎn)移概率 ,即 依概率 1收斂到 .83 其他算法及收斂性分析 1/4 MAXMIN蟻群優(yōu)化算法指定揮發(fā)系數(shù)不隨時(shí)間變化 ,這是和 GBAS算法不同的一點(diǎn) ,改變了信息素?fù)]發(fā)和增強(qiáng)的規(guī)則 (9式 )，同時(shí)給出一個(gè)下界 控制信息素的揮發(fā) . 定理 在 MAXMIN算法中 ,84 其他算法及收斂性分析 2/485 其他算法及收斂性分析 3/486 其他算法及收斂性分析 4/487 蟻群優(yōu)化算法 — 技術(shù)問(wèn)題 解的表達(dá)形式與算法的實(shí)現(xiàn) 每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定 蟻群的規(guī)模和停止規(guī)則 信息素的更改88 解的表達(dá)形式與算法的實(shí)現(xiàn) 1/4 解的表達(dá)形式 解的表達(dá)形式 基于 TSP問(wèn)題的蟻群優(yōu)化算法，其解的形式是所有城市的一個(gè)排列（閉圈，這種情況下誰(shuí)在第一并不重要），信息素痕跡按每個(gè)弧記錄。 的變化僅由 決定，而與先前的狀態(tài)無(wú)關(guān)，這是一個(gè)典型的馬爾可夫過(guò)程。73 蟻群優(yōu)化算法 — 算法模型和收斂性分析 馬氏過(guò)程的收斂定義 GBAS算法的收斂性分析74 馬氏過(guò)程的收斂定義 蟻群優(yōu)化算法的每步迭代對(duì)應(yīng)隨機(jī)變量 其中 為信息素痕跡； 為 n城市的一個(gè)排列，最多有 個(gè)狀態(tài)。由于螞蟻的一步轉(zhuǎn)移概率是隨機(jī)的，從 到 也是隨機(jī)的，是一個(gè)馬爾可夫過(guò)程。假設(shè)第 K次外循環(huán)后得到信息素矩陣 ，得到當(dāng)前最優(yōu)解 。