蟻群算法原理與應(yīng)用-文庫吧資料
2025-05-21 06:21本頁面
【正文】 有效的解決方案。 – 時延 ? 時延是指一個報文或分組從網(wǎng)絡(luò)的一端傳送到另一端所需要的時間。因為路由直接關(guān)系到網(wǎng)絡(luò)性能，所以 QoS路由成為解決 QoS問題的核心技術(shù)之一，也是當(dāng)今網(wǎng)絡(luò)技術(shù)領(lǐng)域內(nèi)的一個研究熱點。 33 QoS網(wǎng)絡(luò)路由 ? 網(wǎng)絡(luò)路由方面的研究主要通過兩個途徑來提高服務(wù)質(zhì)量 (QoS）：一條途徑是節(jié)點控制；另一條途徑是整網(wǎng)或局部網(wǎng)絡(luò)控制。但是對關(guān)鍵應(yīng)用和多媒體應(yīng)用就十分必要。 QoS是網(wǎng)絡(luò)的一種安全機(jī)制 , 是用來解決網(wǎng)絡(luò)延遲和阻塞等問題的一種技術(shù)。 28 基本蟻群算法程序流程圖 輸出程序計算結(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)解。 (8)根據(jù)公式 (2)和式 (3)更新每條路徑上的信息量。 (6)修改禁忌表指針，即選擇好之后將螞蟻移動到新的元素 (城市 )，并把該元素 (城市 )移動到該螞蟻個體的禁忌表中。 (4)螞蟻數(shù)目 k←k+1 。令時間 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 。 , ( , )( ) ( 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)作為蟻群算法的基本模型。 ? 根據(jù)信息素更新策略的不同， Dorigo M提出了三種不同的基本蟻群算法模型，分別稱之為 AntCycle模型、 AntQuantity模型及 AntDensity模型，其差別在于 Δτijk(t)求法的不同。這種更新策略模仿了人類大腦記憶的特點，在新信息不斷存人大腦的同時，存儲在大腦中的舊信息隨著時間的推移逐漸淡化，甚至忘記。顯然，該啟發(fā)函數(shù)表示螞蟻從元素（城市） i轉(zhuǎn)移到元素（城市） j的期望程度。在 t時刻螞蟻 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)動過程中積累的信息在螞蟻運(yùn)動時所起的作用，其值越大，則該螞蟻越傾向于選擇其它螞蟻經(jīng)過的路徑，螞蟻之間的協(xié)作性越強(qiáng)； β為期望啟發(fā)式因子，表示能見度的相對重要性，反映螞蟻在運(yùn)動過程中啟發(fā)信息在螞蟻選擇路徑中的受重視程度，其值越大，則該狀態(tài)狀態(tài)轉(zhuǎn)移概率越接近于貪心規(guī)則； ? ηij(t)為啟發(fā)函數(shù)， ηij(t) =1/dij ? 式中 dij表示相鄰兩個城市之間的距離。這里用禁忌表 tabuk來記錄螞蟻 k當(dāng)前所走過的城市，集合隨著 tabuk進(jìn)化過程做動態(tài)調(diào)整。 ?18 基本蟻群算法數(shù)學(xué)模型 ? 設(shè) bi(t)表示 t時刻位于元素 i的螞蟻數(shù)目， τij (t)為 t時刻路徑 (i, j)上的信息量， n表示 TSP規(guī)模， m為蟻群中螞蟻總數(shù)，則 是 t時刻集合 C中元素（城市）兩兩連接 lij上殘留信息量的集合，在初始時刻各條路徑上的信息量相等，并設(shè) τij(0)=const, 基本蟻群算法的尋優(yōu)是通過有向圖 g=(C, L, Γ)實現(xiàn)的。 – E中的元素總是和 V中的序偶對有對應(yīng)關(guān)系，可用 V中的序偶代替 E中的元素。即螞蟻是反應(yīng)型適應(yīng)性主體 –在個體水平上，每只螞蟻僅根據(jù)環(huán)境做出獨立選擇；在群體水平上，單只螞蟻的行為是隨機(jī)的，但蟻群可通過自組織過程形成高度有序的群體行為。 Asymmetric ? NPhard類問題 – NPC NPhard ?NP P NPhard NPC 14 基本蟻群算法模型 ? 基本假設(shè) –螞蟻之間通過信息素和環(huán)境進(jìn)行通信。 – NP類問題是所有可用 NDTM (NonDeterministic onetape Turing Machine)在多項式時間內(nèi)求解的判定問題 Π的集合 13 P、 NP、 NPC、 NPhard問題 ? NPC類問題 (NPComplete) – 是 NP類中最困難的一類問題。 –若存在一個多項式時間 DTM程序，它在編碼策略 e之下求解判定問題 Π，即 L[Π, e]∈ P,則稱該判定問題屬于 P類問題。 therefore, ants choose whether to turn right or left with equal probability. c) At time t=1 t
研究報告相關(guān)推薦
鄂ICP備17016276號-1