量子遺傳算法及其改進(jìn)與應(yīng)用

于合謠+劉蕊蕊+冀鵬飛

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

【關(guān)鍵詞】遺傳算法 量子遺傳算法 量子門 人臉識(shí)別

一、引言

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

二、量子遺傳算法QGA

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

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

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

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

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

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

三、量子遺傳算法QGA的改進(jìn)

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

基于通用量子門的量子遺傳算法整體結(jié)構(gòu)描述如下：

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

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

第三，Hadamard門變換。Hadamard門變換是量子計(jì)算邏輯運(yùn)算的基礎(chǔ)，對(duì)qj進(jìn)行Hadamard門變換，以便于幺正變換。

第四，構(gòu)造適應(yīng)度函數(shù)。為了提高適應(yīng)度函數(shù)的靈敏度，根據(jù)規(guī)范性、合理性和計(jì)算量簡(jiǎn)單等設(shè)計(jì)原則，以函數(shù)的下界為標(biāo)準(zhǔn)，在原有適應(yīng)度函數(shù)的基礎(chǔ)上，設(shè)計(jì)了新的適應(yīng)度函數(shù)，根據(jù)下界對(duì)qj計(jì)算適應(yīng)度值，以判斷量子染色體的質(zhì)量。

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

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

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

其函數(shù)表達(dá)式為

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

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

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

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

四、量子遺傳算法QGA的應(yīng)用

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

參考文獻(xiàn)

[1]李勝，張培林，李兵，胡勝海，胡浩.基于通用量子門的量子遺傳算法以及應(yīng)用[J].計(jì)算機(jī)工程及應(yīng)用.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ìn)展[J].計(jì)算機(jī)應(yīng)用研究，2012，29（7）：2401-2405.

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