潘曉君，張佑春

(安徽工商職業(yè)學院 1.信息工程學院；2.應用工程學院，合肥 231100)

基于服務質量的遺傳蟻群融合算法應用研究*

潘曉君，張佑春

(安徽工商職業(yè)學院 1.信息工程學院；2.應用工程學院，合肥 231100)

隨著網絡的環(huán)境變得越來越復雜，數據包的轉發(fā)也時常出現一些問題，諸如丟包、延遲、抖動等異常情況.為了更有效地增強網絡路由性能，提出了一種將遺傳算法與蟻群算法相融合的方法來提高數據包的轉發(fā)效率，確保網絡的服務質量.根據服務質量約束條件以及當前的最優(yōu)路徑對可選節(jié)點集進行優(yōu)化，將遺傳算法加入到蟻群算法的每一次迭代過程中,利用遺傳算法全局快速收斂的優(yōu)點,來加快蟻群算法的收斂速度,使求解過程中盡量避免陷入局部最優(yōu)，增強了尋優(yōu)的能力.實驗結果表明，該算法在提高網絡路由效率方面具有一定的理論價值和實際意義.

遺傳算法；蟻群算法；服務質量

1 遺傳算法與蟻群算法的基本原理

遺傳算法由于具有可擴展性、很強的魯棒性及快速的全局搜索能力等特點，可以很容易的和其它算法相結合，但遺傳算法本身對于系統(tǒng)中的反饋信息利用不是很充分，當求解的范圍比較大時，就會進行大量的無效的迭代運算，大大降低了算法的效率；同時，由于其初始信息素資源匱乏，導致該算法開始的時候非常慢[1].

蟻群算法具有很好的正反饋機制和高收斂特性，它運用螞蟻的行走路徑來表示待求解問題的可行解,并不依賴于具體的數學問題,具有非常強的全局優(yōu)化能力,已經廣泛應用于數據優(yōu)化類的NP問題中[2-4].然而，蟻群算法自身也有一些缺陷,諸如易陷入局部最優(yōu)、收斂速度較慢等.

2 基于服務質量的網絡路由模型

基于服務質量的路由選擇是向用戶提供端到端的服務質量保證.服務質量指標主要包含丟包、延遲、抖動等,這些參數構成了服務質量路由選擇的約束條件[5-6].基于服務質量的網絡數據路由的目的就是在網絡中尋找最優(yōu)路徑,要求從源節(jié)點出發(fā),歷經所有的目的節(jié)點,并且滿足所有的約束條件,達到特定條件下的服務水平[7].

網絡路由選擇可以被抽象成為一個帶服務質量約束的有向圖.網絡模型表示為賦權圖G=(V,E),其中V是圖中網絡節(jié)點(諸如主機、交換機、路由器等)組成的集合,E是網絡中數據鏈路的集合，其中的每一條邊表示兩節(jié)點間的可達路徑.這里假定s∈V為源點,M∈{V-{s}}為終點.于是對于任一網絡中的節(jié)點n∈V，定義了三種屬性，分別為丟包率函數packet-loss(n)、延遲函數delay(n)、抖動函數jitter(n)，則對于給定的源點s∈V，終點集合M,節(jié)點t∈M,s與M組成的數據轉發(fā)分層樹T(s,M)則有如下關系:

(1)packet-loss(PT(s,t))=1-∏n∈PT(s,t)(1-packet-loss(n))；

(2)delay(PT(s,t))=∑e∈PT(s,t)delay(e)+∑n∈PT(s,t)delay(n)；

(3)jitter(PT(s,t)=∑e∈PT(s,t)jitter(e)+∑n∈PT(s,t)jitter(e)；

這里PT(s,t)為分層樹T(s,M)上源點s到終點t的數據轉發(fā)路徑.

下面給出網絡數據轉發(fā)路徑選擇的約束條件，該條件定義如下：

(1)丟包率約束:packet-loss(PT(s,t)≤PLt;

(2)延遲約束:delay(PT(s,t))≤Dt

(3)抖動約束:jitter(PT(s,Mt)≤DJt;

其中,PL、tDt、Jt分別代表業(yè)務對網絡丟包率、延遲、抖動的約束限制.

3 遺傳蟻群算法的融合設計

由于單獨的遺傳算法和蟻群算法各自在尋求最優(yōu)解的過程中，都存在一些缺陷，所以為了克服這些缺點，把兩種算法結合起來，將其引入到網絡路由選擇的具體服務中綜合考慮，以尋求尋求全局中的最優(yōu)解.運用遺傳算法具有的全局快速收斂與隨機搜索等特性產生相關問題的初始信息素分布；利用蟻群算法的正反饋機制、并行性等特性來對相關問題進行求解，得出全局最優(yōu)解，這里將遺傳與蟻群相結合的算法稱為遺傳蟻群算法.

3.1 遺傳算法求蟻群初始信息素

(1)初始種群的生成

服務候選集是以隨機的方式生成，依次從每個服務候選集中隨機選出具體服務組成的染色體，得到所需要的初始種群.

(2)算子的選擇

采用最佳個體保留方法進行算法的選擇.

(3)變異算子

變異結點是從當前的染色體中用隨機的方法選擇一個節(jié)點，但起始節(jié)點與目標節(jié)點被排除在外，從變異節(jié)點所對應的服務候選集中隨機選擇新的變異基因替換當前的基因.

3.2 利用蟻群算法求最優(yōu)解

3.2.1 信息素更新規(guī)則

τij(t)表示在t時刻路徑p(i,j)上的遺留的信息素，為了避免殘留信息素過多引起的殘留信息淹沒啟發(fā)式信息的問題，使螞蟻能準確感知路徑信息，我們規(guī)定在每只螞蟻走完所有的服務節(jié)點后，對p(i,j)路徑上的信息素進行全局更新：

zxy(t+n)=r*zxy(t)+Δzxy(t)

(1)

(2)

公式(1)、(2) 中Δzxy(t)表示本次循環(huán)中路徑p(x,y)的信息素增量.

3.2.2 信息素約束規(guī)則

本文的信息素約束函數有如下關系：

(3)

本文采用信息素的約束函數關系來提高全局搜索能力，如公式(3)所示，也就是通過蟻群算法采用最小和最大信息素閾值來阻止因信息素過低而喪失路徑選擇的機率或者是因信息素過高而陷入局部最優(yōu).

3.3 遺傳蟻群算法的流程

基于初始種群的生成方式、信息素更新以及約束規(guī)則，本文的遺傳蟻群算法流程如圖1所示.

圖1 遺傳蟻群算法流程

4 實驗測試與性能分析

4.1 實驗參數的設置

為了驗證融合算法的有效性、穩(wěn)定性及可行性，本文將該算法與傳統(tǒng)的遺傳算法與蟻群算法在網絡服務中對數據的處理進行比較，實驗的參數設定如表1所示.本文設定了三組服務候選集樣本數據，如表2所示，其中包含90個基礎服務，時間、價值、穩(wěn)定性為網絡服務所設定的屬性參數.時間設置的范圍T∈[5，35]，價值設置的范圍在C∈[45，90]、穩(wěn)定性范圍在p∈[1.0，2.0]，這三個屬性參數值都是隨機生成的.本實驗可以對參數進行適當的調整，均可以得到比較滿意的結果.

表1 參數取值表

表2 服務候選集

4.2 實驗測試與結果分析

(1)收斂性

如圖2所示，相對于傳統(tǒng)的遺傳算法和蟻群算法，本文的遺傳蟻群算法在尋求網絡服務最優(yōu)解的過程中，可以在較少的進化迭代次數內得出全局最優(yōu)解，而不是局部最優(yōu)解，該算法較好的克服了普通遺傳算法得出的不是全局最優(yōu)解，普通蟻群算法收斂性能不佳的問題，提高了網絡數據轉發(fā)的效率，增強了整個網絡的性能. 從圖2中看出，蟻群算法的收斂性能較差.

圖2 遺傳算法、蟻群算法與遺傳蟻群算法收斂曲線

(2)代價

在相同條件下，三種算法的網絡路由代價比較如圖3所示，相對于傳統(tǒng)的遺傳算法和蟻群算法,本文的遺傳蟻群算法的代價曲線波動不大，比較平滑，幾乎每一代的遺傳操作均能得到最佳網絡路由，有比較好的收斂性，但由于該算法操作的時間復雜度較大,耗費的運算時間較長,計算量較大，從側面也影響了算法的性能.而遺傳算法的代價波動較大，說明尋找路徑剛開始時,鏈路上的信息素信息非常匱乏.

圖3 遺傳算法、蟻群算法與遺傳蟻群算法代價曲線

(3)延遲

在相同條件下，三種算法的網絡路由延遲比較如圖4所示，相對于傳統(tǒng)的遺傳算法和蟻群算法，本文的遺傳蟻群算法和蟻群算法的延遲曲線相對比較平穩(wěn)，表示能較快地找到最優(yōu)解(或次優(yōu)解)，而遺傳算法相對來說延遲較大，不能很快找出最優(yōu)解.

圖4 遺傳算法、蟻群算法與遺傳蟻群算法代延遲曲線

(4)抖動

在相同條件下，三種算法的網絡路由延遲比較如圖5所示.相對于傳統(tǒng)的遺傳算法和蟻群算法,本文的遺傳蟻群算法的抖動曲線比較平滑，抖動曲線起伏不大,表示在最優(yōu)解附近波動.從圖5中看出，遺傳算法波動起伏較大，離最優(yōu)解較遠.

圖5 遺傳算法、蟻群算法與遺傳蟻群算法抖動曲線

5 結束語

如何提高網絡路由的效率，針對傳統(tǒng)蟻群算法收斂性能不佳的問題，遺傳算法得出的不是全局最優(yōu)解，這里將這兩種算法融合起來進一步增強數據包的轉發(fā)效率.該算法采用蟻群算法的混合螞蟻行為使初始路徑差異化,根據服務質量約束條件以及當前的最優(yōu)路徑對可選節(jié)點集進行優(yōu)化,將遺傳算法加入到蟻群算法的每一次迭代過程中,利用遺傳算法全局快速收斂的優(yōu)點,來加快蟻群算法的收斂速度,使求解過程中盡量避免陷入局部最優(yōu)，增強了尋優(yōu)的能力.實驗結果表明，該算法在提高網絡路由效率方面具有一定的理論價值和實際意義.

[1] 馬 炫,劉 慶.多組播路由問題的粒子群優(yōu)化算法[J].計算機研究與發(fā)展,2013,50(2):260-268.

[2] 李 飛,易傅瀟,王 浩.多QoS約束下的PSO云存儲任務調度算法[J].計算機工程與設計,2015,36(7):1767-1770.

[3] 孔宇彥,姚金濤,張明武.Ad hoc網絡基于GA-NCE的QoS組播路由優(yōu)化算法[J].計算機應用研究,2014,31(8):2426-2429.

[4] 黃永青，張祥德，李旭東.交互式螞蟻算法[J].控制與決策,2012,27(4):609-612.

[5] 周德榮.基于蟻群算法改進的AODV路由協議研究[J].西南師范大學學報(自然科學版),2014，39(11):75-80.

[6] 袁麗喬，楊喜旺，楊夢茹.基于BP分類的粒子群QoS路由算法研究[J].計算機工程與應用,2015,51(9):98-102.

[7] 夏 利,田東渭,張艷艷.網格和組播樹結合的QoS路由[J].小型微型計算機系統(tǒng),2014,35(4):720-722.

ApplicationofGeneticandAntColonyFusionAlgorithmBasedonQualityofService

PAN Xiao-jun1, ZHANG You-chun2

(1. School of Information Eng., 2. School of Applied Eng. Anhui Business Vocational College, Hefei 231100, China)

As the network environment becomes more and more complex, packet forwarding problems often arise, such as packet loss, delay, jitter and other anomalies. In order to enhance the performance of network routing more effectively, a method combining genetic algorithm with ant colony algorithm is proposed to improve the efficiency of data packet forwarding and to ensure the QoS of the network. According to the quality of service constraints and the current optimal path set to optimize the optional nodes, the genetic algorithm is added to each iteration of ant colony algorithm. The advantages of using genetic algorithm to accelerate the convergence, and the convergence speed of ant colony algorithm can avoid falling into a local optimal solution process, and enhance the ability of searching excellence. Experimental results show that the algorithm has certain theoretical value and practical significance in improving routing efficiency.

genetic algorithm; ant colony algorithm; quality of service

2017-05-17

安徽高校自然科學研究重點項目(KJ2017A761)；安徽省高校優(yōu)秀青年人才支持計劃重點項目(gxyqZD2016438)；安徽省質量工程項目(2016tszy012).

潘曉君(1978-)，男，講師，碩士，網絡工程師，研究方向：網絡與信息安全.

TP393.02

A

1671-119X(2017)04-0030-05