摘 要：鑒于最大最小蟻群算法有很好的全局搜索能力，被廣泛應(yīng)用于智能光網(wǎng)絡(luò)的動態(tài)選路。但是該算法存在著計算量大，收斂時間慢等缺陷。為了加快蟻群算法的收斂時間，這篇文章通過引進，并且在TSP問題中進行驗證，實驗結(jié)果表明改進型蟻群算法可以有效的提高蟻群算法的收斂時間。

關(guān)鍵字：智能光網(wǎng)絡(luò)路由；蟻群算法；TSP

智能光網(wǎng)絡(luò)憑借其可動態(tài)分配帶寬、高效地支持大容量數(shù)據(jù)業(yè)務(wù)等優(yōu)良性能，成為了重要的通信傳輸技術(shù)。智能光網(wǎng)絡(luò)除了繼承了光傳送網(wǎng)的主要特點外，還具備以下優(yōu)點：可實現(xiàn)流量工程要求，具有靈活多樣的恢復(fù)能力，能很好地利用資源等。如果把智能光網(wǎng)絡(luò)中的所有設(shè)備都放在一個域中進行管理，域中的每個節(jié)點就都需要維護一個非常龐大的數(shù)據(jù)庫信息。為解決此問題，多域智能光網(wǎng)絡(luò)應(yīng)運而生，成為了未來傳送網(wǎng)規(guī)?；植际焦芾淼谋厝唤Y(jié)果。本文主要針對多域光網(wǎng)絡(luò)中的關(guān)鍵技術(shù)-路由技術(shù)進行研究。

1 智能光網(wǎng)絡(luò)中的路由算法

路由和波長分配指的是在給定一組光路連接請求、拓?fù)浯_定的情況下，尋找一條從源節(jié)點到目的節(jié)點的路由，并為這些路由分配相應(yīng)的波長。

路由技術(shù)分為動態(tài)路由技術(shù)和靜態(tài)路由技術(shù)。靜態(tài)路由是指光連接請求在全網(wǎng)的業(yè)務(wù)矩陣是已知的。靜態(tài)路由是在路由器中設(shè)置固定的路由。動態(tài)路由是網(wǎng)絡(luò)中的路由器之間相互通信，傳遞路由信息，利用收到的路由信息更新路由表的過程。

幾種常見的路由算法定義如下：

固定路由算法：各個節(jié)點之間的信息傳輸路徑是提前確定好的，每個節(jié)點僅需要將靜態(tài)路由信息存儲到其他節(jié)點，請求到達(dá)時，節(jié)點選擇默認(rèn)的到特定目的節(jié)點的路由。

固定備選路由算法：在固定路由算法的基礎(chǔ)上，按固定順序依次考慮一組備用路由的可用性。

自適應(yīng)路由算法：自適應(yīng)路由策略路徑不是提前固定的，而是根據(jù)當(dāng)前網(wǎng)絡(luò)鏈路狀態(tài)，動態(tài)選擇一對節(jié)點之間的每條路由[2]。

本文對智能光網(wǎng)絡(luò)路由算法中的蟻群算法進行了研究，針對該算法收斂性慢的問題進行了改進，提出了一種改進型蟻群算法。

2 蟻群算法

20世紀(jì)90年代，意大利學(xué)者M.Dorigo， V.Maniezzo受到螞蟻集體尋找最短路徑覓食行為的啟發(fā)，首次提出了基于螞蟻種群的新型優(yōu)化算法，即蟻群算法[3]。該算法提出后，以此算法為基礎(chǔ)解決了一系列的組合優(yōu)化問題，如智能光網(wǎng)絡(luò)中的選路問題。

蟻群算法全局搜索能力非常好。但是，存在計算量大、收斂時間慢等缺陷。本文從蟻群算法的收斂速度出發(fā)，采用新的信息素更新策略對最大最小蟻群算法進行了優(yōu)化。

2.1 基本蟻群算法數(shù)學(xué)模型

通過研究，螞蟻在從蟻穴到食物的過程中能夠在它經(jīng)過的路徑上釋放一種叫信息素的物質(zhì)。螞蟻在運動過程中能感知信息素的強度，從而實現(xiàn)信息的交流。算法中螞蟻工作方式如下：每只螞蟻根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則選路，通過局部和全局信息素更新找到最短路徑。

選路過程中，位于節(jié)點i的螞蟻用公式（1）來選擇下一節(jié)點j。

其中為全局信息素?fù)]發(fā)參數(shù)，與局部信息素?fù)]發(fā)參數(shù)值不相同，為一次迭代中找到的全局最優(yōu)路徑，稱之為迭代最優(yōu)路徑。

2.2 改進型蟻群算法的基本原理

為了加快蟻群算法的收斂時間本文對基本蟻群算法的信息素更新公式做了改進?；鞠伻核惴ㄖ?，信息素增量與路徑長度呈線性關(guān)系，且變化較為平緩，不同長度路徑的信息素增量差別不大。針對該問題，本文提出了一種新的信息素更新策略見公式（6）。

改進的信息素更新公式斜率大，不同長度路徑上的信息素增量的差異拉大，這樣不同長度的路徑通過信息素的累積就能更快的區(qū)分開來，從而更快的找到最優(yōu)路徑，收斂速度加快。

3 仿真與結(jié)果分析

本文分別對最大最小蟻群算法和改進型蟻群算法，在TSP問題中進行仿真。仿真拓?fù)錇閑il51。參數(shù)設(shè)置：m =70、=1、=4、Q =100。

圖2和圖3分別為加入最大最小信息素限制的基本蟻群算法和改進型蟻群算法在eil51中的仿真結(jié)果。每幅圖中右圖L best2表示迭代的最優(yōu)路徑，L ave2表示迭代后各螞蟻尋路的平均值；對比兩圖，改進型蟻群算法能夠更快地找到最優(yōu)路徑。

4 結(jié)語

本文首先對基本蟻群算法的原理進行了介紹。然后，就基本蟻群算法收斂速度慢的問題，提出了一種改進型蟻群算法。通過仿真驗證了該改進型算法的可行性。

參考文獻

[1].王玉亭. 智能光網(wǎng)絡(luò)層域路由算法的研究[D]. 北京：北京郵電大學(xué)，2012.

[2]. M Dorigo， G Di Caro. Ant algorithms for discrete opetimization[J]. Artificial Life， 1999， 5（3）： 137-172.

[3].M Dorigo， L M Gambardella. Ant colonies for the traveling salesman problem [J]. BioSystems， 1997， 36（43）： 73-81.

[4].陳昊. 蟻群優(yōu)化算法的原理及其應(yīng)用[J]. 湖北大學(xué)學(xué)報，2006，28（4）： 350-352.

[5].段海濱. 蟻群算法原理及其應(yīng)用[M]. 北京：科學(xué)出版社，2005.

作者簡介

雷夢瑤（1991-），女，山西，碩士研究生，研究方向：多域智能光網(wǎng)絡(luò)路由與波長算法研究。