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

在審

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

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

（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’的方向進化；

（6）通過步驟（3）的適應度函數F(t)選出P(t)中適應度最高的作為第t代的最優解，將第t代最優解與第t代之前得到的最優解b比較，若第t代最優解優于第t代之前的最優解，則用第t代最優解代替B(t-1)中原有的b存入，得到B(t)；反之則繼續保留B(t-1)中原有的最優解b，得到B(t)；

（7）停機條件判斷：當B(t)中最優解b不為全局最優解時，即b為一串由m個1組成的字符串時，且迭代次數t小于給定的限值，則迭代次數t=t+1，轉入步驟（2）繼續進化；否則此時B(t)中輸出最優解b。

2.根據權利要求1所述的新型量子進化方法，其特征在于，所述步驟（3）中，根據評價函數對每一個進行評價時，將中所有的量子比特相加，其結果作為的適應度存入F(t)中。