[發(fā)明專利]一種用于量子遺傳算法的多因子決策量子變異方法

無效

• 申請?zhí)枺?/td>: 200910092226.8
• 申請日: 2009-09-07
• 公開（公告）號: CN101739602A
• 公開（公告）日: 2010-06-16
• 發(fā)明（設(shè)計）人: 柏琳;付佳
• 申請（專利權(quán)）人: 北京郵電大學(xué)
• 主分類號: G06N3/12
• 分類號: G06N3/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域

本發(fā)明涉及一種用于量子遺傳算法的量子位變異方法，屬于進(jìn)化計算技術(shù)領(lǐng)域。

背景技術(shù)

量子遺傳算法是一種將量子計算理論與進(jìn)化算法相結(jié)合的依概率搜索優(yōu)化方法。它利用量子位編碼表示染色體，用量子門更新來完成進(jìn)化搜索。它的最大優(yōu)點是只需要小規(guī)模的種群即可實現(xiàn)高效搜索，收斂速率快。由于其思想簡單，易于實現(xiàn)且表現(xiàn)出的優(yōu)秀計算性能，量子遺傳算法在各個學(xué)科和領(lǐng)域贏得了廣泛的關(guān)注，尤其是在組合優(yōu)化問題求解、自適應(yīng)控制、智能控制、模式識別、人工搜索和機(jī)器學(xué)習(xí)等領(lǐng)域。

在量子遺傳算法中，染色體處于疊加態(tài)或糾纏態(tài)，種群進(jìn)化操作通過量子旋轉(zhuǎn)門作用于量子疊加態(tài)和糾纏態(tài)，從而改變其相位，進(jìn)而改變量子位的基態(tài)。量子旋轉(zhuǎn)門一般表示為：

U(θ)=cos(θ)-sin(θ)sin(θ)cos(θ)]]>

其中θ稱為旋轉(zhuǎn)角。

量子位更新操作為：

α*β*=cos(θ)-sin(θ)sin(θ)cos(θ)αβ]]>

目前量子遺傳算法的進(jìn)化操作主要采用量子旋轉(zhuǎn)門，因此算法性能好壞主要取決于旋轉(zhuǎn)門的質(zhì)量。該算法雖然簡單易行，但是旋轉(zhuǎn)方式、旋轉(zhuǎn)角大小和方向的確定并不是一件容易的事情，往往需要很多次的試探才能找到一個比較合適的旋轉(zhuǎn)角，而且旋轉(zhuǎn)門的通用性不好，一個旋轉(zhuǎn)門往往只適應(yīng)一個或一類問題。在旋轉(zhuǎn)過程中，如果旋轉(zhuǎn)角過大，將很容易錯過優(yōu)良解空間，而旋轉(zhuǎn)角過小會導(dǎo)致收斂速率過慢，優(yōu)良染色體遲遲無法更新到最優(yōu)解。同時，旋轉(zhuǎn)門的判決機(jī)制使得個體均朝著同一個方向進(jìn)化，很容易陷入局部尋優(yōu)，當(dāng)搜索陷入局部尋優(yōu)時，該更新操作無法提供更好的尋優(yōu)策略來逃離該局部搜索空間，導(dǎo)致算法停滯；另外當(dāng)種群收斂到最優(yōu)解附近時，該更新操作無法提供自適應(yīng)的小角度精確搜索，以保持種群的穩(wěn)定性。