[發明專利]一種新型量子進化方法

在審

• 申請號: 201410831269.4
• 申請日: 2014-12-29
• 公開（公告）號: CN104573348A
• 公開（公告）日: 2015-04-29
• 發明（設計）人: 項勝;何怡剛;佐磊;尹柏強
• 申請（專利權）人: 合肥工業大學
• 主分類號: G06F19/00
• 分類號: G06F19/00
• 代理公司: 長沙星耀專利事務所 43205
• 代理人: 黃美玲;寧星耀

技術領域

本發明涉及優化方法領域，更具體的說，是涉及一種引入精英群組和狀態偏好的新型量子進化方法。

背景技術

量子進化方法建立在量子的態矢量表述基礎上，用量子比特的幾率幅來表示染色體的編碼，使得一條染色體可以表達多個態的疊加，并利用量子旋轉門和量子非門實現染色體的更新操作，從而實現了目標的優化求解。但是，現有量子方法收斂方向無法有效控制，可能會出現退化現象。目前，針對量子進化方法有很多改進方法，但都沒有有效地解決收斂方向的問題，因此，如何提高量子進化方法的收斂速度，控制收斂方向防止退化，提高方法穩定性，是量子方法的真正關鍵。

發明內容

本發明要解決的技術問題是，克服現有技術存在的上述缺陷，提供一種能有效控制收斂方向的新型量子進化方法，引入精英群組和狀態偏好控制收斂方向，提高方法穩定性。

本發明解決其技術問題所采用的技術方案是：

一種新型量子進化方法，其特征在于，包括步驟：

（1）根據量子進化方法，初始化代數t=0，初始化種群Q(t)=，n為種群大小，t為進化的代數，為種群第t代的第i個個體，，定義，由m個量子比特組成，ɑ代表每個量子比特狀態為0出現的概率，β代表每個量子比特狀態為1出現的概率，有，每個比特量子隨機生成，滿足公式：

=，表示組成第t代中第i個個體的第j個量子比特狀態為0的概率，表示組成第t代中第i個個體的第j個量子比特狀態為1的概率；初始化最優解集合B(t)，將一個由m個0構成的字符串b作為初始的最優解存入B(t)中；

（2）觀察Q(t），觀測第t代種群的所有個體，對個體而言，觀測其所有的m個量子比特，生成一個長度為m的字符串，i為對應的個體，t為進化代數，字符串中每一位對應個體相應的量子比特，若量子比特為0，則字符串中對應位置寫入0，若量子比特為1則字符串中對應位置寫入1，最后生成P(t)=；

（3）根據評價函數對每一個進行評價，并將評價結果存入適應度函數F(t)中，F(t)={f₁^t ,f₂^t ,…,f_n^t }，表示第t代種群中第i個個體的適應度，n為第t代種群的大小；

（4）從P(t)中選取精英群組E(t)，具體如下：

(4.1)將第t代種群中的所有個體與通過步驟（3）適應度函數評價出來的該代種群中的最差個體進行比較，構建；

(4.2)進入精英群組的概率由概率函數表示，，構建S(t)=；

(4.3)基于S(t)采用輪盤賭法決定P(t)中的個體是否被選入精英群組E(t)中，E(t)=，p為精英群組中的個體總數；

（5）通過進化第t代種群Q(t)，得到第t+1代種群Q(t+1)， ，表示當前的量子比特位于哪一個象限，，是精英群組E(t)對相角旋轉的加權，所以精英群組會對整個群體進化起到積極引導作用；的值根據以下方法選取：1）若第t代種群中的個體入選了精英群組時，則=0；2）若第t代種群中的個體未入選精英群組且=時，則=0；3）若第t代種群中的個體未入選精英群組且狀態為0，狀態為‘1’時，則=，為朝著狀態為‘1’進化的旋轉值，增大從狀態為‘0’進化到狀態為‘1’的概率；4）若第t代種群中的個體未入選精英群組且狀態為‘1’，狀態為‘0’時，則=，為朝著‘0’進化的旋轉值，增大從狀態為‘1’進化到狀態為‘0’的概率；其中，是由步驟（2）確定的第t代種群中個體的量子比特值，是由步驟（4）確定的精英群組E(t)中所有個體，，和表示第t代和的第j個量子比特值；如下表所示

為實現進化方向的控制，即均朝向狀態為1進化，引入狀態偏好進一步加權，具體方法如下：當第t代種群中的個體未入選精英群組且狀態為0，狀態為1時，通過增大的值增大從狀態為‘0’進化到狀態‘1’的概率；當第t代種群中的個體未入選精英群組且狀態為‘1’，狀態為‘0’時，通過減小的值降低從狀態為‘1’進化到狀態‘0’的概率；使得整體的朝著狀態‘1’的方向進化；