【正文】 蟻群優(yōu)化算法 — 技術(shù)問(wèn)題 解的表達(dá)形式與算法的實(shí)現(xiàn) 每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定 蟻群的規(guī)模和停止規(guī)則 信息素的更改 87 解的表達(dá)形式與算法的實(shí)現(xiàn) 1/4 解的表達(dá)形式 解的表達(dá)形式 基于 TSP問(wèn)題的蟻群優(yōu)化算法，其解的形式是所有城市的一個(gè)排列（閉圈，這種情況下誰(shuí)在第一并不重要），信息素痕跡按每個(gè)弧記錄。而對(duì)于一般以順序作為解的優(yōu)化問(wèn)題，誰(shuí)在第一是很重要的。蟻群算法在解決這類(lèi)問(wèn)題時(shí)，只需要建立一個(gè)虛擬的始終點(diǎn)，就可以把 TSP問(wèn)題的解法推廣，用于諸多的優(yōu)化問(wèn)題。 諸如車(chē)間作業(yè)及下料等問(wèn)題，他們的共同特點(diǎn)是解以一個(gè)順序表示。 TSP問(wèn)題尋找的是最短回路，而一般優(yōu)化問(wèn)題中， STEP 3 中的判斷條件 需要根據(jù)實(shí)際問(wèn)題進(jìn)行修改。 ()L s N?88 解的表達(dá)形式與算法的實(shí)現(xiàn) 2/4 算法的實(shí)現(xiàn) 例： 01背包問(wèn)題的解順序表達(dá)形式與算法實(shí)現(xiàn)。設(shè)有一個(gè)容積為 b的背包， n個(gè)尺寸分別為 ，價(jià)值分別為 的物品， 01背包問(wèn)題的數(shù)學(xué)模型為： 假設(shè)其解的順序表達(dá)形式為 ，其中 為 的一個(gè)排列。 ( 1, 2 , ..., )ia i n? ( 1, 2 , ..., )ic i n?? ?11m a x..0 , 1 , 1 , ....,niiiniiiicxs t a x bx j n???????? ?120 , , , ..., ni i i ? ?12, , ..., ni i i? ?1, 2 , 3, ..., n89 解的表達(dá)形式與算法的實(shí)現(xiàn) 3/4 算法的實(shí)現(xiàn) 建立有向圖 ，其中 A中共有 條弧。初始信息素痕跡定義為 。 設(shè)第 s只螞蟻第 k步所走的路線(xiàn)為 ， 表示螞蟻從 0點(diǎn)出發(fā)，順序到達(dá) 。第 步按 TSP算法 的轉(zhuǎn)移概率公式行走選擇 。若 則 ，否則，此螞蟻不再繼續(xù)行走，退回起點(diǎn)。 ( , )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 ??90 解的表達(dá)形式與算法的實(shí)現(xiàn) 4/4 算法的實(shí)現(xiàn) 對(duì)蟻群重復(fù)以上過(guò)程，比較 m只螞蟻的裝包值 并記憶具有最大裝包值的螞蟻為 t。把 GBAS算法中步驟 3中的 改為 ，若滿(mǎn)足此條件則替換當(dāng)前最好解為 ， 對(duì) W上的弧進(jìn)行信息素的加強(qiáng)，其他弧進(jìn)行信息素的揮發(fā)。 算法中記錄了三個(gè)信息：信息素痕跡 ；行走路線(xiàn) ；和問(wèn)題的約束條件 ， 以確定是否將 加入。 ()0, 1 , 2 , . . . ,ii L sic s m????( ( )) ( )f L t f w?( ( )) ( )f L t f w? : ( )W L t?ij?1 2 1( ) (0 , , , . . . . , , )kkL s i i i i ?? 11 jkijab????1ki ?91 每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定 需要記憶的信息 1/3 算法中需要記憶的信息有三部分。 第一部分信息是存在每個(gè)節(jié)點(diǎn)的路由表數(shù)據(jù)結(jié)構(gòu) ，由此決定的的轉(zhuǎn)移概率為 其中 T可以看成節(jié)點(diǎn) i的鄰域。 ? ?| ( , )i ijA a i j A??( 1 ) { ( 1 ) | ( , ) }i ijA k a k i j A? ? ? ?( 1 )( 1 ) ,0ijilijlTakjTakPjT???? ?? ?? ???? ??( 1 ) ( 1 )( 1 ) ( 1 )( 1 ) ,0ij ijil ilijlTkkkka k j TjT?????????? ??????? ? ??? ????92 每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定 需要記憶的信息 2/3 第二部分需要記憶的信息是每個(gè)螞蟻的記憶表中存儲(chǔ)著的自身的歷史信息，這一部分主要由算法的中的 記憶，表示螞蟻已經(jīng)行走過(guò)的節(jié)點(diǎn)。 第三部分為問(wèn)題的約束條件。在 GBAS中， T集合表示滿(mǎn)足約束條件的候選集，在背包問(wèn)題的蟻群算法中由判別條件 ， 來(lái)實(shí)現(xiàn)記 憶功能。 ()Ls11 jkijab???? 1 2 1( ) (0 , , , . . . . , , )kkL s i i i i ??93 每一節(jié)點(diǎn)的記憶信息和系數(shù)的確定 系數(shù)的確定 3/3 殘留信息的相對(duì)重要程度 和預(yù)見(jiàn)值的相對(duì)重要程度 體現(xiàn)了相關(guān)信息痕跡和預(yù)見(jiàn)度對(duì)螞蟻決策的相對(duì)影響。 Dorigo在求解 TSP問(wèn)題時(shí)，推薦參數(shù)的最佳設(shè)置為： 。 ??1 , 5 , 0 . 5? ? ?? ? ?94 蟻群的規(guī)模和停止規(guī)則 一、蟻群大小 一般情況下蟻群中螞蟻的個(gè)數(shù)不超過(guò) 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)化問(wèn)題（目標(biāo)最小化）的一個(gè)下界和一個(gè)誤差值，當(dāng)算法得到的目標(biāo)值同下界之差小于給定的誤差值時(shí)，算法終止。 95 信息素的更改 1/6 信息素的更新分為離線(xiàn)和在線(xiàn)兩種方式。離線(xiàn)方式（同步更新方式）的主要思想是在若干只螞蟻完成 n個(gè)城市的訪(fǎng)問(wèn)后，統(tǒng)一對(duì)殘留信息進(jìn)行更新處理。 信息素的在線(xiàn)更新（異步更新方式）即螞蟻每行走一步，立即回溯并且更新行走路徑上的信息素。 96 信息素的更改 2/6 離線(xiàn)方式的信息素更新可以進(jìn)一步分為單螞蟻離線(xiàn)更新和蟻群離線(xiàn)更新。 蟻群離線(xiàn)更新方式是在蟻群中的 m只螞蟻全部完成 n城市的訪(fǎng)問(wèn)（第 k1次蟻群循環(huán)）后，統(tǒng)一對(duì)殘留信息進(jìn)行更新處理。 其中， 為第 k1次循環(huán)后的的信息素的痕跡值。 單螞蟻離線(xiàn)更新是在第 s只螞蟻完成對(duì)所有 n個(gè)城市的訪(fǎng)問(wèn)后，進(jìn)行路徑回溯，更新行走路徑上的信息素，同時(shí)釋放分配給它的資源。更新公式為 第 s+1只螞蟻根據(jù) 重新計(jì)算路由表。 ( ) ( 1 ) ( 1 )ij ij ijk k k? ? ?? ? ? ? ?()ij k?( 1 ) ( ) ( )ij ij ijs s s? ? ?? ? ? ?( 1)ij s? ?97 信息素的更改 3/6 TSP問(wèn)題中，蟻群優(yōu)化算法根據(jù)信息素痕跡更新方式不同可以分為不 同的算法，采用離線(xiàn)方式，并且 時(shí)，其中 W為 t循環(huán)中 m只螞蟻所行走的最佳路線(xiàn)或第 t只螞蟻所行走 的一條路徑。 Q為一個(gè)常數(shù)，該算法名為蟻環(huán)算法（ antcycle algotithm） ,特點(diǎn)是行走的路徑越短對(duì)應(yīng)保存的信息素的值就越大。 ( 1 ) ( )i j i jks??? ? ?或?yàn)? ) , ( , )( , )0ijQWt i j Wi j W???? ? ??? ??98 信息素的更改 4/6 GBAS算法是典型的離線(xiàn)信息素更新方式。該算法中，蟻群中螞蟻的先后出行順序沒(méi)有相關(guān)性，但是每次循環(huán)需要記憶 m只螞蟻的行走路徑，以進(jìn)行比較選擇最優(yōu)路徑。相對(duì)而言，單螞蟻離線(xiàn)更新方式記憶信息少，只需要記憶第 s只螞蟻的路徑，并通過(guò)信息素更新后，釋放該螞蟻的所有記錄信息。實(shí)際上這種方式等價(jià)于蟻群離線(xiàn)方式中只有一只螞蟻。 99 信息素的更改 5/6 與單螞蟻離線(xiàn)更新方式相比，信息量記憶更小的是信息素在線(xiàn)更新方式，即螞蟻每走一步，馬上回溯并且更新剛剛走過(guò)的路徑上的信息素，其規(guī)則為 其中， k為螞蟻行走的第 k步。 ( 1 ) ( ) ( )ij ij ijk k k? ? ?? ? ? ?100 信息素的更改 6/6 蟻量算法（ antquantity algorithm）的信息素更新 為 ,Q為常量， 表示 i到 j的距離，這樣信息 濃度會(huì)隨城市距離的減小而加大。 蟻密算法（ antdensity algorithm ）信息素更新為 。 以上三種算法中，蟻環(huán)算法效果最好，因?yàn)樗玫氖侨中畔?，而其余兩種算法用的是局部信息。蟻環(huán)離線(xiàn)更新方法很好地保證了殘留信息不至于無(wú)限積累，非最優(yōu)路徑會(huì)逐漸隨時(shí)間推移被忘記。 ()ijijQkd??? ijd()ij kQ???101 應(yīng)用 1/5 光網(wǎng)絡(luò)的智能管理 分布式動(dòng)態(tài)選路及波長(zhǎng)分配 ( RWA , Routing and Wavelength Assignment ) 是指在實(shí)時(shí)業(yè)務(wù)情況下光通路的路由選擇和波長(zhǎng)分配的優(yōu)化問(wèn)題 ,是實(shí)現(xiàn)自動(dòng)交換光網(wǎng)絡(luò) (ASON ,Automatically Switched Optical Network) 的關(guān)鍵技術(shù)之一。研究 RWA 問(wèn)題的目的是盡可能減少所需要的波長(zhǎng)數(shù)和降低光路連接請(qǐng)求的阻塞率。由于 RWA 問(wèn)題是 NPC 問(wèn)題 ,文獻(xiàn)中大多將 RWA 問(wèn)題拆分成路由和波長(zhǎng)分配兩個(gè)子問(wèn)題分別加以解決。但是 ,由于 RWA 問(wèn)題本身是一個(gè)不可分割的整體 ,把 RWA 分開(kāi)考慮必然造成難以得到全局最優(yōu)解的后果。 102 應(yīng)用 2/5 同時(shí) ,分布式的計(jì)算方式則克服了傳統(tǒng)集中式算法可擴(kuò)展性差的缺點(diǎn) ,更適應(yīng)現(xiàn)代頻繁變化的大型光網(wǎng)絡(luò)。因此 ,近年來(lái)國(guó)內(nèi)外對(duì)RWA 并行的分布式算法表現(xiàn)出極大的興趣 ,此類(lèi)算法建立的基礎(chǔ)是分層圖模型 。 用蟻群算法在分層圖模型的基礎(chǔ)上求解動(dòng)態(tài) RWA 問(wèn)題?；谖浵仭?信息素表 ” 來(lái)完成局部信息的刷新計(jì)算。以分布的形式做少量的計(jì)算來(lái)刷新全局路由選擇信息。 參考文獻(xiàn)： 基于蟻群系統(tǒng)的分布式 RWA 算法研究 孫海金 , 朱 娜 , 周乃富 2022 年 第 2 期 光通信研究 103 3/5 蟻群算法用于計(jì)算機(jī)網(wǎng)絡(luò)路由 參考文獻(xiàn)：計(jì)算機(jī)網(wǎng)絡(luò)中的組播路由算法 謝銀祥 104 應(yīng)用 4/5 105 5/5 蟻群算法用于聚類(lèi)（蟻群蟻卵分類(lèi)） 思想：把待聚類(lèi)的數(shù)據(jù)隨機(jī)散布在一個(gè)平面上，放置若干只虛擬螞蟻使其在平面上隨機(jī)運(yùn)動(dòng)。當(dāng)一只螞蟻遇到一個(gè)數(shù)據(jù)時(shí)即拾起并繼續(xù)行走，在行走過(guò)程中，如果遇到附近的數(shù)據(jù)與背負(fù)的數(shù)據(jù)相似性高于設(shè)置的標(biāo)準(zhǔn)時(shí)則將數(shù)據(jù)放置在該位置，繼續(xù)移動(dòng)。重復(fù)以上過(guò)程即可實(shí)現(xiàn)數(shù)據(jù)聚類(lèi)。 106 蟻群優(yōu)化算法 — 參考書(shū) 1 ? 智能蟻群算法及應(yīng)用 吳啟迪 上?？萍汲霭嫔鐝幕窘Y(jié)構(gòu)、算法特點(diǎn)、改進(jìn)方法、突破途徑、實(shí)現(xiàn)模式及應(yīng)用模式等方面進(jìn)行了論述。主要內(nèi)容有蟻群算法的由來(lái)、研究成果、應(yīng)用綜述、算法的具體描述及改進(jìn)、算法的典型優(yōu)化問(wèn)題求解模式、算法的典型應(yīng)用及拓展應(yīng)用。