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