基于量子遗传算法的无线传感器网络QoS路由选择算法研究 第5页
式（2-5）表示状态|000>，|001>，|010>，|011>，|100>，|101>，|110>，|111>出现的概率分别是3/32，9/32，1/32，3/32，3/32，9/32，1/32，3/32，随着 趋于1或0，这时种群多样性消失，算法收敛。
2.3.2 量子旋转门
QGA中的染色体处于叠加或纠缠状态，因而QGA的遗传操作不能采用传统GA的选择、交叉和变异等操作方式，而采用将量子门分别作用于各叠加态或纠缠态；子代个体的产生不是由父代群体决定，而是由父代的最优个体及其状态的概率幅度决定。量子遗传操作主要是将构造的量子门作用于量子叠加态或纠缠态的基态，使其相互干涉，相位发生改变，从而改变各基态的概率幅。因此，量子门的构造既是量子遗传操作要解决的主要问题，也是QGA算法的关键问题，它直接关系QGA的性能好坏。
在QGA中，使用量子门变换，由于概率归一化的条件，变换矩阵必须是幺正矩阵，常用的量子逻辑门有：非门、异或门、受控的异或门和旋转门[19]等。由于量子旋转门的参数可调整性，其通用性更强，因此主要采用量子旋转门，并且在进行遗传操作的时候针对不同规模和特点的问题通过调整旋转门的操作有可能提高算法的收敛速度和改善算法的计算性能。
旋转角为 的量子旋转门 可以表示为：  （2-6）
显然 是个酉正矩阵。量子旋转门的调整操作如式2-7所示： （2-7）
旋转角度 可由表2.1得到， 用来控制旋转角的方向， 用来控制旋转角的大小。δ为旋转角度调整的步长，δ太小将影响算法收敛的速度，太大可能会使结果发散，或早熟收敛到局部最优解。
表2.1中xi为当前染色体的第i位，bi为当前最优染色体的第i位，f(x)和f(b)分别为当前染色体和当前最优染色体的适应度函数。 为旋转角度的大小，当 时， ；当 时， 。δ为旋转角度调整的步长，δ太小将影响算法收敛的速度，太大可能会使结果发散，或早熟收敛到局部最优解。 为旋转角度的方向，保证算法的收敛。
表2.1  旋转角选择策略
xi bi f(x)>f(b)

0 0 False 0 – – – –
0 0 True 0 – – – –
0 1 False δ
0 

0 1 True δ
0
1 0 False δ
0
1 0 True δ
0 

1 1 False 0 – – – –
1 1 True 0 – – – –

该调整策略是将当前染色体的适应度f(x)与当前最优染色体的适应度f(b)进行比较，如果f(x) > f(b)，则调整当前染色体中相应位qubit基因，使得几率幅对 向着有利于xi出现的方向演化；反之，如果f(x) < f(b)，则调整当前染色体中相应位qubit基因，使得几率幅对 向着有利于bi出现的方向演化。
                   
图 2.2  量子旋转门示意图
我们用图2.2说明为什么采用量子旋转门变异策略能够保证算法很快收敛到具有更高适应度的染色体。如当xi = 0，bi = 1，f(x) > f(b)时，为使当前解收敛到一个具有更高适应度的染色体，应增大当前解取 态的概率，即要使 变大，那么如果 在第一、三象限，即 ，则 应为顺时针方向旋转角，因而 取 ；如果 在第二、四象限，即 ，则 应为逆时针方向旋转角，因而 取 。
2.3.3 量子变异操作
变异[20]的作用主要在于阻止未成熟收敛和提高算法局部搜索能力。在QGA中，我们通过量子非门设计了一种量子变异操作。具体方法如下：
(1) 以确定的概率Pm从种群中选取若干个个体；
(2) 对选中的个体按确定的概率确定一个或多个变异位；
(3) 对选中位量子比特的几率幅执行量子非门操作，即完成该量子比特的变异操作。
量子变异操作实际上是更改了该量子比特态叠加的状态，使得原来倾向于坍缩到状态“1”的变为倾向于坍缩到状态“0”，或者相反。
2.3.4 算法描述
QGA是一种和GA类似的概率算法，种群由量子染色体构成，在第t代的种群为 ，其中n为种群大小；k为量子染色体的长度； 定义为如下的染色体：    （2-8）
下面给出QGA的一般步骤：
（1） 初始化种群Q(t)；
（2） 由Q(t)量子坍塌生成P(t)；
（3） 对群体P(t)进行适应度评估，取其中最佳适应度个体作为该个体下一步演化的目标值；
（4） 停止条件判断：当满足时，输出当前最佳个体，算法结束，否则继续；
（5） 利用量子旋转门对种群Q(t)进行更新；
（6） 进行量子变异操作，t = t + 1，转到（2）。
由此可见，QGA与GA的不同仅仅在于（3）、（5）和（6）步。在（1）中，初始种群中的全部染色体的所有基因 初始化为 ，表示所有可能的叠加态均以相同的概率出现；在（2）中通过量子坍塌生成 ，其中 为第t代种群中的第j个解，也就是第j个个体的测量值，表现形式为长度为k的二进制串，其中每一位为0或1是根据量子比特的概率选择确定的。具体过程是：随机产生一个属于[0，1]的数，若它大于 ， 取值1，否则取值0；在（5）中，由于量子旋转门是酉正矩阵，可以用做更新操作的量子门；在（6）中，量子变异的作用主要在于阻止未成熟收敛和提供算法局部搜索能力。具体方法为：首先以一定的概率 从种群中随机选取若干个个体，然后对选中的个体按确定的概率随机确定一个变异位，最后将该位量子比特的几率幅值位置对调；将量子比特的几率幅值对的位置进行对调，实际上就是更改了该量子比特态叠加的状态，使得原来倾向于坍塌到状态 的变为倾向于坍塌到状态 ，或者相

上一页  [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]  ... 下一页  >>