【正文】 54 55 算法構(gòu)造 ? (1)初始化。 without the local updating, all ants would search in a narrow neighborhood of the best previous path. 00( , , ) ( 1 ) ( , , )phe ro i r s phe ro i r s c ons??? ? ?44 信息素全局更新規(guī)則 ? 對于第 i只螞蟻，如果節(jié)點(diǎn) r, s是該螞蟻所選路徑上的兩個(gè)相鄰節(jié)點(diǎn)，則信息素 phero(i, r, s)按公式1調(diào)節(jié) , 否則按公式 2調(diào)節(jié)。節(jié)點(diǎn)控制在單節(jié)點(diǎn)或單鏈路完成，主要控制業(yè)務(wù)對單節(jié)點(diǎn)共享資源的占用；整網(wǎng)或局部網(wǎng)絡(luò)控制通常通過對路由與信令的控制達(dá)到對業(yè)務(wù)流或業(yè)務(wù)連接在網(wǎng)絡(luò)中傳輸?shù)闹苯涌刂啤? , 1 ( , )( ) ( 6 )kijQ k t t i jt? ??????若 第 只 螞 蟻 在 和 之 間 經(jīng) 過0, 否 則26 基本蟻群算法的實(shí)現(xiàn) ? 以 TSP為例，基本蟻群算法的具體實(shí)現(xiàn)步驟如下： (1)參數(shù)初始化。 15 TSP (Traveling Salesman Problem) ? 有向圖 –有向圖 D的三元組為 (V, E, f)，其中 V是一個(gè)非空集合，其元素稱為有向圖的結(jié)點(diǎn)； E是一個(gè)集合，其元素稱為有向圖的弧段（邊）； f是從E到 VxV上的一個(gè)映射（函數(shù)）。 –若存在一個(gè)多項(xiàng)式時(shí)間 DTM程序，它在編碼策略 e之下求解判定問題 Π，即 L[Π, e]∈ P,則稱該判定問題屬于 P類問題。顯然，該啟發(fā)函數(shù)表示螞蟻從元素（城市） i轉(zhuǎn)移到元素（城市） j的期望程度。 28 基本蟻群算法程序流程圖 輸出程序計(jì)算結(jié)果 按式（ 2）和式（ 3）進(jìn)行信息量更新 修改禁忌表 按式（ 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)解。同時(shí)，假定 B(l)表示鏈路 l的可用帶寬，對于一個(gè)路由請求 w，路由算法如果能夠找到一條具有小費(fèi)用的路徑，同時(shí)滿足如下 4個(gè)條件，則此路由請求 w就可接受。當(dāng)某只螞蟻成功地完成路由選擇后，該螞蟻所選路由各路徑上的信息素根據(jù)局部更新規(guī)則進(jìn)行更新。 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 ? 張素兵 , 劉澤民 . 基于螞蟻算法的分級 QoS 路由調(diào)度方法 . 北京郵電大學(xué)學(xué)報(bào) . 2021, 23(4):1115 61 ? /aai2021 –課件 –論文 。 50 平面 QoS螞蟻路由算法具體步驟 (2) ? (4)從蟻巢開始放出 m只螞蟻去尋找食物源，在第一個(gè)時(shí)間單位，每只螞蟻從節(jié)點(diǎn)集合中隨機(jī)地選擇一個(gè)節(jié)點(diǎn)，然后各螞蟻通過重復(fù)應(yīng)用狀態(tài)轉(zhuǎn)移規(guī)則來選擇各自的路徑。 ? 平面 QoS路由 –所有路由器都在同一級內(nèi)， –以前對 QoS路由的研究大多采用平面網(wǎng)絡(luò)， ? 分級 QoS路由 –基本思想：將路由器分成多個(gè)邏輯組，每個(gè)組又可包含更小的組。 (8)根據(jù)公式 (2)和式 (3)更新每條路徑上的信息量。在 t時(shí)刻螞蟻 k由元素（城市） i轉(zhuǎn)移到元素（城市） j的狀態(tài)轉(zhuǎn)移概率： [ ( ) ] [ ( ) ], i f [ ( ) ] [ ( ) ]( ) ( 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ā)式因子，表示軌跡的相對重要性，反映了螞蟻在運(yùn)動(dòng)過程中積累的信息在螞蟻運(yùn)動(dòng)時(shí)所起的作用，其值越大，則該螞蟻越傾向于選擇其它螞蟻經(jīng)過的路徑，螞蟻之間的協(xié)作性越強(qiáng)； β為期望啟發(fā)式因子，表示能見度的相對重要性，反映螞蟻在運(yùn)動(dòng)過程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度，其值越大，則該狀態(tài)狀態(tài)轉(zhuǎn)移概率越接近于貪心規(guī)則； ? ηij(t)為啟發(fā)函數(shù)， ηij(t) =1/dij ? 式中 dij表示相鄰兩個(gè)城市之間的距離。 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 雙橋?qū)嶒?yàn) (Goss S, 1989) Naturwissenschaften 76, 579581 (1989) Selfanized Shortcuts in the Argentine Ant S. Goss, S. Aron, J. L. Deneubourg, and J. M. Pasteels Unit of Behavioural Eco