蟻群算法原理與應(yīng)用(存儲版)
【正文】 學(xué)者基于蟻群算法提出了許多行之有效的解決方案。 42 ? where, q is a random number uniformly distributed in [0,1], qo a constant satisfying [0,1]。 ? (2)刪除帶寬小于需求帶寬的鏈路，把網(wǎng)絡(luò)濾成一個(gè)新的簡單網(wǎng)絡(luò)。 52 分級 QoS螞蟻路由算法 ? 當(dāng)前的大多數(shù)大型網(wǎng)絡(luò) , 包括 Inter, 都使用分級選路方式 . 它的基本思想是 : 路由器被分成多個(gè)邏輯組 , 每個(gè)組又可以包含更小的組 . ? 計(jì)算機(jī)網(wǎng)絡(luò)分簇結(jié)構(gòu)特點(diǎn) –網(wǎng)絡(luò)管理 –路由計(jì)算 –資源利用 – Ad hoc網(wǎng)絡(luò) 53 ? 考慮一個(gè)二級網(wǎng)絡(luò)。 57 分級路由實(shí)例 ? 尋找 → – 首先確定出 level1路由： x→ b→ c或 x→ a→ c – 假定選 x→ a→ c, 則可得出三個(gè)源一目的對 : ? (, ) ? (, ) ? (, ) – 同時(shí)啟動(dòng)三個(gè)蟻群算法計(jì)算出滿足要求的路由鏈路 ? (→ → ), (→ ), ( → → → ) – 根據(jù)此結(jié)果，可擴(kuò)展出最終路由 ? → → → → → → → ) – 若此路由滿足要求就結(jié)束；否則，重新選定 level1路由，進(jìn)行新的選路。 56 算法構(gòu)造 (2) ? (4)根據(jù)此路由，確定每個(gè) level1節(jié)點(diǎn)內(nèi)的源一目的節(jié)點(diǎn)，作為蟻群算法的輸入，同時(shí)調(diào)用蟻群算法進(jìn)行選路 (稱為 level0路由 )，并記錄結(jié)果。 ? (6)選擇建立了最小費(fèi)用并滿足 QoS限制的路由的螞蟻，然后使用全局更新規(guī)則對該螞蟻所選的路由的各路徑上的信息素進(jìn)行更新。 ? 通過上述定義可見，如果所選路由的總費(fèi)用最小，同時(shí) QoS限制也滿足要求，那么最優(yōu)螞蟻所選路由的各鏈路上的信息素應(yīng)該增加更多。 –局部信息素更新規(guī)則。 – 時(shí)延 ? 時(shí)延是指一個(gè)報(bào)文或分組從網(wǎng)絡(luò)的一端傳送到另一端所需要的時(shí)間。 QoS是網(wǎng)絡(luò)的一種安全機(jī)制 , 是用來解決網(wǎng)絡(luò)延遲和阻塞等問題的一種技術(shù)。 (4)螞蟻數(shù)目 k←k+1 。這種更新策略模仿了人類大腦記憶的特點(diǎn)，在新信息不斷存人大腦的同時(shí)，存儲在大腦中的舊信息隨著時(shí)間的推移逐漸淡化，甚至忘記。 ?18 基本蟻群算法數(shù)學(xué)模型 ? 設(shè) bi(t)表示 t時(shí)刻位于元素 i的螞蟻數(shù)目， τij (t)為 t時(shí)刻路徑 (i, j)上的信息量， n表示 TSP規(guī)模， m為蟻群中螞蟻總數(shù)，則 是 t時(shí)刻集合 C中元素（城市）兩兩連接 lij上殘留信息量的集合，在初始時(shí)刻各條路徑上的信息量相等，并設(shè) τij(0)=const, 基本蟻群算法的尋優(yōu)是通過有向圖 g=(C, L, Γ)實(shí)現(xiàn)的。 – NP類問題是所有可用 NDTM (NonDeterministic onetape Turing Machine)在多項(xiàng)式時(shí)間內(nèi)求解的判定問題 Π的集合 13 P、 NP、 NPC、 NPhard問題 ? NPC類問題 (NPComplete) – 是 NP類中最困難的一類問題。 ants can choose to go around it following one of the two different paths with equal probability. c) On the shorter path more pheromone is laid down. 5 Fig. 2. An example with artificial ants a) The initial graph with distances. b) At time t=0 there is no trail on the graph edges。每只螞蟻僅根據(jù)其周圍的局部環(huán)境作出反應(yīng)，也只對周圍的局部環(huán)境產(chǎn)生影響； –螞蟻對環(huán)境的反應(yīng)由其內(nèi)部模式?jīng)Q定。在搜索過程中，螞蟻根據(jù)各條路徑上的信息量及路徑的啟發(fā)信息來計(jì)算狀態(tài)轉(zhuǎn)移概率。 23 ? AntCycle模型 ? 式中， Q表示信息素強(qiáng)度，它在一定程度上影響算法的收斂速度； Lk表示第 k只螞蟻在本次循環(huán)中所走路徑的總長度。 (7)若集合 C中元素 (城市 )未遍歷完，即 km，則跳轉(zhuǎn)到第 (4)步，否則執(zhí)行第 (8)步。當(dāng)網(wǎng)絡(luò)過載或擁塞時(shí)， QoS 能確保重要業(yè)務(wù)量不受延遲或丟棄，同時(shí)保證網(wǎng)絡(luò)的高效運(yùn)行。 36 ? 隨著 Inter的飛速發(fā)展，對 QoS路由的研究已經(jīng)引起了眾多關(guān)注。 ? pi (r, s) represents the probability with which the ith ant positioned on node r chooses the next node s, ? phero(i, r, s) the amount of pheromone deposited on the edge between the nodes r and s currently by the ith type of ants, ? Ji(r) the nodes between which and the node r there is an edge and by which the ithtype ant has not passed during its choosing path. 43 信息素局部更新規(guī)則 ? 對于第 i只螞蟻，如果節(jié)點(diǎn) r, s是該螞蟻所選路徑上的兩個(gè)相鄰節(jié)點(diǎn)，則信息素 phero(i, r, s)用下式來調(diào)節(jié)；否則，不調(diào)節(jié)。 ? (3)初始化網(wǎng)絡(luò)拓?fù)渲懈鬟叺南鄳?yīng)信息素。每個(gè)路由器即為一個(gè)level0節(jié)點(diǎn)，由多個(gè) level0節(jié)點(diǎn)和 level0鏈路形成的 LAN稱為 level1節(jié)點(diǎn)， level1節(jié)點(diǎn)之間通過 level1鏈路連接。 58 ? 基于蟻群算法的 level0路由算法的狀態(tài)轉(zhuǎn)移規(guī)則和信息素局部更新規(guī)則同前所述，但對信息素全局更新規(guī)則中的限制函數(shù) F的定義做了如下改進(jìn)。 ? (3)根據(jù) level1節(jié)點(diǎn)的相鄰關(guān)系，選最少level1節(jié)點(diǎn)數(shù)的路由 (稱為 level
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號-1