高大利

(1.泉州師范學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建泉州 362000；2.福建省大數(shù)據(jù)管理新技術(shù)與知識(shí)工程重點(diǎn)實(shí)驗(yàn)室，福建泉州 362000；3.智能計(jì)算與信息處理福建省高等學(xué)校重點(diǎn)實(shí)驗(yàn)室，福建泉州 362000)

網(wǎng)絡(luò)實(shí)際上可以抽象為一個(gè)具有權(quán)值的有向圖，它由許多節(jié)點(diǎn)、邊以及其方向構(gòu)成，因此網(wǎng)絡(luò)路由可以根據(jù)實(shí)際問(wèn)題的情況來(lái)給這些弧或節(jié)點(diǎn)賦予一個(gè)權(quán)值來(lái)進(jìn)行建模[1]。路由協(xié)議運(yùn)行在網(wǎng)絡(luò)路由器或三層交換機(jī)之上，幫助路由器建立路由表，用來(lái)確定到達(dá)路徑，起到地圖導(dǎo)航，負(fù)責(zé)找路的作用。路由協(xié)議作為T(mén)CP/IP協(xié)議族中重要成員之一，其選路過(guò)程實(shí)現(xiàn)的好壞會(huì)影響整個(gè)Internet網(wǎng)絡(luò)的效率[2]。

一般地，路由協(xié)議常用的度量包括[2]：1)路徑長(zhǎng)度，它是最基本，使用頻率最高的路由度量，通常將其稱為跳數(shù)，即所走路徑上的路由器數(shù)目大小；2)可靠性，指的是網(wǎng)絡(luò)相互鏈接的可依靠性，即其在失效的時(shí)候，能否比其他的鏈接更快地修復(fù)；3)時(shí)延，一個(gè)報(bào)文或分組從一個(gè)網(wǎng)絡(luò)的發(fā)送端傳送到另一個(gè)目的端所經(jīng)歷的時(shí)間，其中包含許多的因素，例如：帶寬、所經(jīng)網(wǎng)絡(luò)鏈接的擁塞情況、物理距離等，時(shí)延實(shí)際上是多個(gè)因數(shù)的混合，是一個(gè)較為有效和使用頻率較高的度量；4)帶寬，在模擬信號(hào)系統(tǒng)又叫頻寬，是指在固定的時(shí)間鏈路中可傳輸?shù)牧魍ㄈ萘?，亦即在傳輸管道中可以傳遞數(shù)據(jù)的能力；5)負(fù)載，指的是網(wǎng)絡(luò)資源的忙碌程度，其中可能存在很多方面的計(jì)算問(wèn)題；6)通信開(kāi)銷(xiāo)，在路由優(yōu)化的問(wèn)題中，通信開(kāi)銷(xiāo)實(shí)際上是指在該網(wǎng)絡(luò)中，在規(guī)定的多個(gè)約束條件中找出從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最小開(kāi)銷(xiāo)路徑，即最佳路徑(即加權(quán)圖上的最優(yōu)路徑)。

蟻群算法作為一種啟發(fā)式的智能優(yōu)化算法，從1992年被Dorigo提出來(lái)后，許多的學(xué)者便開(kāi)始對(duì)其的改進(jìn)及應(yīng)用進(jìn)行了研究[3]。如把該算法應(yīng)用于TSP問(wèn)題[4]、無(wú)人汽車(chē)路徑規(guī)劃問(wèn)題[5]、機(jī)器人問(wèn)題[6]、資源配置問(wèn)題[7]和網(wǎng)絡(luò)路由問(wèn)題[8]等組合優(yōu)化問(wèn)題。蟻群算法屬于一種模仿生物進(jìn)化的算法，它的想法來(lái)源于螞蟻在覓食的行為[9]。蟻群算法具有貪婪啟發(fā)式的搜索特征，能夠在搜索過(guò)程的早期就找到一個(gè)可以被人們所接受的問(wèn)題求解[10]。經(jīng)過(guò)一系列的改進(jìn)，蟻群算法相比較于原始的算法模型，已經(jīng)得到了更多的改善與拓展[11]。鑒于蟻群算法在路由選路的以上優(yōu)勢(shì)和特點(diǎn)，將自適應(yīng)蟻群算法，應(yīng)用于網(wǎng)絡(luò)的路由協(xié)議中。即根據(jù)蟻群算法的參數(shù)自適應(yīng)調(diào)整將路由協(xié)議中的多個(gè)因素(如跳數(shù)、時(shí)延和帶寬等其它因素)和不同的網(wǎng)絡(luò)環(huán)境來(lái)選擇一個(gè)路由的優(yōu)化最佳路徑。

1 算法思想

一般地，把實(shí)際網(wǎng)絡(luò)中的路由選路問(wèn)題抽象成最優(yōu)路徑的問(wèn)題的模型，然后通過(guò)蟻群算法來(lái)求出相對(duì)開(kāi)銷(xiāo)最小的最優(yōu)路徑。建模過(guò)程如下：

針對(duì)網(wǎng)絡(luò)模型G(V,E)，其中V表示節(jié)點(diǎn)集，E表示邊集。把網(wǎng)絡(luò)中的搜尋路徑相關(guān)信息的任務(wù)用一種控制報(bào)文(即螞蟻)來(lái)實(shí)現(xiàn)，并分為兩類(lèi)螞蟻，分別為向前的螞蟻(從源到目的)和向后的螞蟻(從目的返回源)。螞蟻負(fù)責(zé)搜集從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑信息(即時(shí)延、跳數(shù)等)，螞蟻則根據(jù)螞蟻所收集到的信息進(jìn)行修改路徑中節(jié)點(diǎn)的路由相關(guān)信息[12]。在文中，將問(wèn)題簡(jiǎn)化為路徑中所經(jīng)過(guò)的節(jié)點(diǎn)數(shù)表示為跳數(shù)，而路徑中的邊的賦權(quán)則表示為時(shí)延、帶寬等因素。因此本文將主要圍繞跳數(shù)和時(shí)延兩個(gè)約束條件來(lái)進(jìn)行最優(yōu)路徑的選擇，并將網(wǎng)絡(luò)中路由表替換為信息素表以表示信息素的強(qiáng)度。

開(kāi)始階段，將網(wǎng)絡(luò)每一條邊賦予均勻的信息素濃度，通過(guò)螞蟻在搜尋路徑的過(guò)程來(lái)不斷更新邊的信息素濃度，每個(gè)螞蟻所攜帶的信息素量都相同。首先將一組數(shù)量的螞蟻放置源節(jié)點(diǎn)從源節(jié)點(diǎn)出發(fā)尋徑至目的節(jié)點(diǎn)，按照之前介紹的方法進(jìn)行移動(dòng)，在尋徑的過(guò)程中螞蟻能夠記住所走路徑的信息和所經(jīng)過(guò)節(jié)點(diǎn)的信息，直到最后走到目的節(jié)點(diǎn)為止。當(dāng)螞蟻?zhàn)叩侥康墓?jié)點(diǎn)之后，會(huì)根據(jù)搜集到的路徑信息，來(lái)更新所經(jīng)路徑的路由表(即信息素表)，改變路徑上的信息素濃度，再通過(guò)不斷地迭代循環(huán)計(jì)算，最后收斂得到最優(yōu)路徑。

根據(jù)算法思想，螞蟻需要擁有以下的屬性及特性：1)螞蟻擁有相同的信息素量，并且每只螞蟻都能夠更新路徑中的信息素濃度，這是螞蟻之間進(jìn)行信息交換的手段；2)螞蟻需要擁有記憶功能，能夠記住所搜集的路徑信息(即跳數(shù)和時(shí)延)和已經(jīng)遍歷過(guò)的節(jié)點(diǎn)，保證一個(gè)節(jié)點(diǎn)一只螞蟻只會(huì)遍歷一次，防止螞蟻多次訪問(wèn)同一節(jié)點(diǎn)；3)螞蟻在網(wǎng)絡(luò)中的遍歷必須擁有一個(gè)或者多個(gè)終止條件，本文中的螞蟻的終止條件為到達(dá)目的節(jié)點(diǎn)；4)螞蟻需要擁有發(fā)現(xiàn)節(jié)點(diǎn)阻塞的功能，螞蟻能夠及時(shí)發(fā)現(xiàn)存在于路徑中的阻塞節(jié)點(diǎn)，并且需要及時(shí)更新存在阻塞節(jié)點(diǎn)的路徑信息；5)螞蟻必須要依照算法的節(jié)點(diǎn)轉(zhuǎn)移概率規(guī)則來(lái)決定下一跳的節(jié)點(diǎn)。

2 算法實(shí)現(xiàn)

基于算法思想，算法的具體計(jì)算流程如圖1。

圖1 算法流程圖

2.1 狀態(tài)初始化

首先需要對(duì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)(節(jié)點(diǎn)數(shù)量)和每條進(jìn)行狀態(tài)初始化，每個(gè)節(jié)點(diǎn)都分配一個(gè)信息素表，并初始化每條弧的權(quán)值以及信息素濃度，算法則將信息素濃度的初始值設(shè)為1。同時(shí)還需要設(shè)置好螞蟻的數(shù)量以及每只螞蟻所攜帶的信息素量并將這組螞蟻放置源節(jié)點(diǎn)出發(fā)。再來(lái)還需要設(shè)定算法的最大迭代次數(shù)、信息素重要程度因子、啟發(fā)函數(shù)重要程度因子、信息素?fù)]發(fā)因子，跳數(shù)重要程度因子、時(shí)延程度因子、跳數(shù)影響信息素程度因子、時(shí)延重要影響信息素程度因子，為每個(gè)螞蟻創(chuàng)建一個(gè)禁忌表，用于記錄訪問(wèn)過(guò)的節(jié)點(diǎn)。

2.2 逐個(gè)螞蟻的路徑選擇

1)每只螞蟻在尋徑的過(guò)程中都會(huì)記錄下該路徑的路由信息和時(shí)延。算法中的第k只螞蟻在I節(jié)點(diǎn)選擇的下一跳j節(jié)點(diǎn)的規(guī)則如下式(1)。

(1)

其中τij為邊(i，j)上的信息素濃度；ηij=1/dij為節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的啟發(fā)因子，需要通過(guò)啟發(fā)式公式計(jì)算得到；為螞蟻ak下一步被允許訪問(wèn)的節(jié)點(diǎn)集合，然后通過(guò)輪盤(pán)賭法實(shí)現(xiàn)到對(duì)下一個(gè)節(jié)點(diǎn)的選擇并跳躍。

2)第k只螞蟻在概率轉(zhuǎn)移的規(guī)則下完成了對(duì)下一節(jié)點(diǎn)的選擇和跳躍后，就會(huì)將節(jié)點(diǎn)j加入到螞蟻的路徑信息表中，當(dāng)再選擇下一條的節(jié)點(diǎn)時(shí)節(jié)點(diǎn)j就會(huì)被寫(xiě)進(jìn)禁忌表中，若周?chē)B接的所有節(jié)點(diǎn)都在禁忌表中時(shí)(即ak∈φ)，該螞蟻就陷入了死胡同，這種情況就把螞蟻收集的信息清空，重新初始化狀態(tài)放到源節(jié)點(diǎn)重新出發(fā)尋徑。

3)當(dāng)螞蟻到達(dá)目的節(jié)點(diǎn)時(shí)，螞蟻將會(huì)把搜集到的路徑信息(即跳數(shù)和時(shí)延)放入到路徑表route、時(shí)延表Timed和跳數(shù)表hop當(dāng)中，然后終止該螞蟻的生命周期。

2.3 尋找一代螞蟻的最佳路徑

當(dāng)一代的螞蟻全部尋徑結(jié)束后，需要通過(guò)對(duì)每只螞蟻搜集到的路徑信息進(jìn)行分析，找出在跳數(shù)和時(shí)延兩個(gè)約束條件下最優(yōu)的路徑。在這個(gè)過(guò)程中，算法設(shè)置了跳數(shù)重要程度因子ω1、時(shí)延程度因子ω2這兩個(gè)參素來(lái)影響對(duì)于這代螞蟻中最優(yōu)路徑的選擇。定義第k只螞蟻的路徑開(kāi)銷(xiāo)值Gk，它的計(jì)算公式如式(2)。

Gk=hopk*ω1+Timedk*ω2 ，

(2)

hopk為第k只螞蟻所走路徑的跳數(shù)，Timedk為第k只螞蟻所走路徑的時(shí)延總和，開(kāi)銷(xiāo)值Gk越小，說(shuō)第k只螞蟻所走路徑的開(kāi)銷(xiāo)越小。因此算法通過(guò)對(duì)開(kāi)銷(xiāo)值的比對(duì)篩選出這一代螞蟻的最優(yōu)路徑。然后與上一代螞蟻的最優(yōu)路徑進(jìn)行對(duì)比，若這一代的螞蟻選出的最優(yōu)路徑開(kāi)銷(xiāo)比上一代螞蟻要大，則舍棄這代螞蟻的最優(yōu)路徑，將上一代螞蟻的最優(yōu)路徑保存為這一代螞蟻的最優(yōu)路徑。

2.4 信息素的更新

當(dāng)一只螞蟻完成一次尋徑，到達(dá)目的節(jié)點(diǎn)后，算法對(duì)于該路徑上邊的信息素濃度更新方式采取了對(duì)蟻量系統(tǒng)的改進(jìn)，蟻量系統(tǒng)的具體規(guī)則如式(3)。

(3)

則在算法中每條邊上的信息素濃度更新的具體公式如式(4)。

τij=(1-ρ)τij+∑K=1mΔτijk(t),

(4)

其中Δτijk(t)的表示第k只螞蟻在這條邊上信息素濃度的釋放，Δτijk(t)的具體計(jì)算公式如式(5)。

Δτijk(t)=(Q/hop(k))r1+(Q/Timed(k))r2,

(5)

其中r1與r2分別表示為：跳數(shù)影響信息素程度因子、時(shí)延重要影響信息素程度因子。通過(guò)設(shè)立這兩個(gè)參數(shù)來(lái)實(shí)現(xiàn)跳數(shù)和時(shí)延共同對(duì)信息素濃度更新的影響。

最終算法將會(huì)通過(guò)不斷對(duì)上述過(guò)程進(jìn)行循環(huán)迭代，讓算法的結(jié)果逐漸收斂于該網(wǎng)絡(luò)中開(kāi)銷(xiāo)最小的最優(yōu)路徑。

在上述算法執(zhí)行過(guò)程中，相關(guān)參數(shù)數(shù)值的設(shè)定對(duì)算法的性能影響會(huì)非常大。如：如果螞蟻數(shù)量m的值若設(shè)得過(guò)大，會(huì)導(dǎo)致路徑上的信息素濃度比較均勻使收斂速度過(guò)慢，過(guò)小又會(huì)導(dǎo)致收斂速度過(guò)快，解的全局最優(yōu)性降低；迭代次數(shù)若過(guò)大又會(huì)導(dǎo)致計(jì)算時(shí)間過(guò)長(zhǎng)，過(guò)小可能會(huì)導(dǎo)致陷入局部最優(yōu)解。其他參數(shù)相同，參數(shù)的設(shè)定需要通過(guò)不斷的測(cè)試實(shí)驗(yàn)進(jìn)行自適應(yīng)調(diào)整，然后找到一個(gè)合理的數(shù)值區(qū)間。

3 MATLAB仿真實(shí)驗(yàn)

在MATLAB R2020a仿真軟件環(huán)境下，對(duì)傳統(tǒng)蟻群算法和本文算法進(jìn)行仿真，仿真環(huán)境為：Windows 10_64位操作系統(tǒng)；Intel?CoreTMi5-7300HQ CPU @ 2.50 GHz處理器；8 GB內(nèi)存。網(wǎng)絡(luò)路由協(xié)議是基于內(nèi)部網(wǎng)關(guān)OSPF協(xié)議進(jìn)行路由仿真的。

實(shí)驗(yàn)利用MATLAB軟件構(gòu)建了一個(gè)了網(wǎng)絡(luò)拓?fù)鋱D，該圖包括25個(gè)節(jié)點(diǎn)，以英文字母A-Y編號(hào)，將A設(shè)為源節(jié)點(diǎn)，W設(shè)為目的節(jié)點(diǎn)。圖中共有邊的數(shù)量為125，且都賦予權(quán)值(表示為該邊的時(shí)延大小)，如圖2所示。

圖2 仿真實(shí)驗(yàn)的網(wǎng)絡(luò)拓?fù)鋱D

3.1 最優(yōu)路徑選擇實(shí)驗(yàn)

由于最短路徑即是指相對(duì)開(kāi)銷(xiāo)程度最小的路徑，所以在仿真實(shí)驗(yàn)中，設(shè)計(jì)了由跳數(shù)和時(shí)延兩個(gè)約束條件來(lái)實(shí)現(xiàn)對(duì)最優(yōu)路徑的選擇，具體方法為：為了簡(jiǎn)化計(jì)算，將跳數(shù)抽象為路徑中經(jīng)歷的節(jié)點(diǎn)個(gè)數(shù)，將時(shí)延抽象為每條邊的權(quán)值。由于在實(shí)際的網(wǎng)絡(luò)傳輸開(kāi)銷(xiāo)當(dāng)中，跳數(shù)數(shù)量的多少對(duì)于開(kāi)銷(xiāo)的大小相較于時(shí)延會(huì)更大，所以算法的選路的主要規(guī)則就是去尋找跳數(shù)較小的路徑集合中，相對(duì)時(shí)延較小的路徑，并以這兩個(gè)約束條件來(lái)更新信息素濃度。經(jīng)過(guò)實(shí)驗(yàn)之后，最優(yōu)路徑尋徑結(jié)果、最小開(kāi)銷(xiāo)與平均開(kāi)銷(xiāo)走勢(shì)及最優(yōu)路徑的時(shí)延與跳數(shù)走勢(shì)結(jié)果如圖3、圖4和圖5所示。

圖3 最優(yōu)路徑尋徑結(jié)果

圖4 各代最小開(kāi)銷(xiāo)與平均開(kāi)銷(xiāo)走勢(shì)圖

圖5 各代最優(yōu)路徑的時(shí)延與跳數(shù)走勢(shì)圖

由上圖的仿真實(shí)驗(yàn)結(jié)果知道，在該網(wǎng)絡(luò)拓?fù)鋱D中從節(jié)點(diǎn)A到節(jié)點(diǎn)W開(kāi)銷(xiāo)總值最小的路徑(即最優(yōu)路徑為)為A→C→N→O→W，路徑的開(kāi)銷(xiāo)值為68(關(guān)于開(kāi)銷(xiāo)值的計(jì)算公式上節(jié)有介紹)，跳數(shù)為5，時(shí)延為43。通過(guò)多次實(shí)驗(yàn)最終都收斂于該路徑，可以得到該路徑就是當(dāng)前狀態(tài)的唯一最優(yōu)路徑，多次實(shí)驗(yàn)的數(shù)據(jù)統(tǒng)計(jì)如表1。

表1 蟻群優(yōu)化算法選路結(jié)果統(tǒng)計(jì)

在真實(shí)的網(wǎng)絡(luò)環(huán)境中，對(duì)于最優(yōu)路徑的選擇會(huì)更加復(fù)雜多變，需要考慮更多地綜合影響，例如帶寬、差錯(cuò)率、耗費(fèi)等。而在本算法中，可以根據(jù)實(shí)際情況去調(diào)整跳數(shù)重要程度因子ω1與時(shí)延程度因子ω2，還有跳數(shù)影響信息素程度因子r1與時(shí)延重要影響信息素程度因子r2這兩對(duì)參數(shù)的各自值的大小，來(lái)調(diào)整兩者對(duì)選路時(shí)的影響程度。同時(shí)也可以把如帶寬、差錯(cuò)率、耗費(fèi)這類(lèi)的因素分配對(duì)應(yīng)的比例來(lái)賦予權(quán)值，由此來(lái)實(shí)現(xiàn)在多因素綜合影響下選出綜合開(kāi)銷(xiāo)最少的最優(yōu)路徑。

3.2 路由阻塞的避障方式

在實(shí)際的動(dòng)態(tài)網(wǎng)絡(luò)當(dāng)中，時(shí)常會(huì)發(fā)生路由阻塞或者故障的情況，而傳統(tǒng)的鏈路狀態(tài)算法在處理節(jié)點(diǎn)阻塞的情況下會(huì)顯得比較無(wú)力，導(dǎo)致網(wǎng)絡(luò)的開(kāi)銷(xiāo)增加。筆者則基于蟻群算法給出了兩種處理當(dāng)最優(yōu)路徑中的節(jié)點(diǎn)出現(xiàn)阻塞時(shí)的解決方案。

1)通過(guò)將該節(jié)點(diǎn)所連接的邊的權(quán)值賦予一個(gè)相對(duì)無(wú)限大的權(quán)值，通過(guò)算法的自適應(yīng)性使其他節(jié)點(diǎn)到該阻塞節(jié)點(diǎn)的轉(zhuǎn)移概率降到趨近于0，從而避開(kāi)阻塞節(jié)點(diǎn)去選擇其它的最優(yōu)路徑；

2)將阻塞的節(jié)點(diǎn)加入到每只螞蟻的禁忌表中，當(dāng)螞蟻到達(dá)與阻塞節(jié)點(diǎn)相連的節(jié)點(diǎn)時(shí)，將阻塞的節(jié)點(diǎn)直接從下一步被允許訪問(wèn)的節(jié)點(diǎn)集合ak中去除。由此來(lái)達(dá)到避開(kāi)阻塞節(jié)點(diǎn)重新選擇其它的最優(yōu)路徑的目的。

在算法迭代第50次時(shí)，把節(jié)點(diǎn)N設(shè)為阻塞節(jié)點(diǎn)，然后對(duì)這兩種節(jié)點(diǎn)發(fā)生阻塞時(shí)的解決方案分別進(jìn)行仿真實(shí)驗(yàn)，并對(duì)所得到的結(jié)果進(jìn)行對(duì)比。

方案1)結(jié)果如圖4～圖6、圖4～圖7。

圖6 方案1)的各代最小開(kāi)銷(xiāo)與平均開(kāi)銷(xiāo)走勢(shì)圖

圖7 方案1)的避障尋徑結(jié)果

方案2)結(jié)果如圖8、圖9。

圖8 方案2)的各代最小開(kāi)銷(xiāo)與平均開(kāi)銷(xiāo)走勢(shì)圖

圖9 方案2)的避障尋徑結(jié)果

從實(shí)驗(yàn)結(jié)果可知，這兩種方案都能在N節(jié)點(diǎn)(上圖中的紅點(diǎn))發(fā)生阻塞后重新找到開(kāi)銷(xiāo)值最小的最優(yōu)路徑，收斂得到的最優(yōu)路徑分別為：A→P→Q→S→W和A→E→M→O→W。這兩條路徑的開(kāi)銷(xiāo)值都為69，同為最優(yōu)路徑。下面再對(duì)這兩種解決方案進(jìn)行多次實(shí)驗(yàn)，通過(guò)結(jié)果統(tǒng)計(jì)對(duì)比性能，具體結(jié)果統(tǒng)計(jì)對(duì)比如下表2，表中的平均迭代次數(shù)指發(fā)生阻塞后收斂到新的最優(yōu)路徑的平均迭代次數(shù)。

表2 兩種避障方案實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)

通過(guò)對(duì)表中數(shù)據(jù)對(duì)比發(fā)現(xiàn)，兩種方案在發(fā)生阻塞后對(duì)最優(yōu)路徑的重新選擇的收斂速度上，方案1)表現(xiàn)更優(yōu)，但兩者的差距并不是特別大。雖然在本次實(shí)驗(yàn)中兩種方案都做到了100%地規(guī)避了阻塞節(jié)點(diǎn)，但實(shí)際方案1)是還存在極小的概率會(huì)去訪問(wèn)阻塞節(jié)點(diǎn)，而方案2)則可以做到在理論上也100%規(guī)避阻塞節(jié)點(diǎn)，但若在頻繁發(fā)生路由阻塞的網(wǎng)絡(luò)中，則需要頻繁性地去更新和維護(hù)螞蟻的禁忌表。經(jīng)過(guò)綜合考量，基于算法自身自適應(yīng)性去規(guī)避阻塞節(jié)點(diǎn)的方案1)性能更優(yōu)。

3.3 與其他算法對(duì)比

為了展示本文算法的優(yōu)越性，與傳統(tǒng)蟻群算法做了對(duì)比，針對(duì)傳統(tǒng)蟻群算法存在收斂較慢，容易陷入局部最優(yōu)解的不足。本文算法通過(guò)自適應(yīng)性調(diào)整相關(guān)參數(shù)，如：信息素重要程度因子、啟發(fā)函數(shù)重要程度因子和信息素?fù)]發(fā)因子的優(yōu)化策略，加快了算法的收斂速度，同時(shí)也降低了算法陷入局部最優(yōu)解的概率，提高算法的搜索深度。

在初始時(shí)刻，將上述的3個(gè)參數(shù)設(shè)為：α=0.5、β=1、ρ=0.7。當(dāng)算法迭代到最大迭代次數(shù)的1/5時(shí)，則設(shè)置為α=1、β=3、ρ=0.9。然后在MATLAB上對(duì)傳統(tǒng)蟻群算法和本文算法分別進(jìn)行仿真實(shí)驗(yàn)，結(jié)果如表3、表4所示。

表3 傳統(tǒng)蟻群算法仿真結(jié)果

表4 本文算法仿真結(jié)果

由實(shí)驗(yàn)結(jié)果顯示，當(dāng)在一開(kāi)始就把α、β和ρ的數(shù)值設(shè)的較大的話，雖然能夠讓算法更快的收斂，但同時(shí)也使得算法更容易陷入局部最優(yōu)解。而本文算法則可以做到，在算法前期的搜索深度更深，不容易陷入局部最優(yōu)解，而在運(yùn)行到一定迭代次數(shù)后，又能縮小搜索范圍向最佳路徑靠攏，從而提升收斂速度。因此本算法有效地彌補(bǔ)基本蟻群算法的一些不足，減少算法計(jì)算量，提高算法的求解性能。

4 結(jié)語(yǔ)

網(wǎng)絡(luò)中的路由選路優(yōu)化問(wèn)題屬于組合優(yōu)化的離散問(wèn)題，分析了網(wǎng)絡(luò)路由性能度量參數(shù)。然后將自適應(yīng)蟻群算法進(jìn)行建模應(yīng)用于路由協(xié)議優(yōu)化問(wèn)題中，通過(guò)設(shè)立多個(gè)影響因素(跳數(shù)、時(shí)延、帶寬等)來(lái)實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)中最優(yōu)路徑的選擇，解決最優(yōu)路由的優(yōu)化過(guò)程。最后仿真實(shí)驗(yàn)表明，本文算法能夠更好地適應(yīng)動(dòng)態(tài)變化的網(wǎng)絡(luò)，擴(kuò)大了搜索深度，加快了收斂速度，比傳統(tǒng)蟻群算法能較好地解決路由優(yōu)化問(wèn)題。