基于量子進(jìn)化計算的組合優(yōu)化問題求解.pdf

1、量子計算的研究開始于1982年，現(xiàn)在它已經(jīng)成為當(dāng)今世界各國緊密跟蹤的前沿學(xué)科之一。量子計算的并行性、指數(shù)級存儲容量和指數(shù)加速特征展示了其強(qiáng)大的運算能力。本文將組播路由問題看作為一個組合優(yōu)化問題，探討了一種求解組合優(yōu)化問題的量子進(jìn)化計算方法，并用于解決背包問題和時延受限的組播路由問題。本文主要內(nèi)容概括如下：
　　 ⑴首先我們介紹了量子進(jìn)化算法，并將此算法應(yīng)用于經(jīng)典的組合優(yōu)化問題，提出了量子進(jìn)化多維0/1背包算法。利用量子進(jìn)化算法中

2、的狀態(tài)矩陣表示背包問題的解在某一狀態(tài)的概率大小，并對其同一狀態(tài)進(jìn)行多次坍塌以獲得這一狀態(tài)最優(yōu)的解，再加入貪婪策略對得到的解進(jìn)行修正，從而加速了算法的收斂速度。大量仿真表明，該算法具有解決類似復(fù)雜問題的潛力。
　　 ⑵基于量子計算的機(jī)理和特性并結(jié)合進(jìn)化計算，將組播路由問題看作為一個組合優(yōu)化問題，提出了一種新穎的量子進(jìn)化組播路由算法。通過對備選路徑采用量子編碼，從而解決了組播樹中如何選擇路徑問題，并且在每代個體更新中采用量子旋轉(zhuǎn)門策