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

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

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