基于量子遗传算法的无线传感器网络QoS路由选择算法研究 第9页
图3.5 判断获得的新路径中是否含有环路
3.2.6 变异
交叉操作之后是子代的变异操作，变异操作是一种基本操作，它在染色体上自发地产生随机的变化。在遗传算法中，变异操作可以提供初始种群中不含有的基因，或找回选择过程中丢失的基因，为种群提供新的内容。变异操作以一个很小的随机概率改变染色体上某些基因，找回较好的基因，与种群的大小无关。变异操作本身是一种局部随机搜索，与选择操作结合在一起，保证了遗传算法的有效性，使遗传算法具有局部的随机搜索能力；同时使得遗传算法保持种群的多样性，以防止出现非成熟收敛。图4所示为变异操作的处理过程，从染色体中随机选择一个基因（节点N2） 为变异点，从源节点到变异点的基因（节点）保持不变，变异点之后的基因（节点）从连接的基因（节点）随机选择，直到目的节点。
图3.6 变异操作的处理过程
 Ahn提出的基于量子遗传算法的最短路径求解问题相对比传统的路由最短路径算法（Dijkstra）的优势在于其计算时间要短。图3.7[23]比较了两种算法的计算时间。
图3.7 GA与Dijkstra计算时间比较
3.3 基于量子遗传算法的最短路径问题方案
量子遗传算法（Quantum Genetic Algorithm，QGA）是量子计算与遗传算法相结合而发展起来的一种新的遗传算法。它建立在量子的态矢量表述基础上，将量子比特的几率幅表示应用于染色体的编码，使得一条染色体可以表达多个态的叠加，并利用量子旋转门和量子非门实现染色体的更新操作，从而实现了目标的优化求解。它与经典遗传算法相比，区别在于采用量子比特编码方法、量子坍塌过程取代经典遗传算法的交叉操作、量子变异。由上一章的仿真结果可知，量子遗传算法比经典遗传算法具有更好的收敛效果，且最终收敛值较接近目标值。
在量子遗传算法实现最短路径路由选择问题时，关键问题在采用何种量子比特编码。因为其他过程与上一章提到的量子遗传算法的一般过程相同，故本章只介绍量子比特编码的具体过程。
3.3.1 量子比特编码 
在QGA中，采用一种新颖的基于量子比特（qubit）的编码方式，即用qubit来存储和表达一个基因，该基因可以为“0”态或“1”态，或它们的任意叠加态，即该基因所表达的不再是某一确定的信息，而是包含所有可能的信息，对该基因的任一操作也会同时作用于所有可能的信息。一个由 个qubit构成的量子染色体可以描述为
其中 ， 代表第 个基因处于“0”态的概率，而 代表第 个基因处于“1”态的概率。该染色体可以同时表达 个态的信息。
定义3.1（邻接矩阵（adjacent matrix））对于一个无向图 节点集V的节点，构造邻接矩阵A。
定义3.2（邻接点集(adjacent node set)）对于一个无向图 节点集V的节点，可获得网络结构的总节点数N及所有节点中的最大邻接点数L。构造邻接矩阵
HN×L，矩阵行表示节点ID号，矩阵列表示与节点i（∈V）构成链路的所有节点，并按节点ID号大小排序。Hij表示第 个节点的第 个相邻节点；若与 相邻的节点数小于 ，则Hij = 0。
 图3.8为一个7个节点和9条边的简单无向图，所有节点中的最大邻接点数L = 4，故邻接点集H为7×4矩阵。以节点4为例，其邻接点集为{2，3，5，6}，故H41=2，H42=3，H43=5，H44=6。
图3.8  7个节点和9条边的简单无向图
用量子遗传算法求解网络路由的最短路径路由时，量子染色体的量子比特数由网络路由的节点数N和所有节点中最大邻接点数L共同确定，一个节点的量子比特数为K，且K满足 。因此，量子染色体的量子比特M = N×K。
如图1所示网络无向图，一个节点的量子比特数为K = 2，编码时量子染色体的量子比特为M = 14。
 译码过程将量子染色体进行量子坍塌操作，获得二进制形式表示的染色体；将量子坍塌后的染色体分成N组，每组含K个0（或1）；将第i组K个0（或1）当作一个二进制数，转化为十进制数j；然后结合邻接点集矩阵H，表示第i节点的下一节点为Hi，j+1，同理寻找Hi，j+1的下一节点，直至找到目的节点。
假设如图3.8的简单无向图，源节点S = 1，目的节点D = 7，生成的路径path = (1,2,4,6,7)，则经过量子坍塌操作之后的染色体为
（01 01 00 11 00 01 00）                  （3-6）
式（3-6）中黑体部分为判断路径的有用信息。其他信息位可随机变化不会影响最终生成的路径。
3.3.2 基于量子遗传算法的最短路径算法参数设计
为了实现基于QGA的最短路径求解，我们对QGA算法的主要参数进行如下设计：
（1）问题描述。量子染色体的表示和测量过程都和前面QGA的描述相同。
（2）种群初始化：量子染色体中量子比特基因数由计算机网络的节点数N和任意节点的邻接点数K共同确定。初始种群中的量子染色体的Qubit基因均初始化为 ，这意味着一个染色体所表达的是其全部可能状态的等概率叠

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