蟻群算法原理與應(yīng)用(編輯修改稿)
2025-06-18 06:21 本頁面
【文章內(nèi)容簡介】 強度，它在一定程度上影響算法的收斂速度； Lk表示第 k只螞蟻在本次循環(huán)中所走路徑的總長度。 , ( , )( ) ( 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)中利用的是整體信息，即螞蟻完成一個循環(huán)后更新所有路徑上的信息素，在求解 TSP時性能較好，因此通常采用式 (4)作為蟻群算法的基本模型。 , 1 ( , )( ) ( 6 )kijQ k t t i jt? ??????若 第 只 螞 蟻 在 和 之 間 經(jīng) 過0, 否 則26 基本蟻群算法的實現(xiàn) ? 以 TSP為例，基本蟻群算法的具體實現(xiàn)步驟如下： (1)參數(shù)初始化。令時間 t=0和循環(huán)次數(shù) Nc=0，設(shè)置最大循環(huán)次數(shù) Ncmax, 將 m個螞蟻置于 n個元素(城市 )上，令有向圖上每條邊 (i, j)的初始化信息量 τij(t)=const, 其中 const表示常數(shù)，且初始時刻Δτij(0)=0 (2)循環(huán)次數(shù) Nc← Nc+1 。 (3)螞蟻的禁忌表索引號 k=1。 (4)螞蟻數(shù)目 k←k+1 。 27 基本蟻群算法的實現(xiàn) (5)螞蟻個體根據(jù)狀態(tài)轉(zhuǎn)移概率公式 (1)計算的概率選擇元素 (城市 ) j 并前進， j∈ {C tabuk}。 (6)修改禁忌表指針，即選擇好之后將螞蟻移動到新的元素 (城市 )，并把該元素 (城市 )移動到該螞蟻個體的禁忌表中。 (7)若集合 C中元素 (城市 )未遍歷完，即 km，則跳轉(zhuǎn)到第 (4)步，否則執(zhí)行第 (8)步。 (8)根據(jù)公式 (2)和式 (3)更新每條路徑上的信息量。 (9)若滿足結(jié)束條件，即如果循環(huán)次數(shù) Nc≥ Ncmax 則循環(huán)結(jié)束并輸出程序計算結(jié)果，否則清空禁忌表并跳轉(zhuǎn)到第 (2)步。 28 基本蟻群算法程序流程圖 輸出程序計算結(jié)果 按式（ 2）和式（ 3）進行信息量更新 修改禁忌表 按式（ 1）選擇下一元素 螞蟻 k=1 循環(huán)次數(shù) Nc← Nc+1 初始化 開始 結(jié)束 K≥m 滿足結(jié)束條件 螞蟻 k=k+1 N Y Y N 29 ? 復(fù)雜度分析 –對于 TSP，所有可行的路徑共有 (n1)!/2條，以此路徑比較為基本操作，則需要 (n1)!/21次基本操作才能保證得到絕對最優(yōu)解。 –若 1M FLOPS，當(dāng) n=10, 需要 – n=20, 需要 1929年 – n=30, 需要 ? 時間復(fù)雜度 ? 空間復(fù)雜度 30 ? 算法標準 –正確性 –可用性 –可讀性 –執(zhí)行效率 –健壯性 31 蟻群算法應(yīng)用 趙林亮 計算機應(yīng)用技術(shù)研究所 32 Quality of Service, QoS ? QoS的英文全稱為 Quality of Service，中文名為服務(wù)質(zhì)量 。 QoS是網(wǎng)絡(luò)的一種安全機制 , 是用來解決網(wǎng)絡(luò)延遲和阻塞等問題的一種技術(shù)。 ? 在正常情況下，如果網(wǎng)絡(luò)只用于特定的無時間限制的應(yīng)用系統(tǒng)，并不需要 QoS，比如 Web應(yīng)用，或 Email設(shè)置等。但是對關(guān)鍵應(yīng)用和多媒體應(yīng)用就十分必要。當(dāng)網(wǎng)絡(luò)過載或擁塞時， QoS 能確保重要業(yè)務(wù)量不受延遲或丟棄，同時保證網(wǎng)絡(luò)的高效運行。 33 QoS網(wǎng)絡(luò)路由 ? 網(wǎng)絡(luò)路由方面的研究主要通過兩個途徑來提高服務(wù)質(zhì)量 (QoS）：一條途徑是節(jié)點控制；另一條途徑是整網(wǎng)或局部網(wǎng)絡(luò)控制。節(jié)點控制在單節(jié)點或單鏈路完成，主要控制業(yè)務(wù)對單節(jié)點共享資源的占用；整網(wǎng)或局部網(wǎng)絡(luò)控制通常通過對路由與信令的控制達到對業(yè)務(wù)流或業(yè)務(wù)連接在網(wǎng)絡(luò)中傳輸?shù)闹苯涌刂啤Ｒ驗槁酚芍苯雨P(guān)系到網(wǎng)絡(luò)性能，所以 QoS路由成為解決 QoS問題的核心技術(shù)之一，也是當(dāng)今網(wǎng)絡(luò)技術(shù)領(lǐng)域內(nèi)的一個研究熱點。 34 ? QoS指標： – 帶寬 ? 單位時間內(nèi)能夠在線路上傳送的數(shù)據(jù)量， bps(bit per second)。 – 時延 ? 時延是指一個報文或分組從網(wǎng)絡(luò)的一端傳送到另一端所需要的時間。它包括了發(fā)送時延，傳播時延，處理時延，他們的總和就是總時延 – 時延抖動 ? 變化的時延被稱作抖動（ Jitter） – 費用 ? QoS路由的任務(wù) – 在網(wǎng)絡(luò)中尋找一條路徑，使其能滿足帶寬、時延、時延抖動和費用的限制 35 ? Wang Z等證明了，如果 QoS路由至少包含兩個限制時，它是一個 NPC問題。傳統(tǒng)的路由算法很難有效地解決 NPC問題，因此一些學(xué)者基于蟻群算法提出了許多行之有效的解決方案。 36 ? 隨著 Inter的飛速發(fā)展，對 QoS路由的研究已經(jīng)引起了眾多關(guān)注。 ? 平面 QoS路由 –所有路由器都在同一級內(nèi)， –以前對 QoS路由的研究大多采用平面網(wǎng)絡(luò)， ? 分級 QoS路由 –基本思想：將路由器分成多個邏輯組，每個組又可包含更小的組。 37 平面 QoS螞蟻路由算法 ? 問題描述 –將網(wǎng)絡(luò)模型表示為一個有向圖 G =(V， E)， ? 其中 V是圖中所有交換節(jié)點組成的集合 ? E是圖中所有邊的集合 ? 每一條邊表示相鄰兩節(jié)點間的直達通信路徑 –不失一般性，假定相鄰兩節(jié)點間最多僅有一條邊。同時，假定 B(l)表示鏈路 l的可用帶寬，對于一個路由請求 w，路由算法如果能夠找到一條具有小費用的路徑，同時滿足如下 4個條件，則此路由請求 w就可接受。 38 () wB l B?11( ) ( ) wn V l ED N n D L l D??????1( 1 ( ) ) ( 1 )wn
研究報告相關(guān)推薦
鄂ICP備17016276號-1