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