【正文】 回溯并且更新剛剛走過的路徑上的信息素，其規(guī)則為 其中， k為螞蟻行走的第 k步。63 信息素的更改 6/6蟻 量算法 （ antquantity algorithm）的信息素 更新為 Q為常量， 表示 i到 j的距離，這樣信息濃度 會隨城市距離的減小而加大。蟻密算法 （ antdensity algorithm ）信息素 更新為。 以上 三種算法中 ，蟻周算法 效果最好，因為他用的是全局信息，而其余兩種算法用的是局部信息 。蟻周離線 更新方法很好地保證了殘留信息不至于無限積累，非最優(yōu)路徑會逐漸隨時間推移被 忘記。64 應用 1/5 光 網(wǎng)絡的智能管理 分布式 動態(tài)選路及波長分配 ( RWA , Routing and Wavelength Assignment ) 是指在實時業(yè)務情況下光通路的路由選擇和波長分配的優(yōu)化問題,是實現(xiàn)自動交換光網(wǎng)絡 (ASON ,Automatically Switched Optical Network) 的關鍵技術之一。研究RWA 問題的目的是盡可能減少所需要的波長數(shù)和降低光路連接請求的阻塞率。由于 RWA 問題是 NPC 問題 ,文獻中大多將 RWA 問題拆分成路由和波長分配兩個子問題分別加以解決。但是 ,由于 RWA 問題本身是一個不可分割的整體 ,把 RWA 分開考慮必然造成難以得到全局最優(yōu)解的后果。65 應用 2/5 同時 ,分布式的計算方式則克服了傳統(tǒng)集中式算法可擴展性差的缺點 ,更適應現(xiàn)代頻繁變化的大型光網(wǎng)絡。因此 ,近年來國內外對 RWA 并行的分布式算法表現(xiàn)出極大的興趣 ,此類算法建立的基礎是分層圖模型 。 用蟻群算法在分層圖模型的基礎上求解動態(tài)RWA 問題?；谖浵?“信息素表 ”來完成局部信息的刷新計算。以分布的形式做少量的計算來刷新全局路由選擇信息。 參考文獻：孫海金 , 朱　娜 , 周乃富 基于蟻群系統(tǒng)的分布式 RWA算法研究 [J].光通信研究 ,66 3/5蟻群算法用于計算機網(wǎng)絡路由參考文獻：謝銀祥計算機網(wǎng)絡中的組播路由算法67 應用 4/568 5/5 蟻群算法用于聚類（ 蟻群蟻卵分類 ） 思想：把待聚類的數(shù)據(jù)隨機散布在一個平面上，放置若干只虛擬螞蟻使其在平面上隨機運動。當一只螞蟻遇到一個數(shù)據(jù)時即拾起并繼續(xù)行走，在行走過程中，如果遇到附近的數(shù)據(jù)與背負的數(shù)據(jù)相似性高于設置的標準時則將數(shù)據(jù)放置在該位置，繼續(xù)移動。重復以上過程即可實現(xiàn)數(shù)據(jù)聚類。69第五章第五章 結束結束智能優(yōu)化方法智能優(yōu)化方法 信息系統(tǒng)與管理學院 70 蟻群優(yōu)化算法研究現(xiàn)狀 1/790年代 Dorigo最早提出了蟻群優(yōu)化算法 螞蟻系統(tǒng)（ Ant System, AS） 并將其應用于解決優(yōu)化算法中經(jīng)典的旅行商問題（ TSP）。從螞蟻系統(tǒng)開始，基本的蟻群算法得到了不斷的發(fā)展和完善，并在 TSP以及許多實際優(yōu)化問題求解中進一步得到了驗證。這些 AS改進版本的一個共同點就是 增強了螞蟻搜索過程中對最優(yōu)解的探索能力，它們之間的差異僅在于搜索控制策略方面。而且，取得了最佳結果的 ACO是通過引入局部搜索算法實現(xiàn)的，這實際上是一些結合了標準局域搜索算法的混合型概率搜索算法，有利于提高蟻群各級系統(tǒng)在優(yōu)化問題中的求解質量。71 2/7 最初提出的 AS有三種版本： Antdensity、 Antquantity和 Antcycle。在 Antdensity和 Antquantity中螞蟻在兩個位置節(jié)點間每移動一次后即更新信息素，而在 Antcycle中當所有的螞蟻都完成了自己的行程后才對信息素進行更新，而且每個螞蟻所釋放的信息素被表達為反映相應行程質量的函數(shù)。通過與其它各種通用的啟發(fā)式算法相比，在不大于 75城市的 TSP中，這三種基本算法的求解能力還是比較理想的，但是當問題規(guī)模擴展時， AS的解題能力大幅度下降。 因此，其后的 ACO研究工作主要都集中于 AS性能的改進方面。較早的一種改進方法是精英策略 (Elitist Strategy)， 其思想是在算法開始后即對所有已發(fā)現(xiàn)的最好路徑給予額外的增強，并將隨后與之對應的行程記為 Tgb(全局最優(yōu)行程 )，當進行信息素更新時，對這些行程予以加權，同時將經(jīng)過這些行程的螞蟻記為 “精英 ”，從而增大較好行程的選擇機會。這種改進型算法能夠以更快的速度獲得更好的解。但是若選擇的精英過多則算法會由于較早的收斂于局部次優(yōu)解而導致搜索的過早停滯。 72 3/7為了進一步克服 AS中暴露出的問題，提出了蟻群系統(tǒng) (Ant Colony System, ACS)。 該系統(tǒng)的提出是以AntQ算法為基礎的。 AntQ將螞蟻算法和一種增強型學習算法 Qlearning有機的結合了起來。 ACS與 AS之間存在三方面的主要差異：首先， ACS采用了更為大膽的行為選擇規(guī)則；其次，只增強屬于全局最優(yōu)解的路徑上的信息素。其中， 0ρ1是信息素揮發(fā)參數(shù)， 是從尋路開始到當前為止全局最優(yōu)的路徑長度。73 4/7再次，還引入了負反饋機制，每當一只螞蟻由一個節(jié)點移動到另一個節(jié)點時，該路徑上的信息素都按照如下公式被相應的消除一部分，從而實現(xiàn)一種信息素的局部調整，以減小已選擇過的路徑再次被選擇的概率。 74 5/7在對 AS進行直接完善的方法中， MAXMIN Ant System是一個典型代表。該算法修改了 AS的信息素更新方式，每次迭代之后只有一只螞蟻能夠進行信息素的更新以獲取更好的解。為了避免搜索停滯，路徑上的信息素濃度被限制在 [MAX， MIN ]范圍內，另外，信息素的初始值被設為其取值上限，這樣有助于增加算法初始階段的搜索能力。75 6/7另一種對 AS改進的算法是 Rankbased Version AS。與 “精英策略 ”相似，在此算法中總是更新更好進程上的信息素，選擇的標準是其行程長度 決定的排序，且每個螞蟻放置信息素的強度通過下式中的排序加權處理確定，其中， ｗ 為每次迭代后放置信息素的螞蟻總數(shù)。 76 7/7這種 算法求解 TSP的能力與 AS、精英策略AS、遺傳算法和模擬退火算法進行了比較。在大型 TSP問題中（最多包含 132座城市），基于 AS的算法都顯示出了優(yōu)于 GA和 SA的特性。而且在Rankbased AS和精英策略 AS均優(yōu)于基本 AS的同時，前者還獲得了比精英策略 AS更好的解。 77