蟻群算法原理與應用-文庫吧在線文庫
【正文】 1路由 )。 51 平面 QoS螞蟻路由算法具體步驟 (3) ? (5)對所有的螞蟻重復第 (4)步，直到 m只螞蟻都完成了第 (4)步。, : the p r oc e ss de l a y , l oss r a t e o f n od e .rrrsN D N L r46 限制函數(shù) F的定義 121112 2 3112( ) ( ) ( )W he r e i s t he node num be r , A , B a nd C a r e posi t i v e r e a l c oe f f i c i e nt s.H( Z ) =0, if Z 0, othe r wis e H( Z ) =Z .(VVdij ijijjiNNijijjidij ij ij wwF F FF L C PF A H Z B H Z C H ZNZ P L B BZ D L??????? ? ??? ? ?????????31)( 1 ) ( 1 )ddij ij i iNdi i wiD P N N DZ N N L L??? ? ? ?? ? ??47 信息素的全局更新規(guī)則 ? 式中， N表示網(wǎng)絡的節(jié)點數(shù)目； A、 B和 C分別表示帶寬可用限制、端到端時延限制和端到端丟失率限制，且為正實數(shù)； ? F1表示費用限制； F2表示 QoS限制。 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的路由上，端到端時延限制為 (3)在 w的路由上，端到端丟失率限制為 (4)在目的節(jié)點，端到端時延抖動限制為 () wN DV d J?39 符號 ? Bw、 Dw、 Lw、 Jw表示 QoS要求的帶寬、時延、丟失率、抖動限制 ? DN：節(jié)點處理延時 ? DL：鏈路時延 ? V1： w路由的節(jié)點集合 ? E1： w路由的鏈路集合 ? LR：節(jié)點丟失率 ? NDV：目的節(jié)點 d的節(jié)點時延變化 40 算法設計 ? 蟻群算法的兩個步驟 : –按照信息素的量選擇路徑 –更新路徑上的信息素數(shù)量 ? 假定平面 QoS螞蟻路由算法中有 m只螞蟻，設計如下的三個規(guī)則： –狀態(tài)轉移規(guī)則 –全局信息素更新規(guī)則。 34 ? QoS指標： – 帶寬 ? 單位時間內(nèi)能夠在線路上傳送的數(shù)據(jù)量， bps(bit per second)。 –若 1M FLOPS，當 n=10, 需要 – n=20, 需要 1929年 – n=30, 需要 ? 時間復雜度 ? 空間復雜度 30 ? 算法標準 –正確性 –可用性 –可讀性 –執(zhí)行效率 –健壯性 31 蟻群算法應用 趙林亮 計算機應用技術研究所 32 Quality of Service, QoS ? QoS的英文全稱為 Quality of Service，中文名為服務質量 。 (3)螞蟻的禁忌表索引號 k=1。 21 ? 為了避免殘留信息素過多引起殘留信息淹沒啟發(fā)信息，在每只螞蟻走完一步或者完成對所有 n個城市的遍歷 (也即一個循環(huán)結束 )后，要對殘留信息進行更新處理。 –一個有向圖Ｄ可簡記為 (V, E). 16 TSP (Traveling Salesman Problem) ? TSP 設 C={c1, c2, …, } 是 n個城市的集合， L={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)是一個有向圖， TSP的目的是從有向圖 G中尋出長度最短的 Hamilton圈， 即一條對 C={c1, c2, …, } 中 n個元素（城市）訪問且只訪問一次的最短封閉曲線 17 TSP (Traveling Salesman Problem) ? TSP簡單形象描述 給定 n個城市，一個旅行商從某一城市出發(fā)，訪問各城市一次且僅有一次后再回到原出發(fā)城市，要求找出一條最短的巡回路徑 可分為對稱 TSP (Symmetric Traveling Salesman Problem) 和非對稱 TSP (Asymmetric Traveling Salesman Problem) ? TSP是 NPC問題 ? n城市規(guī)模的 TSP，存在 (n1)!/2條不同閉合路徑。 12 P、 NP、 NPC、 NPhard問題 ? NP類問題 (Nondeterministic Polynomial) –若存在一個多項式函數(shù) g(x) 和一個驗證算法 H, 對一類判定問題 A的任何一個“是”回答，滿足其輸入長度 d(s)不超過 g(d(I)), 其中 d(I)為 I的輸入長度，且驗證算法中 S為 I的“是”回答的計算時間不超過 g(d(I)), 則稱判定問題 A為非多項式確定問題。 therefore, ants choose whether to turn right or left with equal probability. c) At time t=1 trail is stronger on shorter edges, which are therefore, in the average, preferred by ants. 6 雙橋實驗 (Goss S, 1989) Naturwissenschaften 76, 579581 (1989) Selfanized Shortcuts in the Argentine Ant S. Goss, S. Aron, J. L. Deneubourg,
研究報告相關推薦
鄂ICP備17016276號-1