基于量子遗传算法的无线传感器网络QoS路由选择算法研究 第6页
反。QGA的算法流程图如图2.3所示。
在搜索过程中，QGA通过选择使具有较高适应度的个体不断增多，并且根据量子坍塌的机理，采用随机观察方法产生新的个体，不断探索未知空间，像GA 那样，使搜索过程得到最大的积累收益；其次，QGA 采用量子染色体的表示形式，使一个量子染色体上携带着多个状态的信息，能带来丰富的种群，进而保持群体的多样性，克服早熟；另外QGA 对量子染色体采用一种“智能”进化的策略来引导进化，提高收敛速度，由于QGA中量子染色体实际上是一种概率表示，GA 中的交叉和变异操作是等效的，因此在算法中主要对量子染色体采用变异操作[21]。
 图 2.3  量子遗传算法流程图
2.4 算法性能测试
为了验证算法的可行性和有效性，下面用一个典型复杂函数进行验证，如式（2-9）所示。
Min （2-9）
这是一个二维函数，它在整个解域中只有一个全局最小点f(1,1)=0。
我们主要采用遗传算法（GA）和量子遗传算法（QGA）对式（2-9）求最小
值。实验测试的结果如图2.3所示。
 图2.3  收敛曲线
从图中可以看出，经典遗传算法的收敛效果不太理想，量子遗传算法比经典遗传算法具有更好的收敛效果，且最终收敛值较接近目标值，而改进的量子遗传算法比量子遗传算法要具有更快的收敛速度，能够更快的接近目标值。
2.5 本章小结
本章从经典遗传算法出发，首先介绍了遗传算法的思想、基本结构、算法流程及其特点，然后引入了基于量子计算特性的量子遗传算法的概念。具体介绍了QGA中的量子染色体、算法流程和具体的实现操作方法；分析研究了算法中的量子旋转门调整策略及量子遗传操作，提出了一种可自适应调节的动态量子旋转门策略，并对量子遗传算法整体进行了改进，通过实验测试可知，改进的量子遗传算法比量子遗传算法要具有更快的收敛速度，能够更快的接近目标值。
第三章 基于量子遗传算法的最短路径算法研究
3.1 路由选择算法
网络层的概念建立在互联网基础上的，所谓互联网是各种通信子网通过网络层设备（如路由器）和协议互相连接，形成一个很大的逻辑网络，实现端到端的数据通信，互联网的模型如图3.1所示。
图3.1 互连网模型
在互连网模型中，端节点主要完成数据的分组和组装，中间节点则基于存储-转发技术，负责选择适当的路由来转发这些数据分组；对于面向连接的传输方式，中间节点只是在建立连接时选择一次路由，以后每个数据分组都沿着该路由进行传输；对于无连接的传输方式，中间节点要为每个数据分组选择路由，每个数据分组的传输路径可能是不同的。因此，路由选择是中间节点网络层的重要功能之一。
中间节点在选择路由是主要基于如下原理：每个中间节点都采用适当的路由选择算法支持路由选择，并维持一个路由表来记录有关路由信息，如端节点地址与线路（或端口）对应关系、路由开销等。在转发数据分组时，路由器将根据数据分组的目的地址查找路由表获取有关路由信息，并采用某种路由选择算法计算最佳路由，然后按该路由转发数据分组。
路由选择的质量关键在于路由选择算法。路由选择算法有很多种，大致可以分成静态算法和动态算法两大类[22]。
1. 静态路由选择算法
静态路由选择算法是指采用某种选择算法预先计算出每个路由器的路由表，在路由器加电启动时加载到路由器中。在路由器工作过程中，路由表内容保持不变。如果网络拓扑结构或其他网络参数发生变化，则需要重新计算出各个路由器的路由表，并重新加载到路由器中。这种路由选择算法也称固定路由选择算法。
在静态路由选择算法中，有最短径（shortest path, SP）和基于流量的路由选择（flow-based routing, FR）等。
（1）最短路径选择
在最短路径选择中，根据网络拓扑结构将一个通信网络表示成一个加权无
向图，参见图3.2（a）。
图中每个节点代表网络中的路由器，连线代表通信线路，连线上标注的数
字代表线路的权值。权值可以用线路长度、信道带宽、平均通信量、通信费用、队列长度、线路延时以及占用可用资源数量等加权函数计算出来。SP算法就是按照线路的加权值寻找出最短路径。SP算法最初由Dijkstra提出的，故也称Dijkstra算法。
SP算法是一个逐步搜索过程，其搜索过程如下：
1） 假如第m步已经搜索到一个最短路径，该路径上有n个距离源节点
最近的节点，它们构成了一个节点结合N。
2） 在第m+1步，继续搜索不属于N的距离源节点最近的节点，并将搜
索到的节点加入到N中。
3） 继续搜索，直至到达目的节点，N中的节点集合便是从源节点到目
的节点的最短路径。
在搜索过程中，每个节点用从源节点沿已知的最短路径到本节点的距离来
标注，例如，在B（2，A）标注中，B表示本节点名；2表示在最短路径上源节点到本节点的距离（权值累加）；A表示最短路径上的上游节点名。在初始时，由于最短路径是未知的，故所有节点都标志为无穷大（∞）。随着算法的进展和不断搜索到最短路径，节点的标注值也随之改变，反映出一个较好的路径。
如果将该算法应用于图3.2（a）中，假设搜索从A到G的最短路径，其搜

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