計(jì)算機(jī)網(wǎng)絡(luò)路由選擇中改進(jìn)量子進(jìn)化算法的應(yīng)用

史望聰，耿 健

（1.陜西交通職業(yè)技術(shù)學(xué)院 信息工程系，陜西 西安　710018；2.陜西高速公路電子收費(fèi)有限公司 陜西 西安　710018）

計(jì)算機(jī)網(wǎng)絡(luò)路由選擇中改進(jìn)量子進(jìn)化算法的應(yīng)用

史望聰1，耿 健2

（1.陜西交通職業(yè)技術(shù)學(xué)院 信息工程系，陜西 西安710018；2.陜西高速公路電子收費(fèi)有限公司 陜西 西安710018）

科技的發(fā)展和計(jì)算機(jī)技術(shù)的進(jìn)步極大的帶動(dòng)了我國(guó)經(jīng)濟(jì)的發(fā)展，現(xiàn)階段我國(guó)任何行業(yè)的發(fā)展都離不開對(duì)計(jì)算機(jī)網(wǎng)絡(luò)的應(yīng)用。但就目前互聯(lián)網(wǎng)規(guī)劃和拓展的實(shí)際情況來看，仍然存在著一些亟待解決的問題，其中最為典型的就是如何在滿足互聯(lián)網(wǎng)各節(jié)點(diǎn)通訊需求的前提下，選擇可以提升互聯(lián)網(wǎng)通信效率的計(jì)算機(jī)網(wǎng)絡(luò)路由問題。與傳統(tǒng)計(jì)算機(jī)網(wǎng)絡(luò)路由選擇算法相比，改進(jìn)量子進(jìn)化算法的應(yīng)用能夠有效的互聯(lián)網(wǎng)通信效率。基于此，本文首先闡述了計(jì)算機(jī)網(wǎng)絡(luò)路由選擇的含義，然后對(duì)量子進(jìn)化算法進(jìn)行了分析，最后研究了量子進(jìn)化算法的改進(jìn)策略，希望能夠引起讀者的思考。

計(jì)算機(jī)網(wǎng)絡(luò)；路由選擇；改進(jìn)量子進(jìn)化算法；應(yīng)用

眾所周知，互聯(lián)網(wǎng)已然成為了人們生活中不可或缺的部分，互聯(lián)網(wǎng)為人們的衣食住行帶來了便捷，同時(shí)我國(guó)現(xiàn)代經(jīng)濟(jì)的發(fā)展也離不開互聯(lián)網(wǎng)的支持［1-3］。近年來，隨著互聯(lián)網(wǎng)的更大規(guī)模的規(guī)劃和拓展，計(jì)算機(jī)網(wǎng)絡(luò)路由選擇存在的問題日益暴露出來。目前我國(guó)計(jì)算機(jī)網(wǎng)絡(luò)路由選擇算法已經(jīng)不能滿足現(xiàn)代社會(huì)發(fā)展的需求和計(jì)算機(jī)網(wǎng)絡(luò)的正常運(yùn)行需要，因此對(duì)計(jì)算機(jī)網(wǎng)絡(luò)路由選擇算法進(jìn)行優(yōu)化改進(jìn)是現(xiàn)階段我國(guó)計(jì)算機(jī)網(wǎng)絡(luò)發(fā)展亟待解決的問題。下面本文就圍繞量子進(jìn)化算法的改進(jìn)問題進(jìn)行進(jìn)一步的研究。

1　計(jì)算機(jī)網(wǎng)絡(luò)路由選擇的含義

爬山法、梯度法、模擬退算法和列表尋優(yōu)法是計(jì)算機(jī)網(wǎng)絡(luò)路由選擇的傳統(tǒng)方法，這些方法具有一定程度的局限性，并且受限條件也比較多，致使其作用無法得到有效的發(fā)揮［4-5］。計(jì)算機(jī)網(wǎng)絡(luò)路由選擇的主要含義為：在滿足現(xiàn)有的計(jì)算機(jī)網(wǎng)絡(luò)拓?fù)洹⒕W(wǎng)絡(luò)通信容量和網(wǎng)絡(luò)各節(jié)點(diǎn)需求的前提下，對(duì)網(wǎng)絡(luò)各節(jié)點(diǎn)的路由進(jìn)行選擇，從而使計(jì)算機(jī)網(wǎng)絡(luò)的時(shí)延性得到最大程度的縮小。通常情況下，計(jì)算機(jī)網(wǎng)絡(luò)路由的選擇可以運(yùn)用一些簡(jiǎn)化工作：1）假設(shè)計(jì)算機(jī)網(wǎng)絡(luò)各節(jié)點(diǎn)內(nèi)部緩沖器的容量是足夠大的，不可能因?yàn)橐绯龆鴮?dǎo)致數(shù)據(jù)包丟失；2）假設(shè)報(bào)文長(zhǎng)度可以按實(shí)際指數(shù)分布，并且按照泊松到達(dá)；3）對(duì)節(jié)點(diǎn)處理報(bào)文的時(shí)延性進(jìn)行忽略；4）所有報(bào)文傳輸均屬于同等級(jí)服務(wù)。

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

2.1量子進(jìn)化計(jì)算法

量子進(jìn)化算法實(shí)際上是基于量子計(jì)劃和進(jìn)化算法的結(jié)合，該算法是建立在態(tài)矢量的基礎(chǔ)之上的，并且以量子的比特編碼表示染色體，而染色體的更新依靠量子旋轉(zhuǎn)門和非門來實(shí)現(xiàn)，從而進(jìn)一步完成計(jì)算機(jī)網(wǎng)絡(luò)路由的最優(yōu)化選擇［6］。

在量子進(jìn)化算法中，量子染色體可以用以下矩陣表示：

式中，αi，βi分別代表量子比特|0＞態(tài)和量子比特|1＞態(tài)的概率幅，并且兩者之間滿足以下條件：

問題的解可以由一個(gè)量子染色體進(jìn)行表征，其主要原理是通過量子染色體的隨機(jī)測(cè)量結(jié)果和概率方式，并通過二進(jìn)制實(shí)現(xiàn)坍塌表現(xiàn)，在實(shí)踐過程中我們不難發(fā)現(xiàn)量子染色體對(duì)問題解決有著明顯的優(yōu)越性［7］。然后，量子進(jìn)化算法的進(jìn)化是通過利用量子旋轉(zhuǎn)門來實(shí)現(xiàn)的，其主要原理是利用搜索法將當(dāng)前的解逼近至最佳解，利用概率增加或減少的形式對(duì)結(jié)果進(jìn)行保留或者剔除，進(jìn)而實(shí)現(xiàn)量子進(jìn)化算法的進(jìn)化。

當(dāng)量子進(jìn)化算法更新至第t代為P（t）=｛pt1，…，ptN｝，其適應(yīng)值為：f（t）=｛ft1，…，ftN｝量子染色體ptj上基因位的第 i個(gè)值用向量（αi，βi）T進(jìn)行表示，并采用量子旋轉(zhuǎn)門對(duì)其進(jìn)化，進(jìn)而得到（α′i，β′i）T，具體進(jìn)化方法如下式：

其中，θi代表旋轉(zhuǎn)角，計(jì)算公式如下：

式中Δθi，s（αi，βi）的取值見表1，Δθi代表的是量子旋轉(zhuǎn)門的旋轉(zhuǎn)角值，主要作用是控制量子進(jìn)化算法的收斂速度，而s（αi，βi）主要是完成對(duì)旋轉(zhuǎn)門旋轉(zhuǎn)角方向的控制，從而為算法向著最優(yōu)解的方向開展搜索提供保障。

表1　函數(shù)查詢表

表1中，xi代表第i位量子染色體的二進(jìn)制解，bi表示第i位搜索的最佳二進(jìn)制解，fx≥fb表示解x比解b更優(yōu)。當(dāng)量子染色體出現(xiàn)坍塌為二進(jìn)制解而出現(xiàn)不變解的時(shí)候，可以采用下式進(jìn)行處理：

其中，ε是一個(gè)正數(shù)，但是其數(shù)值比較小。

2.2量子進(jìn)化算法的流程

1）初始化種群Q（t），t=0；

2）對(duì)初始種群中各個(gè)體進(jìn)行測(cè)量，并得到一組狀態(tài)P（t）。

3）評(píng)估P（t）的適應(yīng)度

4）對(duì)最優(yōu)的個(gè)體狀態(tài)及其適應(yīng)度值進(jìn)行記錄

5）如果處于非結(jié)束狀態(tài)，然后繼續(xù)進(jìn)行以下步驟：

Begin

①t=t+1；

②測(cè)量種群Q（t-1），進(jìn)而得到狀態(tài)P（t）；

③評(píng)估P（t）的適應(yīng)度

④利用量子門對(duì)Q（t）進(jìn)行更新，得到子代種群Q（t+1）；

⑤將最優(yōu)個(gè)體狀態(tài)及其適應(yīng)度值記錄下來。

End

End

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

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

傳統(tǒng)的量子進(jìn)化算法應(yīng)用過程中，旋轉(zhuǎn)角的確定通常是利用查表的方式，故而旋轉(zhuǎn)角是不連續(xù)的，在空間搜索方面具有跳躍性，導(dǎo)致搜索不夠全面和精細(xì)［8-9］。文中從動(dòng)態(tài)調(diào)整的角度出發(fā)對(duì)量子進(jìn)化算法進(jìn)行改進(jìn)。其中，Δθi改進(jìn)后的調(diào)整式為：

式中，fb表示搜索的最佳個(gè)體B及其使用度，fx表示當(dāng)前個(gè)體X及適用度。通過對(duì)式（6）進(jìn)行分析可得，Δθi代表的是一個(gè)區(qū)間，與其個(gè)體相適應(yīng)。Δθi值越大，就表示當(dāng)前個(gè)體與最佳個(gè)體之間的距離越遠(yuǎn)，搜索網(wǎng)絡(luò)就越大。因此搜索速度需要進(jìn)一步的提高。反之，Δθi值越小就表示當(dāng)前個(gè)體與最佳個(gè)體之間的具體就越近，搜索網(wǎng)絡(luò)就越小，能夠采用個(gè)細(xì)搜索實(shí)現(xiàn)對(duì)最優(yōu)解的尋找。

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

鑒于個(gè)體基因間的相關(guān)性不是很強(qiáng)的特點(diǎn)，量子位可以定義為：1）在滿足歸一化條件的前提下，而實(shí)現(xiàn)（αi，βi）的實(shí)數(shù)對(duì)，然后再對(duì)應(yīng)到一個(gè)量子位相應(yīng)的概率幅［10-12］。（2）將（1）中的量子位對(duì)應(yīng)到相應(yīng)的二維空間，其相位角為arctan（βi/αi），并用符號(hào)w進(jìn)行表示。在上述定義的基礎(chǔ)上，文中提出了一種通過二維空間中量子位的象限和相位角的大小來對(duì)旋轉(zhuǎn)角的方向進(jìn)行調(diào)整的方法，如表2所示。

表2　旋轉(zhuǎn)角方向調(diào)整方法

最優(yōu)個(gè)體B的第i個(gè)量子位的概率幅用表2中的αbi，βbi表示，其相位角為ωbi=arctg（βbi/αbi）；αxi，βxi表示個(gè)體第i個(gè)量子位概率幅的更新值，其相應(yīng)的相位角為：ωxi=arctg（βxi/αxi）。量子位的更新旋轉(zhuǎn)方向?yàn)椋簊（αxi/βxi），其中+1表示順時(shí)針方向，-1表示逆時(shí)針方向［13］。通過對(duì)表2進(jìn)行分析可得，通過這種方法可以有效的使當(dāng)前的解無限逼近最優(yōu)解，而且提高了收斂速度。

4　改進(jìn)量子進(jìn)化算法的仿真測(cè)試

為了進(jìn)一步的說明本文所提出的改進(jìn)量子進(jìn)化算法在計(jì)算機(jī)網(wǎng)絡(luò)路由選擇中的優(yōu)越性，下面進(jìn)行了仿真實(shí)驗(yàn)，并且和傳統(tǒng)的算法進(jìn)行了比較，實(shí)驗(yàn)結(jié)果如圖1所示。

圖1　改進(jìn)算法和傳統(tǒng)算法性能對(duì)比

根據(jù)圖1可知，文中所研究的改進(jìn)量子進(jìn)化算法與傳統(tǒng)的量子進(jìn)化算法相比具有明顯的優(yōu)越性，其尋優(yōu)能力和收斂速度都有了很大程度的提升［14］。通過仿真測(cè)試，可以有效的為改進(jìn)后量子進(jìn)化算法在實(shí)際計(jì)算網(wǎng)絡(luò)路由選擇的應(yīng)用提供指導(dǎo)作用，保證改進(jìn)后的算法在實(shí)際應(yīng)用過程中發(fā)揮其最大的作用。通過利用這種改進(jìn)方法可以保證選擇的路由能夠很好的處理計(jì)算機(jī)網(wǎng)絡(luò)運(yùn)行過程中出現(xiàn)的問題，從而維護(hù)計(jì)算機(jī)網(wǎng)絡(luò)的正常運(yùn)行，有效提高工作人員的工作效率［15］。實(shí)際計(jì)算機(jī)網(wǎng)絡(luò)路由選擇的應(yīng)用過程中，文中所研究的改進(jìn)方法也得到了證實(shí)。

5　結(jié)束語

總而言之，在計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)飛速發(fā)展的今天，計(jì)算機(jī)網(wǎng)絡(luò)路由的選擇顯得尤為關(guān)鍵，這就進(jìn)一步推動(dòng)了對(duì)計(jì)算機(jī)量子進(jìn)化算法的改進(jìn)研究。文中所提出的量子進(jìn)化算法的改進(jìn)方法的建立在傳統(tǒng)量子進(jìn)化算法的基礎(chǔ)之上的。通過仿真模擬，證實(shí)了文中所提出的改進(jìn)方法無論是在尋優(yōu)搜索還是在收斂速度上都表現(xiàn)出了明顯的優(yōu)勢(shì)，有效的解決了目前計(jì)算機(jī)網(wǎng)絡(luò)路由選擇面臨的問題，提高了互聯(lián)網(wǎng)通信效率。

［1］文孟飛，彭軍，張曉勇.無線傳感器網(wǎng)絡(luò)中基于同心圓樹的路由選擇算法［J］.中南大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，43 （9）：3490-3495.

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

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

［4］雷華軍，秦開宇.基于改進(jìn)量子進(jìn)化算法的測(cè)試優(yōu)化選擇［J］.儀器儀表學(xué)報(bào)，2013（4）：838-844.

［5］趙榮香.改進(jìn)量子進(jìn)化算法在計(jì)算機(jī)網(wǎng)絡(luò)路由選擇中的應(yīng)用探究［J］.科技傳播，2014（24）：148-152.

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

［7］劉宏艷，王偉，翟穎.計(jì)算機(jī)網(wǎng)絡(luò)路由優(yōu)化及優(yōu)化算法的運(yùn)用［J］.赤子，2014（17）：241.

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

［9］魏娜，黃學(xué)宇，劉守東.量子進(jìn)化算法原理及改進(jìn)策略研究［J］.計(jì)算機(jī)工程，2011，37（20）：223-226.

［10］葉慶波.量子Grover算法的改進(jìn)及其在Ad Hoc網(wǎng)絡(luò)路由選擇中的應(yīng)用［D］.南京：南京郵電大學(xué)，2013.

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

［12］丁文.基于免疫多目標(biāo)優(yōu)化的網(wǎng)絡(luò)組播路由選擇［J］.計(jì)算機(jī)應(yīng)用研究，2012，29（4）：1477-1479.

［13］田園，張杰.基于SpaceWire的鏈路狀態(tài)算法研究與設(shè)計(jì)［J］.計(jì)算機(jī)工程，2011，37（23）：113-115.

［14］申曉寧.一種新型的多目標(biāo)優(yōu)化混合量子進(jìn)化算法［J］.計(jì)算機(jī)應(yīng)用研究，2012，29（12）：4441-4444.

［15］鄭建國(guó)，錢潔.采用灰色碼觀測(cè)的量子進(jìn)化算法［J］.信息與控制，2012，41（3）：350-355.

Application of computer network routing improved quantum evolutionary algorithm

SHI Wang-cong1，GENG Jian2
（1.Information Engineering of Shaanxi Vocational and Technical College，Xi'an 710018，China；2.Shaanxi Expressway Electronic Toll Co.，Ltd.，Xi'an 710018，China）

Progress and development of science and technology and computer technology greatly promoted China's economic development，the development of any industry are inseparable from our present stage of computer network applications. However，the current situation and to expand the Internet planning point of view，there are still some problems to be solved，the most typical is how to meet the needs of Internet communication nodes premise，select the computer network can improve the efficiency of Internet traffic routing problem.And conventional computer network routing algorithm，the improved application of quantum evolutionary algorithm can effectively Internet communications efficiency.Based on this，this paper describes the computer network routing meaning，then quantum evolutionary algorithms are analyzed，the final study of quantum evolutionary algorithm improvement strategies，hoping to arouse the reader ponder.

computer network；routing selection；improved quantum evolutionary algorithm；application

TNO

A

1674－6236（2016）09-0045-03

2015-09-17稿件編號(hào)：201509125

交通運(yùn)輸部科技計(jì)劃項(xiàng)目（2015319G02190）

史望聰（1981—），男，陜西戶縣人，講師。研究方向：計(jì)算機(jī)應(yīng)用及交通信息化的教學(xué)與科研工作。