量子計算智能 課件 第 4 章 量子進(jìn)化組播路由算法

1提綱第4章量子進(jìn)化組播路由算法2提綱第4章量子進(jìn)化組播路由算法4.1量子進(jìn)化多維背包算法

4.1.1基本理論4.1.2量子進(jìn)化多維背包算法

4.1.3仿真實驗及結(jié)果4.2量子進(jìn)化組播路由

4.2.1量子進(jìn)化算法4.2.2時延受限組播路由問題定義4.2.3量子進(jìn)化組播路由算法4.2.4仿真實驗及結(jié)果分析4.3量子進(jìn)化動態(tài)組播路由

4.2.1動態(tài)組播問題的定義4.2.2量子進(jìn)化動態(tài)組播路由算法4.4結(jié)論與討論3提綱第4章量子進(jìn)化組播路由算法4.1量子進(jìn)化多維背包算法

4.1.1基本理論4.1.2量子進(jìn)化多維背包算法

4.1.3仿真實驗及結(jié)果4.2量子進(jìn)化組播路由

4.2.1量子進(jìn)化算法4.2.2時延受限組播路由問題定義4.2.3量子進(jìn)化組播路由算法4.2.4仿真實驗及結(jié)果分析4.3量子進(jìn)化動態(tài)組播路由4.2.1動態(tài)組播問題的定義4.2.2量子進(jìn)化動態(tài)組播路由算法4.4結(jié)論與討論4進(jìn)化算法（EAs）是一種基于自然生物進(jìn)化的隨機(jī)搜索優(yōu)化算法。相對于傳統(tǒng)的優(yōu)化算法，進(jìn)化算法有更好的魯棒性和全局搜索能力。目前研究的進(jìn)化計算主要有三種典型的算法：Fraser[1]，Bremermann[2]和Holland[3]提出的遺傳算法、Foge[4]提出的進(jìn)化規(guī)劃、Rechenberg[5]和Schwefel[6]提出的進(jìn)化策略。進(jìn)化算法主要是通過對一個近似最優(yōu)解的個體進(jìn)行一系列操作以取得最優(yōu)解，其主導(dǎo)思想是利用適者生存的原理逐漸地逼近最優(yōu)解。在進(jìn)化算法中的每一代中，一組新的近似解是根據(jù)個體與問題主要方面的適應(yīng)度來選取的并不斷對其進(jìn)行變異操作。這一過程有可能使得種群中的新個體相對于初始產(chǎn)生的個體更能適應(yīng)環(huán)境，如同自然界中進(jìn)化的生物對自然環(huán)境的適應(yīng)。4.1.1基本理論54.1.1基本理論進(jìn)化算法的特點在于對解的個體表示，評價函數(shù)用來表示個體的適應(yīng)度水平。種群規(guī)模，變異算子，雙親選擇，復(fù)制和遺傳，生存競爭的方法等這些都是在動態(tài)變化的。在平衡算法的搜索能力和復(fù)雜度之間的矛盾中，上面所提到的都需要很好的設(shè)計，特別是在本書中對個體的表示方法。本書的算法中使用較少的個體（甚至只使用一個個體）通過相應(yīng)的變異算子能夠更好的搜索解空間，且花費很少的時間獲得全局最優(yōu)解。上述效果的取得，主要是因為在進(jìn)化算法中引進(jìn)了量子計算的概念。量子計算機(jī)在1980年[7]初被提出其具體描述和成型是在1980年代末[8]?，F(xiàn)在已經(jīng)提出了許多著名的量子算法，如Shor的量子因式分解[9][10]，還有Grover數(shù)據(jù)庫搜索算法[11][12]。64.1.1基本理論進(jìn)化算法的特點在于對解的個體表示，評價函數(shù)用來表示個體的適應(yīng)度水平。種群規(guī)模，變異算子，雙親選擇，復(fù)制和遺傳，生存競爭的方法等這些都是在動態(tài)變化的。在平衡算法的搜索能力和復(fù)雜度之間的矛盾中，上面所提到的都需要很好的設(shè)計，特別是在本書中對個體的表示方法。本書的算法中使用較少的個體（甚至只使用一個個體）通過相應(yīng)的變異算子能夠更好的搜索解空間，且花費很少的時間獲得全局最優(yōu)解。上述效果的取得，主要是因為在進(jìn)化算法中引進(jìn)了量子計算的概念。量子計算機(jī)在1980年[7]初被提出其具體描述和成型是在1980年代末[8]?，F(xiàn)在已經(jīng)提出了許多著名的量子算法，如Shor的量子因式分解[9][10]，還有Grover數(shù)據(jù)庫搜索算法[11][12]。74.1.1基本理論

1990年代末已開始研究進(jìn)化計算和量子計算的融合。它們主要分為兩類。一類是利用自動規(guī)劃技術(shù)產(chǎn)生新的量子算法如遺傳規(guī)劃[13]，另一類是在傳統(tǒng)的計算機(jī)上應(yīng)用量子進(jìn)化算法[14][15]，其中一個分支是將量子計算中的原理如疊加性，相干性，糾纏性，并行性等應(yīng)用在進(jìn)化計算中。在[16]和[17]中，疊加性就包含在了交叉算子中。1.量子比特的狀態(tài)表示在量子系統(tǒng)中，最小的信息單元為一個量子位（即量子比特），一個量子位的狀態(tài)可以取值0（記為）或1（記為），或者是兩者的任意疊加態(tài)記為，可以表示為：(4-1)84.1.1基本理論2.量子比特個體的編碼方式進(jìn)化算法的常用編碼方式有二進(jìn)制、十進(jìn)制和符號編碼。在本算法中，使用一種新穎的基于量子比特的編碼方式，這里用一對實數(shù)定義一個量子比特來表示一個基因位，一個具有N個量子比特的系統(tǒng)（個體）可以描述為：

(4-2)其中且在本書中和取值為0到1之間的實數(shù)。表示第l個基因位取值為0的概率，表示第l個基因位取值為1的概率。因此，這種表示方法可以表征任意的線性疊加態(tài)，例如一個具有如下三對概率幅的3量子比特系統(tǒng)：

(4-3)94.1.1基本理論則系統(tǒng)的狀態(tài)可以表示為：(4-4)上面結(jié)構(gòu)表示狀態(tài),,,,,,和出現(xiàn)的概率分別為和。因此，這個3量子比特系統(tǒng)表示了八個狀態(tài)疊加的信息，即它可以同時表示出八個狀態(tài)的信息。由于使用量子比特個體能夠表征疊加態(tài)，一個量子個體攜帶了豐富的信息，作用在其上的操作就具有并行性。如在上例中，一個量子比特個體足以表示八個狀態(tài)，而在傳統(tǒng)進(jìn)化算法至少需要八個個體(000)，(001)，(010)，(011)，(100)，(101)，(110)和(111)來表示；同時采用這種方式的編碼具有好的收斂性，隨著，趨于1或0，量子比特個體收斂于一個狀態(tài)，這時多樣性消失。104.1.1基本理論3.QEA算法的整體結(jié)構(gòu)將上述編碼方式將其運用到進(jìn)化計算當(dāng)中，有人提出了量子進(jìn)化算法(Quantum-InspiredEvolutionaryAlgorithm-QEA）[18]，算法總體流程如圖4-1：圖4-1量子進(jìn)化算法總體流程圖ProcedureQEAbegini)initializeQ(t)ii)makeP(t)byobservingthestatesofQ(t)iii)evaluateP(t)iv)storethebestsolutionamongP(t)intoB(t)while(nottermination-condition)dobegint=t+1v)makeP(t)byobservingthestatesofQ(t-1)vi)evaluateP(t)vii)updateQ(t)usingQ-gatesviii)storethebestsolutionamongB(t-1)andP(t)intoB(t)ix)storethebestsolutionbamongB(t)x)if(migration-condition)thenmigratebtoB(t)globallyorlocally，respectivelyendend114.1.1基本理論本質(zhì)上QEA是一種相似于其它進(jìn)化算法的概率算法。然而QEA中的個體是由多個量子比特位構(gòu)成的，將其稱之為量子染色體。種群t表示在第t代，n是種群中個體數(shù)目，為量子染色體定義如下：

(4-5)這里m是個體中量子比特位個數(shù)，j=1，2，，n，QEA的具體流程如下：(1)

在“initializeQ(t)”中，和，i=1，2，，m。，所有的，j=1，2，，n，都初始化為。這意味一個量子染色體表示所有可能的線性疊加態(tài)都以相同的概率

(4-6)其中是表示的第k代狀態(tài)，由組成，而,i=1，2，，m。是根據(jù)或者的概率大小得出的0或1。124.1.1基本理論

(2)

通過觀測的狀態(tài)得到二進(jìn)制字符串解，其中在第0代。解是一個長度為m的二進(jìn)制字符串。是通過分別觀測每一個量子比特位的狀態(tài)或者,i=1，2，，m，的概率大小得出的0或1。如果是在量子計算機(jī)上，通過觀測其量子狀態(tài)將會很快并行坍塌到某一單一狀態(tài)，得到一組二進(jìn)制串。而由于實驗是在傳統(tǒng)計算機(jī)上運行的，所以在QEA中將發(fā)生的方式會與上述情況有所不同。(3)將所有種群中的每個（二進(jìn)制字符串）通過相應(yīng)的處理并解碼得到，用適應(yīng)度函數(shù)進(jìn)行評價。(4)在中選擇初始化中得到的最優(yōu)解并儲存到中，其中和，一樣都在第0代。134.1.1基本理論

(5)

在while循環(huán)中，在種群中的量子染色體是由觀測中狀態(tài)矩陣得到的，具體方法同步驟ii)一樣，解碼后重新每個量子染色體的適應(yīng)度。應(yīng)當(dāng)注意到中的可以通過多次觀測中的得到。在這種情況下，應(yīng)當(dāng)被取代，其中為觀測索引值。(6)

這一步中，通過量子旋轉(zhuǎn)門(Q-gate）更新中表示量子染色體狀態(tài)矩陣。

定義4.1：Q-gate是QEA中的一種變異方法，在更新量子染色體中的比特位時要滿足歸一化條件，其中和就是更新其比特位時的狀態(tài)值。在QEA中Q-gate的具體形式如下

(4-7)l14其中，i=1，2，，m。，是每個量子比特位朝向0或1的旋轉(zhuǎn)角度。的設(shè)計是與實際問題密切相關(guān)的。在下文中將要講到的背包問題，是根據(jù)最優(yōu)解中的第i個比特位和第i個比特位之間的關(guān)系函數(shù)得到的。通過Q-gate可以調(diào)整表示0或1的概率大小使其變?yōu)?或0，這樣就避免了陷入局部最優(yōu)。viii，ix)最優(yōu)解是在和中選擇的并存儲到中，如果中的最優(yōu)解比b好，那么b將會被新產(chǎn)生的最優(yōu)解所取代。(7)

從中挑選出全局最優(yōu)解并用于指引下一代的變異。4.1.1基本理論154.1.2量子進(jìn)化多維背包算法1.背包問題描述背包問題（knapsackproblem）是運籌學(xué)中一個典型的優(yōu)化難題[19]，在實踐中有重要的應(yīng)用如預(yù)算控制，項目選擇、材料切割、貨物裝載等，并且還常常作為其他問題的子問題加以研究。隨著網(wǎng)絡(luò)技術(shù)的快速發(fā)展，背包公鑰密碼在電子商務(wù)中的公鑰設(shè)計中也起著重要的作用。在過去的幾十年中，背包問題吸引了理論研究人員和實際工程人員的注意力，因而得到了深入的研究。理論方面研究興趣來自于該問題簡單的結(jié)構(gòu)，這種特點可以深入探索許多組合特性，而更為復(fù)雜的優(yōu)化問題可以通過求解一系列背包子問題來最終解決。164.1.2量子進(jìn)化多維背包算法0-l背包問題的數(shù)學(xué)模型可以表述如下：

(4-8)其中表示物品的價值，表示物品占用的某種資源的數(shù)量，表示背包所能提供的某種資源的量。當(dāng)時，稱為多維0-1背包問題。背包問題在實踐中有廣泛的應(yīng)用背景，如許多簡單結(jié)構(gòu)組合構(gòu)成了復(fù)雜系統(tǒng)，對簡單問題的深入探索也使復(fù)雜問題的求解變得相對容易。在設(shè)計解決大量的復(fù)雜組合優(yōu)化問題算法時，背包問題往往會作為子問題出現(xiàn)，所以背包問題的算法的改進(jìn)，對復(fù)雜組合優(yōu)化問題算法的改良是十分有益的。174.1.2量子進(jìn)化多維背包算法背包問題屬于NP難解問題，意味著基于的，無法找到多項式時間算法求得該類問題。已有的求解方法可分為精確算法（如動態(tài)規(guī)劃、回溯法、分支定界、隱枚舉法等）以及近似算法，如（貪婪算法，搜索算法、模擬退火法等）兩大類。Dantzig在二十世紀(jì)五十年代中期首先進(jìn)行了開創(chuàng)性研究[20]，利用貪婪算法求得了一個理想解，得出了0-1背包問題最優(yōu)解的上界。1974年，Horowitz和Sahni首先利用分支定界技術(shù)改進(jìn)了Dantzig上界[21]。1980年，Balas和Zemel首先提出了解答背包問題的“核（Core）”思想，使問題的研究有了較大進(jìn)展。在八十年代末Pisinger利用平衡技術(shù)[22]和“核膨脹”思想[23]設(shè)計的算法，該算法結(jié)合動態(tài)規(guī)劃技術(shù)，使解答背包問題的算法有了實質(zhì)的進(jìn)展。184.1.2量子進(jìn)化多維背包算法在進(jìn)入二十世紀(jì)的九十年代以后，生物仿生技術(shù)和Internet技術(shù)的飛速發(fā)展，使得模擬生物學(xué)規(guī)律的各種近似并行算法不斷涌現(xiàn)，遺傳算法已經(jīng)在0-1背包問題上得到了很好的應(yīng)用，螞蟻算法、粒子算法等仿生算法也在各種組合優(yōu)化問題中得到了應(yīng)用。2.算法具體步驟量子進(jìn)化算法的本質(zhì)是一種概率算法。對問題進(jìn)行量子編碼，用狀態(tài)矩陣表示解在某一狀態(tài)的概率大小，再通過量子旋轉(zhuǎn)門對狀態(tài)矩陣進(jìn)行更新，使得在下一次坍塌時，得到最優(yōu)解的概率更大，經(jīng)過多次迭代后最終收斂到最優(yōu)解。算法總體流程如圖4-2所示194.1.2量子進(jìn)化多維背包算法圖4-2量子進(jìn)化多維背包算法總體流程圖204.1.2量子進(jìn)化多維背包算法算法中的各個算子的設(shè)計如下：1)編碼：對背包問題的解進(jìn)行量子編碼，用狀態(tài)矩陣表示背包問題解的狀態(tài)，其中m是物品的個數(shù)，t表示在第t代。在t=0時，。狀態(tài)矩陣U坍塌后，編碼0表示將對應(yīng)物品未放入背包中，1表示放入。2)觀測：對同一狀態(tài)矩陣進(jìn)行多次觀測，這樣的好處是可以增加解的多樣性，因為如果只對狀態(tài)矩陣中的一組或觀測一次時，很難發(fā)現(xiàn)這一狀態(tài)下能夠產(chǎn)生的最優(yōu)解，從而會影響對下一次迭代的指引，導(dǎo)致陷入局部最優(yōu)。214.1.2量子進(jìn)化多維背包算法3)計算適應(yīng)度：適應(yīng)度的計算方法為：其中，＝0或1，是對應(yīng)背包的價值。4)修正染色體算子：由于初始群體隨機(jī)性以及迭代過程中的觀測操作都可導(dǎo)致不滿足約束條件的染色體，所以在計算個體適應(yīng)度之前要對不滿足約束條件的染色體進(jìn)行處理。修正法主要有兩種方法即隨機(jī)修正和貪婪修正。所謂隨機(jī)修正就是對于不滿足約束條件的染色體，隨機(jī)將某些為1的比特位，將其變?yōu)?。也就是說對于超出背包資源容量的，隨機(jī)取出一些物品，直到滿足約束條件為止。224.1.2量子進(jìn)化多維背包算法貪婪修正就是挑選那些性價比小的物品，將其取出，直到滿足約束條件為止。實驗證明，采用貪婪修正法的效果要好于其它方法[24]。為了加快算法的收斂性，將采用貪婪法對滿足約束的染色體進(jìn)行進(jìn)一步的優(yōu)化，主要分為兩步，如下圖4-3和4-4所示：圖4-3修正不滿足約束條件解的流程圖一，修正不滿足約束條件的解：第1步，通過計算

，其中

，

＝0或1，

表示背包的體積，

為第

維的約束條件，找出不滿足約束條件的維數(shù)

；第2步，將

維中狀態(tài)為“1”的第

個背包都計算profit/cost[i]并按降序序排列；

第3步，將末位狀態(tài)為“1”的背包設(shè)為“0”，并重新計算代價，如果滿足結(jié)束條件，則終止，否則繼續(xù)執(zhí)行第三步。234.1.2量子進(jìn)化多維背包算法圖4-4添加滿足約束條件的背包流程圖更新：此算法利用上一代中的最優(yōu)解（量子染色體）和量子旋轉(zhuǎn)門(Q-gate)更新狀態(tài)矩陣U。具體參照表4-1：二，添加滿足約束條件的背包第1步，

將狀態(tài)為“0”的第

個背包計算

，其中

表示維數(shù)，將所得結(jié)果按降序排列；

第2步,

按序列順序嘗試將每一個背包狀態(tài)設(shè)置為“1”，驗證添加后是否滿足每一維的約束條件，如果滿足，則這個背包的狀態(tài)為“1”，否則繼續(xù)保持為“0”。244.1.2量子進(jìn)化多維背包算法表4-1旋轉(zhuǎn)角選擇策略其中是背包的價值，和分別對應(yīng)新得到量子染色體和已知最優(yōu)解中的第i個比特位，，，，，，，，。經(jīng)Q-gate更新操作后的量子狀態(tài)矩陣中的比特變?yōu)椋?/p>

(4-9)00false00true01false01true10false10true11false11true254.1.3仿真實驗及結(jié)果1.試驗數(shù)據(jù)說明本次實驗采用文獻(xiàn)[25]提供的標(biāo)準(zhǔn)測試數(shù)據(jù)，對目前已經(jīng)給出最優(yōu)解的數(shù)據(jù)都進(jìn)行了測試。具體的測試結(jié)果如下表格所示，其中的一些測試指標(biāo)描述如下：表示背包的維數(shù)，表示物資的個數(shù)，表4-2，4-3中的表示在20次獨立試驗中求得最優(yōu)解的次數(shù)，表4-4中的表示在50次獨立試驗中求得最優(yōu)解的次數(shù)。表示獲得最優(yōu)解的平均值，表示求得的最優(yōu)解，，，分別表示目標(biāo)函數(shù)值的平均計算次數(shù)，最大次數(shù)，最小次數(shù)。平均百分誤差，其中是第次試驗得到的最優(yōu)值，是已知最優(yōu)值。試驗均采用C++語言在DuoCPU2.0GHz，2GBRAM的PC機(jī)上完成。264.1.3仿真實驗及結(jié)果2.測試結(jié)果1在該部分，給出了在量子進(jìn)化算法加入貪婪策略求得的結(jié)果，其中表4-2和表4-3是每次都找到已知最優(yōu)解的結(jié)果，表4-4是某些時候沒有找到最優(yōu)解的結(jié)果。針對不同的問題，在算法使用的進(jìn)化代數(shù)和在每一步中量子旋轉(zhuǎn)門坍塌的次數(shù)都是不定的，但全部是以計算適應(yīng)度函數(shù)的次數(shù)為評價標(biāo)準(zhǔn)的，終止條件為給定進(jìn)化代數(shù)。表4-2QEA算法測試結(jié)果問題mn

Weing12281412781412781505246177120Weing22281308831308831994.8472849020Weing32289567795677957.8189231120Weing4228119337119337806.3106840120Weing52289876998769661.812412220Weing62281306231306231636255034120274.1.3仿真實驗及結(jié)果表4-2QEA算法測試結(jié)果問題mn

Weing72105109544510954451887.72396143620Weing821056243196243192739.25205190720Weish0153045544554704.710883920Weish0253045364536540.310312220Weish0353041154115770.5117735620Weish0453045614561288.58023320Weish055304514451497.1251420Weish06540555755577790.619116357920Weish0754055675567668.499634020Weish08540560556057292.211828231020Weish0954052465246404.9747520Weish10550633963395085.817996212420Weish1155056435643865.3111819020Weish12550633963395221.416067197720284.1.3仿真實驗及結(jié)果表4-3QEA算法測試結(jié)果問題mnWeish13550615961591962.2317492720Weish14560695469541291.8184896320Weish15560748674861974.4530870120Weish16560728972892857.63813230920Weish17560863386334614.77547341320Weish19570769876983389.34796221720Weish20570945094504271.55265306120Weish21570907490743380.54982228120Weish23580834483447522.110059546220Weish25580993999394837.36845333520Weish265909584958412157.528530168020Weish27590981998194537.510196452420Weish285909492949228512436772062720Weish295909410941018147282131018220294.1.3仿真實驗及結(jié)果表4-3QEA算法測試結(jié)果問題mnWeish3059011191111916466.19910551520Pb1427309030901156.1221656020Pb2434318631864641.37588314720Pb422995168951681565.5236945820Pb51020213921391905341394620Pet21010870168701611.149120Pet3101540154015112.24272020Pet4102061206120729.625738820Pet5102812400124006649.911557116720Pet7550165371653738897541922627120Flei1020213921393389.7674378320Hp1428341834181646.42343103120Hp2435318631867315.912432362120304.1.3仿真實驗及結(jié)果表4-4QEA算法測試結(jié)果(a)Weish8(5,40)問題(b)Pb2(4,34)問題問題mnWeish1857095809574.1290.07%5058089478944.4870.20%50Weish245801022010215.330.048%50Sento1306077727486.8421.71%50Sento2306087228709.5221.145%50Pb7303710351034.24120.096%50314.1.3仿真實驗及結(jié)果(c)Wing8(2,105)問題(d)Weish30(5,90)問題圖4-5QEA算法針對四個典型問題的收斂曲線圖從表4-4可以看出，對于個別的測試數(shù)據(jù)，結(jié)果不很理想。這與問題本身的特點有關(guān)，需要具體分析。上述實驗表明，量子進(jìn)化算法解決0-1背包問題是有效的。與相應(yīng)的傳統(tǒng)進(jìn)化算法相比，該算法僅需一個個體，操作簡單搜索能力強(qiáng)，有效地避免了陷入局部最優(yōu)值的情形，而且尋優(yōu)效果明顯，收斂速度快。324.1.3仿真實驗及結(jié)果圖4-5表明了該算法較強(qiáng)的搜索能力和較快地收斂速度。實驗中還發(fā)現(xiàn)，如果對于物品個數(shù)和維數(shù)限制較多時，增加每一代中量子旋轉(zhuǎn)門坍塌的次數(shù)比延長算法的進(jìn)化代數(shù)更能加快其收斂的速度。對于Weish和Wing系列中的大多數(shù)問題的試驗結(jié)果分析表明，進(jìn)化代數(shù)為150次，而每代中量子旋轉(zhuǎn)門坍塌的次數(shù)則在20~200次不等，就可取得最優(yōu)值。3.測試結(jié)果2在該部分，將量子進(jìn)化算法(QEA)與免疫克隆算法（ImmuneClonalAlgorithm-ICA）[26]作對比測試，ICA的抗體種群規(guī)模為40，克隆規(guī)模為200，變異概率為編碼長度的倒數(shù)，對抗體的修補(bǔ)采用貪婪策略。具體的結(jié)果如表4-5：334.1.3仿真實驗及結(jié)果表4-5QEA與ICA部分測試結(jié)果對比與ICA相比，對于文獻(xiàn)[25]給出的主要數(shù)據(jù)測試，在50次的獨立實驗中，Weish10這個測試數(shù)據(jù)的結(jié)果比ICA差，而其它的結(jié)果要好于ICA的結(jié)果。這說明了量子進(jìn)化算法較強(qiáng)的搜索能力和較快的收斂速度。測試數(shù)據(jù)平均計算次數(shù)最大計算次數(shù)最小計算次數(shù)problemmnQEAICAQEAICAQEAICAWeing122814127815053426.5246161377711444Weing810526243191798.836420.9242886640113414079Weish013054554704.72021.61088361039361Weish1050563395085.56678.5179961010821242888Weish1460569541291.89548.51848137189635415Weish1970576983389.3976547961696722175415Weish2790598184937.5245841019661009452412274Pb127430901156.173152216151625603249Hp128434181646.4105452343249091031433234提綱第4章量子進(jìn)化組播路由算法4.1量子進(jìn)化多維背包算法

4.1.1基本理論4.1.2量子進(jìn)化多維背包算法

4.1.3仿真實驗及結(jié)果4.2量子進(jìn)化組播路由

4.2.1量子進(jìn)化算法4.2.2時延受限組播路由問題定義4.2.3量子進(jìn)化組播路由算法4.2.4仿真實驗及結(jié)果分析4.3量子進(jìn)化動態(tài)組播路由4.2.1動態(tài)組播問題的定義4.2.2量子進(jìn)化動態(tài)組播路由算法4.4結(jié)論與討論35量子信息學(xué)是二十世紀(jì)的一門新興學(xué)科，是量子力學(xué)與經(jīng)典信息學(xué)的交叉學(xué)科，也是當(dāng)今世界各國緊密跟蹤的前沿學(xué)科之一。量子計算是該學(xué)科中最為重要的概念之一。早在1982年Benioff和Feynman提出了將量子力學(xué)系統(tǒng)用于推理計算的可能，并且給出了量子計算的概念[27][28]。到1985年Deutsch提出了第一個量子計算模型[29]，1994年Shor提出了離散對數(shù)問題和大整數(shù)質(zhì)因子分解問題的量子算法[30][31]，讓人們第一次看到了量子計算獨具優(yōu)勢的應(yīng)用前景。相對于傳統(tǒng)的計算而言，量子計算從本質(zhì)上改變了傳統(tǒng)計算的理念，它利用量子態(tài)的疊加性和相干性，以及量子比特之間的糾纏性等實現(xiàn)量子的并行計算，能快速并行的處理海量信息，使得大規(guī)模復(fù)雜問題能夠在有限的指定時間內(nèi)完成。量子計算以其獨特的計算性能成為當(dāng)前信息領(lǐng)域的一個很活躍的研究課題。4.2.1量子進(jìn)化算法36在上述背景下，量子機(jī)理和特性為計算智能的研究提供了新的思路，量子進(jìn)化算法（QuantumEvaluationAlgorithm:QEA）應(yīng)運而生。量子進(jìn)化算法的研究始于二十世紀(jì)九十年代，A.Narayanan和M.Moore首先將量子理論與遺傳算法結(jié)合，于1996年提出了量子遺傳算法的概念[17]。Kuk-HyunHan和Jong-HwanKim在2000年提出了一種遺傳量子算法[32]，后來他們在遺傳量子算法的基礎(chǔ)上于2002年提出了量子進(jìn)化算法，并在求解優(yōu)化問題上獲得了突破性結(jié)果[33]。量子進(jìn)化算法與進(jìn)化算法相比，能夠更容易的在探索與開發(fā)之間取得平衡，具有并行計算、種群規(guī)模小、收斂速度快以及全局尋優(yōu)能力強(qiáng)等特點。本書就是基于量子進(jìn)化算法的這些特點，結(jié)合組播路由問題求解遇到的瓶頸問題，研究了基于量子進(jìn)化算法的組播路由算法。4.2.1量子進(jìn)化算法37量子進(jìn)化算法是量子計算與進(jìn)化算法相融合的產(chǎn)物，已經(jīng)成為解決數(shù)值優(yōu)化[34][35]、組合優(yōu)化、信號處理優(yōu)化等問題的一種新方法[36][37]，它以量子計算的一些概念和理論為基礎(chǔ)，如量子位、量子疊加態(tài)等。量子進(jìn)化算法中采用量子比特位來對個體進(jìn)行編碼，通過量子更新，量子交叉，量子變異以及個體選擇等算子來完成主要進(jìn)化操作。下面將對這些概念和理論進(jìn)行具體介紹。1.量子比特編碼相對于經(jīng)典信息的基本存儲單元比特（bit），量子信息的基本存儲稱為量子比特(qubit)[38]。一個量子比特的狀態(tài)可以處于兩個極化狀態(tài)，即取值0（記為）或1（記為），也可以處于兩者的任意疊加態(tài)記為，一個量子比特的狀態(tài)可以表示為：

4.2.1量子進(jìn)化算法38

(4-10)其中，，為任意復(fù)數(shù)，代表相應(yīng)狀態(tài)的概率幅，且滿足：

(4-11)其中，分別表示量子位處于狀態(tài)0和狀態(tài)1的概率。進(jìn)化算法中常用的編碼方式有二進(jìn)制編碼，十進(jìn)制編碼和符號編碼，量子進(jìn)化算法中，不再使用這些確定性的編碼方式，而是根據(jù)量子的疊加性，使用一種新的基于量子比特的概率編碼方式，使用量子比特編碼的個體稱為量子個體，一個具有L個量子比特位的個體可以表示成如下形式：

(4-12)

4.2.1量子進(jìn)化算法39且滿足，其中和取值為0到1之間的實數(shù)。表示第個基因位取值為0的概率，表示第

個基因位取值為1的概率。這個個體處在個量子比特的疊加狀態(tài)，可以同時代表種狀態(tài)。所以對于上述具有個量子比特位的量子個體的一次操作，就相當(dāng)于對傳統(tǒng)系統(tǒng)中的個信息單元同時操作，這就是量子的并行計算。在量子進(jìn)化算法中，若干個量子個體就構(gòu)成了種群，第代種群可以表示為：

(4-13)其中為種群規(guī)模，為進(jìn)化代數(shù)，表示第代種群中第個量子個體，其具體形式可以表示為：

(4-14)4.2.1量子進(jìn)化算法ll40其中L表示量子比特的位的長度，即個體的長度，。量子進(jìn)化算法中采用量子比特的編碼方式，一個個體可以代表任意線性疊加狀態(tài)，一個量子個體就能攜帶大量的信息，作用在個體上的操作就具有了并行性。而在進(jìn)化算法中一個個體只能表示一個具體的狀態(tài)，所以QEA比EA更容易保持種群的多樣性。隨著和逐漸趨于0或者1，量子個體也逐漸收斂到單一狀態(tài)，多樣性逐漸減少，算法收斂。2.量子觀測量子觀測是指模擬量子的坍塌性對種群中的各個體進(jìn)行一次測量，使得個體從疊加態(tài)轉(zhuǎn)化到單一的確定狀態(tài)。量子理論指出，對一個處于任意疊加態(tài)的量子比特進(jìn)行觀測時，能使該量子比特從某一疊加態(tài)退化到狀態(tài)“0”或者“1”上，使量子個體狀態(tài)確定，經(jīng)過量子觀測后的4.2.1量子進(jìn)化算法41量子狀態(tài)稱為觀測態(tài)，記為，觀測態(tài)種群的具體形式可以表示為：

(4-15)其中觀測態(tài)個體是長度為的二進(jìn)制串，具體是根據(jù)根據(jù)量子比特的概率幅的取值情況得到的，一般過程是：隨機(jī)產(chǎn)生一個[0,1]的數(shù)，若，則二進(jìn)制串上第i位上取1，否則取0。3.量子評價量子評價是指得到量子觀測態(tài)后，對觀測態(tài)個體進(jìn)行好壞的評價，個體的好壞用適應(yīng)度值來度量，量子的評價過程就是根據(jù)問題所設(shè)計的適應(yīng)度函數(shù)計算個體的適應(yīng)度大小。其中適應(yīng)度函數(shù)的設(shè)計，通常情況下，可直接將問題的目標(biāo)函數(shù)轉(zhuǎn)化成適應(yīng)度函數(shù)，另外適應(yīng)度函數(shù)還要求盡可能符合以下幾個要求：一是適應(yīng)度函數(shù)是單值、連續(xù)、非負(fù)以及4.2.1量子進(jìn)化算法42最大化函數(shù)；其次要求適應(yīng)度函數(shù)要能合理的反應(yīng)問題對應(yīng)解的好壞程度；第三要求適應(yīng)度盡可能簡單，盡量減少時間和空間復(fù)雜度。適應(yīng)度的大小直接反應(yīng)個體的好壞，進(jìn)化算法中遵循“優(yōu)勝劣汰”的規(guī)則，適應(yīng)度的評價直接影響算法搜索最優(yōu)解的質(zhì)量，對算法的收斂速度以及結(jié)果都起著關(guān)鍵作用，本書算法所使用的適應(yīng)度函數(shù)將在后面的量子進(jìn)化組播路由算法中具體介紹。4.量子進(jìn)化量子進(jìn)化是指量子進(jìn)化算法中種群進(jìn)化的機(jī)制，常用的量子進(jìn)化操作有量子交叉、量子變異、量子更新、個體選擇等。目前，應(yīng)用最廣泛的方式是以量子更新為種群進(jìn)化的最主要方式，結(jié)合量子交叉以及量子變異等輔助種群進(jìn)化。4.2.1量子進(jìn)化算法431)量子更新量子更新是指根據(jù)量子疊加特性以及量子變遷的理論，通過適合問題的量子門來轉(zhuǎn)換量子位狀態(tài)的過程，即將量子門作用于量子疊加態(tài)或者糾纏態(tài)的基態(tài)，使其相互干涉，改變其相位，從而改變各基態(tài)的概率幅。由于量子比特的概率幅必須滿足歸一化條件，在進(jìn)行量子門變換時要求變換矩陣必須是可逆的酉正矩陣，即滿足,其中為矩陣的共軛轉(zhuǎn)置，常用的量子變換矩陣有旋轉(zhuǎn)門、異或門以及Hadamard門等。QEA中主要采用的是量子旋轉(zhuǎn)門(QuantumRotationGate),其矩陣形式表示如下：(4-16)4.2.1量子進(jìn)化算法44其中表示旋轉(zhuǎn)角度。種群中的個體通過旋轉(zhuǎn)門更新量子位來完成量子更新，具體過程可以如下式4-17所示：

(4-17)其中，表示第代種群中某量子個體的第個量子比特位，表示更新后得到的第代種群中對應(yīng)的那個量子個體的第個量子比特位。的定義如下式4-18：(4-18)其中決定了旋轉(zhuǎn)的方向，保證算法的收斂；的取值與求解的問題相關(guān)，它控制搜索的范圍即旋轉(zhuǎn)角度的步長，決定了算法的收斂速度，如果取值過小，將導(dǎo)致搜索空間小，會使更新操作慢甚至停滯，反之，4.2.1量子進(jìn)化算法45則會使算法收斂慢以及容易使算法陷入局部最優(yōu)。目前的取值沒有明確的理論知道，一般都根據(jù)具體問題的實驗進(jìn)行取值，其大小一般控制在之間[39]，目前常用的選擇策略值可以通過下面的表4-6查得。表4-6旋轉(zhuǎn)角選擇策略常用查詢表4.2.1量子進(jìn)化算法00false0000000true0000001false0000001true0+1010false-1+1010true+1-1011false+1-1011true+1-1046表4-6中為當(dāng)前觀測態(tài)個體的第位，為當(dāng)前最優(yōu)個體觀測態(tài)的第位；表示當(dāng)前個體的適應(yīng)度值，表示當(dāng)前最優(yōu)個體的適應(yīng)度值。表4.6中的值是目前常用的一組取值，如下圖4-6所示的圖更直觀的說明該策略如何能夠使算法收斂到適應(yīng)度值更高的個體。假設(shè)，，成立，此時滿足表4-6中第四種情況，那么為了使當(dāng)前解收斂到一個更高的適應(yīng)度值，應(yīng)當(dāng)增加取狀態(tài)“0”的概率，即增大的值，根據(jù)圖4-6，如果在第一、三象限，應(yīng)該向順時針方向旋轉(zhuǎn)，如果在第二、四象限，應(yīng)該向逆時針方向旋轉(zhuǎn)。在每次對種群進(jìn)行更新時，都加入了當(dāng)前最優(yōu)個體的信息，不斷的指導(dǎo)種群向著最優(yōu)個體的方向進(jìn)化，從而加快了算法的收斂。4.2.1量子進(jìn)化算法47圖4-6量子旋轉(zhuǎn)門角度調(diào)整示意圖本書研究的基于進(jìn)化算法的組播路由算法中對適合求解組播問題的旋轉(zhuǎn)角選擇進(jìn)行了探討，根據(jù)路由問題的特點引入了一個權(quán)值因子，控制旋轉(zhuǎn)角的步長，加速了收斂速度，具體實現(xiàn)將在后文詳細(xì)介紹。4.2.1量子進(jìn)化算法482)量子交叉量子交叉是根據(jù)量子的相干性，使種群中的個體相互交換信息，改變了原來個體的結(jié)構(gòu)，從而產(chǎn)生新的個體的過程。最常用的量子交叉算子是對角法的全干擾交叉，即按照對角線重新排列組合的交叉方式，充分交換種群中個體之間的信息，產(chǎn)生新的個體，阻止種群進(jìn)化出現(xiàn)早熟。3)量子變異量子變異的常用操作是通過量子非門對量子位進(jìn)行的，將量子非們作用于需要變異的量子位使其狀態(tài)發(fā)生翻轉(zhuǎn)。前面介紹的量子更新其實也可以看作是一種量子變異，量子變異的主要目的是產(chǎn)生新的個體，增加種群的多樣性。4.2.1量子進(jìn)化算法495.量子進(jìn)化算法的流程量子進(jìn)化算法的一般算法流程如下：1) 初始化進(jìn)化代數(shù)，初始化種群：將種群中個體的所有量子位的概率幅值均初始化為，表示每個個體代表所有可能狀態(tài)的等概率疊加；2) 對種群中的各個體進(jìn)行量子觀測，得到觀測態(tài);3) 根據(jù)觀測態(tài)種群進(jìn)行量子評價，并保留最優(yōu)個體信息；4) 判斷是否滿足停機(jī)條件，若是，進(jìn)化結(jié)束，輸出當(dāng)前最優(yōu)個體，若否，跳轉(zhuǎn)到下一步；5) 根據(jù)交叉變異條件，對種群中的個體進(jìn)行量子交叉和量子變異等量子進(jìn)化操作；4.2.1量子進(jìn)化算法506) 完成量子進(jìn)化后對個體進(jìn)行量子更新，得到新一代種群；7) 進(jìn)化代數(shù)，轉(zhuǎn)到2）。4.2.1量子進(jìn)化算法51本書根據(jù)組播路由算法的特點，提出基于邊編碼的改進(jìn)量子進(jìn)化算法求解時延受限組播路由問題，下面首先給出時延受限組播路由問題的定義。首先將網(wǎng)絡(luò)抽象為無向連通圖，其中為網(wǎng)絡(luò)節(jié)點（路由器）的集合，E為邊（通信鏈路）的集合，在網(wǎng)絡(luò)中的任意邊上定義權(quán)值函數(shù)和，其中表示邊的代價，表示邊的延時。表示一條從到的路徑，延時函數(shù)和代價函數(shù)可表示如下：

(4-19)(4-20)給定源節(jié)點和目的節(jié)點集合。時延受限組播路由問題轉(zhuǎn)化為尋找一棵組播樹()滿足如下條件：4.2.2時延受限組播路由問題定義52

(4-21)(4-22)其中表示所求組播樹上從源節(jié)點到目的節(jié)點的路徑，是最大允許延時。從(4-21)和(4-22)式可以看出，求解時延受限組播路由問題實際上就是一個約束優(yōu)化問題，即求解在滿足式4-21的約束條件下求解4-22中代價的最小值。4.2.2時延受限組播路由問題定義531.問題描述時延受限組播問提已經(jīng)被證明了是NP完全問題[40]，針對這一問題已經(jīng)存在多種啟發(fā)式算法，在前面的章節(jié)已經(jīng)介紹。由于啟發(fā)式存在的一些缺陷，出現(xiàn)了一些用智能算法求解該問題的算法，現(xiàn)在大多數(shù)智能算法都采取預(yù)處理備選路徑集的方式，這種方式編解碼過程復(fù)雜，且算法的時間復(fù)雜度以及搜索空間隨網(wǎng)絡(luò)規(guī)模的增大而劇烈增大，算法效率低。本書結(jié)合文獻(xiàn)[41]中給出的有效降低算法復(fù)雜度的編碼策略，結(jié)合量子進(jìn)化算法的優(yōu)點和組播問題的特點，改進(jìn)了常用的量子旋轉(zhuǎn)門策略，提出了量子進(jìn)化時延受限組播路由算法(IQEA)，通過仿真實驗證明，IQEA在運行的時間，收斂速度以及組播代價三個方面均優(yōu)于文獻(xiàn)[41]中的正交遺傳算法求解的結(jié)果。4.2.3量子進(jìn)化組播路由算法542.算子設(shè)計1)編碼策略對于給定網(wǎng)絡(luò)中的所有邊，首先以列優(yōu)先的順序從1到進(jìn)行編號,那么整個網(wǎng)絡(luò)就可用一個量子比特位的量子個體進(jìn)行編碼，其中表示網(wǎng)絡(luò)中邊的總數(shù)。量子個體上的每一個量子比特位表示對應(yīng)邊在組播樹上的狀態(tài)，當(dāng)為狀態(tài)“0”時，表示邊不在組播樹上，為狀態(tài)“1”時表示邊在組播樹上，一個量子個體可以表示組播樹上網(wǎng)絡(luò)中邊存在的狀態(tài)。為了更清楚的說明編碼策略，舉例如下圖4-7所示的網(wǎng)絡(luò)，根據(jù)編碼策略對網(wǎng)絡(luò)中的邊進(jìn)行編號，該網(wǎng)絡(luò)中,那么就可以用一個長度為14的量子個體對該網(wǎng)絡(luò)進(jìn)行編碼。4.2.3量子進(jìn)化組播路由算法55假設(shè)源節(jié)點為1，目的節(jié)點集合為｛3，4，9｝，網(wǎng)絡(luò)中代價和時延權(quán)值均為1，當(dāng)觀測得到的染色體串為“11010010010000”時，該個體對應(yīng)于如圖4-8所示的組播樹。圖4-7編碼策略中編號和編碼方法的網(wǎng)絡(luò)

圖4-8量子個體例對應(yīng)的組播樹其中仍需滿足，,,P表示種群規(guī)模，t表示進(jìn)化代數(shù)。因此，量子種群可以表示為。這種編碼方式簡單，不用預(yù)處理備選路徑集，大大降低了算法的復(fù)雜度，而且由于它包括了整個4.2.3量子進(jìn)化組播路由算法56網(wǎng)絡(luò)的信息，能快速反應(yīng)網(wǎng)絡(luò)中的變化情況，對于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化和組播成員變化的動態(tài)組播路由，這種編碼方式均仍然適用，因此后面第四章中以這種編碼編碼策略為基礎(chǔ)，討論了動態(tài)組播路由問題的求解。2)觀測算子算法中的觀測算子就是量子進(jìn)化算法中的量子觀測算子，經(jīng)過量子觀測的操作，得到種群的觀測態(tài)，具體實現(xiàn)方式就在前面已經(jīng)介紹，這里就不在贅述。設(shè)Q(t)為第t代的量子個體種群，通過量子觀測產(chǎn)生的確定解為，其中是一個長度為的二進(jìn)制串。種群的觀測態(tài)是一組二進(jìn)制串，根據(jù)每一個二進(jìn)制串都可以得到一個原網(wǎng)絡(luò)圖的子圖，具體實現(xiàn)過程是：對的第位進(jìn)行判斷，當(dāng)?shù)谖欢M(jìn)制取值為“1”時，則原圖中對應(yīng)編號為的邊在子圖中是存在的，若取值為“0”則該邊不在子圖中出現(xiàn)。4.2.3量子進(jìn)化組播路由算法57這樣就得到每個個體對應(yīng)的子圖。3)檢查修復(fù)算子根據(jù)觀測算子觀測后的個體得到的子圖的代價權(quán)值可生成最小代價生成樹，但是得到的可能是沒有完全覆蓋組播組的樹，因此設(shè)計了檢查修復(fù)算子對染色體進(jìn)行修復(fù)，具體的操作過程如下：(1) 用文獻(xiàn)[42]中的搜索算法對子圖進(jìn)行搜索，生成代價最小的生成樹；(2) 從根節(jié)點開始搜索樹，將生成樹上非目的節(jié)點的葉子節(jié)點刪除并記錄已在樹上的目的節(jié)點。檢查生成樹上所覆蓋的節(jié)點，如果生成的是一棵覆蓋了所有源節(jié)點和目的節(jié)點集合的樹，轉(zhuǎn)(4),否則轉(zhuǎn)(3);4.2.3量子進(jìn)化組播路由算法58(3) 根據(jù)原網(wǎng)絡(luò)圖，將不在當(dāng)前樹上的目的節(jié)點用距離當(dāng)前樹代價最小且滿足時延約束的路徑與樹相連，直至所有組播組節(jié)點都在當(dāng)前最小代價生成樹上后轉(zhuǎn)(4);(4) 根據(jù)得到的生成樹修復(fù)觀測態(tài)染色體，即將新加入樹上的邊對應(yīng)的二進(jìn)制位置“1”，將從樹上刪除的邊以及沒有參與生成樹的邊上對應(yīng)的二進(jìn)制位都置“0”，檢查修復(fù)算子完成。經(jīng)過檢查修復(fù)算子，完成了對染色體的修復(fù)，使得種群中所有的個體的觀測態(tài)都能對應(yīng)于一棵覆蓋所有組播組成員的生成樹。4)適應(yīng)度評價算子適應(yīng)度評價是指通過適應(yīng)度函數(shù)計算個體的適應(yīng)度值，根據(jù)適應(yīng)度值的大小完成量子評價的過程。適應(yīng)度值能反應(yīng)個體的性能，適應(yīng)度值4.2.3量子進(jìn)化組播路由算法59越大，個體性能越好。本算法參考文獻(xiàn)[41]，定義適應(yīng)度函數(shù)如下：

(4-24)其中表示組播樹代價的倒數(shù)，則用于度量時延約束條件的滿足程度，本算法中在檢查修復(fù)算子操作中，對部分路徑的時延約束進(jìn)行了修復(fù)，但不能保證所有路徑均滿足時延約束條件。因此，本書算法也選擇與比較算法相同的評價函數(shù)。該評價函數(shù)有兩個目標(biāo)，所以每個個體對應(yīng)的適應(yīng)度值為向量(，)。

根據(jù)上述適應(yīng)度函數(shù)，假設(shè)組播樹

和

的適應(yīng)度值向量分別為

和

，當(dāng)滿足

或者當(dāng)

時，可判定組播樹

優(yōu)于組播樹

。根據(jù)這一規(guī)則對種群中的所有個體進(jìn)行評價，搜索并記錄最優(yōu)解。4.2.3量子進(jìn)化組播路由算法605)量子更新算子量子更新通過量子旋轉(zhuǎn)門策略完成，在基本量子進(jìn)化算法中已經(jīng)介紹了，量子旋轉(zhuǎn)門的旋轉(zhuǎn)角的選擇是旋轉(zhuǎn)門策略的關(guān)鍵。本算法在實驗過程中針對收斂速度相對較慢的問題，嘗試了對量子旋轉(zhuǎn)門策略進(jìn)行了改進(jìn)，即引入一個權(quán)值因子來控制量子旋轉(zhuǎn)門旋轉(zhuǎn)角的步長，對進(jìn)化過程中的一代種群中每個個體的每一量子比特位均采用不同的旋轉(zhuǎn)角進(jìn)行量子旋轉(zhuǎn)門更新[43]-[44]。種群中第個個體的第個量子比特位在進(jìn)行量子旋轉(zhuǎn)門更新時選擇的旋轉(zhuǎn)角的具體定義如下：

(4-25)(4-26)4.2.3量子進(jìn)化組播路由算法61在進(jìn)化中后期，為了加速收斂速度，根據(jù)之前每代種群中最優(yōu)個體各量子比特位出現(xiàn)“1”態(tài)或“0”態(tài)的概率,當(dāng)該概率值超過初始設(shè)定閾值時，本算法引入一個較小的權(quán)值因子縮小搜索范圍，如果該位在“0”和“1”出現(xiàn)的概率相當(dāng)，權(quán)值因子取相對大的值，使其能在一個相對較大的范圍內(nèi)搜索。為(0,1)之間取值的閾值[43]。在前面已經(jīng)介紹了旋轉(zhuǎn)角的取值范圍，因此權(quán)值因子只能在(0.1,5)之間取值，本書簡單的確定了三種搜索范圍，即一次取值1，2，3。作為嘗試，概率閾值取值規(guī)則如下[36]，若單一狀態(tài)出現(xiàn)概率超過80%，取最小權(quán)值，即，；若出現(xiàn)概率在60%~80%之間，搜索空間取中間范圍，即，；其他情況引入大權(quán)值，擴(kuò)大搜索空間。需要特別說明的是，該操作是在進(jìn)化的中后期才進(jìn)行的，仿真實驗中是在進(jìn)化到最大進(jìn)化代數(shù)的一半時改用上面的規(guī)則選擇旋轉(zhuǎn)角。其基礎(chǔ)步長和旋轉(zhuǎn)角的方向通過前面表。4.2.3量子進(jìn)化組播路由算法624-6查得。6)停機(jī)條件

本算法的目的是尋找一棵滿足約束條件的最小代價樹，算法以最大進(jìn)化代數(shù)作為停機(jī)條件。3.算法描述該算法大致流程同量子進(jìn)化算法，步驟如下，流程圖如表4-7所示：4.2.3量子進(jìn)化組播路由算法63表4-7量子進(jìn)化組播路由算法步驟4.算法復(fù)雜度分析假設(shè)給定網(wǎng)絡(luò)規(guī)模為，目的節(jié)點總數(shù)為，網(wǎng)絡(luò)中編碼邊的長度為，種群規(guī)模為,最大進(jìn)化代數(shù)為，檢查修復(fù)算子操作的時間復(fù)雜量子進(jìn)化組播路由算法Step1：初始化進(jìn)化代數(shù)t=0以及初始化表示多棵組播樹集合的種群

，即將種群中所有的概率幅初始化賦值為

，使所有的編碼邊都有相同的概率參與構(gòu)建組播樹；Step2：用量子觀測算子觀測種群

，量子態(tài)坍塌到觀測態(tài)，得到二進(jìn)制表達(dá)的觀測態(tài)

;Step3：用檢查和修復(fù)算子對當(dāng)前觀測種群進(jìn)行修復(fù)，使所有組播成員均在當(dāng)前組播樹上；Step4：根據(jù)評價函數(shù)評價當(dāng)前觀測種群，并記錄最優(yōu)個體信息；Step5：判斷停機(jī)條件，若滿足，輸出當(dāng)前最優(yōu)個體即為所求解，若不滿足轉(zhuǎn)step6；Step6：根據(jù)上面介紹的量子旋轉(zhuǎn)門策略對種群進(jìn)行更新，得到新一代的種群

；Step7：

更新進(jìn)化代數(shù)t=t+1,跳轉(zhuǎn)到step2。4.2.3量子進(jìn)化組播路由算法64度為，搜索最優(yōu)組播樹的時間復(fù)雜度，其他操作都可以在時間復(fù)雜度內(nèi)完成。因此，本算法的復(fù)雜度為：++。其中，和是確定的常數(shù)，編碼長度與網(wǎng)絡(luò)規(guī)模成線性關(guān)系，根據(jù)的運算規(guī)則，算法的復(fù)雜度可以化簡為：

(4-27)啟發(fā)式算法BSMA的算法復(fù)雜度為[45]，基于備選路徑集的量子進(jìn)化計算組播路由算法（QEA）的算法復(fù)雜度為[46]。為了區(qū)別文獻(xiàn)[46]中的QEA將本書算法記為IQEA。因此從理論分析可知，本書提出的算法(IQEA)在時間復(fù)雜度上優(yōu)于BSMA和QEA。4.2.3量子進(jìn)化組播路由算法655.算法收斂性分析定理4.1算法IQEA的種群序列是有限齊次馬爾可夫鏈。證明：由于IQEA采用量子比特對個體A進(jìn)行編碼，對于EA個體的取值是離散的0、1，假設(shè)個體長度為，種群規(guī)模為，則種群所在的狀態(tài)空間大小是。由于A的取值是連續(xù)的，所以理論上種群所在的狀態(tài)空間是無限的，但另一方面，實際運算中A是有限精度的，設(shè)其維數(shù)為v，則種群所在的狀態(tài)空間大小為，因此種群是有限的，而算法中采用的量子更新、選擇操作保證僅與有關(guān)，即是有限齊次馬爾可夫鏈。證畢。設(shè)，下標(biāo)t表示進(jìn)化的代數(shù)，表示在第t代時的一個種群，表示第i個個體。設(shè)f是上的適應(yīng)度函數(shù)其中，令4.2.3量子進(jìn)化組播路由算法66

(4-28)稱為最優(yōu)解集，其中為全局最佳值，則有如下定義：

定義4.2：設(shè)是一個隨機(jī)變量序列，序列中的變量代表在時間步t狀態(tài)中的最佳的適應(yīng)度。如果當(dāng)且僅當(dāng)

(4-29)則稱算法收斂。即表明當(dāng)算法迭代到足夠多的代數(shù)后，群體中包含全局最優(yōu)解的概率接近1。

定理4.2：對于算法IQEA的馬爾可夫鏈序列的種群滿意值序列是單調(diào)不減的，即對于任意的，有，即種群中的任何一個個體都不會退化。證明：顯然，由于在本算法中采用保留最優(yōu)個體來指導(dǎo)量子旋轉(zhuǎn)門更新，因此保證了每一代個體都不會退化。4.2.3量子進(jìn)化組播路由算法67

定理4.3：算法IQEA是以概率1收斂的。證明：由上所述，本算法的狀態(tài)轉(zhuǎn)移由馬爾可夫鏈來描述。將規(guī)模為P的群體認(rèn)為是狀態(tài)空間S中的某個點，用表示是S中的第i個狀態(tài)，相應(yīng)本算法，顯然表示在第t代時種群處于狀態(tài)，其中隨機(jī)過程的轉(zhuǎn)移概率為，則

(4-30)下面給出兩種特殊情況：設(shè)當(dāng)時：由于(4-30)式和定理4-2使得

(4-31)即當(dāng)父代中出現(xiàn)最優(yōu)解時不論經(jīng)歷多少代的進(jìn)化最優(yōu)解都不會退化。4.2.3量子進(jìn)化組播路由算法68當(dāng)時：由定理4-2可知：，所以

(4-32)在討論了轉(zhuǎn)移概率的兩種特殊情況后，接下來證明(4-29)式。設(shè)為種群處在狀態(tài)的概率，，則由馬爾科夫鏈的性質(zhì)可知：

(4-33)由于(4-34)因此(4-35)把(4-35)式代入(4-33)式，再利用(4-31)式和(4-32)式，則：

(4-36)因此：(4-37)4.2.3量子進(jìn)化組播路由算法69又因為和(4-37)式可知：

(4-38)即所有包含在非全局最優(yōu)狀態(tài)中的概率收斂于0。則包含在全局最優(yōu)狀態(tài)中的概率收斂為1。證畢。4.2.3量子進(jìn)化組播路由算法70采用Waxman隨即網(wǎng)絡(luò)模型[47]，生成節(jié)點平均度為4的網(wǎng)絡(luò)對上面介紹的量子進(jìn)化組播路由算法(IQEA)進(jìn)行測試。并與基于正交遺傳的組播路由算法(OGA)[48]進(jìn)行了比較。實驗運行的PC環(huán)境為主頻2.33GHzPentiumIV和2G內(nèi)存，在VC6.0編譯環(huán)境下使用C語言編程實現(xiàn)。仿真實驗主要考察了IQEA與OGA在組播樹代價和算法運行時間兩個方面的性能。此次仿真共設(shè)置了兩組實驗，分別討論采用改進(jìn)的量子旋轉(zhuǎn)門選擇策略前后IQEA算法性能的不同，并與OGA的性能進(jìn)行了比較。為了比較的公平性，種群規(guī)模均設(shè)為100。所有實驗結(jié)果均是獨立運行20次的基礎(chǔ)上得到的。4.2.4仿真實驗及其結(jié)果分析71討論改進(jìn)量子旋轉(zhuǎn)門策略對IQEA性能的影響測試實驗中，相關(guān)參數(shù)設(shè)置如下：OGA和IQEA的種群規(guī)模設(shè)為P＝100，OGA的參數(shù)設(shè)置使用文獻(xiàn)[48]中的一組設(shè)置：變異概率，交叉概率以及正交表。由于在IQEA和OGA中，都使用了相同的評價函數(shù)和選擇機(jī)制，所以也可以采用如下的性能指標(biāo)對組播代價進(jìn)行比較：

(4-39)其中T表示實驗次數(shù)，r值小于1表示Algorithm1的平均性能優(yōu)于Algorithm2，r值變大，則說明Algorithm 1的平均性能變差，因此可用于評價組播樹的代價。在下文中的所以圖和表格中，表示目的節(jié)點的總數(shù)，表示網(wǎng)絡(luò)規(guī)模即網(wǎng)絡(luò)中的節(jié)點總數(shù)。4.2.4仿真實驗及其結(jié)果分析72

實驗1：IQEA中僅使用表3-1中的旋轉(zhuǎn)門策略作為量子更新算子時，算法隨網(wǎng)絡(luò)節(jié)點增長性能的比較和算法隨目的節(jié)點的增長性能的比較，由于不加入改進(jìn)量子旋轉(zhuǎn)門策略時IQEA收斂慢，先將IQEA的最大進(jìn)化代數(shù)設(shè)為500，OGA進(jìn)化代數(shù)設(shè)為200。下表4-8中給出了網(wǎng)絡(luò)規(guī)模從20變化到和100時，目的節(jié)點在網(wǎng)絡(luò)中所占比例為5%，量子進(jìn)化組播路由算法（IQEA）和正交遺傳組播路由算法（OGA）所得到的組播代價和算法運行時間的結(jié)果。表4-8當(dāng)目的節(jié)點在網(wǎng)絡(luò)中占比例為5%時，組播代價和運行時間結(jié)果表4.2.4仿真實驗及其結(jié)果分析IQEA組播代價OGA組播代價IQEA運行時間（秒）OGA運行時間（秒）2014.04.06.7280.76402277.8317.015.7333.31603269.4269.625.3689.37804452.1469.543.7926.501005609.2723.858.4994.8673表4-9當(dāng)目的節(jié)點在網(wǎng)絡(luò)中占比例為15%時，組播代價和運行時間結(jié)果表表4-9中給出了網(wǎng)絡(luò)規(guī)模從20變化到和100時，目的節(jié)點在網(wǎng)絡(luò)中所占比例為15%，量子進(jìn)化組播路由算法（IQEA）和正交遺傳組播路由算法（OGA）所得到的組播代價和算法運行時間的結(jié)果。表4-10給出了網(wǎng)絡(luò)規(guī)模從20變化到和400時，目的節(jié)點在網(wǎng)絡(luò)中所占比例為30%時，量子進(jìn)化組播路由算法（IQEA）和正交遺傳組播路由算法（OGA）所得到的組播代價和算法運行時間的結(jié)果。4.2.4仿真實驗及其結(jié)果分析mIQEA組播代價OGA組播代價IQEA運行時間（秒）OGA運行時間（秒）203174.131787.5484.22406498.3543.319.1407.87609911.895231.8878.1280121032.3110954.0994.86100151059.61211.7135.91310.2574表4-10當(dāng)目的節(jié)點在網(wǎng)絡(luò)中占比例為30%時，組播代價和運行時間結(jié)果表根據(jù)三個表中的結(jié)果，在各表內(nèi)進(jìn)行比較，在不同的參數(shù)下，IQEA都是優(yōu)于OGA的，并且隨著網(wǎng)絡(luò)規(guī)模的增大，該結(jié)論仍然是成立的。各表之間進(jìn)行比較可以看出，當(dāng)網(wǎng)絡(luò)規(guī)模相同，增大目的節(jié)點的比例時，IQEA的性能仍然優(yōu)于OGA。需要特別說明的是在算法運行時間上，隨著網(wǎng)絡(luò)規(guī)模的增大，OGA的耗時劇烈增長，對實時通信中，4.2.4仿真實驗及其結(jié)果分析IQEA組播代價OGA組播代價IQEA運行時間（秒）OGA運行時間（秒）206304.7345.57.54165.3140121017.4106620.7449.6560181597.21676.543.1903.4380241613.51648.572.01192.24100301686.11689.3257.71333.42006040164030559.53928.03300906073.46159.8707.95265.744001208829.290631005.86873.6475這種耗時是無法被接受的，雖然IQEA的耗時也在增長，但仍然大大低于OGA的耗時，這說明從運行時間方面來講，IQEA更容易滿足時效性高的條件，也更適合解決大規(guī)模網(wǎng)絡(luò)。IQEA的組播代價也都略優(yōu)于OGA，雖然差距并不是很大，但是仍然能夠說明IQEA具有更優(yōu)的性能。

實驗2：使用改進(jìn)量子旋轉(zhuǎn)門策略在進(jìn)化的中后期作為IQEA的量子更新算子，算法隨網(wǎng)絡(luò)節(jié)點增長性能的比較和算法隨目的節(jié)點的增長性能的比較。為了和實驗1中的算法進(jìn)行區(qū)分，將使用了改進(jìn)量子旋轉(zhuǎn)門策略后的算法記作IGQEA。IGQEA與OGA的最大進(jìn)化代數(shù)均設(shè)為200，且IGQEA中進(jìn)化到最大進(jìn)化代數(shù)的一半時，改用改進(jìn)的量子旋轉(zhuǎn)門策略進(jìn)行種群更新。其他實驗設(shè)置與實驗1中都相同，比較算法也是OGA，4.2.4仿真實驗及其結(jié)果分析76綜合實驗1的結(jié)果，在下表4-11中給出了網(wǎng)絡(luò)規(guī)模從20變化到和400時，目的節(jié)點在網(wǎng)絡(luò)中所占比例分別取5%、15%和30%時IGQEA、IQEA和OGA所得到的組播代價和算法運行時間的結(jié)果。其中運行時間的單位仍為秒。從表4-11中顯示的結(jié)果可以看出，改進(jìn)后的量子進(jìn)化組播路由算法在保證能獲得更小的代價的前題下，進(jìn)一步減少了算法運行的時間，也就是說IGQEA更容易滿足時效性高的條件,能夠更快速的得到更