【正文】 　，其中　　　為　　　　　　的一個排列。Date89 解的表達形式與算法的實現(xiàn) 算法的實現(xiàn)建立有向圖 ，其中 A中共有 條弧。初始信息素痕跡定義為 。設(shè)第 s只螞蟻第 k步所走的路線為 ，表示螞蟻從 0點出發(fā)，順序到達 。第 步按 TSP算法的轉(zhuǎn)移概率公式行走選擇 。若 則 ，否則，此螞蟻不再繼續(xù)行走，退回起點。Date90 解的表達形式與算法的實現(xiàn) 算法的實現(xiàn) 對蟻群重復以上過程，比較 m只螞蟻的裝包值 并記憶具有最大裝包值的螞蟻為 t。把 GBAS算法中步驟 3中的改為 ，若滿足此條件則替換當前最好解為 ，對 W上的弧進行信息素的加強，其他弧進行信息素的揮發(fā)。 算法中記錄了三個信息：信息素痕跡 ；行走路線 ；和問題的約束條件 ，以確定是否將 加入。 Date91 每一節(jié)點的記憶信息和系數(shù)的確定 需要記憶的信息算法中需要記憶的信息有三部分。第一部分信息是存在每個節(jié)點的路由表數(shù)據(jù)結(jié)構(gòu) ，由此決定的的轉(zhuǎn)移概率為其中 T可以看成節(jié)點 i的鄰域。Date92 每一節(jié)點的記憶信息和系數(shù)的確定 需要記憶的信息 第二部分需要記憶的信息是每個螞蟻的記憶表中存儲著的自身的歷史信息，這一部分主要由算法的中的 記憶，表示螞蟻已經(jīng)行走過的節(jié)點。 第三部分為問題的約束條件。在 GBAS中， T集合表示滿足約束條件的候選集，在背包問題的蟻群算法中由判別條件 ， 來實現(xiàn)記 憶功能。Date93 每一節(jié)點的記憶信息和系數(shù)的確定 系數(shù)的確定 殘留信息的相對重要程度 和預見值的相對重要程度 體現(xiàn)了相關(guān)信息痕跡和預見度對螞蟻決策的相對影響。 Dorigo在求解 TSP問題時，推薦參數(shù)的最佳設(shè)置為： 。Date94 蟻群的規(guī)模和停止規(guī)則一、蟻群大小 一般情況下蟻群中螞蟻的個數(shù)不超過 TSP圖中節(jié)點的個數(shù)。二、終止條件 1 給定一個外循環(huán)的最大數(shù)目，表明已經(jīng)有足夠的螞蟻工作； 2 當前最優(yōu)解連續(xù) K次相同而停止，其中 K是一個給定的整數(shù)，表示算法已經(jīng)收斂，不再需要繼續(xù)； 3 目標值控制規(guī)則，給定優(yōu)化問題（目標最小化）的一個下界和一個誤差值，當算法得到的目標值同下界之差小于給定的誤差值時，算法終止。Date95 信息素的更改 信息素的更新分為離線和在線兩種方式。離線方式（同步更新方式）的主要思想是在若干只螞蟻完成 n個城市的訪問后，統(tǒng)一對殘留信息進行更新處理。 信息素的在線更新（異步更新方式）即螞蟻每行走一步，立即回溯并且更新行走路徑上的信息素。Date96 信息素的更改 離線方式的信息素更新可以進一步分為單螞蟻離線更新和蟻群離線更新。 蟻群離線更新方式是在蟻群中的 m只螞蟻全部完成 n城市的訪問（第 k1次蟻群循環(huán)）后，統(tǒng)一對殘留信息進行更新處理。 其中， 為第 k1次循環(huán)后的的信息素的痕跡值。 單螞蟻離線更新是在第 s只螞蟻完成對所有 n個城市的訪問后，進行路徑回溯，更新行走路徑上的信息素，同時釋放分配給它的資源。更新公式為 第 s+1只螞蟻根據(jù) 重新計算路由表。 Date97 信息素的更改TSP問題中，蟻群優(yōu)化算法根據(jù)信息素痕跡更新方式不同可以分為不同的算法，采用離線方式，并且時，其中 W為 t循環(huán)中 m只螞蟻所行走的最佳路線或 第 t只螞蟻所行走的一條路徑。 Q為一個常數(shù)，該算法名為蟻環(huán)算法（ antcycle algotithm） ,特點是行走的路徑越短對應保存的信息素的值就越大。Date98 信息素的更改 GBAS算法是典型的離線信息素更新方式。該算法中，蟻群中螞蟻的先后出行順序沒有相關(guān)性，但是每次循環(huán)需要記憶 m只螞蟻的行走路徑，以進行比較選擇最優(yōu)路徑。相對而言，單螞蟻離線更新方式記憶信息少，只需要記憶第 s只螞蟻的路徑，并通過信息素更新后，釋放該螞蟻的所有記錄信息。實際上這種方式等價于蟻群離線方式中只有一只螞蟻。Date99 信息素的更改 與 單 螞蟻離線更新方式相比，信息量記憶更小的是信息素在線更新方式，即螞蟻每走一步，馬上回溯并且更新剛剛走過的路徑上的信息素，其規(guī)則為 其中， k為螞蟻行走的第 k步。Date100 信息素的更改 蟻量算法（ antquantity algorithm）的信息素更新為 ,Q為常量， 表示 i到 j的距離，這樣信息濃度會隨城市距離的減小而加大。蟻密算法（ antdensity algorithm ）信息素更新為 。 以上三種算法中，蟻環(huán)算法效果最好，因為他用的是全局信息，而其余兩種算法用的是局部信息。蟻環(huán)離線更新方法很好地保證了殘留信息不至于無限積累，非最優(yōu)路徑會逐漸隨時間推移被 忘記。Date101 應用 光 網(wǎng)絡(luò)的智能管理 分布式動態(tài)選路及波長分配 ( RWA , Routing and Wavelength Assignment ) 是指在實時業(yè)務情況下光通路的路由選擇和波長分配的優(yōu)化問題 ,是實現(xiàn)自動交換光網(wǎng)絡(luò) (ASON ,Automatically Switched Optical Network) 的關(guān)鍵技術(shù)之一。研究 RWA 問題的目的是盡可能減少所需要的波長數(shù)和降低光路連接請求的阻塞率。由于 RWA 問題是 NPC 問題 ,文獻中大多將 RWA 問題拆分成路由和波長分配兩個子問題分別加以解決。但是 ,由于 RWA 問題本身是一個不可分割的整體 ,把 RWA 分開考慮必然造成難以得到全局最優(yōu)解的后果。Date102 應用 同時 ,分布式的計算方式則克服了傳統(tǒng)集中式算法可擴展性差的缺點 ,更適應現(xiàn)代頻繁變化的大型光網(wǎng)絡(luò)。因此 ,近年來國內(nèi)外對 RWA 并行的分布式算法表現(xiàn)出極大的興趣 ,此類算法建立的基礎(chǔ)是分層圖模型 ?！? 用蟻群算法在分層圖模型的基礎(chǔ)上求解動態(tài) RWA 問題?；谖浵?“信息素表 ”來完成局部信息的刷新計算。以分布的形式做少量的計算來刷新全局路由選擇信息。 參考文獻： 基于蟻群系統(tǒng)的分布式 RWA 算法研究 孫海金 , 朱　娜 , 周乃富 2022 年　第 2 期 光通信研究Date103 蟻群算法用于計算機網(wǎng)絡(luò)路由參考文獻：計算機網(wǎng)絡(luò)中的組播路由算法 謝銀祥 Date104 應用Date105 蟻群算法用于聚類（蟻群蟻卵分類） 思想：把待聚類的數(shù)據(jù)隨機散布在一個平面上，放置若干只虛擬螞蟻使其在平面上隨機運動。當一只螞蟻遇到一個數(shù)據(jù)時即拾起并繼續(xù)行走，在行走過程中，如果遇到附近的數(shù)據(jù)與背負的數(shù)據(jù)相似性高于設(shè)置的標準時則將數(shù)據(jù)放置在該位置，繼續(xù)移動。重復以上過程即可實現(xiàn)數(shù)據(jù)聚類。Date106 蟻群優(yōu)化算法 — 參考書 1? 智能蟻群算法及應用 吳啟迪 上海科技出版社從基本結(jié)構(gòu)、算法特點、改進方法、突破途徑、實現(xiàn)模式及應用模式等方面進行了論述。主要內(nèi)容有蟻群算法的由來、研究成果、應用綜述、算法的具體描述及改進、算法的典型優(yōu)化問題求解模式、算法的典型應用及拓展應用。Date107 蟻群優(yōu)化算法 — 參考書 2? 蟻群算法及其應用 李士勇 哈工大出版社 國內(nèi)首部 蟻 群算法的 專 著，系 統(tǒng) 地 闡 述 蟻 群算法的基本原理、基本 蟻 群算法及改 進 算法， 蟻 群算法與 遺傳 、免疫算法的融合，自適 應蟻 群算法，并行 蟻 群算法， 蟻 群算法的收 斂 性與理 論 模型及其在 優(yōu) 化 問題 中的 應 用。本 書 可供人工智能、 計算機科學、信息科學、控制工程、管理工程、交通工程、網(wǎng) 絡(luò)工程、智能 優(yōu) 化算法及智能自 動 化等 領(lǐng) 域的廣大 師 生和科技人員 學 習 及參考。Date108