量子遗传算法的应用总结.pptVIP

量子遗传算法的应用研究 答 辩 人：梁 浩 指导老师：孙力娟 QoS单播路由选择问题的描述 单播（Unicast）指网络中从源向目的地转发单播流量的过程。单播传输是 局域网传输中的主要使用方式。 随着多种高速通信网络的出现，以及视频点播、多媒体会议等多媒体应用的不断增长，能有效地支持服务质量(QoS)变得越来越重要。本课题所要解决的问题是：在给定的一个网络拓扑图中，寻找一条满足QoS的路径。 遗传算法 遗传算法是采用达尔文生物进化理论中的“自然选择”、“适者生存”法则以及孟德尔基因遗传变异规律来解决组合优化问题的一种启发式智能优化算法。它包括三个最基本的遗传算子：选择、交叉和变异。 选择 选择是指从群体中选择适应度值大的个体。 选择过程的第一步是计算个体适应度值。在被选集合中每个个体都具有一个选择概率，这个选择概率取决于种群中个体的适应度及其分布。 交叉 基因交叉是把两个父本的部分结构加以替换重组而生成新个体的操作。交叉的目的是为了能够在下一代产生新的个体，通过交叉操作，遗传算法的有哪些信誉好的足球投注网站能力得以提高，它是遗传算法获得新优良个体的最重要的手段。 交叉操作一般分两步进行： 1、对新群体中的个体随机配对； 2、对每一对个体在其串长度范围内随机地产生一个或多个整数作为交叉点，按照交叉概率对配对的个体在交叉点上进行交叉运算。 变异 变异以较小的变异概率随机地改变新群体中某些个体的某些位。变异本身是一种随机有哪些信誉好的足球投注网站，它能恢复计算过程中丢失的某些重要信息，以保持群体的多样性，从而保证了遗传算法的有效性。 遗传算法流程图 量子遗传算法流程图 遗传算法的缺点：对系统中的反馈信息利用不够，当求解到一定范围时往往做大量无为的冗余迭代，求精确解的效率低，容易陷入局部最优解。 量子遗传算法 量子遗传算法建立在量子的态矢量表述的基础上，将量子比特的几率幅表示应用于染色体的编码，使得一条染色体可以同时表达多个状态的叠加，并利用量子旋转门的调整和量子非门来实现染色体的更新操作，从而实现了目标的优化求解。 量子比特 在量子计算机中，充当信息存储单元的物理介质是一个双态量子系统，称为量子比特。一个量子比特可能处于“1”状态，“0”状态或者两者的任一叠加态。 量子比特的状态可表示为 |φ=α|0+β|1 其中α和β是两个复常数，用于定义相应状态可能的几率幅。|α|2表示量子比特为“0”态的概率。|β|2表示量子比特为“1”态的概率。即α，β满足条件： |α|2＋|β|2＝1 采用多量子比特来编码多状态基因如下 其中qjt代表第t代、第j个个体的染色体，k为编码每一个基因的量子比特数，m为染色体的基因个数。 量子遗传算法流程图 遗传算法流程图 量子旋转门调整策略 作为演化操作的执行机构，量子门可根据具体问题进行选择，根据量子遗传算法的计算特点，选择量子旋转门较为合适。量子旋转门U(t)的调整操作如下所示： 其中，(αi,βi)为染色体中的第i个量子比特， θi为旋转角，θi =S(αi,βi)Δθi，其中S(αi,βi)和Δθi分别表示旋转的方向和角度。 量子变异 量子遗传算法变异操作的步骤与遗传算法相似。不同之处在于量子变异操作实际上是更改了该量子比特态叠加的状态，使得原来倾向于塌缩到状态“1”的变为倾向于塌缩到状态“0”，或者相反。显然，该变异操作对染色体所有叠加态均同时有效。 基于量子遗传算法的单播路由选择 (1) 首先采用量子比特对染色体进行编码。每条染色体代表一条路径。 (2) 确定种群大小，（一般取小于10的整数），随机产生初始种群。 (3) 对种群中的每个个体进行一次适应度评估。 (4) 记录下适应度值最大的个体，即代价最小的路径，及其适应度值。将该值作为初始目标值。 (5) 对个体进行旋转门调整。并按照一定概率对种群中的某个个体进行变异。 (6) 对个体进行一次适应度评估，若该代种群的最优个体适应度大于目标适应度，则替代之。 (7) 转到步骤(5)，直到达到所要求的迭代次数为止。 仿真试验结果比较 致谢 本人在毕业设计过程中，得到了老师和同学的帮助。在这里，我要特别感谢孙力娟