量子遺傳算法的改進(jìn)研究及在路由選擇問題中的應(yīng)用.pdf

1、量子遺傳算法是將量子計算與遺傳算法相結(jié)合而形成的一種混合遺傳算法，它彌補(bǔ)了傳統(tǒng)遺傳算法的某些不足；利用量子計算的一些概念和理論，如量子位、量子疊加態(tài)等，使用量子比特編碼染色體，這種概率幅表示可以使一個量子染色體同時表達(dá)多個狀態(tài)的信息，用量子門對疊加態(tài)的作用作為進(jìn)化操作，能很好地保持種群多樣性和避免選擇壓力問題，而且當(dāng)前最優(yōu)個體的信息能夠很容易用來引導(dǎo)變異，使得種群以大概率向著優(yōu)良模式進(jìn)化，從而實(shí)現(xiàn)目標(biāo)的優(yōu)化求解。 在量子遺傳算法

2、被提出以后，由于量子算法的內(nèi)在并行性，在許多領(lǐng)域的應(yīng)用都獲得了成功；人們也相繼提出了許多改進(jìn)算法。本文在已有研究的基礎(chǔ)上，主要做了以下研究工作： 1.進(jìn)一步改進(jìn)了量子遺傳算法的收斂性能，提出了一種改進(jìn)的混合量子遺傳算法(An Improved Hybrid Quantum Genetic Algorithm，IHQGA)，該算法在量子個體上實(shí)施量子交叉，這一操作有利于保留相對較好的基因段；采用量子比特相位法更新量子門和自適應(yīng)調(diào)整

3、搜索網(wǎng)格的策略；引入擬Newton算法進(jìn)行局部搜索操作，使得種群的多樣性強(qiáng)，解的收斂精度高，收斂速度快；通過復(fù)雜函數(shù)測試標(biāo)明此算法的優(yōu)化質(zhì)量和效率都強(qiáng)于傳統(tǒng)遺傳算法和量子遺傳算法。 2.將量子遺傳算法用在組合優(yōu)化問題中，提出了一種基于改進(jìn)量子遺傳算法的QoS組播路由算法，該算法通過量子非門進(jìn)行量子變異操作阻止未成熟收斂和提高算法的全局搜索能力；采用量子比特相位法更新量子門策略保持種群的多樣性；使用最小代價組播樹算法(簡稱KMB算

4、法，由Kou Markowsky和Berman提出的)進(jìn)行受約束最小Steiner樹的生成，通過仿真實(shí)驗標(biāo)明，此算法在種群規(guī)模較小、迭代次數(shù)較少的情況下就可以收斂到最優(yōu)解，該算法的優(yōu)化質(zhì)量和效率都強(qiáng)于傳統(tǒng)遺傳算法和量子遺傳算法。 量子遺傳算法將量子機(jī)制引入到常規(guī)遺傳算法中，具有收斂速度快和全局尋優(yōu)能力強(qiáng)的特點(diǎn)，這將使得它有望獲得更廣泛的關(guān)注和應(yīng)用。本文對量子遺傳算法改進(jìn)與應(yīng)用研究，進(jìn)一步提高了算法的性能，拓展了算法的應(yīng)用領(lǐng)域，對