【正文】 , 若第k只螞蟻在本次循環(huán)中經(jīng)過(i,j)否則(34)在 ant quantity system 和 ant density system， ?244。ij 分別為：Qdij0,?244。ij k (t) = {Q0,,第k只螞蟻在t到t+1時間段之間經(jīng)過(i,j)否則第k只螞蟻在t到t+1時間段之間經(jīng)過(i,j)否則(35)(36)其區(qū)別在于:式（35）, (36)兩種模型中利用的是局部信息，即每個螞蟻不是在整個路徑結(jié)束后釋放信息素，而是在完成每一步(從一個城市到達另外一個城市后)更新所有(36),每當(dāng)螞蟻經(jīng)過邊(i,j)時，濃度為常量Q 的信息素被釋放在這條邊上。對于(35)．每當(dāng)螞蟻經(jīng)過邊(i,j)時．濃度為Qd ij的信息索被釋放在這條邊上。很明顯，在(26) 中，螞蟻釋放的信息索濃度與邊長度d 無關(guān)。在(35)中，這兩者就建立了相關(guān)性 也就是說．螞蟻傾向于選擇下一步較短的路徑.而式（34）利用的是整體信息，螞蟻在一個循環(huán)(對所有 n 個城市的訪問)以后，更新所有路徑上的信息素。因此，在求解 TSP 問題時 ant cycle system 性[14] 蟻群算法的優(yōu)缺點 蟻群算法優(yōu)點由以上所述，蟻群算法是一種有效的隨機搜索算法，具有如下優(yōu)點：(1) 蟻群算法是一種自然選擇算法，是基于螞蟻覓食而建立最優(yōu)路徑的原理機理。(2) 蟻群算法本質(zhì)上是一種分布式的并行算法。自然界螞蟻的這種分布式行為將引向蟻群在完成某項工作時，許多螞蟻都會為共同的目的進行同樣的工作，而且最終工作事務(wù)的完成不會由于其中某些個體的缺陷而受到影響。蟻群20?244。ij(t)={?244。ijk(t)={能較好。因而我們采用式（34）作為基本模型。上海海洋大學(xué)碩士學(xué)位論文的這種群體式分布特性使得該算法具有較強的全局搜索能力，同時也增加了算法的可靠性。(3) 正反饋機制 由蟻群的覓食來看，螞蟻能夠最終找到最優(yōu)路徑，直接依賴于最優(yōu)路徑上信息素的堆積，而信息素的堆積卻是一個正反饋的過程。這樣正反饋就縮小了螞蟻搜索的范圍，從而保證了蟻群系統(tǒng)以求的最優(yōu)解為宗旨來進化，很顯然，算法在正反饋作用下，蟻群算法得以自組織進化，從而使的問題在一定程度上的取得了滿意解。(4) 自組織性 自組織是生物體的典型特征，生物學(xué)上認為，由于這類生物個體作用簡單，而個體之間的協(xié)作作用就特別的明顯，因此可以把它們當(dāng)做一個整體來研究，也可以把它們看做一個獨立的生物體。這類群落生物體個體相互作用。協(xié)同完成某項群體工作，自然就體現(xiàn)出很強的自組織特性，該自組織特性大大增強了該算法的魯莽性。 蟻群算法不足任何事物都具有兩面性，作為一種新興的仿生優(yōu)化算法，螞蟻算法同樣也存在一些缺點[36]：(1) 搜索時間長根據(jù)TSP問題定義描述，在解決規(guī)模為n的TSP問題的時候，我們所能計算出得所有可以行進的路由條數(shù)共有(n ?1)!2。在以TSP問題為背景的蟻群算法中，我們以比較路徑作為蟻群算法的基本操作，根據(jù)這樣的推理機制，若要找得到絕對最優(yōu)路由線路的話就需要(n ?1)!21次路徑比較操作。我們拿每秒可執(zhí)行100萬次浮點運算的計算機來說，當(dāng)n=；當(dāng)n=3017需要較長的搜素時間，且收斂速度也較慢。很明顯，這對于未來大規(guī)模的計算機網(wǎng)絡(luò)通信計算系統(tǒng)來說，將是一個很大的挑戰(zhàn)。(2) 易陷于局部最優(yōu)解蟻群算法的自組織系統(tǒng)是通過正反饋和負反饋的結(jié)合，來實現(xiàn)系統(tǒng)的自我創(chuàng)造和自我更新。但是由于蟻群算法正反饋機制作用太強，當(dāng)搜索到一定程度后，負反饋僅僅保持構(gòu)造解得范圍，但是算法采用的反饋方式是在有較優(yōu)解經(jīng)過的路徑上留下更多的信息素，更多的信息素又可以引來更多的螞蟻，這個正反饋的過程就使得初始值不斷擴大，同時縮小了搜素范圍，很容易陷入局部最10年才能找到最優(yōu)解。因此當(dāng)n較大時，對于蟻群算法來說就上海海洋大學(xué)碩士學(xué)位論文優(yōu)解。這樣就不能夠?qū)饪臻g進一步搜索，也很不利于發(fā)現(xiàn)更好的解。 局部最優(yōu)解判斷為了提高蟻群算法的全局搜索能力及其搜索速度，防止它過早陷入局部最優(yōu)解。為此本章下面部分給出了一種判斷陷入局部最優(yōu)的策略，并以此方法為指導(dǎo)，來利用和控制算法中各個參數(shù)的取值和變化，從而以高概率跳出局部最優(yōu)解，以求得全局最優(yōu)解。蟻群系統(tǒng)在進行路由選擇時依據(jù)的是路徑上信息素的強度，某條路徑上信息素強度大，則螞蟻選擇該路徑的概率就越大，反之，螞蟻選擇其他路徑的概率就越小。我們認為當(dāng)螞蟻所走的路徑是其他各條信息素強度最大的路徑的組合時，螞蟻再路由到其他的路徑的概率就很小的，這時螞蟻所走的路徑，我們稱之為信[8]此時蟻群算法陷入局部最優(yōu)。于是，我們在求解 TSP 問題時我們可以用信息素強度最大路徑的長度 LM 和算法算出路徑最小路徑的長度 LMIN 相比較，來判斷算法是否陷入局部最優(yōu)。當(dāng)LM LMIN 時，那么此時算法還沒有進入局部最優(yōu)；當(dāng) LM ≥ LMIN 時，我們可以判斷算法此時有可能進入局部最優(yōu)，等算法再運行幾次后還是這個結(jié)果，那么就可以判斷算法陷入局部最優(yōu)啦！ 算法改進思路在蟻群算法系統(tǒng)中，人工螞蟻具有人類記憶的功能機制，那么隨著時間的推移，之前螞蟻釋放的信息素就會逐漸消失掉。本文在蟻群系統(tǒng)數(shù)學(xué)模型中，我們用參數(shù) 241。 表示信息素的揮發(fā)因子，則 1 241。 就表示信息素遺留因子。 241。 的大小與蟻群算法的全局搜索能力及其收斂速度有著直接的關(guān)系；而 1 241。 反應(yīng)了蟻群個體之間相互影響的強弱。當(dāng) 241。 過大時螞蟻會再次選擇以前搜索過的路徑概率加大，同時蟻群算法的隨機性以及全局搜索能力也會受到影響，因此，借助一定的軟機制減小 241。 可以提高算法的全局搜素能力和隨機性，不過這樣做會降低算法的收斂速度。如前所述，在蟻周系統(tǒng)模型中，為了更好地利用蟻群系統(tǒng)的全局反饋信息，22息素強度最大路徑。當(dāng)該算法再運行一段時間之后，螞蟻就只走某一條路徑時，上海海洋大學(xué)碩士學(xué)位論文我們使用 Q 記錄了螞蟻循環(huán)一周時釋放在其經(jīng)過的路徑上的信息素總量,這樣算法就以正反饋方式搜索到問題全局最好解。Q 值與鏈路上的信息素累積強度是成正比的，也就是說 Q 值越大，則螞蟻在已經(jīng)過的鏈路上信息素累積程度就會加強，這樣螞蟻的正反饋搜索機制性能也就得到了加強，這對提高算法的收斂速度有很大幫助。當(dāng) LM ≥ LMIN ，此時蟻群算法可能陷入了局部最優(yōu)，這里我們設(shè)定信息素揮發(fā)因子 241。 的初始值 241。 (t0 ) = 1，則當(dāng)蟻群算法所求最優(yōu)解在 Nc次循環(huán)內(nèi)沒有明顯改進時，我們可以通過調(diào)整 Q 和 241。 的取值以高概率跳出局部最優(yōu)。將 Q 的值減小即: Q(t+1) = 241。 (t) Q(t)[7] (t ), (t )241。min241。 (t +1) = ∫241。 min,否則（37）（38）式中， 241。min 為 241。 的的最小值，可以防止 241。 過小會使算法的收斂速度降低。同時，為了提高該算法的全局搜索能力和算法的隨機性能，算法還在每次循環(huán)結(jié)束時求出最優(yōu)解并將其保留。當(dāng)算法將給定的參數(shù)改變后，仍然繼續(xù)運行。 基于改進蟻群算法的 QoS 路由算法當(dāng)將蟻群算法應(yīng)用于計算機網(wǎng)絡(luò)路由時，我們把蟻穴當(dāng)做源節(jié)點，把食物源當(dāng)作為目的節(jié)點，那么分組數(shù)據(jù)包就認為是一個個螞蟻，使用路由表來代替螞蟻在經(jīng)過的路徑上留下的信息素，路由表中信息素的強度以概率值的形式來表示，同時要求路由節(jié)點維持一個路由表。這里的螞蟻尋路原理與螞蟻根據(jù)信息素的多少來選擇路徑具有本質(zhì)的一致性。螞蟻安照一定的周期來更行信息素表即路由表，通過信息素表來選擇下一步要走的路徑，經(jīng)過 Nc迭代后,找到滿足 QoS 路由約束條件的路徑，這條路徑就是所要求的最優(yōu)解。根據(jù)第二章中無線 Mesh 網(wǎng)絡(luò) QoS 路由數(shù)學(xué)模型和本章改進蟻群算法的思路，下面給出基于改進蟻群算法的無線 Mesh 網(wǎng)絡(luò)中 QoS 路由算法的步驟：(1)首先構(gòu)造無線 Mesh 網(wǎng)絡(luò)系統(tǒng)架構(gòu)，算法隨機給出 R 個節(jié)點作為網(wǎng)絡(luò)節(jié)點，然后從這些節(jié)點中選出 P 個子系統(tǒng)的中心節(jié)點，那么 P 個子系統(tǒng)有 P 個中心節(jié)點；然后根據(jù)這 P 個子系統(tǒng)中心節(jié)點來訪問其他節(jié)點的花費來把剩余的節(jié)點歸入到 P23將241。改為函數(shù)：上海海洋大學(xué)碩士學(xué)位論文個子系統(tǒng)中，就這樣就形成了 P 個網(wǎng)絡(luò)子系統(tǒng)。其中，各個子節(jié)點和中心節(jié)點之間以及 P 個中心節(jié)點之間是聯(lián)通的。(2)設(shè)置無線 Mesh 網(wǎng)絡(luò)系統(tǒng)參數(shù) R、P 的初始值以及算法各個參數(shù)的初始化。(3)設(shè)定無線 Mesh 網(wǎng)絡(luò)系統(tǒng)架構(gòu)中各個鏈路上路由值，初始時設(shè)置各個節(jié)點和其所在子系統(tǒng)中心節(jié)點之間鏈路路由值大于其他鏈路的初始路由信息值，設(shè)定算法中螞蟻數(shù)目為 m 只，并放置到各個源節(jié)點。(4)放置到源節(jié)點的螞蟻開始運動，它們首先判斷源節(jié)點所在的子系統(tǒng)，然后跳轉(zhuǎn)到源節(jié)點所在的子系統(tǒng)的中心節(jié)點；然后按照禁忌表元素值，每只螞蟻根據(jù)信息素表的概率值來選擇下一步要走的節(jié)點，然后再判斷該節(jié)點所在的子系統(tǒng)，并找出其中心節(jié)點，同時比較從當(dāng)前節(jié)點經(jīng)過下一步節(jié)點到其中心節(jié)點的花費以及從當(dāng)前中心節(jié)點直接到下一跳節(jié)點的中心節(jié)點的花費的大小，螞蟻選擇從當(dāng)前子系統(tǒng)到下一子系統(tǒng)的路徑就是二者路徑花費較小的路徑。此時，螞蟻完成一次路由選擇后就根據(jù)局部信息素更新規(guī)則來更新其所經(jīng)過的路徑上的各鏈路信息素強度值。(5)所有的 m 只螞蟻執(zhí)行第四步路由選擇規(guī)則，若每只螞蟻都已經(jīng)完成一個完整的路徑，則對當(dāng)前最優(yōu)路徑上的信息素進行全局更新。(6)判斷算法是否陷入局部最優(yōu)，若算法陷入局部最優(yōu)則執(zhí)行步驟(7)，否則，算法繼續(xù)運行；(7)改變算法的參數(shù)(8)比較選擇使用最小花費并滿足 QoS 路由約束的螞蟻。(9)重復(fù)第(4)～(8)步，直到滿足結(jié)束條件。 本章小結(jié)本章首先研究了基本蟻群算法原理，給出 TSP 問題的描述及解決 TSP 問題的蟻群算法模型，同時分析了蟻群算法的優(yōu)缺點。為了克服蟻群算法搜索時間長和易陷于局部最優(yōu)解的缺點，通過研究基本蟻群算法陷入局部最優(yōu)解原因及判斷方法給出了改進蟻群算法的思路，最后根據(jù)第二章中無線 Mesh 網(wǎng)絡(luò) QoS 路由數(shù)學(xué)模型和本章改進蟻群算法的思路，提出了基于改進蟻群算法的無線 Mesh 網(wǎng)絡(luò) QoS 路由算法。24上海海洋大學(xué)碩士學(xué)位論文第四章 實驗仿真與結(jié)果分析 仿真實驗環(huán)境硬件平臺：CPU: Intel Core(TM)2 Duo Processor。 內(nèi)存 2094996 KB操作系統(tǒng)：Windows Server 2003仿真軟件：MATLAB R2009a , Visual C++. 網(wǎng)絡(luò)拓撲與參數(shù)設(shè)定根據(jù)無線 Mesh 網(wǎng)絡(luò)拓撲架構(gòu)，我們從 R 個網(wǎng)絡(luò)節(jié)點中選出 5 個子系統(tǒng)的中心節(jié)點，并根據(jù)這 5 個中心節(jié)點訪問其它節(jié)點的花費來把剩余節(jié)點歸入 5 個子系統(tǒng)形成 Mesh 網(wǎng)絡(luò)系統(tǒng)結(jié)構(gòu)。然后通過 5 個中心節(jié)點來路由選取從起點到終點的最佳路由。在實驗中,蟻群算法需要設(shè)置的參數(shù)分別是：螞蟻數(shù)量 m、啟發(fā)式因子 225。 、信息素揮發(fā)因子 241。 、期望啟發(fā)式因子 226。 和信息素強度 Q。從基本蟻群算法的多次仿真及 TSP 的應(yīng)用試驗不難看出，算法中的參數(shù)取值不同對算法的性能及 QoS 有很大的影響，但算法參數(shù)選取的方法和原則，當(dāng)前仍然沒有一個統(tǒng)一的標準，在不同情況的下，螞蟻系統(tǒng)的參數(shù)設(shè)置通常是根據(jù)經(jīng)驗值和試驗來定的。 實驗仿真結(jié)果及分析改變蟻群算法的其它參數(shù)，每組參數(shù)抽取運行結(jié)果 100 組取平均值進行比較。MAX 為 100 組結(jié)果中的最大值，MIN 為最小值，AVG 為平均值。實驗一：改變蟻群算法中幾組不同的 241。 、Q參數(shù)，設(shè)定螞蟻數(shù)目m=20,算法迭代次數(shù)N=120，運用于節(jié)點數(shù)目R=30的無線Mesh網(wǎng)絡(luò)拓撲中，比較基于改進蟻群算法的無線Mesh網(wǎng)QoS路由算法的參數(shù)自適應(yīng)調(diào)整后算法對多約束QoS性能參數(shù)（包括傳輸時延、包丟失率、費用）的影響。實驗結(jié)果如表41。25上海海洋大學(xué)碩士學(xué)位論文表 41 QoS 路由實驗結(jié)果Table 41. Experimental result of QoS routing仿真結(jié)果表明由于在改進蟻群算法中引入路由參數(shù)自動協(xié)商更改機制,在滿足算法約束條件下繼續(xù)運行,在無線 Mesh 網(wǎng)絡(luò)中,該算法在多約束 QoS 性能參數(shù)費用代價、延遲代價、丟包率方面較算法局部最優(yōu)解取得了較好的結(jié)果。為了更加直觀的反應(yīng)比較結(jié)果，其他參數(shù)保持不變，抽取兩組實驗(ρ=,Q=1000)進行對比分析，實驗結(jié)果如圖 41 和圖 42 所示。