查道貴，許彩芳

宿州職業(yè)技術(shù)學(xué)院計(jì)算機(jī)信息系，安徽宿州，234101

?

基于改進(jìn)量子進(jìn)化算法的計(jì)算機(jī)網(wǎng)絡(luò)最佳路由選擇分析

查道貴，許彩芳

宿州職業(yè)技術(shù)學(xué)院計(jì)算機(jī)信息系，安徽宿州，234101

摘要：為了進(jìn)一步改進(jìn)網(wǎng)絡(luò)性能，采用改進(jìn)量子進(jìn)化算法優(yōu)化計(jì)算機(jī)網(wǎng)絡(luò)中路由選擇問題，運(yùn)用量子計(jì)算方法得出并評(píng)估具體狀態(tài)及相關(guān)適應(yīng)數(shù)值，并通過改進(jìn)量子進(jìn)化算法的旋轉(zhuǎn)角度、調(diào)整函數(shù)等手段來優(yōu)化路由選擇和流量分布。算法仿真測(cè)試表明改進(jìn)后的量子進(jìn)化算法平均時(shí)延低、鏈路利用效率高、降低了擁塞、提升了質(zhì)量，因此，改進(jìn)量子進(jìn)化算法更符合路由選擇問題的求解，可使得路由在面臨選擇的過程中具備更加優(yōu)越的收斂速度和尋優(yōu)功能。

關(guān)鍵詞：改進(jìn)量子進(jìn)化算法；計(jì)算機(jī)網(wǎng)絡(luò)；路由選擇；仿真

量子計(jì)算是利用量子世界的疊加形態(tài)以及糾纏性與相干性等特點(diǎn)，促使量子信息系統(tǒng)突破以往經(jīng)典信息體系的限制?，F(xiàn)階段，用量子計(jì)算方法解決經(jīng)典計(jì)算中的NP問題(非圖靈機(jī)上的多項(xiàng)式時(shí)間算法問題)是研究的焦點(diǎn)，其中量子進(jìn)化算法是最新形成的以量子計(jì)算原理為基礎(chǔ)的概率優(yōu)化方法，它以量子計(jì)算中的概念、理論為基礎(chǔ)，用量子位編碼表示染色體，并巧妙借助量子門的功能進(jìn)行搜索。因其自身的種群規(guī)模小，且不會(huì)對(duì)算法性能產(chǎn)生影響，故有收斂速度快、在全局尋優(yōu)能力強(qiáng)的優(yōu)點(diǎn)。本文主要分析用改進(jìn)量子進(jìn)化算法的計(jì)算機(jī)網(wǎng)絡(luò)最佳路由選擇問題，以證明這種算法在路由選擇問題方面的可行性。

1路由選擇問題

在現(xiàn)代計(jì)算機(jī)通信網(wǎng)絡(luò)系統(tǒng)中，用數(shù)據(jù)包平均傳輸時(shí)延作為衡量網(wǎng)絡(luò)性能的指標(biāo)，其中科學(xué)合理的路由策略可以促使各個(gè)節(jié)點(diǎn)發(fā)送出的報(bào)文按時(shí)到達(dá)目的地，縮減額外費(fèi)用，并高效利用網(wǎng)絡(luò)資源，降低整個(gè)運(yùn)營(yíng)成本[1]。在已知的網(wǎng)絡(luò)拓?fù)?、鏈路容量與各個(gè)節(jié)點(diǎn)在滿足通信要求的條件下，怎樣確定節(jié)點(diǎn)對(duì)通信路由產(chǎn)生的作用，降低網(wǎng)絡(luò)平均時(shí)延，這種路由選擇優(yōu)化問題屬于非線性0-1規(guī)劃問題，其數(shù)學(xué)模型可表示如下：

(1)

2量子進(jìn)化算法

這種算法是將量子計(jì)算和進(jìn)化算法有機(jī)結(jié)合，是在量子態(tài)矢量的基礎(chǔ)上進(jìn)行計(jì)算，用量子比特編碼代表染色體，同時(shí)用量子旋轉(zhuǎn)門、量子肺門更新染色體，進(jìn)一步優(yōu)化求解目標(biāo)問題。在量子進(jìn)化算法中，用下列矩陣代表量子染色體，長(zhǎng)度單位m。

(2)

公式(2)中，量子比特|0>態(tài)的概率幅度用αm表示，其中|1>態(tài)的概率幅度用βm表示，且滿足下面歸一化要求：

αn2+βn2=1，n=1，2，3，…，m

(3)

為了解空間的全部解疊加情況，借助量子染色體作為坍塌解，可知量子染色體能很好地體現(xiàn)出解的多樣性，但要借助量子旋轉(zhuǎn)門完成量子計(jì)劃算法的進(jìn)化對(duì)策。原理：利用搜索方法把新得出的解無限逼近找出最優(yōu)解，保留各種概率增加行駛，消除各種無用結(jié)果的概率行駛，促使其向進(jìn)化方向發(fā)展[3-4]。

(4)

其中，θi表示旋轉(zhuǎn)角度，具體計(jì)算方法為：

θi=Δθis(αi，βi)π

(5)

在這個(gè)公式中，量子旋轉(zhuǎn)門的旋轉(zhuǎn)角度數(shù)值用Δθi表示，其取值范圍如表1所示。主要控制算法收斂速度，其中量子旋轉(zhuǎn)門旋轉(zhuǎn)角度的方向是由函數(shù)s(αi，βi)實(shí)現(xiàn)，確保算法向最優(yōu)解方向進(jìn)行搜索。

表1　函數(shù)數(shù)值取值表

表1中，最優(yōu)二進(jìn)制解搜索b的第i位用bi表示，且解x比解b更優(yōu)用fx≥fb代表。由于量子染色體可能發(fā)生坍塌新城二進(jìn)制解的概率，繼而發(fā)生不變解，公式(6)可以化解這種不良情況。

(6)

其中ε表示某一個(gè)正數(shù)，數(shù)值很小。

量子計(jì)算方法的程序，首先初始化種群確保Q(t)，其中t為0，開始測(cè)量種群的各個(gè)個(gè)體，得出一組狀態(tài)P(t)，評(píng)估它的適應(yīng)度，并記錄下最佳個(gè)體狀態(tài)的相應(yīng)適應(yīng)度數(shù)值，當(dāng)其處于非技術(shù)狀態(tài)下開始計(jì)算，要求t=t+1，檢測(cè)出種群Q(t-1)，得出具體狀態(tài)并評(píng)估，再通過量子門更新Q(t)，得出子代種群Q(t+1)，并記錄最佳個(gè)體狀態(tài)及其相關(guān)適應(yīng)度數(shù)值[5]。

3改進(jìn)量子進(jìn)化算法

在不斷更新種群的過程中，改進(jìn)量子進(jìn)化法，其中合理調(diào)整Δθi以及s(αi，βi)是重點(diǎn)內(nèi)容。以往算法多先查表，給出不連續(xù)性旋轉(zhuǎn)角度，這樣，針對(duì)各個(gè)問題解空間的搜索帶有一定的跳躍性，因此需要對(duì)其進(jìn)行動(dòng)態(tài)改進(jìn)。

3.1檢測(cè)初始種群

由于改進(jìn)后的量子進(jìn)化算法編碼是多維的，操作0、1字符串時(shí)，需要將量子進(jìn)化的編碼映射至二進(jìn)制編碼方面，具體測(cè)量過程：在一個(gè)[0，1]的數(shù)值區(qū)間范圍內(nèi)，如果壁概率幅度大，檢測(cè)出來的結(jié)果是1，相反則是0，評(píng)估解的適應(yīng)度，將其作為下一步演化的目標(biāo)數(shù)值[6]。

3.2優(yōu)化調(diào)整旋轉(zhuǎn)角度

3.3優(yōu)化調(diào)整函數(shù)

采用組合優(yōu)化法可知，個(gè)體基因之間的關(guān)聯(lián)性較弱，對(duì)于這種情況定義量子位。

定義1：滿足歸一化條件，進(jìn)一步實(shí)現(xiàn)(αi，βi)的實(shí)數(shù)對(duì)，得出量子位概率幅度。

定義2：找出定義1中量子位所對(duì)應(yīng)的二維空間，相位角度是arctan(βi/αi)，并用符號(hào)ω表示，其中ω∈(-π/2，π/2)。

依照上述兩個(gè)定義，設(shè)計(jì)出一種依照量子位且在二維實(shí)空間內(nèi)的象限，并不斷調(diào)整相位角大小、旋轉(zhuǎn)角度方向。搜索出來的αib，βib是最優(yōu)個(gè)體B中第i個(gè)量子位概率幅度，其中相位角度ωib=arctg(βib /αib)，個(gè)體中第i個(gè)量子位的概率幅度待更新數(shù)值，用αix，βix表示，更新以后的量子位方向的變化用s(αix，βix)表示，其中順時(shí)針方向需用+1表示，而逆時(shí)針方向用-1表示，進(jìn)一步促使現(xiàn)行解向最優(yōu)解方向靠近。隨著收斂速度越來越快，列出第一象限的數(shù)據(jù)，并檢查其他各個(gè)象限的具體情況，找出不同類型的旋轉(zhuǎn)方向。

3.4變異

通過變異，可以有效阻止沒有成熟收斂于各種算法的小范圍內(nèi)搜索功能，由量子非門操作量子變異。具體方法：先從一定概率的種群中選出若干個(gè)個(gè)體，針對(duì)選出的個(gè)體依照確定概率決定一個(gè)或者多個(gè)變異位。針對(duì)選中的位量子比特概率幅度進(jìn)行量子非門操作。量子變異操作實(shí)質(zhì)上改變了比特態(tài)疊加狀態(tài)，促使原來向1方向坍縮方向轉(zhuǎn)變成0，且這種變異操作對(duì)于染色體的疊加狀態(tài)會(huì)產(chǎn)生一定效果[8]。

4算法仿真測(cè)試

為了進(jìn)一步證明算法在計(jì)算機(jī)網(wǎng)絡(luò)系統(tǒng)中屬于最佳選擇路徑，需要對(duì)這種算法進(jìn)行仿真實(shí)驗(yàn)，然后和傳統(tǒng)量子進(jìn)化算法作詳細(xì)比較，所得實(shí)驗(yàn)結(jié)果如表2所示。由表2可知，改進(jìn)的量子進(jìn)化算法的尋優(yōu)功能、收斂速度明顯優(yōu)于傳統(tǒng)的量子進(jìn)化算法，且在計(jì)算機(jī)網(wǎng)絡(luò)路由選擇方面，表現(xiàn)出良好的性能。

表2　路由選擇仿真　　　　　%

同時(shí)，將改進(jìn)后的量子進(jìn)化算法所得結(jié)果和改進(jìn)遺傳算法、禁忌搜索算法進(jìn)行對(duì)比可知，前者的平均時(shí)延、鏈路利用效率均優(yōu)于后二者，且結(jié)果穩(wěn)定。在一定程度上表明了在網(wǎng)絡(luò)負(fù)荷增重、分組長(zhǎng)度增加的情況下，改進(jìn)量子進(jìn)化算法可以搜索到合理路由，進(jìn)而把流量從利用率高的鏈路再次分配至利用率較低的鏈路，并且確保流量分布均勻，降低擁塞概率，提升解質(zhì)量。

5結(jié)束語

將改進(jìn)量子進(jìn)化算法應(yīng)用于計(jì)算機(jī)網(wǎng)絡(luò)系統(tǒng)中，可以讓計(jì)算機(jī)網(wǎng)絡(luò)路由在遇到選擇時(shí)獲取更加快速的收斂速度、更好的尋優(yōu)功能。且在一定程度上解決了計(jì)算機(jī)通信鏈路需要解決的最優(yōu)路由難題。同時(shí)，還能降低網(wǎng)絡(luò)平均時(shí)延和費(fèi)用，從而降低網(wǎng)絡(luò)總體運(yùn)營(yíng)費(fèi)用，提高鏈路利用效率。將改進(jìn)量子進(jìn)化算法應(yīng)用于優(yōu)化計(jì)算機(jī)網(wǎng)絡(luò)路由選擇中，效果良好，可以為其他類型網(wǎng)絡(luò)的性能優(yōu)化提供有益借鑒。

參考文獻(xiàn)：

[1]宋明紅，俞華鋒，陳海燕．改進(jìn)量子進(jìn)化算法在計(jì)算機(jī)網(wǎng)絡(luò)路由選擇中的應(yīng)用研究[J]．科技通報(bào)，2014，8(1)：170-173

[2]張大陸，曹孝晶，胡治國(guó)．基于用戶體驗(yàn)評(píng)價(jià)模型的最優(yōu)路由選擇算法[J]．計(jì)算機(jī)應(yīng)用，2012(10)：2683-2695

[3]楊曉琴，章麗芳，曹慶皇，等．基于鏈路帶寬利用率的路由選擇算法[J]．計(jì)算機(jī)應(yīng)用，2012(9)：2422-2425

[4]趙清艷，熊茂華．基于改進(jìn)禁忌搜索算法的無線傳感器網(wǎng)絡(luò)路由選擇[J]．計(jì)算機(jī)測(cè)量與控制，2012，2(5)：1442-1444

[5]朱凱．FCoE路由管理模塊的設(shè)計(jì)與實(shí)現(xiàn)[D]．北京：北京郵電大學(xué)計(jì)算機(jī)學(xué)院，2010：14-18

[6]宋強(qiáng)磊，車阿大．量子進(jìn)化算法在生產(chǎn)調(diào)度中的應(yīng)用綜述[J]．計(jì)算機(jī)應(yīng)用研究，2012，6(5)：1601-1605

[7]蘇超．基于Kademlia協(xié)議的網(wǎng)絡(luò)模型和路由的研究[D]．成都：西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院，2009：36-43

[8]夏礻韋，于舒娟，張昀．基于量子免疫優(yōu)化的盲檢測(cè)算法[J]．計(jì)算機(jī)技術(shù)與發(fā)展，2014，04(4)：41-44

(責(zé)任編輯：汪材印)

中圖分類號(hào)：TP393.02

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1673-2006(2016)02-0104-03

作者簡(jiǎn)介：查道貴(1975-)，安徽安慶人，碩士，講師，主要研究方向：計(jì)算機(jī)應(yīng)用技術(shù)。

基金項(xiàng)目：安徽省高校人文社會(huì)科學(xué)研究重點(diǎn)項(xiàng)目“皖北地區(qū)高職英語教師科研現(xiàn)狀調(diào)查與研究”(SK2014A400)。

收稿日期：2015-08-17

doi:10.3969/j.issn.1673-2006.2016.02.029