網(wǎng)絡(luò)中Steiner樹問題的量子與智能優(yōu)化算法研究.pdf

1、近年來隨著網(wǎng)絡(luò)和多媒體技術(shù)的飛速發(fā)展，網(wǎng)絡(luò)多媒體服務(wù)（如視頻會議、視頻點播，數(shù)據(jù)分發(fā)和網(wǎng)絡(luò)游戲等）應(yīng)用成為網(wǎng)絡(luò)應(yīng)用的大勢所趨，如果應(yīng)用傳統(tǒng)通信方式，它們大都需要消耗很多的網(wǎng)絡(luò)帶寬資源。為了節(jié)約帶寬，提高網(wǎng)絡(luò)中各種資源的利用率，當(dāng)前比較現(xiàn)實的也是比較有效的方法就是使用組播技術(shù)。構(gòu)建費用較小、性能較好的組播分發(fā)樹成為制約組播應(yīng)用的一個瓶頸。在這類問題中，以求解最小Steiner樹最為典型。一般的求解Steiner樹算法，首先要計算源端點到每

2、個目的端點的路徑費用等數(shù)據(jù)，然后依據(jù)這些費用信息，進(jìn)行路徑的合并來得到可行解。這些方法簡單可行，但是重復(fù)計算較多，從而導(dǎo)致算法平均搜索時間較大，算法整體上效率不高。另外一類算法就是智能優(yōu)化算法，如蟻群優(yōu)化、粒子群優(yōu)化算法等，它們都具有分布式并行性、較好的尋優(yōu)能力等特點，被越來越多地應(yīng)用到求解Steiner樹問題，取得了較好的結(jié)果。但是，此類算法仍然存在諸如收斂速度慢、計算復(fù)雜、早熟收斂等不足之處。
　　 以量子力學(xué)為基礎(chǔ)的量子算

3、法在近年來快速崛起，具有高度并行性、存儲容量超大、可以加速其他算法的優(yōu)點。將量子的思想應(yīng)用到求解Steiner樹問題中，既可以提高原算法的性能，又拓寬了量子算法的應(yīng)用范圍。借鑒“組合優(yōu)化”的思想，為了充分發(fā)揮智能優(yōu)化算法與量子算法各自的優(yōu)點，克服原有算法早熟收斂等不足之處，提高全局尋優(yōu)能力，加快收斂速度，本文將量子算法與智能優(yōu)化算法結(jié)合起來，提出了新的求解網(wǎng)絡(luò)中Steiner樹問題的方法。
　　 本文所做的主要工作是研究量子及其

4、智能優(yōu)化算法在求解網(wǎng)絡(luò)中Steiner樹的應(yīng)用，具體內(nèi)容如下:
　　 (1)在基本量子算法的基礎(chǔ)上，提出了一種新的基于量子的算法來求解網(wǎng)絡(luò)中Steiner樹問題。該算法以量子比的概率幅表示其代表的圖中的邊被選入Steiner樹的概率，之后通過觀測量子比特來得到解。針對原有算法中要計算源端點到每個目的端點的路徑來形成樹，重復(fù)計算較多，效率不高的缺點，本算法采用直接合并代表可行解的樹的方式對結(jié)果從整體上進(jìn)行優(yōu)化，同時用自適應(yīng)的量子旋

5、轉(zhuǎn)門策略更新量子比特的相位，優(yōu)化量子個體，以進(jìn)化該種群。該本文算法在一般情況下能夠增強全局尋優(yōu)能力，并較快地加速了算法的收斂。通過仿真實驗結(jié)果表明，大多數(shù)情況下，本文算法與傳統(tǒng)算法相比，在得到更優(yōu)解的同時，大大縮短了收斂時間，提高了算法的效率，尤其是當(dāng)網(wǎng)絡(luò)的拓?fù)湟?guī)模增大時，該算法收斂速度快的優(yōu)越性會變得更加明顯。
　　 (2)為了使智能優(yōu)化算法與量子算法發(fā)揮各自的優(yōu)點，依照“組合優(yōu)化”的思想，在蟻群優(yōu)化算法和粒子群優(yōu)化算法的基礎(chǔ)

6、上，結(jié)合量子算法，分別提出了量子蟻群算法和量子粒子群算法來求解Steiner樹問題。其中，在量子蟻群算法中，螞蟻看作是量子比特，并用量子比特的概率幅表示螞蟻當(dāng)前位置，用量子旋轉(zhuǎn)門實現(xiàn)量子的進(jìn)化，通過量子非門實現(xiàn)種群的變異;在量子粒子群算法中，將量子進(jìn)化的思想引入粒子群算法，采用量子比特對粒子的當(dāng)前位置進(jìn)行編碼，用量子選擇門搜索粒子最優(yōu)位置，用量子非門實現(xiàn)粒子位置的變異以避免早熟收斂。仿真實驗結(jié)果表明，與原有的蟻群算法和粒子群算法相比，新