于合謠+劉蕊蕊+冀鵬飛

【摘要】文章在介紹基本量子遺傳算法（QGA）的原理、方法和基本流程的基礎上，主要歸納總結了最近幾年QGA的改進，包括理論基礎的編碼擴展、算子的創(chuàng)新和量子門旋轉角度、復雜高維函數(shù)優(yōu)化、混合算法等，以及新的應用研究成果，以及在不同領域的一些應用，進而提出了QGA未來的發(fā)展方向。

【關鍵詞】遺傳算法 量子遺傳算法 量子門 人臉識別

一、引言

量子遺傳算法（Quantum Genetic Algorithm），簡稱QGA，結合了量子計算的并行運算和遺傳算法的種群多樣性等優(yōu)勢，具有較高的全局搜索效率和種群多樣性[1]。在遺傳算法中，通過對適應度函數(shù)的研究，可以提升遺傳算法的優(yōu)化效果[1]。Narayanan等人[2]最先提出量子衍生遺傳算法（QIGA）的概念；緊接著Han等人[3]提出真正意義上的基于量子比特和量子態(tài)疊加特性的量子遺傳算法（QGA），并應用到解決背包問題，實現(xiàn)了比常規(guī)遺傳算法更好的效果。目前，量子遺傳算法的研究已經(jīng)取得了一些研究成果，文獻[4]總結了2011年以前對量子遺傳算法的研究進展情況。

二、量子遺傳算法QGA

QGA算法：基于量子位的表示方法和量子力學的態(tài)疊加原理，QGA的具體算法如下：

第一，初始化，包含n個個體的種群，其中Ptj（j=1，2，…，n）為種群中第t代的一個個體，且有，其中m為量子位數(shù)目，即量子染色體的長度。在開始時，所有αi，βi（i=1，2，…，m）都取。

第二，根據(jù)P（t）中概率幅的取值情況構造出R（t），，其中 是長度為m的二進制串。

第三，用適應值評價函數(shù)對R（t）中的每個個體進行評價，并保留次代中的最優(yōu)個體。若獲得滿意解，則算法終止，否則，轉入第四繼續(xù)進行。

第四，使用恰當?shù)牧孔娱TU（t）更新P（t）。

第五，遺傳代數(shù)t=t+1，算法轉至第二繼續(xù)進行。

三、量子遺傳算法QGA的改進

目前，對量子遺傳算法的研究主要集中在染色體編碼方式和參數(shù)更新方面，其本質仍是單純的引入量子計算的基本原理。但是，對如何能更好地實現(xiàn)量子遺傳算法，并應用于量子計算機等研究還不夠深入，從而，導致現(xiàn)有量子遺傳算法的運算效率和特征選擇效果沒有達到預期目標，因此，本文提出了一種新的特征選擇算法—基于通用量子門的量子遺傳算法（Quantum Genetic Algorithmwith Universal Quantum Gate，UQGA）。在該算法中，首先，以Hadamard門為基礎，之后，根據(jù)新的旋轉角度函數(shù)，利用通用量子門對染色體中各個基因進行遺傳操作，最后，以適應度函數(shù)值為標準，得到求解問題的全局最優(yōu)解集。

基于通用量子門的量子遺傳算法整體結構描述如下：

第一，量子態(tài)描述：其中公式為

第二，種群初始化：設量子種群Q（t）={q1，q2，…，qm}，qj為其中的一個量子染色體，含有m個量子位，則

第三，Hadamard門變換。Hadamard門變換是量子計算邏輯運算的基礎，對qj進行Hadamard門變換，以便于幺正變換。

第四，構造適應度函數(shù)。為了提高適應度函數(shù)的靈敏度，根據(jù)規(guī)范性、合理性和計算量簡單等設計原則，以函數(shù)的下界為標準，在原有適應度函數(shù)的基礎上，設計了新的適應度函數(shù)，根據(jù)下界對qj計算適應度值，以判斷量子染色體的質量。

第五，選擇操作。利用受控門Ucnot依據(jù)適應度值對qj進行選擇，以達到優(yōu)勝劣汰的目標。又由于Fit（f（x））∈[0，1]，適應度函數(shù)值越大，其特征越少，可避免算法造成欺騙，因此，根據(jù)經(jīng)驗所得，本文選擇0.9950作為節(jié)點，如下判別方式：

①若Fit（f（x））∈[0，0.9950]，則該染色體被淘汰；

②若Fit（f（x））∈[0.9950，1]，則該染色體被選擇，保留最佳個體。

其函數(shù)表達式為

其中，q”j值是根據(jù)Fit（f（x））判別并經(jīng)Ucnot后的。

第六，遺傳操作。若當代染色體被選擇，則使用量子旋轉門R對q”j進行遺傳操作，以更新染色體中的量子位，其函數(shù)表達式為

雖然遺傳操作沒有明確的交叉和變異操作，但是由于量子態(tài)的概率表示和量子旋轉門的操作，使得種群可以保持多樣性。同時，對于旋轉角度的局部最優(yōu)解，一般采用經(jīng)驗方式，來尋找適應度函數(shù)的全局最優(yōu)解。

第七，終止條件。當達到設定的最大迭代次數(shù)tmax或者Fit（f（x））的值達到最佳時，循環(huán)終止；否則，將返回步驟第三迭代計算。

四、量子遺傳算法QGA的應用

根據(jù)QGA的種群多樣性好，全局收斂性強的優(yōu)點，基于QGA的人臉圖像分割，將其應用于人臉圖像的閾值分割，從而達到提高計算速度和計算精度的目的。運用QGA時，必須進行兩個重要步驟：即把所有問題的解編碼成染色體；永和市的適應度函數(shù)返回值來評價個體的好壞。

參考文獻

[1]李勝，張培林，李兵，胡勝海，胡浩.基于通用量子門的量子遺傳算法以及應用[J].計算機工程及應用.2017，53（7）：54-59.

[2]Narayanan A，MOORE M.Quantum-inspired genetic algorithm[C].Proc of IEEE Internation on Conference on Congress on EvolutionaryComputation.1996：61-66.

[3]Han K H，Kim J H.Genetic quantum algorithm and its application to combinatorial optimization problem[C].Proc of IEEE Congress on Evolutionary Computation，2000：1354-1360.

[4]梁昌勇，柏樺，蔡美菊等.量子遺傳算法研究進展[J].計算機應用研究，2012，29（7）：2401-2405.

作者簡介：于合謠（1993-），女，漢族，山東日照人，就讀于山東科技大學，研究方向：控制理論。