蟻群算法原理與應(yīng)用(文件)
【正文】 [ ( ) ] [ ( ) ]( ) ( 1 )0 el sewi sekij ikkkis isijs a ll o w e dttj a l l o w e dttpt?????????? ???? ?? ?????20 ? 其中 allowedk={Ctabuk}表示螞蟻 k下一步允許選擇的城市；α為信息啟發(fā)式因子，表示軌跡的相對(duì)重要性，反映了螞蟻在運(yùn)動(dòng)過程中積累的信息在螞蟻運(yùn)動(dòng)時(shí)所起的作用，其值越大，則該螞蟻越傾向于選擇其它螞蟻經(jīng)過的路徑，螞蟻之間的協(xié)作性越強(qiáng)； β為期望啟發(fā)式因子，表示能見度的相對(duì)重要性，反映螞蟻在運(yùn)動(dòng)過程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度，其值越大，則該狀態(tài)狀態(tài)轉(zhuǎn)移概率越接近于貪心規(guī)則； ? ηij(t)為啟發(fā)函數(shù)， ηij(t) =1/dij ? 式中 dij表示相鄰兩個(gè)城市之間的距離。這種更新策略模仿了人類大腦記憶的特點(diǎn)，在新信息不斷存人大腦的同時(shí)，存儲(chǔ)在大腦中的舊信息隨著時(shí)間的推移逐漸淡化，甚至忘記。 , ( , )( ) ( 4 )k kijQk i jLt????? ???若 第 只 螞 蟻 在 本 次 循 環(huán) 中 經(jīng) 過0, 否 則24 ? AntQuantity模型 , 1 ( , )( ) ( 5 )k ijijQk t t i jdt?????? ???若 第 只 螞 蟻 在 和 之 間 經(jīng) 過0, 否 則25 ? AntDensity模型 ? 區(qū)別： – 式 (5)和式 (6)中利用的是局部信息，即螞蟻完成一步后更新路徑上的信息素；而式 (4)中利用的是整體信息，即螞蟻完成一個(gè)循環(huán)后更新所有路徑上的信息素，在求解 TSP時(shí)性能較好，因此通常采用式 (4)作為蟻群算法的基本模型。 (4)螞蟻數(shù)目 k←k+1 。 (8)根據(jù)公式 (2)和式 (3)更新每條路徑上的信息量。 QoS是網(wǎng)絡(luò)的一種安全機(jī)制 , 是用來解決網(wǎng)絡(luò)延遲和阻塞等問題的一種技術(shù)。 33 QoS網(wǎng)絡(luò)路由 ? 網(wǎng)絡(luò)路由方面的研究主要通過兩個(gè)途徑來提高服務(wù)質(zhì)量 (QoS）：一條途徑是節(jié)點(diǎn)控制；另一條途徑是整網(wǎng)或局部網(wǎng)絡(luò)控制。 – 時(shí)延 ? 時(shí)延是指一個(gè)報(bào)文或分組從網(wǎng)絡(luò)的一端傳送到另一端所需要的時(shí)間。 ? 平面 QoS路由 –所有路由器都在同一級(jí)內(nèi)， –以前對(duì) QoS路由的研究大多采用平面網(wǎng)絡(luò)， ? 分級(jí) QoS路由 –基本思想：將路由器分成多個(gè)邏輯組，每個(gè)組又可包含更小的組。 –局部信息素更新規(guī)則。 ? where, 0α0 1, cons is a constant. Adjusting the amount of pheromone by the rule can make the desirability of edges change dynamically. In this way, ants will make a better use of pheromone information。 ? 通過上述定義可見，如果所選路由的總費(fèi)用最小，同時(shí) QoS限制也滿足要求，那么最優(yōu)螞蟻所選路由的各鏈路上的信息素應(yīng)該增加更多。 50 平面 QoS螞蟻路由算法具體步驟 (2) ? (4)從蟻巢開始放出 m只螞蟻去尋找食物源，在第一個(gè)時(shí)間單位，每只螞蟻從節(jié)點(diǎn)集合中隨機(jī)地選擇一個(gè)節(jié)點(diǎn)，然后各螞蟻通過重復(fù)應(yīng)用狀態(tài)轉(zhuǎn)移規(guī)則來選擇各自的路徑。 ? (6)選擇建立了最小費(fèi)用并滿足 QoS限制的路由的螞蟻，然后使用全局更新規(guī)則對(duì)該螞蟻所選的路由的各路徑上的信息素進(jìn)行更新。 ? 在大多數(shù)應(yīng)用中，時(shí)延要求是最為重要的，為了方便起見，這里在研究 QoS路由時(shí)僅考慮時(shí)延限制。 56 算法構(gòu)造 (2) ? (4)根據(jù)此路由，確定每個(gè) level1節(jié)點(diǎn)內(nèi)的源一目的節(jié)點(diǎn)，作為蟻群算法的輸入，同時(shí)調(diào)用蟻群算法進(jìn)行選路 (稱為 level0路由 )，并記錄結(jié)果。 59 211112111111 , 0()0 L A NNNdij ijijjiNNdij ijijjiFFFF L C Pi f ZF H Zothe rw i seZ L D P??????????????? ? ??????其 中 表 示 內(nèi) 節(jié) 點(diǎn) 的 端 到 端 時(shí) 延 限 制60 參考文獻(xiàn) ? Zhang S B, Liu Z M. A QoS routing algorithm based on ant algorithm. Proceedings of the IEEE ICC, 2021,5:15811585 ? 張素兵 , 劉澤民 . 基于螞蟻算法的分級(jí) QoS 路由調(diào)度方法 . 北京郵電大學(xué)學(xué)報(bào) . 2021, 23(4):1115 61 ? /aai2021 –課件 –論文 。 57 分級(jí)路由實(shí)例 ? 尋找 → – 首先確定出 level1路由： x→ b→ c或 x→ a→ c – 假定選 x→ a→ c, 則可得出三個(gè)源一目的對(duì) : ? (, ) ? (, ) ? (, ) – 同時(shí)啟動(dòng)三個(gè)蟻群算法計(jì)算出滿足要求的路由鏈路 ? (→ → ), (→ ), ( → → → ) – 根據(jù)此結(jié)果，可擴(kuò)展出最終路由 ? → → → → → → → ) – 若此路由滿足要求就結(jié)束；否則，重新選定 level1路由，進(jìn)行新的選路。 ? (2)根據(jù)呼叫的源一目的節(jié)點(diǎn)，確定此源一目的節(jié)點(diǎn)是否在同一級(jí)內(nèi)：若在 (如→ )，直接在相應(yīng)級(jí) x內(nèi)調(diào)用蟻群算法進(jìn)行選路 (1evel0路由 )；若不在同一級(jí)內(nèi)，則執(zhí)行第 (3)步。 52 分級(jí) QoS螞蟻路由算法 ? 當(dāng)前的大多數(shù)大型網(wǎng)絡(luò) , 包括 Inter, 都使用分級(jí)選路方式 . 它的基本思想是 :
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1