量子遺傳演演算法

量子遺傳演演算法發展簡介：

量子遺傳演演算法是量子計算與遺傳演演算法相結合的產物。目前，這一領域的研究主要集中在兩類模型上：一類是基於量子多宇宙特徵的多宇宙量子衍生遺傳演演算法(Quantum Inspired Genetic algorithm)，另一類是基於量子比特和量子態登加特性的遺傳量子演演算法(Genetic Quantum Algorithm,GQA)。前者的貢獻在於將量子多宇宙的概念引入遺傳演演算法，利用多個宇宙的并行搜索，增大搜索範圍，利用宇宙之間的聯合交叉，實現信息的交流，從而整體上提高了演演算法的搜索效率。但演演算法中的多宇宙是通過分別產生多個種群獲得的，並沒有利用量子態，因而仍屬於常規遺傳演演算法。後者將量子的態矢量表達引入遺傳編碼，利用量子旋轉門實現染色體的演化，實現了比常規遺傳演演算法更好的效果。但該演演算法主要用來解決0-1背包問題。編碼方案和量子旋轉門的演化策略不具有通用性，尤其是由於所有個體都朝一個目標演化，如果沒有交叉操作，極有可能陷入局部最優。

文獻[1]對QGA進行了改進，提出量子遺傳演演算法(Quantum GeneticA lgorithm,QGA)。QGA採用多狀態基因量子比特編碼方式和通用的量子旋轉門操作。引入動態調整旋轉角機制和量子交叉，比文獻[2]的方法更具有通用性，且效率更高。但該方法仍是一個群體獨自演化沒有利用盈子信息的多宇宙和宇宙間的糾纏特性效率有待進一步提高。文獻[3]提出一種多宇宙并行量子遺傳演演算法(Multiuniverse Parallel Quantum Genetic Algorithm,MPQGA)，演演算法中將所有的個體按照一定的拓撲結構分成一個個獨立的子群體，稱為宇宙；採用多狀態基因量子比特編碼方式來表達宇宙中的個體；採用通用的量子旋轉門策略和動態調整旋轉角機制對個體進行演化；各宇宙獨立演化，這樣可擴大搜索空間，宇宙之間採用最佳移民、量子交叉和量子變異操作來交換信息使演演算法的適應性更強，效率更高。

參考文獻：

[1] Yang junan,ZhuangZhenquan.Research of Quantum Genetic Algorithm and Its Applicationin Blind Source Separation.

[2] Han K-H.Genetic Quantum Algorithm and its Application to Combinatorial Optimization Problem.

[3] Yang Junan.Zhuang Zhenquan.Multi-Universe Parallel Quantum Genetic Algorithm and Its Application in Blind Source Separation.