蟻群算法原理與應(yīng)用-在線瀏覽
2025-07-16 06:21本頁(yè)面
【正文】 {lij|ci, cj C}是集合 C中的元素（城市）兩兩連接的集合， dij(i, j=1,1,…,n) 是 lij的 Euclidean距離，即 ?22( ) ( )ij i j i jd x x y y? ? ? ?G=(C, L)是一個(gè)有向圖， TSP的目的是從有向圖 G中尋出長(zhǎng)度最短的 Hamilton圈， 即一條對(duì) C={c1, c2, …, } 中 n個(gè)元素（城市）訪問(wèn)且只訪問(wèn)一次的最短封閉曲線 17 TSP (Traveling Salesman Problem) ? TSP簡(jiǎn)單形象描述 給定 n個(gè)城市，一個(gè)旅行商從某一城市出發(fā)，訪問(wèn)各城市一次且僅有一次后再回到原出發(fā)城市，要求找出一條最短的巡回路徑 可分為對(duì)稱(chēng) TSP (Symmetric Traveling Salesman Problem) 和非對(duì)稱(chēng) TSP (Asymmetric Traveling Salesman Problem) ? TSP是 NPC問(wèn)題 ? n城市規(guī)模的 TSP，存在 (n1)!/2條不同閉合路徑。 1()niim b t?? ?{ ( ) | , }ij i jt c c C?? ? ?19 ? 螞蟻 k(k=1,2,…,m) 在運(yùn)動(dòng)過(guò)程中，根據(jù)各條路徑上的信息量決定其轉(zhuǎn)移方向。在搜索過(guò)程中，螞蟻根據(jù)各條路徑上的信息量及路徑的啟發(fā)信息來(lái)計(jì)算狀態(tài)轉(zhuǎn)移概率。對(duì)螞蟻 k而言， dij越小，則 ηij(t)越大， pijk也就越大。 21 ? 為了避免殘留信息素過(guò)多引起殘留信息淹沒(méi)啟發(fā)信息，在每只螞蟻?zhàn)咄暌徊交蛘咄瓿蓪?duì)所有 n個(gè)城市的遍歷 (也即一個(gè)循環(huán)結(jié)束 )后，要對(duì)殘留信息進(jìn)行更新處理。由此， t+n時(shí)刻在路徑 (i, j)上的信息量可按如下規(guī)則進(jìn)行調(diào)整 1( ) ( 1 ) ( ) ( ) ( 2)( ) ( ) ( 3)ij ij ijmkij ijkt n t ttt? ? ? ????? ? ? ? ? ?? ? ??22 ? 式中， ρ表示信息素?fù)]發(fā)系數(shù)，則 1ρ表示信息素殘留因子，為了防止信息的無(wú)限積累， ρ的取值范圍為 [0， 1), Δτij(t)表示本次循環(huán)中路徑 (i, j)上的信息素增量，初始時(shí)刻 Δτij(t) =0, Δτijk(t) 表示第 k只螞蟻在本次循環(huán)中留在路徑 (i, j)上的信息量。 23 ? AntCycle模型 ? 式中， Q表示信息素強(qiáng)度，它在一定程度上影響算法的收斂速度； Lk表示第 k只螞蟻在本次循環(huán)中所走路徑的總長(zhǎng)度。 , 1 ( , )( ) ( 6 )kijQ k t t i jt? ??????若 第 只 螞 蟻 在 和 之 間 經(jīng) 過(guò)0, 否 則26 基本蟻群算法的實(shí)現(xiàn) ? 以 TSP為例，基本蟻群算法的具體實(shí)現(xiàn)步驟如下： (1)參數(shù)初始化。 (3)螞蟻的禁忌表索引號(hào) k=1。 27 基本蟻群算法的實(shí)現(xiàn) (5)螞蟻個(gè)體根據(jù)狀態(tài)轉(zhuǎn)移概率公式 (1)計(jì)算的概率選擇元素 (城市 ) j 并前進(jìn)， j∈ {C tabuk}。 (7)若集合 C中元素 (城市 )未遍歷完，即 km，則跳轉(zhuǎn)到第 (4)步，否則執(zhí)行第 (8)步。 (9)若滿足結(jié)束條件，即如果循環(huán)次數(shù) Nc≥ Ncmax 則循環(huán)結(jié)束并輸出程序計(jì)算結(jié)果，否則清空禁忌表并跳轉(zhuǎn)到第 (2)步。 –若 1M FLOPS，當(dāng) n=10, 需要 – n=20, 需要 1929年 – n=30, 需要 ? 時(shí)間復(fù)雜度 ? 空間復(fù)雜度 30 ? 算法標(biāo)準(zhǔn) –正確性 –可用性 –可讀性 –執(zhí)行效率 –健壯性 31 蟻群算法應(yīng)用 趙林亮 計(jì)算機(jī)應(yīng)用技術(shù)研究所 32 Quality of Service, QoS ? QoS的英文全稱(chēng)為 Quality of Service，中文名為服務(wù)質(zhì)量 。 ? 在正常情況下，如果網(wǎng)絡(luò)只用于特定的無(wú)時(shí)間限制的應(yīng)用系統(tǒng)，并不需要 QoS，比如 Web應(yīng)用，或 Email設(shè)置等。當(dāng)網(wǎng)絡(luò)過(guò)載或擁塞時(shí)， QoS 能確保重要業(yè)務(wù)量不受延遲或丟棄，同時(shí)保證網(wǎng)絡(luò)的高效運(yùn)行。節(jié)點(diǎn)控制在單節(jié)點(diǎn)或單鏈路完成，主要控制業(yè)務(wù)對(duì)單節(jié)點(diǎn)共享資源的占用；整網(wǎng)或局部網(wǎng)絡(luò)控制通常通過(guò)對(duì)路由與信令的控制達(dá)到對(duì)業(yè)務(wù)流或業(yè)務(wù)連接在網(wǎng)絡(luò)中傳輸?shù)闹苯涌刂啤? 34 ? QoS指標(biāo)： – 帶寬 ? 單位時(shí)間內(nèi)能夠在線路上傳送的數(shù)據(jù)量， bps(bit per second)。它包括了發(fā)送時(shí)延，傳播時(shí)延，處理時(shí)延，他們的總和就是總時(shí)延 – 時(shí)延抖動(dòng) ? 變化的時(shí)延被稱(chēng)作抖動(dòng)（ Jitter） – 費(fèi)用 ? QoS路由的任務(wù) – 在網(wǎng)絡(luò)中尋找一條路徑，使其能滿足帶寬、時(shí)延、時(shí)延抖動(dòng)和費(fèi)用的限制 35 ? Wang Z等證明了，如果 QoS路由至少包含兩個(gè)限制時(shí)，它是一個(gè) NPC問(wèn)題。 36 ? 隨著 Inter的飛速發(fā)展，對(duì) QoS路由的研究已經(jīng)引起了眾多關(guān)注。 37 平面 QoS螞蟻路由算法 ? 問(wèn)題描述 –將網(wǎng)絡(luò)模型表示為一個(gè)有向圖 G =(V， E)， ? 其中 V是圖中所有交換節(jié)點(diǎn)組成的集合 ? E是圖中所有邊的集合 ? 每一條邊表示相鄰兩節(jié)點(diǎn)間的直達(dá)通信路徑 –不失一般性，假定相鄰兩節(jié)點(diǎn)間最多僅有一條邊。 38 () wB l B?11( ) ( ) wn V l ED N n D L l D??????1( 1 ( ) ) ( 1 )wnVLR n L?? ? ??(1)在 w的路由的每條路徑 l上，帶寬可用限制為 (2)在 w的路由上，端到端時(shí)延限制為 (3)在 w的路由上，端到端丟失率限制為 (4)在目的節(jié)點(diǎn)，端到端時(shí)延抖動(dòng)限制為 () wN DV d J?39 符號(hào) ? Bw、 Dw、 Lw、 Jw表示 QoS要求的帶寬、時(shí)延、丟失率、抖動(dòng)限制 ? DN：節(jié)點(diǎn)處理延時(shí) ? DL：鏈路時(shí)延 ? V1： w路由的節(jié)點(diǎn)集合
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1