量子算法
学院：专业：智能科学与技术姓名：学号：
（一）引言
目前，国内外提出了大量的进化算法，如遗传算法、免疫算法、粒子群优化算法、差异进化算法、量子算法等智能计算优化算法。其中，量子遗传算法是量子计算与遗传算法相结合的产物。最近这一领域的研究主要集中在两类模型上：一类是基于量子多宇宙特征的多宇宙量子衍生遗传算法(Quantum Inspired Genetic Algorithm)，另一类是基于量子比特和量子叠加特性的遗传量子算法。前者的贡献在于将量子多宇宙的概念引入遗传算法，利用多个宇宙的并行搜索，增大搜索范围，利用宇宙之间的联合交叉，实现信息的交流，从而整体上提高了算法的搜索效率。但算法中的多宇宙是通过分别产生多个种群获得的，并没有利用量子态，因而仍属于常规遗传算法。后者将量子的态矢量表达引入遗传编码，利用量子旋转门实现染色体的演化，实现了比常规遗传算法更好的效果。但该算法主要用来解决0-1背包问题。不过，编码方案和量子旋转门的演化策略不具有通用性，尤其是由于所有个体都朝一个目标演化，如果没有交叉操作，极有可能陷入局部最优。
（二）算法介绍
2.1算法原理
量子遗传算法的提出基于量子理论的基本量子位和量子叠加态的概念。量子位或量子比特是量子计算中的最小信息单位，一个量子位可以有三种状态，即|0>态、|1>态、以及|0>与|1>之间的叠加态。因此任何一个量子比特的状态可以描述为|ψ>=α|0>+ β|1>,其中α、β称为量子位对应态的概率幅，且满足归一条件|α|2+|β|2=1
量子遗传算法中采用基于量子位的编码方式。一个量子位可由其概率幅定义αα1α2?αm为[β]。同理，m个量子位可以定义为 ，其中
β1β2?βm αi 2+ βi 2=1,i=1,2,…,m。这种描述的优点在于可以表达任意量子叠加态。
由于量子系统能够描述叠加态，因此基于量子位编码的进化算法，比传统算法具有更好的种群多样性，因为其一条染色体可以利用叠加态描述多个状态。当 αi 2和 βi 2趋近于0或1时，多样性将逐渐消失，量子染色体会收敛到一个确定的状态。
2.2算法结构
量子遗传算法的伪代码如下： Procedure QGA Begin
t=0
Initialize Q(t)
Make P(t) by observing Q(t) states Evaluate P(t)
Store the best solution among P(t) While(not termination-condition) do Begin
t=t+1
make p(t) by observing Q(t) states evaluate P(t)
update Q(t) using quantum gate U(t)
store the best solution among P(t)
End End
与遗传算法相似，QGA也是一种概率搜索算法，拥有一个量子种群Q（t）={ qt1， qt1，…qtn},其中n表示种群规模，t表示遗传代数，qtj表示一条量子染
ttα1
色体，其定义为qj= t
β1
αt2βt2
?
?
αtm
t ，其中m是量子位数，即量子染色体的长βm
度，j=1,2，…，n。
具体步骤如下：
首先，将种群初始化（initialize Q(t)）,即将全部n条染色体的2mn个概率幅都初始化为2，它表示在t=0代，每条染色体以相同的概率处于所有可能
t t t 状态的叠加态。其次，通过观察Q（t）的状态来生成二进制解集p（t）= x1x2? xn,
1每个解xjt为一个长度为m的二进制串。然后，计算P（t）中每个解的适应度，存储最优解。
在循环中，首先通过观察种群Q（t-1）的状态，获得二进制解集P（t），计算每个解的适应度。之后，为了获得更加优良的染色体，通过将二进制解集P（t）与当前存储的最优解比较，用适当的量子门U（t）更新种群Q（t）。量子门可根据实际问题具体设计，通常采用的量子门定义为U（θ）=
cosθ?sinθ
，
sinθcosθ
其中θ是旋转角度。最后选择P（t）中的当前最优解，若该最优解优于目前存储的最优解，则用该最优解将其替换。
相关推荐：
loading