（信号与信息处理专业论文）量子遗传算法在认知无线电频谱分配中的应用研究.pdf

k e y w o r d s ：q u a n t u m g e n e t i ca l g o r i t h m ；c o g n i t i v er a d i o ；s p e c t r u ma l l o c a t i o n 直瘟鲣虫太堂硒班塞生堂僮i 金塞 擅要 摘要 量子遗传算法是量子计算与遗传算法相结合的产物。其算法具有寻优能力强、收敛速 度快和计算时间短的特点，所以在许多领域都得到了广泛应用。无线频谱是一种宝贵的自 然资源，为了缓解无线频谱资源短缺、频谱利用率不均的局面，人们提出了使用认知无线 电技术的动态频谱分配机制，本文主要研究将量子遗传算法用于认知无线电频谱分配模型 中。 本文的主要研究内容包括： 第一，研究了基于遗传算法的认知无线电频谱分配模型。并在频谱分配模型的公平性、 总带宽和网络效益等性能指标上，将遗传算法和经典算法进行对比试验。仿真结果表明， 使用遗传算法可以在损失少量总带宽的前提下，更加公平的进行用户间频谱分配，并且可 以获得更高的网络效益。 第二，研究了基于量子遗传算法的认知无线电频谱分配模型。并在算法流程上进行改 进，并把用户需求考虑到模型中，使得用户之间的频谱分配更加公平。在网络总效益、平 均效益和网络效益等性能指标上与经典算法和遗传算法进行比较，仿真结果表明，改进的 量子遗传算法可以得到比其他算法更优的性能。 关键词：量子遗传算法；认知无线电；频谱分配 a b s t r a c t q u a n t u mg e n e t i ca l g o r i t h mi st h ep r o d u c tw h i c hq u a n t u mc o m p u t i n ga n dg e n e t i ca l g o r i t h m u n i f y t h ea l g o r i t h mh a ss t r o n go p t i m i z a t i o na b i l i t y , f a s tc o n v e r g e n c er a t ea n ds h o r tc o m p u t i n g t i m e t h e r e f o r ei th a st h ew i d e s p r e a da p p l i c a t i o ni nm a n yd o m a i n s t h ew i r e l e s sf r e q u e n c y s p e c t r u mi s ak i n do fp r e c i o u sn a t u r a lr e s o u r c e t h ep e o p l ep r o p o s e dt h a tc o g n i t i o nr a d i o t e c h n o l o g yi su s e di nd y n a m i cs p e c t r u ma s s i g n m e n ti no r d e r t oa l l e v i a t es h o r tw i r e l e s sf r e q u e n c y s p e c t r u mr e s o u r c e sa n du s et h ef r e q u e n c ys p e c t r u mu n f a i r l y t h i sp a p e rm a i n l yr e s e a r c ht h a t q u a n t u mg e n e t i ca l g o r i t h mi su s e di nt h ec o g n i t i o nr a d i of r e q u e n c ys p e c t r u ma l l o c a t i o nm o d e l t l l i sa r t i c l em a i nr e s e a r c hc o n t e n ti n c l u d e s ： f i r s t l y , c o g n i t i o nr a d i of r e q u e n c ys p e c t r u ma l l o c a t i o nm o d e lb a s e do ng e n e t i ca l g o r i t h mi s s t u d i e d t h e ng e n e t i ca l g o r i t h ma n dc l a s s i c a la l g o r i t h ma r ec o m p a r e do nf a i m e s s ，t o t a lb a n dw i d t h a n dn e t w o r kb e n e f i tb a s e do nt h em o d e l t h es i m u l a t i o nr e s u l ti n d i c a t e dt h a tg e n e t i ca l g o r i t h m m a yc a r r yo nb e t w e e nt h eu s e rt h ef r e q u e n c ys p e c t r u mf a i r e rt h a nc l a s s i c a la l g o r i t h m ，a n di tc a n o b t a i nh i g h e rn e t w o r kb e n e f i t s e c o n d l y , c o g n i t i o nr a d i of r e q u e n c ys p e c t r u ma l l o c a t i o nm o d e lb a s e do nq u a n t u mg e n e t i c a l g o r i t h mi ss t u d i e d ，a n dh a v ei m p r o v e m e n ti nt h ea l g o r i t h mf l o w , a n du s e r sn e e d si sc o n s i d e r e d i nt h em o d e l s ot h ef r e q u e n c ys p e c t r u ma l l o c a t i o nb e t w e e nt h eu s e r si sf a i r e r t h e nq u a n t u m g e n e t i ca l g o r i t h mi sc o m p a r e dw i t hg e n e t i ca l g o r i t h ma n dc l a s s i c a la l g o r i t h mo nf a i r n e s s ，t o t a l b a n dw i d t ha n dn e t w o r kb e n e f i tb a s e do nt h em o d e l t h es i m u l a t i o nr e s u l ti n d i c a t e dt h a tq u a n t u m g e n e t i ca l g o r i t h mm a y o b t a i n s u p e r i o rp e r f o r m a n c e t h a ng e n e t i ca l g o r i t h m a n dc l a s s i c a l a l g o r i t h m k e yw o r d s ：q u a n t u mg e n e t i ca l g o r i t h m ；c o g n i t i v er a d i o ；s p e c t r u m a l l o c a t i o n i i 2 3 1 量子遗传算法概述9 2 3 2 量子染色体1 0 2 3 3 量子旋转门l o 2 3 4 量子变异、变异操作1 2 2 3 5 算法描述1 3 2 4 量子遗传算法的改进1 5 2 4 1 改进的算法流程1 5 2 4 2 算法性能测试1 6 2 5 本章小结1 8 第三章基于遗传算法的认知无线电频谱分配1 9 3 1 认知无线电系统1 9 i i ! 直塞邮电塞堂亟班究生堂僮i 金塞 目苤 3 1 1 认知无线电原理1 9 3 1 2 频谱分配技术2 2 3 1 3 频谱分配模型的分析与比较2 4 3 1 4 国内外研究现状2 8 3 2 基于图论模型的算法研究3 0 3 2 1 图论分配模型的数学描述3 0 3 2 2 经典算法研究3 2 3 3 3 算法的分析与比较3 8 3 3 基于遗传算法的认知无线电频谱分配流程图3 8 3 4 算法性能仿真3 9 3 4 1 总带宽指标比较研究3 9 3 4 2 公平性指标比较研究4 1 3 4 3 网络效益指标比较研究4 2 3 5 本章小结4 4 第四章基于量子遗传算法的认知无线电频谱分配4 6 4 1 引言。4 6 4 2 基于用户需求认知无线电频谱分配的量子遗传算法流程4 6 4 3 算法性能仿真。4 9 4 3 1 总带宽指标比较研究4 9 4 3 2 公平性指标比较研究5 1 4 3 3 网络效益指标比较研究5 2 4 4 本章小结5 4 第五章总结与展望5 5 致谢5 6 参考文献5 7 攻读硕士学位期间完成的论文6 0 i v 3 g h z 以上的频段几乎没有被使用，而3 g h z 以下频段有多达7 0 未被充分利用。 因此近几年来，能够对不可再生的频谱资源实现再利用的频谱共享技术受到了人们的 广泛关注，认知无线电口1 正是在这样的背景下应运而生。 在认知无线电中，为了解决频谱资源的匾乏和目前固定分配频谱利用率较低的问题， 就要求找到更有效的方法来充分感知和利用无线频谱资源。基本途径有两条：其一，提高 频谱利用率，将已授权用户的频谱资源充分利用，减少浪费；其二，提高系统通信效率， 将己获得的频谱资源和其他资源综合优化分配，进而提高利用率，这些都涉及到频谱分配 的内容h 1 。 频谱分配是能够主动检测可用频谱资源，充分利用无线频谱的新一代无线电，它能根据 需要接入系统的节点数目及其服务要求将频谱分配给一个或多个指定节点。频谱分配策略 的选择直接决定系统容量、频谱利用率以及能否满足用户因不同业务而不断变化的需求， 即是决定能否充分高效利用有限频谱的关键。因此，认知无线电频谱分配问题的研究是认 知无线电技术发展必须解决的关键问题之一。 认知无线电频谱分配方法研究的出现为解决频谱资源不足、实现频谱动态管理及提高 频谱利用率开创了崭新的局面。 量子遗传算法( q u a n t u mg e n e t i ca l g o r i t h m ，q g a ) 晦印是量子计算与经典遗传算法 ( g e n e t i ca l g o r i t h m ，g a ) 相结合而产生的一个新的研究领域。算法利用了量子计算的量子并 行特性，采用了多状态基因量子比特编码方式和量子旋转门更新操作，引入动态和静态调 整旋转角机制和量子变异，使得算法比经典遗传算法具有更强的并行处理能力、更快的收 i 义，并把遗传算法用于模型中，提出了具体的算法流程，并把遗传算法和经典算法相比较， 得出了遗传算法能够在牺牲较少带宽的情况下对用户实施频谱分配时的公平性，并且可以 得到更高的网络效益。 第四章：研究了基于量子遗传算法的认知无线电频谱分配模型。并把用户需求考虑进 去，改进了算法流程，并在最大总带宽和公平性两个性能指标上与经典算法和遗传算法进 2 直塞鲣蛊太堂亟班宜生堂僮i 金塞 筮= 童缝论 行比较和研究，还对用户数和频带数两个参数在不同变化下的网络效益进行仿真分析，证 明了量子遗传算法比遗传算法和经典算法的优越性。 第五章：工作总结，指出可进一步研究的问题。 第二章量子信息基础及量子遗传算法 2 1 量子信息处理基础 2 1 1 量子态空间及量子比特 量子力学引入了几率幅( 即量子态) 。量子态及作用在该量子态上的变换可简洁的d i r a c 左右矢符号表示。右矢i x 表示列矢量，用于描述x 代表的量子态，左矢 i 拘共 轭转置，是行矢量。 符号讧iy ) 表示两个态矢量的内积，它是一个标量，如 c 。i 。，= ( t 。) ( 三) = ，c t i ，= ( 。) ( ：) = ， c 。i - ，= ( 。) ( ：) = 。，c t i 。，= ( 。- ) ( 三) = 。 ( 2 1 ) 符号i d + 6 i l ( 2 3 ) 2 1 2 量子态的叠加、相干和消相干 量子计算的基本特征是量子态的叠加性。相干( c o h e r e n c e ) 和消相干( d e c o h e r e n c e ) 是与线性叠加的概念紧密相关的。如果一个量子系统处于基态的线性叠加之中，那么就称 此量子系统是相干的；但是当一个相干的量子系统以某种方式与它所处的环境发生相互作 用( 例如对处于叠加态的量子位进行观察和测量) 时，叠加态将受到干扰并发生变化，线 性叠加将被破坏，由此所引起的相干的损失就称为消相干或坍缩( c o l l a p s e ) 。 4 2 1 3 量子并行 在量子计算机中，处于叠加态的n 位量子寄存器可同时存储从0 到2 ”一l 的所有2 一个 数，它们各以一定的概率同时存在，在量子计算机中，1 个n 位量子寄存器可以以一定的 概率同时存储2 ”个n 位二进制数。量子计算机可以解决经典计算机不能解决的某些计算复 杂度很高的问题，如大数的质因子分解这一n p 难解问题【7 】【8 】【9 】。 发生相互作用的两个或多个子系统构成的复合系统的态，如果不能表示为其子系统态 的张量积的形式，则称这个复合系统处于纠缠态( e n t a n g l e ds t a t e ) i o 】。例如，有两个双态 量子系统a 和b ，其状态分别为 l ) = q1 0 ) + 口2i l ( 2 4 ) l = 6 11 0 ) + b 21 1 ) ( 2 5 ) 当两个子系统相互独立时，复合系统的态是两子系态的张量积，即 ly 爿y b = | 少一) 圆iy b = ( a i0 a ) + l1 a ) 圆( 包10 b + 6 2l1 8 ) ) ，1 八 l z o j = q6 l1 0 a 0 口) + 0 1 6 2l o 月l 口) + a 2 b l1 1 0 b ) + a 2 b 2h l 占 但是，若两个子系统发生相互作用，系统的自由度将受到一些限制，此时便存在一些 态，如 = 击fo a o b + 去i 1 a 1 8 ) ( 2 7 ) = 击f 0 a 1 8 + 击1 1 , 4 0 8 ) ( 2 8 ) 少 = 击h 嗡+ 万10 , 4 1 b 爿0 a 。去( 怫 + 1 1 瑚 ( 2 9 ) 它们并不能表示为两个子系统态的张量积，这样的态就称为纠缠态。而可以表示成两个子 系统态的张量积，则式( 2 9 ) 所表示的态是非纠缠态。 2 1 4 量子逻辑门与量子门组网络 量子计算过程是对量子态的幺正演化过程，由于幺正变换的可逆性，量子门是可逆的， 郎输入态经过相当于痧变换的量子门演化为输出态，输出态经过相当于d 变换的量子门 5 痧i 爿虬埘 ，d i 埘) 爿) ( 2 1 0 ) 在经典计算机中，“与 门、“或 门等是不可逆的，而量子逻辑门却是可逆的。量子 逻辑门的可逆性是量子计算机的个特点。几个重要的量子门有量子非门( x 门) 、 h a d a m a r d 门( h 门) 、相移门( p 门) 、量子异或( x o r ) 门或控非门( c - n o tf 1 ) 、控控 非门( c c _ n o t 门或t 门) 、量子与门等。 除上述5 种特殊的量子门外，还可以构造量子通用门【1 1 1 ，量子通用门是能实现任意 幺正变换的量子门。 量子门组网络【1 2 1 由多个量子通用门组成，这些量子门的操作在时间上同步，可实现任 意n 维h i l b c r t 空间的所有幺正变换，即与经典计算机的逻辑门组网络在算法控制下可实 现经典计算一样，量子门组网络在算法控制下可实现量子计算。量子计算机的门组网络模 型可描述如下： 量子计算机的存储器由按一定次序排列的双态量子系统( 即q u b i t ) 组成，n 个q u b i t 的2 ”维h i l b e r t 空间用来编码要处理的信息。量子计算由对编码量子态的幺正演化完成， 而幺正演化由量子门组网络在算法控制下实现。 本节简要介绍了量子信息处理研究中涉及到的一些主要概念和基本知识，包括描述量 子态的态空间和左右矢符号、单量子比特( q u b i t ) 和多量子比特( 量子寄存器q r e g i s t e r ) 、 量子态的叠加原理和量子态的相干与消相干、量子并行和量子纠缠特性、几个重要的量子 逻辑门及由量子门构成的量子门组网络等。 2 2 经典遗传算法 2 2 1 遗传算法的基本原理 遗传算法是一种随机全局搜索算法，是对目标空间进行随机搜索。 遗传算法的几个基本概念： 染色体( c h r o m o s o m e ) ：在使用g a 时，需要把问题解编成具有固定结构的符号串，它 的每一位代表一个基因。一个染色体就代表问题的一个解，每个染色体称为一个个体。 群体( p o p u l a t i o n ) ：每代所产生的染色体总数。一个群体包含了该问题在这一代的一 些解的集合。 6 适应度( f i t n e s s ) ：每个个体对应一个具体问题的解，每个解对应的函数值即为适应 函数，它是衡量染色体对环境适应度的指标，也是反映实际问题的目标函数。 简单遗传算法( s i m p l eg e n e t i ca l g o r i t h m s ，s g a ) 是所有遗传算法的基础，也是研究各 种遗传算法性能和优缺点的对象。遗传算法的基本流程如图2 - 1 ：简单遗传算法的基本步 骤如下： s t e p l ：对所涉及问题的可能解进行染色体( c h r o m o s o m e ) 编码； s t e p 2 ：针对问题，寻找一个客观的适应度函数( f i t n e s sf u n c t i o n ) ； s t e p 3 ：生成满足所有约束条件的初始种群( i n i t i a lp o p u l a t i o n ) ； s t e p 4 ：计算种群中每个染色体的适应度( f i t n e s sc o r e ) ； s t e p 5 ：若满足停机条件，退出循环，输出最优解；否则，继续向下执行； s t e p 6 ：根据每个染色体的适应度，产生新的种群，即进行选择操作； s t e p 7 ：进行交叉操作和变异操作； s t e p 8 ：返回s t e p 4 ，进行计算。 图2 1 遗传算法基本流程 7 2 2 2 遗传算法常见编码方法和基本操作 编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。而 由遗传算法解空间向问题空间的转换称为解码n 3 1 。 二进制编码方法是遗传算法中最主要的一种编码方法，它使用的编码符号集是由二进 制符号0 和1 所组成的二值符号集 0 ，1 ) ，它所构成的个体基因型是一个二进制编码符号串。 二进制编码符号串的长度与问题所要求的求解精度有关。 浮点数编码方法是指个体的每个基因值用某一范围内的一个浮点数来表示，个体的编 码长度等于其决策变量的个数。此编码方法可以用来解决一些多维、高精度要求的连续函 数优化问题，因为二进制码在这类问题中不好用。 树形编码主要用于遗传规划中的演化编程或者表示。在树形编码中，每个基因都是由 数字或符号组成的树形结构。 选用什么方法编码主要取决于所要解决的问题本身。 遗传算法包括三种基本的操作：选择、交叉、变异。 ( 1 ) 选择( s e l e c t i o n ) 选择又称复制( r e p r o d u c t i o n ) ，是在群体中选择生命力强的个体产生新的群体的过程。 常用的方法有： 轮盘赌或蒙特卡罗选择法，它是利用比例于各个个体适应度的概率决定其子孙的遗 传可能性。若某个个体为j ，其适应度为疗，则其被选择的概率表示为： | m 仍= z z ( 2 1 1 ) ，t = l 显然，选择概率大的个体能多次被选中，它的遗传因子就会在种群中扩大。 最佳个体保存方法，把群体中适应度最高的个体不进行配对交叉而直接复制到下一 代中。 排序选择方法，指在计算每个个体的适应度后，根据适应度对群体中个体排序，然 后把事先设计好的概率表按序分配给个体，作为各自的选择概率。 ( 2 ) 交叉( c r o s s o v e r ) 交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作，也称基因重 组。常用的交叉操作方法有：单点交叉算子、两点交叉算子和多点交叉算子。除了上述交 叉方法，还有均匀交叉、部分匹配交叉、顺序交叉、循坏交叉等交叉方法。 r ( 3 ) 变异( m u t a t i o n ) 变异即对群体中的个体串的某些基因座上的基因值作变动。交叉和变异是遗传算法中 最重要的部分，算法的结果受交叉和变异的影响最大。变异的目的有两个：1 ) 使遗传算法 具有局部的随机搜索能力；2 ) 保持群体的多样性。 2 2 3 遗传算法的特点 遗传算法的独特优点：遗传算法在寻优过程中，仅需要得到适应度函数的值作为寻 优的依据；遗传算法的优化搜索是从问题解的集合( 种群) 开始，而不是从单个解开始； 遗传算法使用概率性的变换规则，而不是确定性的变换规则；遗传算法适应度函数的 计算相对于寻优过程是独立的；遗传算法面对的是参数的编码集合，而并非参数集合本 身，通用性强。它尤其适用于处理传统优化算法难于解决的复杂和非线性问题。 遗传算法提供了一种求解复杂系统优化问题的通用框架，可以广泛应用于许多学科。 下面是遗传算法的一些主要应用领域n 制，比如h 函数优化、组合优化、生产调度问题自动控 制、图像处理和模式识别。另外，遗传算法在机器人智能控制，人工生命、机器学习等领 域也已经有一些成功的应用。 2 3 量子遗传算法 2 3 1 量子遗传算法概述 量子遗传算法( q u a n t u mg e n e t i ca l g o r i t h m ，q g a ) 是量子计算与遗传算法相结合的 产物。它建立在量子的态矢量表述基础上，将量子比特的几率幅表示应用于染色体的编码， 使得一条染色体可以表达多个态的叠加，并利用量子旋转门或量子非门实现染色体的更新 操作，从而实现了目标的优化求解。目前，这一领域的研究主要集中在量子模型上：一是 量子衍生遗传算法( q u a n t u mi n s p i r e dg e n e t i ca l g o r i t h m ) 1 1 5 ，二是基于量子比特和量子态 叠加特性的遗传量子算法( g e n e t i cq u a n t u ma l g o r i t h m ) 和并行量子遗传算法n 引口7 1 。 本节是在经典遗传算法的基础上研究量子遗传算法，它与经典遗传算法相比，区别在 于采用量子比特编码方法、量子坍塌过程取代经典遗传算法的交叉操作以及量子变异的方 法上。因此，量子遗传算法既具有较好的种群多样性，又具有更好的全局搜索能力。 9 2 3 2 量子染色体 q g a 使用一种基于量子比特的编码方式，即用一对g 数g z - 个量子比特位，一个葡 k 个量子比特位的系统描述为 嘲兹 ，岍脖，i = 1 , 2 , - - , k 缇 其中呸，屈是两个复数，是第j 个量子比特的概率幅，其模满足归一化条件，iq1 2 表 示测量时发现10 ) 的概率，i 层1 2 表示发现ll 的概率。这种表示可表征任意的线性叠加态， 例如有一个3 量子比特系统 瞄z i 2 23 m 1 2 ，2 汜 则系统的状态表示为 1 l 2气1气i 2 知10 0 0 + 办10 0 1 + 赤10 1 0 + 匆1 0 1b + 移3 1 21 1 0 0 + 硒31 1 0 1 + 万1 | 1 1 0 + 移3 1 2 l l l l ( 2 1 4 ) 上面的表示状态1 0 0 0 ，1 0 0 1 ，1 0 1 0 ，1 0 11 ，1 1 0 0 ，i l o l ，1 11 0 ，1 111 出现的概率分别是 3 3 2 ，9 3 2 ，1 3 2 ，3 3 2 ，3 3 2 ，9 3 2 ，1 3 2 ，3 3 2 ，随着口，趋于1 或0 ，这时种群多样性消失，算法收 敛。 2 3 3 量子旋转门 q g a q b 的染色体处于叠加或纠缠状态，因而q g a 的遗传操作不能采用传统g a 的选择、 交叉和变异等操作方式，而采用将量子门分别作用于各叠加态或纠缠态。 在o g a 中，使用量子门变换，由于概率归一化的条件，变换的矩阵必须是幺正矩阵， 常用的量子逻辑门有：非门、异或门、受控的异或门、h a d a m a r d i 3 矛1 旋转门等。 旋转角为0 的量子旋转门u ( o ) 可以表示为： w ，= 瞄茄) 亿 1 0 函数适应度值厂( 匆) 进行比较，如果( 薯) 厂( 匆) ，则调整中相应位量子比特，使得几率 幅对( q ，屈) 向着有利于出现的方向演化；反之，则调整t 中响应位量子比特，使得几率 幅对( q ，屈) 向着有利于岛出现的方向演化。 l 膨i 一 l1 厂孬j 弋 1 lqf r 2 3 4 量子变异、变异操作 图2 2 量子旋转门示意图 o 在遗传算法中，变异操作的作用相对于交叉操作而言并不是作用非常大，其意义主要 在于阻止未成熟收敛和提供算法局部搜索能力。首先定义一种比较简单的单量子比特变异 操作，这种方法如下： 首先对每一代的个体随机确定一个变异位，然后将该位量子比特的几率幅位置对调， 即完成该量子比特的变异操作。 将量子比特的几率幅对的位置进行对调，实际上就是更改了该量子比特态叠加的状 态，使得原来倾向于坍缩到状态i1 ) 的变为倾向于坍缩到状态l0 ) ，或者相反。 下面给出另一种量子变异策略，由当前最优解中反推出一个量子染色体的概率分布， 类似一种概率遗传算法，但是操作过程简单。用公式表示为 皱o ) = 口( f ) + ( 1 一口) ( 1 一乞o ) ) ( 2 1 7 ) q o + 1 ) = q o ) + 6 n o r m r n d ( o ，1 ) ( 2 1 8 ) 其中只( ，) 为到第玳为止的最优个体，q g 为指导量子染色体，口为( f ) 的影响因子， 6 为量子种群随机散布的方差。 交叉算子在传统遗传算法中有着重要的作用，交叉的作用是实现两个个体间结构信息 的互换。 这种交叉操作和传统遗传算法中的交叉操作基本相同，它们都是限制在两个个体之 1 2 工引 问，当交叉的两个个体相同时，就不再起作用。本文中将使用量子的相干特性构造一种新 的量子交叉操作一全干扰交叉。 在这种交叉操作中，种群中的所有染色体均参与交叉。这里假设每一代的染色体个数 为5 ，染色体长度为7 ，具体的操作如图2 4 所示， 图2 3 中仅给出了一种重新排列组合的方式，实际上还可以采用不同的方法产生“交叉 基因位一来实施交叉。这种量子交叉可以从分利用种群中的尽可能多的染色体的信息，改 进普通交叉的局部性与片面性，在种群进化出现早熟时，它能够产生新的个体，给进化过 程注入新的动力。这种全干扰交叉操作借鉴的是量子的相干特性，可以克服普通染色体在 进化后期的早熟现象。 a ( 1 )a ( 2 )a ( 3 )a ( 4 )a ( 5 ) a ( 6 )a ( 7 ) b ( 1 )b ( 2 )b ( 3 )b ( 4 )b ( 5 )b ( 6 )b ( 7 ) c ( 1 )c ( 2 )c ( 3 ) c ( 4 )c ( 5 )c ( 6 )c ( 7 ) d ( 1 ) d ( 2 ) d ( 3 ) d ( 4 ) d ( 5 ) d ( 6 ) d ( 7 ) e ( 1 )e ( 2 ) e ( 3 )e ( 4 )e ( 5 )e ( 6 )e ( 7 ) a ( 1 )e ( 2 ) d ( 3 ) c ( 4 )b ( 5 )a ( 6 )e ( 7 ) b ( 1 )a ( 2 )e ( 3 ) d ( 4 )c ( 5 )b ( 6 ) a ( 7 ) c ( 1 )b ( 2 )a ( 3 )e ( 4 ) d ( 5 )c ( 6 )b ( 7 ) d ( 1 )c ( 2 )b ( 3 )a ( 4 )e ( 5 ) d ( 6 ) c ( 7 ) e ( 1 ) d ( 2 )c ( 3 )b ( 4 )a ( 5 )e ( 6 ) d ( 7 ) 图2 - 3 全干扰交叉示意图 2 3 5 算法描述 q g a 是一种和g a 类似的概率算法，种群由量子染色体构成，在第芒代的种群为 q ( ，) = 反，玩，g ：) ，其中以为种群大小；妫量子染色体的长度；彰定义为如下的染色体： 目；=：ip。；：ii。pz；：il-i。p。2：1，f=：1，2，。 ( 2 1 9 ) 下面给出q g a 的一般步骤： ( 1 ) 初始化种群q 以) ； ( 2 )由q 厅夕量子坍塌生脚厅夕。 ( 3 ) 对群体p 厅) 进行适应度评估，取其中最佳适应度个体作为该个体下一步演化的目 标值； ( 4 ) 停止条件判断：当满足时，输出当前最佳个体，算法结束，否则继续； ( 5 ) 利用量子旋转门对种群q “夕进行更新； ( 6 ) 进行量子变异操作，t = t + 1 ，转到( 2 ) 。 由此可见，q g a 与g a 的不同仅仅在于( 3 ) 、( 5 ) 和( 6 ) 步。在( 5 ) 中，由于量子 旋转门是酉正矩阵，可以用做更新操作的量子门；在( 6 ) 中，量子变异的作用主要在于 阻止未成熟收敛和提供算法局部搜索能力。q g a 的算法流程图如图2 4 所示。 在搜索过程中，q g a 通过选择使具有较高适应度的个体不断增多，并且根据量子坍塌 的机理，采用随机观察方法产生新的个体，不断探索未知空间，像g a 那样，使搜索过程 得到最大的积累收益；其次，q g a 采用量子染色体的表示形式，使一个量子染色体上携带 着多个状态的信息，能带来丰富的种群，进而保持群体的多样性，克服早熟；另外q g a 对量子染色体采用一种“智能 进化的策略来引导进化，提高收敛速度，因此在算法中主 要对量子染色体采用变异操作n 町 1 4 图2 4 量子遗传算法流程图 2 4 量子遗传算法的改进 2 4 1 改进的算法流程 文献n 钾对q g a 算法进行了如下几个方面的改进，分析此改进算法思想以对典型复杂函数 做性能测试： ( 1 ) 量子遗传算法中采用了量子旋转门的演化策略，使所有的个体向着同一个目标演 化，所的到的解有可能陷入局部最优，为了克服这种局限性，我们在量子遗传算法 运行的开始，对初始种群进行分组，每个组中的染色体向着各自的目标演化，通过 组间的移民和交叉来交换各组的优良个体，从而提高算法的效率。 ( 2 ) 用最优保留机制保留的最优个体来更新量子旋转门的旋转角，以便加快算法的收敛 速度。 1 6 趔 籀 团 趔 籀 圜 图2 - 6 局部放大的收敛曲线 图2 - 7 函数收敛曲线 1 7 我们主要采用遗传算法( g a ) 、量子遗传算法( o g a ) 、改进的量子遗传算法进行对 照比较。实验测试的结果如图2 5 至2 7 所示。图2 5 和图2 6 是公式2 2 0 的收敛曲线和局部 放大图。图2 - 7 是公式2 2 l 的收敛曲线图。 从图中可以看出，经典遗传算法的收敛效果不太理想，且收敛速度较慢。量子遗传算 法比经典遗传算法具有更好的收敛效果，且最终收敛值较接近目标值，而改进的量子遗传 算法比量子遗传算法要具有更快的收敛速度，能够更快的接近目标值。 2 5 本章小结 本章从经典遗传算法出发首先介绍了遗传算法的思想、基本结构、算法流程及其特点， 然后引入了基于量子计算特性的量子遗传算法的概念。具体介绍了q g a 中的量子染色体、 算法流程和具体的实现操作方法；分析研究了算法中的量子旋转门调整策略及量子遗传操 作，提出了一种可自适应调节的动态量子旋转门策略，并对量子遗传算法整体进行了改进， 通过实验测试可知，改进的量子遗传算法比量子遗传算法要具有更快的收敛速度，能够更 快的接近目标值。 认知无线电的概念由j o s e p bm i t o l a 博士首先提出，他在1 9 9 9 年发表的一篇学术论文中描 述了认知无线电如何通过一种“无线电知识表示语言( r a d i ok n o w l e d g er e p r e s e n t a t i o n l a n g u a g e ，r k r l ) 的新语言提高个人无线业务的灵活性。 f c c 定义认知无线电是一种可通过与其运行环境交互而改其发射机参数的无线电呦1 。 该定义目前大家比较认同。 认知无线电是依靠人工智能的支持，感知外部无线环境、智能调整无线电参数并根据 一定的学习和决策算法来实时、自适应地改变系统工作参数，以最佳满足外部环境需求口， 动态地检测和有效地利用空闲频谱的无线电瞳羽，期望实现高可靠性的通信并最大化频谱利 用率瞳3 | 。 认知无线电( c o g n i t i v er a d i o ，c r ) 技术近年来引起了无线通信领域的极大关注。通常， c r 具有如下基本功能：感知功能( 包括r f 频谱感知、地理环境感知、用户需求感知等) 、 学习功能和自适应参数调整功能。 认知无线电系统通过分析外部环境提供的激励来认识它通信的任务内容，然后对接收 和发送的内容进行分析，再选择合适的解决方式，目的是为了实现通信的高可靠性和频谱 的高利用率。 目前，国内外对认知无线电技术的研究已全面展开，涉及的研究方向包括认知无线电的 协议体系与网络架构、认知无线电频谱检测技术、认知无线电媒质接入技术、认知无线电 频谱资源分配技术等等，可以说，认知无线电技术必将成为2 1 世纪无线通信领域的热门技 术，得到广泛的关注和长足的发展。 从比较完整的意义上一般认为，认知无线电系统应该具备检测、分析、调整等能力网。 事实上，这些具体功能就是一个认知循环的主要组成部分。现简要论述各部分功能。 ( 1 ) 检测 由特殊应用环境所决定，认知无线电必须具备精确的无线频谱检测能力，必须在可使 用的全频段范围内多维度进行频谱检测，从而发现可使用的频段。由于是免许可使用，认 1 9 直塞鲣血太堂亟鲤塞生堂焦途塞筮三童基王遗佳篡这鳆丛翅玉缮电题遭盆酲 知无线电必须具备迅速发现主用户的能力，在工作过程中时刻检测主用户是否处于活动状 态，从而确保不对其产生干扰。 ( 2 ) 分析 认知分析包括对自身性能、网络内部状态、外部相关数据( 包括频谱使用、策略使用等) 和用户自身需求等相关知识的分析。如果说检测是信息的获取，那么分析就是对相关信息 的初步处理。认知无线电设备通过所获取的频谱检测结果分析主用户的位置、使用的频点 和发射时间，同时分析可用频点位置、可用带宽、信道状况、自身传输可能会对其他用户 产生的影响以及完成业务传输所需的带宽和时间等等。 ( 3 ) 调整 调整能力是完成传输的关键，根据检测和分析的相关结果，认知无线电设备通过先进 的功率控制技术、不同的编解码以及调制技术，选择合适的频点和发射时机，从而成功地 完成传输。这就要求认知无线电设备能够在较宽的频段内实现不同传输方案之间的切换， 并且在突发事件发生后能够及时暂停或恢复传输，确保在不干扰首要用户的情况下获取最 大限度的传输能力。 一个认知无线电系统基本的认知过程要经历3 个基本步骤：无线传输场景分析、信道状 态估计及其容量预测、功率控制和频谱管理，它们的顺序执行使得系统的认知功能得以实 现。认知无线电系统传输信号时，首先要分析无线传输场景，判断干扰温度的大小同时检 测出频谱空穴和估计一些传输参数统计量，进行信道状态估计及其容量预测，接收机把检 测到的信道特征的传输参数反馈到发送端，基于这些参数，发送端通过某些策略来实现功 率控制和频谱管理功能，使系统的传输性能达到最佳。 一个一个认知无线电系统一般由五个部分模块组成：频谱生成模块、信道传输模块、 信道检测模块、频谱分配模块和功率控制模块，各模块的顺序执行，完成了系统的一个认 知过程。 ( 1 ) 频谱生成 频谱生成模块类似于信号源，将一定带宽的频带随机划分为带宽不等的多个子频段， 从多个子频段中随机地选择出几个，将信号分配给它们，被分配了信号的频段表示了该信 道被某个用户( 主用户或次用户) 占用，其他用户不能使用，而未分配信号的频段则说明了 在该频段上没有信号传输，为空闲频谱，可以被认知用户使用。一般情况下，在相同时间 段内，信道被占用的时间长短并不固定，不同时刻信道的占用情况是不同，这体现了认知 系统环境的时变性。 ( 2 ) 传输信道 2 0 直塞鲤鱼盔堂亟班塞生堂焦论塞筮三童基i 三亟佳簋洼鲍丛翅玉线曳麴遴岔醒 无线信道包含了多径传播、时延扩展、衰落以及多普勒效应等特性，在一般的无线传 输信道模型中常使用的信道主要有高斯白噪声信道、瑞利多径衰落信道和莱斯衰落信道。 瑞利信道和莱斯信道都是衰落信道，信号经过信道后其包络服从瑞利分布和莱斯分布。瑞 利衰落属于小尺度的衰落效应，它总是叠加于如阴影、衰减等大尺度衰落效应上。莱斯信 道较瑞利信道则是信道中多存在一个例如直射信号( l o s ) 的主要分量。高斯自噪声信道是理 想信道，它只包含了高斯白噪声，信道特性最为简单，也是系统仿真中最常用的信道模型。 ( 3 ) 频谱检测 一般的频谱区域可分成3 种类型：a ) 黑色区域，常被高能量的局部干扰占用；b ) 灰色区 域，在部分时间被低能量干扰占用；c ) 白色区域，只有环境噪声而没有射频干扰的占用。 一般情况下，只有白色区域和有限度的灰色区域可被等待服务的用户并没有使用的频带。 认知无线电系统中频谱检测的主要作用是尽量快而准确地确定频谱空穴，也就是侦测出频 谱区域中的白色区域和有限度的灰色区域。判断频谱是否可以为认知无线电用户使用有两 种模型：一种是“0 ，1 模型 ，就是认知无线电用户通过检测主用户信号来判断主用户当 前是否占用频谱，若某频段已经被主用户占用，则该频段对认知用户来说是不可用的，赋 予该频段“0 ”标志，若某频段未被占用，则赋予“1 标志。另一种是“干扰温度模型”， 认知用户认为如果它在某个频段上传输会导致干扰温度超过预设的干扰温度限，该频段是 不可用的，如果未超过干扰温度限，则该频段是可用的。在“0 ，l 模型 中，当在某个频 段检测到主用户的信号时，认知无线电用户释放该频段：在干扰温度模型中，当认知无线 电用户发现在其干扰范围内的某个频段的干扰温度超过了干扰温度限时认知无线电用户 才释放该频段。 用于频谱检测的方法有：能量检测、循环平稳信号的谱相关检测和本地振荡器的能量 泄露检测。 ( 4 ) 频谱分配 频谱分配是指根据需要接入到频谱的用户数目及其服务要求将可用频谱分配给一个或 多个指定用户。频谱分配的主要目的是通过一个自适应策略有效地选择和利用射频( i 强) 频 谱。利用动态频谱分配可以提高无线通信的灵活性和降低信道能量的使用，可以使主用户 和次用户之间避免冲突并共享频谱资源盈引。 ( 5 ) 功率控制 在认知无线电通信系统中功率控制的实现以分布方式进行的，它可以扩大系统工作范 围，提高接收机性能。在多址接入信道环境中，主要采用协作机制方法，多用户问彼此协 作工作，可以提高系统工作性能，支持更多用户接入。同时，在给定的网络资源限制下， ! l 直塞唑虫盔堂亟班塞生堂僮途