基于服務(wù)質(zhì)量的遺傳蟻群融合算法應(yīng)用研究*

潘曉君，張佑春

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

基于服務(wù)質(zhì)量的遺傳蟻群融合算法應(yīng)用研究*

潘曉君，張佑春

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

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

遺傳算法；蟻群算法；服務(wù)質(zhì)量

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

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

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

2 基于服務(wù)質(zhì)量的網(wǎng)絡(luò)路由模型

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

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

(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的數(shù)據(jù)轉(zhuǎn)發(fā)路徑.

下面給出網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)路徑選擇的約束條件，該條件定義如下：

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

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

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

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

3 遺傳蟻群算法的融合設(shè)計

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

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

(1)初始種群的生成

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

(2)算子的選擇

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

(3)變異算子

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

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

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

τij(t)表示在t時刻路徑p(i,j)上的遺留的信息素，為了避免殘留信息素過多引起的殘留信息淹沒啟發(fā)式信息的問題，使螞蟻能準確感知路徑信息，我們規(guī)定在每只螞蟻走完所有的服務(wù)節(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ī)則

本文的信息素約束函數(shù)有如下關(guān)系：

(3)

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

3.3 遺傳蟻群算法的流程

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

圖1 遺傳蟻群算法流程

4 實驗測試與性能分析

4.1 實驗參數(shù)的設(shè)置

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

表1 參數(shù)取值表

表2 服務(wù)候選集

4.2 實驗測試與結(jié)果分析

(1)收斂性

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

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

(2)代價

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

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

(3)延遲

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

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

(4)抖動

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

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

5 結(jié)束語

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

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

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

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

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

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

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

[7] 夏 利,田東渭,張艷艷.網(wǎng)格和組播樹結(jié)合的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

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

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

TP393.02

A

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