看官大人,文章很长哦,来点音乐?


首先假设大家在阅读本文之前已经对经典的遗传算法框架有所了解,然后进入今天的主题《量子遗传算法》,较经典的遗传算法来说,有以下几点不同:

 1.不再采用单调的二进制位来对解空间中的可行解进行编码,取而代之的是采用量子位进行编码。
 2.不再单纯的仅仅进行交叉,变异操作,而是加入了通过量子旋转门对染色体进行更新操作。
 3.每一个量子位均是一个不确定的状态,属于0和1的叠加态,也因此解码操作会有所不同。

下面具体介绍各个关键步骤。

量子位编码

在量子遗传算法中,染色体上的基因不是确定值,而是采用概率幅的方式表示,也因此每个量子位可能代表1,也可能代表0,也可能代表0和1的叠加态,所以量子位的编码方式使同等长度的编码较经典遗传算法能表示更多的信息,也因此可以在较小的种群规模下工作的很好。
一个量子位表示为

\left[\begin{array}{c} \alpha_i\\  \beta_i \end{array}\right]

其中α,β均是复数,分别表示状态0|>和1|>的概率幅,且满足:

\alpha_i^2+\beta_i^2=1

此时一个量子态就可以表示为:

\Psi_i=\alpha_i|0+\beta_i|1

n个量子位的染色体形式如下:

\left[
\begin{matrix}
\alpha_1&\alpha_2&\alpha_3&\cdots&\alpha_n\\
\beta_1&\beta_2&\beta_3&\cdots&\beta_n
\end{matrix}
\right]

其可同时表示2^n个状态。且满足:

\Psi_i=\sum_{k=1}^{2^n}C_k|S_k

其中Ck为状态Sk的概率幅,且满足归一化条件:

|C_1|^2+|C_2|^2+\cdots=1

例如有一个由3个量子位编码的染色体:

\left[
\begin{matrix}
\frac{1}{2}&1&\frac{\sqrt{2}}{2}\\
\\
\frac{\sqrt{3}}{2}&0&-\frac{\sqrt{2}}{2}
\end{matrix}
\right]

其可以转换为如下形式:

\begin{matrix}
\frac{\sqrt{2}}{4}|000&
-\frac{\sqrt{2}}{4}|001&
0|010&
0|011&
\frac{\sqrt{6}}{4}|100&
-\frac{\sqrt{6}}{4}|101&
0|110&
0|111
\end{matrix}

从而得到这八种状态的概率分别为:

\begin{matrix}
000&
001&
010&
011&
100&
101&
110&
111\\
\frac{1}{8}&
\frac{1}{8}&
0&
0&
\frac{3}{8}&
\frac{3}{8}&
0&
0
\end{matrix}

从这里可以看出,一个染色体本身同时代表着多种状态的叠加态,这也解释了为什么量子遗传算法需要的种群数量较小。另外也可以看出随着概率幅的范数平方趋向0或者1,染色体会趋于单一的状态,这也保证了量子遗传算法具有较好的收敛性。

量子旋转门

在量子遗传算法中,由于量子编码作用下的染色体不再是单一的纯态,遗传操作不能继续仅仅采用传统的选择,交叉,变异这些操作,而采用量子旋转门作用于量子染色体的基态,使其相互干涉,相位发生变化,从而改变概率幅的分布,也因此,量子旋转门的设计是整个算法框架里的重中之重。其形式如下:

U_i=\left[\begin{matrix}
\cos\theta_i&-\sin\theta_i\\
\sin\theta_i&\cos\theta_i
\end{matrix}\right]

量子位的更新,通过量子旋转门实现,过程如下:

\left[\begin{array}{c} \alpha_i^{'}\\ \beta_i^{'} \end{array}\right]=U_i\left[\begin{array}{c} \alpha_i\\ \beta_i \end{array}\right]

其中[αi,βi]'是第i个量子位,θi为旋转角。θi的大小与符号在量子位的更新过程中有着举足轻重的地位,具体阐述如下:

xzm.png
xzm.png

如图可以看出θi太小,将导致收敛太慢,而太大则会导致早熟,而θi的正负情况将决定量子门的旋转方向,如θi为正,当量子比特位于第一三象限时,将提高其为1的概率,类似的如果量子比特位于第二四象限,将提高其为0的概率。

量子交叉和量子变异

量子交叉操作

交叉操作在传统遗传算法最优解的搜索更新过程中有着核心作用,同样的在量子遗传算法中具有重要地位,交叉操作用于产生新个体,在解空间中进行有效搜索,同时降低了对有效模式的破坏概率,与传统遗传算法不同的是,量子交叉操作是作用于量子位的,量子交叉操作通常有以下几种:

  1.单点交叉
  2.多点交叉
  3.均匀交叉
  4.算术交叉

下面只介绍一种多点交叉,所谓多点交叉是指:

  相互配对的两个染色体,在编码串中随机选取两个交叉点,然后两者互换交叉点之间的部分,从而产生两个新个体。

量子变异操作

当交叉操作的后代的适应值不再变化且没有达到最优时,这就意味着算法早熟收敛,其本质上是因为有效基因的缺损,而变异操作增加了物种的多样性,一定程度上客服了这种问题,可以这么说在量子遗传算法中,量子旋转门一定程度上避免了算法的早熟收敛,而变异操作则防止了算法的早熟收敛。具体来说,量子变异操作同样是基于量子位的,一般可采用均匀变异和高斯变异,和传统的变异操作并无太大不同,不再赘述。

灾变操作

量子遗传算法中的灾变操作常用于避免算法陷入局部最优值(也可以在经典遗传算法中加入灾变操作达到此目的),其核心思想为:

   若算法连续若干代,均保持最优值不变,则仅保留种群中的最优个体,其余个体将被抛弃,重新生成新个体与之前的最优个体一块组成新的种群。

可以说灾变操作进一步提高了物种多样性,加快了搜索效率,避免陷入局部最优值。

量子遗传算法的具体算法流程

基于以上的部分,现给出量子遗传算法的算法流程图:

流程图

GALC.png
GALC.png

具体流程描述:

流程描述

(1)随机产生规模为n的种群

P(t)=\left[\begin{matrix}p_1^t&p_2^t&p_3^t&\cdots&p_n^t\end{matrix}\right]

其中t代表代数,并且有:

p_j^t=\left[\begin{matrix}
\alpha_1^t&\alpha_2^t&\alpha_3^t&\cdots&\alpha_m^t\\
\beta_1^t&\beta_2^t&\beta_3^t&\cdots&\beta_m^t
\end{matrix}\right]

显然m表示量子编码长度。

(2)根据P(t)的概率幅取值情况,构造出R(t),其形式如下:

R(t)=\left[\begin{matrix}a_1^t&a_2^t&a_3^t&\cdots&a_n^t\end{matrix}\right]

其中每个aj均是一个长度为m的二进制串,二进制串的构造比较简单,可以采用如下策略:
对于每个染色体的每个量子位,产生一个[0,1]的随机数γ,若对应位的αi的范数平方值大于γ,则该位取1,否则取0。

(3)评价R(t)中的各个个体的适应值(隐含着二进制解码操作),判断是否满足停止条件,若满足则终止算法流程,否则继续迭代。

(4)判断种群是否需要灾变,如果需要保优后跳转至流程(7),否则流程继续。

(5)使用量子旋转门U(t)更新P(t),对于每个量子染色体的每个量子位执行如下操作:

\left[\begin{array}{c} \alpha_i^{'}\\ \beta_i^{'} \end{array}\right]=U_i\left[\begin{array}{c} \alpha_i\\ \beta_i \end{array}\right],
U_i=\left[\begin{matrix}
\cos\theta_i&-\sin\theta_i\\
\sin\theta_i&\cos\theta_i
\end{matrix}\right]

(6)进行量子交叉和变异操作更新P(t)。

(7)令t=t+1,跳转至步骤(2)。

重点:量子旋转门的设计

量子旋转门的设计,主要在于对θi取值措施的设计,一般的我们设如下关系:

\theta_i=s(\alpha_i,\beta_i)\Delta\theta_i

其中Δθ为大小,s(α,β)表示其正负情况,很显然,正负情况与当前量子位的概率幅的取值有关,而Δθ一般取0.01π-0.05π之间的数值,设ri和bi分别表示当前个体和当前最优个体的第i个量子位的二进制取值,则此时对应的θi可通过下表计算得到:

theta.png
theta.png

结语

以上便是对量子遗传算法的详细介绍,后续会更新具体实现和应用(看心情吧。。。。)。