量子算法范文

量子算法范文（精选8篇）

量子算法 第1篇

自从1994年Shor提出第一个求解大数质因子分解算法[1]和1996年Grover提出量子搜索算法之后[2],量子计算引起人们的广泛关注。量子遗传算法(Quantum Genetic Algorithm, QGA)是量子计算与遗传算法(Genetic Algorithm, GA)相结合的一种优化算法。它以量子计算的概念和理论为基础,用量子位编码来表示染色体,用量子门作用更新来完成进化搜索,具有种群规模小而不影响算法性能、同时兼有“勘探”和“开采”、收敛速度快和全局寻优能力强的特点[3]。文献[4,5]对量子遗传算法进行了研究,结果表明,QGA的性能大大优于传统遗传算法(Convention Genetic Algorithm, CGA)。然而,QGA在实施过程中,存在储存量大和早熟现象等问题。为此,本文提出以角度编码方式,引入小区间方法,利用Hε门[6]的思想改进旋转门,采用动态的量子步长调整策略,引入量子交叉和量子变异操作的新的改进量子遗传算法(Novel Improved Quantum Genetic Algorithm, NIQGA)。

1 基本原理

1.1 染色体的编码方式

在量子计算中,采用|0>和|1>表示单量子比特的基态,而且还可以表示2个量子的叠加态为:

$|\phi >=\alpha |0>+\beta |1>(1)$

式(1)中(α,β)是一对复数,表示相应比特的概率幅且满足$\left|\alpha \right|{}^2+\left|\beta \right|{}^2=1$,$\left|\alpha \right|{}^2$表示取|0>的概率,$\left|\beta \right|{}^2$表示取|1>的概率。量子比特也可借助于三角函数表示为:

$|\phi >=\cos \theta |0>+\sin \theta |1>(2)$

以量子比特的矢量形式编码染色体,则每一个基因位都是一个复数对,需要保存四个实数。即使每一个复数都简单地取为实数,也需要保存两个实数,故存储量很大[7]。普通量子遗传算法编码中,若一个染色体的长度为m,则至少需要保存2m个实数。

NIQGA编码方式受三角函数表示的启发,直接用角度作为染色体基因链的编码,编码方案如下:

$q{}_i=[\theta {}_{i1},\theta {}_{i2},\cdots ,\theta {}_{im}](3)$

式(3)中$\theta {}_{ij}\in \left[0,\text{π}/2\right]$, i=1,2,n,j=1,2,,m, n是种群规模,m是染色体长度。

这种编码形式在存储上,一个染色体只需要保存m个实数,存储量变为原来的一半。

1.2 小区间方法

利用小区间方法生成的初始种群均匀地分布在解空间里,利于保持种群的多样性。本文引入小区间方法,其核心是将量子位概率空间分为N个, 初始化过程按式(4)对概率空间进行平分, 将每个子种群初始化为相同概率的量子染色体。

$\theta {}_k=\frac{i}{{\rm N}}\frac{\text{π}}{2}(4)$

式(4)表示N个种群中第i个染色体的初始值。

1.3 量子门的更新

量子门更新操作是染色体进化的主要手段。新的编码量子染色体的每一个基因位都是一个在$\left[0,\frac{\text{π}}{2}\right]$上取值的角, 则旋转门对基因位的作用由矩阵与向量相乘, 变成了角度的加减, 其形式得到了简化, 计算量也大大减少了。新的旋转门更新操作通过对种群中染色体的各个基因位θij进行增减操作,染色体将向着演化目标进化,即保证了种群向着最优解收敛,同时也保持了种群的多样性[8]。旋转门U可表示为式:

${\theta }^{\prime }=\theta +S(\theta )\Delta \theta (5)$

式(5)中θ′和θ分别为操作后和操作前的染色体第j个基因位的值,S(θ)为旋转的方向,即取正或负,Δθ为量子步长,是更新操作的大小值。

1.3.1 量子步长的调整

Δθ的大小在0～π/2之间,可根据实际情况进行选择,可以选取固定的值,也可根据进化代数等因素进行动态调整。选取为固定值时,通常选取范围为0.000 1 π～0.05 π之间。也可采用动态步长,根据实际情况进行设计以达到最佳优化效果。本文就是采用文献[9]的自适应的动态调整策略,公式如式(6)。

$\Delta \theta =\theta {}_{\min }+f(\theta {}_{\max }-\theta {}_{\min })(6)$

式(6)中,θmin为Δθ区间的最小值0.001π;θmax为Δθ区间的最大值0.05π;$f=\frac{(f{}_{\max }-f{}_x)}{f{}_{\max }}$,fmax为搜索到的最优个体的适应度,fx为当前个体的适应度。由式(6)看出当前个体与最优个体比较远时,Δθ的值就比较大;而当前个体与最优个体比较近时,Δθ的值就比较小,实现自适应搜索,有利于寻找最优解。

1.3.2 旋转方向

目前多数的量子遗传算法采用文献[4]提出的查询表方法,列出各种可能情况,作为辅助决策的工具,运算时非常繁琐[10]。其实,实施基因旋转的目的是位了使当前个体逼近最优个体。如果把当前个体的基因位和最优个体的基因位放在坐标系里比较,可以得出:若最优个体的基因位大于当前个体所对应的基因位,则方向应取正,反之取负。文献[11]有定理可以保证此结论的正确性。

令$\widehat{\theta }$是当前搜索到的最优个体中的某个基因位,θ是当前要进化个体相应的基因位。根据上面的分析,得到:

$\text{s}\text{i}\text{g}\text{n}(\Delta \theta )=\{\begin{array}{c}1,\widehat{\theta }>\theta \\ -1,\widehat{\theta }-\theta <0\\ 0,\widehat{\theta }=\theta \end{array}(7)$

1.3.3 Hε门

文献[6]中提出了Hε门的概念,利用这一概念,类似地,本文把旋转门Uε公式定义成:

$\tilde{\theta }=U{}_{\epsilon }=\{\begin{array}{c}\epsilon ,\text{当}{\theta }^{\prime }<\epsilon \\ \frac{\text{π}}{2}-\epsilon ,\text{当}{\theta }^{\prime }>\frac{\text{π}}{2}-\epsilon \\ {\theta }^{\prime },\text{否}\text{则}\end{array}(8)$

1.4 量子交叉

染色体交叉的主要作用是增加种群多样性,防止未成熟收敛,本文采用如下的全干扰交叉操作:

这是一种按对角线重新排列组合的交叉方式,其中每一行代表交叉后的一个新染色体,如: A(1)-E(2)-D(3)-C(4)-B(5)-A(6)-E(7)。

1.5 量子变异

普通的量子遗传算法采用量子非门实现量子染色体变异。量子变异操作实际上是更改了该量子比特态叠加的状态,使得原来倾向于坍塌到状态|1>的变为倾向于坍塌到状态|0>;或者相反。利用这种思想,在本文中变异公式的如式(9)。

$\tilde{\theta }=\frac{\text{π}}{2}-\theta (9)$

变异概率是确定变异操作的关键。在本文里采用自适应变异,公式(10)。

$p{}_m=\{\begin{array}{c}pm{}_2-\frac{(pm{}_2-pm{}_1)(f{}_{\max }-f{}_x)}{f{}_{\max }-f{}_{\text{a}\text{v}\text{g}}},f{}_x>f{}_{\text{a}\text{v}\text{g}}\\ pm{}_2,f{}_{x}f{}_{\text{a}\text{v}\text{g}}\end{array}(10)$

式(10)中,pm2>pm1,取值范围为0.01～0.1。

2 改进的算法流程

(1)初始化种群:

取初始种群 Q(t),按式(4)确定种群初始值。

(2)量子坍缩:

对Q(t)中的个体进行一次观测,以获得一组确定的解$R(t)=\left\{p{}_1^t,p{}_2^t,\cdots ,p{}_n^t\right\}$,其中p${}_i^t$为第t代种群中第i个染色的观测值,形式为长度为m的二进制串。具体操作为:随机生成一个0～π/2的数,若它大于θij,则对应基因位的观测值取1;否则取0。

(3)适应度计算:

将量子坍缩生成的每一组二进制串转化为函数自变量取值范围内的实数值,将其代入适应度函数计算。记历代获得的最优染色体为qb,当代最优染色体为qs,若f(qs)>f(qb),则qb=qs,否则,qs=qb。

(4) Uε门更新:

根据式(5)～式(8)更新种群。

(5) 量子交叉:

对整个种群运用全干扰交叉操作。

(6) 量子变异:

根据式(9)～式(10)对染色体进行变异操作。

(7) 量子灾变:

当在规定的代数内,最优染色体不变化,就进行一次灾变。

(8)终止条件:

当迭代代数t达到T时,进化结束,输出结果;否则转向(2)。

3 算法性能分析

NIQGA较QGA具有更多的性能优势,主要表现在以下几点:

(1)存储量少:QGA以复数表示基因位,一个量子比特位存储需要4个数;若以实数表示基因位,一个量子比特位存储则需要2个数;而NIQGA以角度编码表示基因位,一个量子比特位只需要[0,π/2]内的一个实数。所以,在计算时,计算机存储量大大减少。

(2)计算量少:在量子坍缩中,NIQGA直接比较角度的大小,每一代减少了 (mn)次平方运算;量子旋转门的作用形式由矩阵与矢量相乘, 变成角度的加减,量子非门的形式也简化成了角度相减。确定量子旋转方向时,避免了查表,采用与最优个体计较的方法来确定。所以,NIQGA大大简化了计算的复杂度。

(3)防止早熟:基因位一旦收敛, 则其测量值就很难再跳出固定的个体, 从而造成早熟收敛。为了防止早熟现象,本文根据Hε门的概念,设计了Uε门。该方法可以有效的防止早熟收敛。本文还采用了小区间方法和量子灾变,以保持种群的多样性,提高全局搜索能力。

4 算法性能测验

4.1 典型的多峰值函数

4.1.1 Schaffer函数

$\begin{array}{l}f{}_1(x,y)=0.5-\frac{\sin {}^2\sqrt{x{}^2+y{}^2}-0.5}{[1.0+0.001(x{}^2+y{}^2)]{}^2},\\ (-10x,y10)。\end{array}$

该函数为多峰函数,有无穷多个局部极大点,其中只有一个全局最大点f1(0,0)=1,在函数最大值周围有两圈脊峰,它们的取值分别为0.962 776和0.990 284。因此一般算法容易陷入在这些局部最优点中。

4.1.2 Bohachevsky函数

$\begin{array}{l}f{}_2(x,y)=0.3\cos 3\text{π}x-0.3\cos 4\text{π}y-x{}^2-y{}^2-0.3\\ (-1x,y1)。\end{array}$

该函数有多个局部极大值点,其中有两个为全局最大点,为(0,±0.239 838),最大值为0.2 400 345。一般当优化结果大于0.24时,认为算法收敛。

对于上述两个函数,分别用CGA、QGA、PQGA[10]和NIQGA优化100次,然后统计每种算法的结果,制成下述表格。四种算法的最大优化代数为500,CGA的种群规模为50,交叉概率为0.8,变异概率为0.05;QGA、PQGA和NIQGA的种群规模为30;QGA的转角步长及PQGA的转角步长初值为0.01π;NIQGA的转角最小值为0.001π,最大值为0.05π,ε=0.001π,变异概率pm1=0.01,pm2=0.05。上述实验在Matlab7.1中进行。结果如下表1、表2。

4.2 测试结果分析

从上述的两个表和图中可以得知,NIQGA所计算的结果更接近理论值,收敛次数最多,迭代的步数最少,所花费的计算时间最短。因此,在多峰值函数寻优问题上,本文的NIQGA算法性能优于CGA、QGA、PQGA。

5 结 语

在分析了QGA不足后,为了提高QGA的性能,本文提出了一种新的量子遗传算法(NIQGA),以角度编码减少了存储量;染色体的观察方式发生了改变,其更新过程由矩阵与向量相乘简化成角度的加减,减少了计算时间;设计了Uε门,防止早熟现象;采用小区间方法,保持种群的多样性,提高全局搜索能力。将NIQGA用于多峰值函数优化问题,显示了良好的寻优性能。但是,经验证NIQGA对一些单峰病态函数的寻优效果相当不好,例如De Jong函数f=100(y-x2)2+(1-x)2,需要今后进一步研究。

摘要：针对量子遗传算法存在储存量大和易陷入局部最优解等问题,提出一种新的量子遗传算法。该算法采用角度编码方式表示染色体,从而减少编码的存储空间。引入小区间方法初始化量子种群,使量子染色体均匀分布于初值空间。利用改进的旋转门对种群进行更新操作。采用动态的量子步长调整策略实现自适应搜索。引入量子交叉和量子变异操作防止早熟问题。通过典型的多峰值函数优化实验,表明该算法具有收敛速度快、全局寻优能力强和计算时间短的特点,可以用于多峰值函数优化问题。

关键词：角度编码,小区间方法,改进的旋转门,量子交叉,量子变异,多峰值函数

参考文献

[1] Shor P W.Algorithms for quantum computation:Discrete logarit ctor-ing.Proc of 35 th annual Symposium:Foundation of Computer Sci-ence.Santa Fe,1994:20—22

[2] Grover L K.A fast quantum mechanical algorithm for databasesearch.Proc of 28th ACM Symposium:Theory of Computing.NewYork,1996:212—221

[3]张葛祥,李娜,金炜东,等.一种新量子遗传算法及其应用.电子学报,2004;32(3):476—479

[4] Han K H,Kim J H.Genetic quantum algorithm and its application tocombinatorial optimization problems.Proc of IEEE Conference on Evo-lutionary Computation.Piscataway:IEEE Press,2000:1354—1360

[5] Han K H,Park K H,et al.Parallel quantum2inspired genetic algo-rithm for combinatorial optimization problems.Proc of the IEEE Con-ference on Evolutionary Computation.Piscataway:IEEE Press,2001:1442—1429

[6]朱筱蓉,张兴华.基于改进量子遗传算法的连续函数优化研究.计算机工程与设计,2007;28(21):5195—5197

[7]高颖慧,沈振康.角度编码染色体量子遗传算法.计算机工程与科学,2009;31(3):75—79

[8]方超.量子遗传算法的改进及其在火电机组负荷优化分配上的应用.北京:华北电力大学,2011

[9]张宗飞.一种改进型量子遗传算法.计算机工程,2010;36(6):181—183

[10]肖红,尚福华,曹茂俊.一种新量子遗传算法及应用.科学技术与工程,2010;10(8):1874—1877

量子算法 第2篇

关键词:量子遗传算法;多目标分配;最优化

中图分类号:TP18 文献标识码:A 文章编号:1674-7712 (2012) 12-0176-01

一、引言

遗传算法不同于传统寻优算法的特点在于:遗传算法在寻优过程中,仅需要得到适应度函数的值作为寻优的依据;同时使用概率性的变换规则,而不是确定性的变换规则;遗传算法适应度函数的计算相对于寻优过程是独立的;算法面对的是参数的编码集合,而并非参数集合本身,通用性强。它尤其适用于处理传统优化算法难于解决的复杂和非线性问题。[1]

目前,GA已经在很多领域得到成功应用,但随着问题规模的不断扩大和搜索空间的更加复杂,GA在求解很多具体问题时往往并不能表现出其优越性。于是,近年来便出现了遗传算法与其它理论相结合的实践,其中遗传算法与量子理论的结合是一个崭新的、极富前景和创意的尝试。

量子遗传算法QGA是量子计算特性与遗传算法相结合的产物。基于量子比特的叠加性和相干性,在遗传算法中借鉴量子比特的概念,引入了量子比特染色体。由于量子比特染色体能够表征叠加态,比传统GA具有更好的种群多样性,同时QGA也会具有更好的收敛性,因此在求解优化问题时,QGA在收敛速度、寻优能力方面比GA都将有较大的提高。QGA的出现结合了量子计算和遗传算法各自的优势,具有很高的理论价值和发展潜力。

本论文提出用量子遗传算法处理和解决多目标分配问题,为多目标问题的解决提供一种新的思路。

二、量子遗传算法

在传统计算机中,信息存储是以二进制来表示,不是“0”就是“1”态,但是在量子计算机中,充当信息存储单元的物质是一个双态量子系统,称为量子比特(qubit),量子比特与比特不同之就在于它可以同时处在两个量子态的叠加态,量子进化算法建立在量子的态矢量表述基础上,将量子比几率幅表示应用于染色体的编码,使得一条染色体可以表示个态的叠加,并利用量子旋转门更新染色体,从而使个体进达到优化目标的目的。

一个 位的量子位染色体就是一个量子位串,其表示如下:

其中 。在多目标优化中,一个量子染色体代表一个决策向量,在量子态中一个 位的量子染色体可以表达 个态,采用这种编码方式使得一个染色体可以同时表达多个态的叠加,使得量子进化算法比传统遗传算法拥有更好的多样性特征。

为了实现个体的进化,经典进化算法中通过染色体的交叉、变异操作推进种群的演化,而对量子进化算法而言,量子染色体的调整主要是通过量子旋转门实现的,算法流程如下:

(1)进化代数初始化: ;

(2)初始化种群 ,生成并评价 ;

(3)保存 中的最优解 ;

(4) ;

(5)由 生成 ;

(6)个体交叉、变异等操作,生成新的 (此步可省评价);

(7)评价 ,得到当前代的最优解 ;

(8)比较 与 得到量子概率门 ,保存最优解于 ;

(9)停机条件 当满足停机条件时,输出当前最优个体,算法结束,否则继续;

(10)以 更新 ,转到4)。

三、基于量子遗传算法的多目标分配应用

如今为了满足市场的需要,很多工厂的生产种类多、生产量大,从而设置了不同的生产车间,根据产品的性质分配生产车间合理与否直接影响工厂的经济收益,这同样可采用遗传算法的目标分配方法进行分配。

模型构建:设工厂有i个生产车间。 为在第i个车间生产第j种产品的收益, 为第j种产品的需求量;如果第j种产品被选中,则 为在第i个车间生产该产品的总收益。由题意知为求解 最大问题。

仿真实例:设有10个生产车间,要生产15种产品,用Matlab程序编程,设定40个粒子,迭代200次,代沟0.9。运行结果如下:

此图表明经200次迭代后的目标分配方案为:第1种产品由第3个车间生产,以此类推,车间5生产第2种产品,车间8生产第3种产品,……。次方案对应的车间总收益值为2.7030e+003,成功进行了多目标分配问题的解决。

四、结论

基于量子遗传算法的多目标分配,为多目标分配突破传统寻优模式找到了一个可行的解决方法。根据这种方法实验,仿真结果可以看出,基本符合要求,并且能够在一定的时间内得到最优的分配方案,因此,本文在探索多目标分配问题上找到了一种新的解决思路。

参考文献:

[1]吉根林.遗传算法研究综述[J].计算机应用与软件,2004,21(2):69-73

[2]肖晓伟,肖迪.多目标优化问题的研究概述[J].计算机应用研究,2011,3,28(3):805-808

[3]原银忠,韩传久.用遗传算法实现防空导弹体系的目标分配[J].火力与指挥控制,2008,3,33(3):80-83

[4]郭张龙,李为民,王刚.基于遗传算法的目标分配问题的研究[J].现代防御技术,2002,6:0172-0180

[5]孙祥,徐流美.matlab7.0基础教程[M].北京:清华大学出版社,2005

量子算法 第3篇

QoS多播路由技术是网络信息传输的关键技术,随着光纤网络等高性能网络的发展,基于QoS 多播路由协议的设计理论与方法的研究已成为网络领域中的一类重要课题。提供满足QoS 需求多播服务的关键是如何建立满足多个QoS 约束的最小代价树,这个问题称为受约束最小Steiner 树问题,它是NP 完全问题[1],针对该问题,目前采用的方法多为启发式算法,典型的启发式算法有MST、RS等[2];基于启发式的解决方案,在优化性能上有时不能满足要求,求得的解是不稳定的,而需要使用可以在不同解之间移动的技术,如进化规划、遗传算法。

量子遗传算法是新兴起的一种基于量子计算原理的概率优化方法,它以量子计算的概念和理论为基础,用量子位编码来表示染色体,从而一条染色体可以表达多个态的叠加,缩小了种群的规模,增加了种群的多样性;用量子门作用和量子门更新来进行进化搜索;利用量子纠缠设计的量子交叉可以在整个种群中进行信息交流,使得种群易于发现优秀演化个体,文献[3,4]分别提出了遗传量子算法和并行量子遗传算法,并用来求解优化问题,结果表明,QGA 的性能优于传统遗传算法,是解决NP完全问题的有效方法。本文通过量子遗传算法和IMST算法的结合使用,提出了一种求解受约束QoS多播路由算法,详细介绍了该算法的实现过程;通过仿真实验比较,该算法具有较好的收敛性。

2 QoS多播路由模型

设图G=(V,E)表示网络结构,其中V表示节点集,E表示节点间链路集,s∈V为多播源点,M⊆{V-{s}}为多播目的节点集,R+表示正实数集,R+表示非负实数集。对于任一链路e∈E,定义4种度量:延时函数delay(e):ER+,费用函数cost(e):ER+,带宽函数bandwidth(e):ER+和延时抖动函数delay_jitter(e):ER+。对于任一网络节点n∈V,也定义4 种度量:延时函数delay(n):VR+,费用函数cost(n):VR+,延时抖动函数delay_jitter(n):VR+和包丢失率函数packet_loss(n):VR+。则对于给定的源节点s∈V,目的节点集M,s 和M组成的多播树T(s,M) 存在下列关系:

则QoS多播路由问题可以描述为:在网络G=(V,E)中,s∈V 为多播源点,M⊆{V-{s}}为多播目的节点集,延时函数delay(*)∈R+,延时抖动函数delay_jitter(*)∈R+,费用函数cost(*)∈R+,带宽函数bandwidth(*)∈R+和包丢失率函数packet_loss(*)∈R+,寻找一棵多播树T(s,M)满足:

(1)延时约束:delay(PT(s,t))Dmax

(2)带宽约束:bandwidte(PT(s,t))≥Bmin

(3)延时抖动约束:delay_jitter(PT(s,t))J max

(4)包丢失率约束:packet_loss(PT(s,t))L max

(5)费用约束:在所有满足(1)(4)条件的多播树中,cost(T(s,M))最小。

其中,PT(s,t)为T(s,M)上源点s 到目的节点t 的路由路径,Bmin是带宽约束,Dmax、Jmax 和Lmax 分别是延时、延时抖动和包丢失率约束。

3 量子遗传算法简介

3.1 量子比特编码

量子比特是一个充当信息储存单元的双态量子系统,是定义在二维复向量空间中的一个单位向量,该空间由一对特定的标准正交基{|0>,[1]>}组成, 因此它可以同时处于两个量子态的叠加态中,定为:|Φ>α|0>+β[1]>|, 其中0 、1 在量子力学中分别表示自旋向下态和自旋向上态,α、β是两个复数概率幅对,|α|2+|β|2=1,|α|2可看成量子处于自旋向下态的概率, |β|2可看成量子处于自旋向上态的概率,所以一个量子比特可同时包含0 和1 的信息,在量子遗传算法中,采用量子比特表达一个基因,当|α|2=1时,该基因可具有“0 态”,当|β|2=1时,该基因可具有“1 态”,|α|2≠0,|β|2≠0时,该基因可具有任意叠加态。因此,对多态问题可采用量子比特编码如下:

undefined

其中qundefined为第t代第j个量子个体, k为每个量子基因编码所用的量子比特数,n为染色体基因个数, 其中|αundefined|2为第i 个自变量在用长度为k 的二进制编码时第j个基因取0 的概率,而|βundefined|2为取1 的概率。qundefined产生的所有可能二进制串的个体为2nk个,量子编码qundefined对应长为n k 的二进制字符串可通过测量来确定。 所谓一次测量,根据量子比特概率幅|αundefined|2来确定第((i-1)(k+j))位上的0 或1;具体方法为:随机产生一个[0 ,1 ]数,若它概率幅|αundefined|2的值,则测量第((i-1)(k+j))位取1 ,否则取0。

显然,此种量子编码方式使个体拥有更好的多样性,且随着|α|2和|β|2趋于0 或1 ,染色体将收敛到一个单一态。

3.2 量子遗传算法流程

(1) 令t = 0 ,取种群规模为N 的初始种群Q( t);

(2) 对初始种群每个个体实施一次测量,得一个状态p(t) ;

(3) 对每个状态计算适应度;

(4)记录最佳个体及其适应度值;

(5) while (小于最大迭代次数)

a、t = t + 1 ;

b、对种群Q ( t) 中每个个体实施一次测量,得到一个状态p (t) ;

c、对每个状态计算适应度;

d、利用旋转量子门操作对种群个体进行更新;

e、记录下最佳个体及其适应度。

4 基于量子遗传算法和IMST算法的QoS多播路由算法

首先使用QGA算法来选择Steiner 点, 然后对选定的Steiner 点, 使用IMST算法求解在这些Steiner 点下的Steiner 树;由于QGA算法中的每一个个体对应于一棵Steiner 树, 这样可以通过QGA算法的量子交叉和旋转量子门操作使个体逐步进化, 最终求得优化的QoS路由选择问题的解。

4.1 网络结构的简化处理

在实施该算法之前,先根据带宽约束条件,对网络结构进行预处理,产生一个满足带宽约束条件的连通网络;并对每个节点用1,2,,n-1,n来进行编号,其中n表示网络中节点的个数。具体如下:

(1)删除不满足带宽约束条件的边;

(2)假设节点v 的度deg (v ) = 1,边e(v,w)∈E,如果v ∈M, 那么任何最小生成树MST 都一定包括边e(v,w), 因此节点v 和边e(v,w)可从图G 中移去;

(3)用Floyds 算法[6]求距离图D (G) , 得任意两点v,w间最短路径sp(v,w ) (这也是IMST算法所必需的);若e(v,w)∈E且e(v,w)>sp(v ,w ) ,那么没有MST会包含e(v,w), 可以删去这条边。

4.2 染色体的量子比特编码

对表示路由链路的初始群体进行量子比特编码, 其中每个基因码的量子比特数为n(节点个数), 而每个染色体的基因个数为m(目的节点数),则得到链路的量子比特编码为:

undefined

其中qundefined代表第t代第j个个体的染色体;在初始情况下, 种群中全部染色体的所有基因的概率幅(αundefined,βundefined)被初始化成undefined, 经过一次量子测量,则可以得到初始种群Q(t)={p1,p2pN}。

4.3 适应度函数

适应度是利用种群中每个个体的适应值来进行筛选的, 适应度函数直接影响到算法的收敛速度以及能否找到最优解;本文定义适应度函数为:

undefined

其中,ω1,ω2,ω3和ω4是关于费用、延迟、延迟抖动和分组丢失率的权重系数,f(d) ,f(j) 和f (p)分别为:

其中Fd(x),Fj(x)和Fp(x)是针对延迟、延迟抖动和分组丢失率的罚函数,∂,β和λ都是小于1的正数。

4.4 IMST算法

IMST 算法可以把选择的节点解释为有效的Steiner树,且代价评估中不需要加惩罚项, 避免不可行解指派代价可能引起的问题;具体步骤如下:

(1)使用Floyds 算法求出图G= (V,E) 的距离图D(G) ,两两节点间为最小代价路径;

(2)图D(G)中构造只包含M (目的节点)的子图G1;

(3)计算图G1 的MST: T1;

(4)T1 中的每条边替代以相应的图G 中的最短路径, 构造图G 的子图G2;

(5)计算图G2 的MST: T2;

(6)T2 中依次删除满足以下条件的节点:v∉s,且deg (v ) = 1,从T2 得到树TMST,

即为所求Steiner树。

4.5 量子交叉

利用量子力学的纠缠、干涉特征设计量子交叉,具体做法如下:

(1)在规模为N种群Q(t)中,染色体如(1)所示;

(2)交叉后代C1的第i个基因段第一对概率幅值为:

undefined,第j对概率幅值为undefined:,最后一对概率幅值为:C1(α1k)=[(qN(α1k))+(q1(α1k))/2],C1(βik)的求法同上,在j

(3)用(2)的方法重复操作,直到取得N个交叉后代为止。

从整个量子交叉的过程来看,量子交叉的作用就是在整个种群内部进行信息传递,而且个体中出现频率高的基因值得以保留,有利于算法收敛。

4.6 旋转量子门操作

定义1:角度θ定义为一个量子位的相位,即θ=arctan(β/α)

用符号d 表示α和β的乘积,即d=αβ,其中d的正负值代表此量子位的相位θ在平面坐标中所处的象限,如果d的值为正, 则表示θ处于第一、三象限, 否则处于第二、四象限。设种群的大小为N , 其染色体用量子位表示为Q(t)={q1,q2 , } , 如(1)式,旋转量子门

undefined

其中,θ为量子门的旋转角,取值为:θ=kf(αi,j,βi,j) , k 是一个与算法收敛速度有关的系数, k 的取值必须合理选取,如果k 的值取得太大,算法搜索的范围就很大,容易出现早熟现象,算法易收敛于局部极值点, 反之,算法速度太慢,甚至会处于停滞状态。由此,本文将k 视为一个变量,将k 定义为一个与进化代数有关的变量,以便自适应地调整搜索范围的大小。如undefined,其中t 为进化代数,maxt是一个根据优化问题复杂性而定的一个常数。函数f(αi,j,βi,j)的作用是使算法朝着最优解的方向搜索。本文采用如表1 所示的搜索策略,其原理是使当前解逐渐逼近搜索的最佳解,从而确定量子门的旋转方向。

这样,量子门的更新过程可描述为qundefined=G(t)qundefined

4.7 算法流程

(1)对网络结构图形进行简化处理;

(2)令t=0,初始化种群Q(t),种群规模为N;

(3)对种群Q(t)中每个量子个体实施N1(N1 是小于N的偶数)次测量,得到局部群体(译码后的个体集合)p(t,j)(j=1～N);

(4)用IMST算法求解各个体的Steiner 树,计算局部种群p(t,j)中每个个体的适应度,令p(t,j)中的最好个体代表Q(t)中第j个量子个体(j=1～N);

(5)while (小于最大迭代次数)

a、t=t+1;

b、对群体Q1(t)中每个个体进行量子交叉操作,得到交叉后群体 Q1(t)(j =1～N);

c、对种群Q1(t)中每个量子个体实施N1次测量,得到局部群p(t,j)体的N1个元素(j=1～N);

d、用IMST算法求解各个体的Steiner 树,对局部群体p(t,j)中每个个体计算适应度,令p(t,j)中的最好个体代表Q1(t)中第j个量子个体(j=1～N);

e、利用旋转量子门操作对种群Q1(t)中个体进行更新得下一代种群Q(t+1)

(6)对于图形简化技术删去的必在Steiner 树中的边, 其代价加到最优解的最小代价上。

随着算法循环的深入,种群逐渐收敛于最优解,此算法包含的模式多,使得搜索空间较大,又不是盲目搜索,利用IMST算法方向性强,加快收敛到最优解的速度。

5 仿真实验

采用Visual C++ 6.0 为编程工具,在CPU 为Celeron 2. 50GHz,内存256MB,操作系统为Windows XP的计算机上求解。仿真实验中采用如图1的网络模型。实验中假设所有组播目的节点的各QoS约束相同,并且只考虑边的特性而忽略了节点的特性,同时将网络模型根据带宽约束进行了预处理;图中边的特性采用一个4元组( d,j,b,c) 来分别描述其延迟、延迟抖动、带宽以及费用。

实验中的参数设定为:种群规模N=50,局部种群N1 = 10,迭代次数maxt=100,ω1=0.8,ω2=0.5,ω3=0.5,ω4=0.3,∂=0.5,β=0.5,λ=0.5 。

图1是本实例的一个网络结构图,网络的节点数为13,设源节点s为节点0,目的节点集M = { 2, 5, 7, 9,11}。

在利用遗传算法求解QoS 多播路由问题的各种算法中,文献[5]提出的算法QoSMR- GA 和文献[6]提出的QoS-QGA算法是近年来的典型方法;本文主要与QoSMR- GA 算法、QoSMR-QGA算法进行了比较实验。

从图2三种算法收敛性的比较可以看出,本文的算法在保证质量的前提下收敛速度更快。

6 结论及下一步的工作

本文提出了一种求解QoS多播路由算法,采用了量子比特相位法更新量子门和自适应调整搜索网格的策略;另外,量子交叉和改进MST算法的引入,不仅增强了种群的多样性,也加快了种群的收敛速度,使得算法性能得以较大提高;与传统量子遗传算法、遗传算法作了比较,实验也表明该算法收敛速度优于传统量子遗传算法和遗传算法;继续以下几个方面的工作:

(1) 改变基因表达结构,进一步减少不可行解的个数。

(2) 改进算法的终止条件,使其具有自适应性,摆脱人为设定;进一步改进旋转量子门,使得算法更好的逃离局部最优。

参考文献

[1] Chen Nian-sheng,Li La-yuan,Dong Wu-shi A multicast routing algorithm of multiple QoS based on widest-bandwidth[J].journal of Systems Engineering and Electronics ,2006,17(3):642-647.

[2] BernarM W.Routing of multipoint connections[J].IEEE JSAC,1998,6:1617-1621.

[3] Han K H,Kim J H .Genetic quantum algorithm and its application to combinational optimization problems[A].Proc of IEEE Conference on Evolutionary Computation[C].Piscataway:IEEE Press2000.1354-1360.

[4] Han K H,Park K H ,et al. Parallel quantum-inspired genetic algorithm for combinatorial optimization problems[A].Prioc of IEEE Conference on Evolutionary Computation[C].Piscataway: IEEE Press2001. 1429-1442.

[5] 刘莹,吴建平.求解带时延约束多播路由问题的启发式遗传算法[J].计算机研究与发展,2003,40(3)381- 386.

[6] 王征应,石冰心.基于启发式遗传算法的QoS 组播路由问题求解[J].计算机学报,2001,24(1):56- 61.

[7] 越民义.最小网络——斯坦纳树问题.上海科学技术出版社,2006 年11月.

量子算法 第4篇

1 知识覆盖问题

通过对考试科目的学习,学生学习掌握的知识储存在头脑中。由于学生个体之间的学习差异,导致每个学生大脑中储存和掌握的情况具有不确定性。考试的目的在于,通过试卷测试对学生学习情况做出相对确定的评价。科目知识是相对固定的,我们总是将科目知识当作图谱,按图索骥地构造出试卷去测试学生大脑中相关区域中知识的学习掌握情况,即是否掌握,掌握水平如何等。但在目标试卷生成以前,题库中的考题相对与目标试卷而言表现为存在或不存在两种可能形态。基于此,本文引入量子态对考题进行描述、编码和处理。

1.1 试卷分布构成

试卷覆盖是指由计算机考试系统生成一组考题集合(试卷)对测试区域各个知识点的涵盖。试卷的目的是系统地测试和评价试卷覆盖知识区域内学生的学习情况,并对这些数据进行处理,获得详尽而准确的信息,传送到需要这些信息的教师和教学管理部门。

考题是由考点以问题的形式构成的。其中考点与考试科目的相关知识点对应。因此考题的分布是考试系统获取学生学习信息的关键因素之一,其覆盖范围以及分布优化也随之成为研究领域中的重点。

1.2 试卷覆盖问题

试卷由数量有限的考题组成,每道考题包含若干有针对性的知识点所设置的考点。这些考点形成了考题的测试范围。如何组织试卷完成对目标区域的检测,就是考试系统覆盖性的问题。考题分布优化的任务就是在保持试卷结构完整的前提下,动态调整考题组成,以获得尽可能大的覆盖率,也就是使试卷能获得更广泛的信息。在保持考点充分覆盖的前提下,引入以下定义。

假设考察科目所涵盖的知识范围用集合S表示,组成每套试卷的考题用集合Q={qi,i=1,2,...,n}表示,每道考题测试的知识范围为ci,试卷的测试目标知识区域为则理想的探测效果为为试卷有效覆盖知识区域的度量(考点数),d2=‖A‖为目标科目知识区域的度量(知识点数),则称ρ=d1/d2为试卷覆盖度。

覆盖性问题不仅反映了试卷所能测试的范围,而且通过合理的覆盖控制还可以使试卷中的考题组合得到优化,提高试卷的命题质量。

1.3 约束条件

我们采用以下公理化方式对知识覆盖问题进行描述(目标):在考题集合Q={q1,q2,...,qn}中求一个子集T作为试卷,使得满足以下约束条件。

(1)各考题满足试卷总体约束条件;

(2)试卷覆盖度ρ最大;

(3)考题数目‖T‖为最少。

3 量子遗传算法的考题分布优化

试卷的考题分布优化是一个多目标优化问题,需要在考题数与知识覆盖率之间达到平衡。即在保持试卷中考题数目与题型符合命题要求的情况下,尽可能增加试卷的知识覆盖度,使考题获取最广泛的测试信息。

3.1 量子遗传算法

量子遗传算法是量子计算与遗传算法相结合的产物。它以量子计算的一些概念和理论为基础,用量子比特编码来表示染色体,用量子门作用和量子门更新来完成进化搜索[2]。

我们根据考题在科目知识中的分布和权重(主要是指命题价值)按字典序编号,形成知识地图的坐标。由于题库中的考题在目标试卷生成以前具有不确定性,即在目标试卷中既可能存在,也可能不存在。这符合量子力学中的测不准原则。我们对这些编号进行量子编码,并用量子遗传算法在命题规则的约束下进行知识分布优化。

3.1.1 量子编码

1)量子态引入

我们用Dirac算符|↑>和|>分别表示考题在目标试卷中表现为存在或不存在的两种可能形态。若用“1”表示存在,用“0”表示不存在。考题以叠加态的形式存在。即将一个量子比特可能处于|0>和|1>之间的中间态。可表示为:

其中α和β分别是|0>和|1>的概率幅,且满足下列归一化条件:

式(3)中,|α|2表示量子比特的观测值在|0>状态的概率投影,|β|2表示量子比特的观测值在|1>状态的概率投影。

定义2.1满足式(2)和式(3)的一对实数α、β称为一个量子比特的概率幅,记为[α,β]T。

定义2.2角度ζ(ζ∈[-π/2,π/2])定义为一个量子比特的相位,即ζ=arctan(β/α)。

2)染色体量子编码

我们从题型、章节、考题三个方面对试卷的染色体及种群进行量子编码。

其中,m为染色体的基因个体表示知识分布数量(章节数);k为每个基因的量子比特数表示每道题的属性数量。n个这样的个体构成的种群Q(t)={q1t,q2t,...,qnt}表示试卷,其中n为题型数量。

3.1.2 量子旋转门

量子旋转门是实现演化操作的执行机构。[3,4,5]图1为量子旋转门示意图。

其操作规律如下:

其中量子旋转门为为更新前染色体中的第i个量子比特,(αi',βi')T为更新后染色体中的第i个量子比特,θi为量子门的旋转角,取值为

其中k是一个与算法收敛速度有关的系数,k的取值必须合理选取,如果k的取值过大,算法搜索的网格就很大,容易出现早熟现象,算法易于收敛于局部极值点,反之,如果k的取值过小,则搜索速度太慢甚至会处于停滞状态。因此,本文将k视为一个变量,将k定义为一个与进化代数有关的变量,如其中t为进化代数,max t是根据待求解的具体问题而设定的一个常数,因此k可以根据进化代数合理地调整网格大小。

函数f(αi,βi)的作用是使算法朝着最优解得方向搜索。本文采用表1的搜索策略。其原理是使当前解逐渐逼近搜索到的最佳解,从而确定量子旋转门的旋转方向。其中符号e表示α和β的乘积,即e=α*β,e的正负值代表此量子比特的相位ζ在平面坐标中所处的象限。如果e的值为正,则表示ζ处于第一、三象限,否则处于第二或第四象限。

在表1中,α1和β1是搜索到的最佳节的概率幅,α2和β2是当前解的概率幅,当e1,e2同时大于0时,意味着当前解和搜索到的最佳解均处于第一或第三象限。当|ζ1|>|ζ2|时,表明当前解应朝着逆时针方向旋转,其值为+1,反之为-1。同理可推出其他三种情况。

这样,量子门的更新过程可以描述为qjt+1=G(t)*qjt其中,上标t为进化代数,G(t)为第t代量子门,为第t代某个个体的概率幅,qjt+1为第t+1代相应个体的概率幅。

3.1.3 量子遗传算法流程(见图2)

(1)初始化种群,种群Q={q1,q2,...,qn},其中qj为种群中的第j个个体。令种群中全部的染色体基因(αi,βi)(i=1,2,...,m)都被初始化为这意味着一个染色体所表达的是其所有可能状态的等概率叠加。同时初始化进化代数t=0。

(2)量子坍塌法测量:对处于叠加态的量子位进行观测时,叠加态将因此受到干扰,并发生变化,称为坍塌。扰动使为叠加态坍缩为基本态。确定种群大小n和量子位的数目m,包含n个个体的种群通过量子坍塌,得到P(t),其中为第t代种群的第j个解(即第j个个体的测量值),表现形式为长度m为的二进制串,其中每一位为0或1。(量子坍塌即对Q进行测量,测量的步骤是生成一个[0,1]之间的随机数,若其大于概率幅的平方,则测量结果值取1,否则取0。

(3)群体的适应度评价,保存最优解作为下一步演化的目标值。

(4)算法进入循环。首先判断是否满足算法终止条件,如果满足,则程序运行结束;否则对种群中个体实施一次测量,获得一组解及其相应的适应度。

(5)根据当前的演化目标,运用量子旋转门进行调整更新,获得子代种群。调整过程为根据式(6)计算量子旋转门的旋转角,并应用式(5)作用于种群中的所有个体的概率幅,即更新Q。

(6)群体灾变:当接连数代的最优个体为局部极值,这时就实行群体灾变操作,即对进化过程中的种群施加一个较大扰动,使其脱离局部最优点,开始新的搜索。具体操作为:只保留最优值,重新生成其余个体。

(7)迭代与终止进化代数t'=t+1,算法转至式(2)继续执行,直到算法结束。

4 仿真试验

为了验证算法的有效性,我们对传统遗传算法(CGA)与量子遗传算法(QGA)所获得的考题知识覆盖度进行仿真对比。我们将考题对考查科目所含知识的覆盖问题简化为:用12个半径为200的圆所代表的考题去覆盖一块12001000的二维平面内用矩形代表的知识区域;种群个体数P=45,量子位数目m=30,运行600代。算法运行结果对照如下。

从图3所示考题知识分布优化中覆盖度的变化特性可以看出在不同阶段的变化中,量子遗传算法优化性能高于传统遗传算法而且稳定性也更强。

5 结论

在试卷中存在考题不合理分布造成的测试阴影和盲区。通过量子遗传算法优化考题分布,使其在保证命题要求的情况下,用最少的考题取得最大的覆盖率,可以有效地消除探测区域内的阴影和盲点。仿真结果也表明,算法能够较好地完成试卷考题的分布优化,从而有效提高试卷的测试能力,对于实际的试卷命制提供了可靠的解决方案和调整依据。本文提出了创新性的考题分布的优化方法,即确立了试卷的覆盖模型,并以此为目标函数,运用量子遗传算法对考题分布进行优化。

参考文献

[1]张维,何蓉.基于参数估计的遗传算法组卷研究[J].云南民族大学学报,2009,18(3):276-278.

[2]Donald A.Prospective Algorithms for Quantum Evolutionary Computation[C].Proc of the2nd Quantum Interaction Symposium(QI-2008),College Publications,UK,2008.

[3]黄友锐.智能优化算法及其应用[M].北京:国防工业出版社,2008:38-40.

[4]唐欢容,蒋浩,郑金华.量子多目标进化算法研究[J].计算机工程与应用,2007,43(13):48.

量子小波变换算法及线路实现 第5篇

量子计算是只有二三十年历史的一门新兴边缘学科,但是近年来却是发展的异常迅速,也受到了越来越多的人关注。1985年,Deutsch提出了量子图灵机的概念,设计出了Deutsch算法和量子计算网络[11]。但是直到1994年Shor提出了可以在量子计算机上实现的分解大数因子算法以及1996年Grover提出了可以在量子计算机上得到加速的无结构空间上的量子算法[3],这才使得人们相信量子计算机超越经典计算机成为了可能。量子计算可以看作是在Hilbert空间中一系列对输入态作用的么正变换。现在已经发现的么正变换包括:傅立叶变换,Walsh-Hadamard变换和各种小波变换。量子Walsh-Hadamard变换是Shor算法和Grove算法的重要组成部分,量子傅立叶变换(QFT)在很多已知的量子算法中扮演了重要的角色。目前在经典计算中,小波变换和傅立叶变换一样成为了非常有用的工具,因此在量子计算领域中,对小波变换的研究也是极其重要的。

在经典计算中,傅立叶变换占据着非常重要的角色,但人们在应用的过程中,发现了它的一些缺陷[12]。为了改进这些缺陷,人们提出了小波这个概念,在傅立叶变换的基础上发展起来,弥补了傅立叶变换的不足。小波变换被誉为数学显微镜,因为它具有多分辨率的特性,而且采用逐渐精细的时域或空域取样步长,这样可以得到对象的任何细节。目前,小波变换在影像处理、数据压缩、语音和人工视觉等方面有着重要的应用。

通过把小波算子分解成更小算子之间的点积、直和、直积的形式,而这些更小的算子可以通过一位和二位的量子门来实现。本文在对Haar小波变换分解时,引入了正移置换矩阵。Haar小波变换矩阵可以用W-H变换矩阵和正移置换矩阵的组合,由此可以得出相关的逻辑线路,经分析后量子Haar小波函数的计算复杂度为O(n2)。在对D(4)小波变换矩阵进行分解过程中,文中引入了下移置换矩阵Q2n,Q2n可在量子傅立叶变换的基础上再分解为一系列二阶和四阶么正矩阵,由此可以得出相关的逻辑线路,其计算复杂度和相关的QFT相同。

1 Haar小波变换矩阵的分解和逻辑线路实现

1.1 正移置换矩阵的定义及其逻辑实现

矩阵Π2n,它的各个元素Πij对于i和j=0,1,,2n-1,可表示为:

Πij=1,当i为偶数,并且j=i/2或i为奇数且j=(i-1)/2+2n-1

Πij=0,其他 (1)

从式(1)中,我们可以把Π2n看作为:

Π2n:|an-1an-2...a1a0>|a0an-1an-2...a1> (2)

从式(2)可以看出Π2n的作用就是让量子位左移。而Π${}_{2{}^n}^t$为Π2n的转置,其作用为让量子位右移。

让我们先来看看四阶正移置换矩阵Π4,它是一个基本量子逻辑门。它的作用可表示为:Π4:|a1a0>|a0a1>,使得相邻两个量子位交换位置。Π4的矩阵形式可表示为:

Π4可以用三个可控非门(CNOT)组成,它的作用效果和量子线路图如图1,图2所示。

从Π4的效果图我们可以看到,对于由n个量子位组成的2n维矢量,只要经过O(n)个Π4门对相邻的量子位进行作用,就能实现n量子位的正移置换矩阵Π2n,它的时间复杂度为O(n)。

因此,得到Π2n的表达式如下:

Π2n=(I2n-2⨂Π4)(Π2n-1⨂I2) (4)

又可以进一步分解为:

Π2n=(I2n-2⨂Π4)(I2n-3⨂Π4⨂I2)(I2n-i⨂Π4⨂I2i-2)(I2⨂Π4⨂I2n-3)(Π4⨂I2n-2) (5)

1.2 Haar小波变换和其线路实现

Haar小波变换可以从小波函数[8]中得到定义。Hoyer[1]通过扩展Kronecker积的递归方式来定义Haar小波矩阵,可以表示为如下形式:

H2n=Π2n((H2n-1,I2n-1)⨂W) (6)

由Hoyer[1]可知,(4)式可以化为:

H2n=Π2n((H2n-1,I2n-1)⨂I2)(I2n-1⨂W) (7)

H2n可以进一步化解为:

H2n = (I2n-1⨂W)(I2n-i⨂W♁I2n-2n-i + 1)(W♁I2n-2 )(Π4⊕I2n-4)(Π2i⊕I2n-2i)(Π2n-1⊕I2n-1)Π2n (8)

我们令H2n=H${}_{2{}^n}^{(1)}$H${}_{2{}^n}^{(2)}$,其中

H2n(1) = (I2n-1⨂W)...(I2n-i⨂W♁I2n -2n-i + 1)

(W⊕I2n-2) (9)

H${}_{2{}^n}^{(2)}$=(Π4⊕I2n-4)(Π2i⊕I2n-2i)

(Π2n-1⊕I2n-1)Π2n (10)

由此,我们能得到如图3所示H2n的完整的逻辑线路图。

由式(8)可以得知,H2n的复杂度主要是由H${}_{2{}^n}^{(1)}$和H${}_{2{}^n}^{(2)}$的复杂度来决定。从图3中可以看出,H${}_{2{}^n}^{(1)}$由O(n)的W-H变换组成,因此,它的复杂度为O(n)。对于H${}_{2{}^n}^{(2)}$的复杂度,我们可以看出(Π2i⊕I2n-2i)是由O(i)个Π4变换得到,由此可以推出H${}_{2{}^n}^{(2)}$的的复杂度为O(n2)。由H2n=H${}_{2{}^n}^{(1)}$H${}_{2{}^n}^{(2)}$得到,H2n的复杂度为O(n2)。

2 Daubechies D小波分解及其逻辑线路的实现

2.1 位元反转置换矩阵

N维位元反转置换矩阵P2n可以通过作用在给定的矢量上的效果来表示。假定Z是一个2n维的向量,且Y=P2nZ,那么对于i=0,1,,2n-1,j由下标i二进制表示的反转得到,Yi=Zj。所以,P2n的矩阵元素可以表示如下:

P2n的量子描述如下:

P2n:|an-1an-2a1a0>|a0a1an-2an-1> (12)

经典计算中的位反转指的是一个向量中各元素下标的二进制表示的反转,而在量子计算中,位反转置换矩阵P2n表现出是对量子位序列的反转。

根据P2n可以通过Π2i分解得到如下形式:

P2n=Π2n(I2⨂Π2n-1)(I2i⨂Π2n-i)(I2n-3⨂

Π8)(I2n-2⨂Π4) (13)

由式(5)和式(13)可以得到,经过O(n2)个Π4作用后,就能实现n个量子位的位反转置换矩阵P2n,其时间复杂度为O(n2)。其逻辑线路图如图4所示。

2.2 量子快速傅立叶变换(Quantum FFT)及其有效线路图

对于2n维的向量,Cooley-Tukey快速傅立叶变换可分解为:

$F{}_{2{}^n}=\underset{¯}{F}{}_{2{}^n}{\rm P}{}_{2{}^n}$ (14)

可根据文献[9]得到$\underset{¯}{F}{}_{2{}^n}$的线路图如图5所示。

图中,θjk是一个二量子门作用在第j和第k量子位上。因此,$\underset{¯}{F}{}_{2{}^n}$的时间复杂度为O(n2)。

2.3 Daubechies D小波的分解及其线路实现

由文献[4]可以得到四阶Daubechies小波的2n维的矩阵可以表示如下:

$D{}_{2{}^n}^{(4)}=\left(\begin{array}{ccccccccccc}c{}_0& c{}_1& c{}_2& c{}_3& & & & & & & \\ c{}_3& -c{}_2& c{}_1& -c{}_0& & & & & & & \\ & & c{}_0& c{}_1& c{}_2& c{}_3& & & & & \\ & & c{}_3& -c{}_2& c{}_1& -c{}_0& & & & & \\ ⋮& ⋮& & & & & \ddots & & & & \\ & & & & & & & c{}_0& c{}_1& c{}_2& c{}_3\\ & & & & & & & c{}_3& -c{}_2& c{}_1& -c{}_0\\ c{}_2& c{}_3& & & & & & & & c{}_0& c{}_1\\ c{}_1& -c{}_0& & & & & & & & c{}_3& -c{}_2\end{array}\right)(15)$

其中$c{}_0=\frac{(1+\sqrt{3})}{4\sqrt{2}},c{}_1=\frac{(3+\sqrt{3})}{4\sqrt{2}},c{}_2=\frac{(3-\sqrt{3})}{4\sqrt{2}},c{}_3=\frac{(1-\sqrt{3})}{4\sqrt{2}}$,对于经典计算和所给的稀疏结构来说,D2n(4)的变换需要O(2n)的复杂度。

式(15)所给出的矩阵D2n(4),Hoyer[1]给出了它的分解:

D2n(4) = (I2n-1⨂C1 )S2n(I2n-1⨂C0) (16)

其中,

S2n为置换矩阵,它的元素Sij=1,如果i=j且i为偶数或者i+2=j(mod2n)且i为奇数。S2n可以分解为两个置换矩阵之积,如下所示:

S2n=Q2nR2n (18)

其中:

$Q{}_{2{}^n}=\left(\begin{array}{cccccccc}0& 1& & & & & & \\ 0& 0& 1& & & & & \\ 0& 0& 0& 1& & & & \\ 0& 0& 0& 0& 1& & & \\ ⋮& ⋮& ⋮& & & \ddots & & \\ ⋮& ⋮& ⋮& & & & \ddots & \\ 0& 0& 0& \cdots & 0& 0& 0& 1\\ 1& 0& 0& \cdots & 0& 0& 0& 0\end{array}\right)(19)$

$R{}_{2{}^n}=\left(\begin{array}{cccccccc}0& 1& 0& 0& 0& & & \\ 1& 0& 0& 0& 0& & & \\ 0& 0& 0& 1& 0& & & \\ 0& 0& 1& 0& 0& & & \\ & \ddots & \ddots & \ddots & \ddots & & & \\ & & & & & & & \\ & & & & & & 0& 1\\ & & & & & & 1& 0\end{array}\right)(20)$

容易看出,R2n=I2n-1⨂N, 其中

${\rm N}=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$

,由此,D2n(4)可以表示如下:

D2n(4) = (I2n-1⨂C1 )Q2n(I2n-1⨂N)(I2n-1⨂C0)

=(I2n-1⨂C1)Q2n(I2n-1⨂C) (21)

其中,

因此,D2n(4)的逻辑线路和复杂度可以归结到Q2n的逻辑线路和复杂度。

由文献[2]可以得到Q2n的分解可以基于通过FFT算法来求得Q2n,即:

Q2n=F2nT2nF${}_{2{}^n}^{*}$ (23)

F*2n表示为F2n的共轭转置,T2n是一个对角矩阵,其可表示为:

${\rm T}{}_{2{}^n}=\text{d}\text{i}\text{a}\text{g}\left\{1,\omega {}_{2{}^n},\omega {}_{2{}^n}^2,\cdots ,\omega {}_{2{}^n}^{2{}^n-1}\right\}$,其中$\omega {}_{2{}^n}=e{}^{\frac{-2i\pi }{2{}^n}}$。T2n可以进一步分解为:

T2n=(G(ω${}_{2{}^n}^{2{}^{n-1}}$)⨂I2n-1)(I2i-1⨂G(ω${}_{2{}^n}^{2{}^{i-1}}$)⨂I2n-i)

(I2n-1⨂G(ω2n)) (24)

其中:

T2n的逻辑线路图如图6所示。

通过利用Cooley-Tukey分解,即由和可以得到Q2n的进一步的表示:

$Q{}_{2{}^n}=\underset{¯}{F}{}_{2{}^n}{\rm P}{}_{2{}^n}{\rm T}{}_{2{}^n}{\rm P}{}_{2{}^n}\underset{¯}{F}{}_{2{}^n}^{*}$ (26)

因为已知$\underset{¯}{F}{}_{2{}^n}$、P2n和T2n的线路图,因此可以很容易地得到D2n(4)的线路图如图7所示。

由此,可以看出Q2n和D2n(4)的复杂度同量子FFT算法相同,所以D2n(4)的复杂度为O(n2)。

3 结 论

量子并行性是量子计算区别于经典计算的一个重要特征,正是这个特征,使量子计算具有经典计算不可比拟的计算效率。可以看到,对于Haar小波和Daubechies D小波变换的稀疏矩阵,经典计算需要指数级的复杂度,而这在现实中是不可能实现的。由于量子并行性的特性,量子算法只要多项式的复杂度就能实现,因此在物理上完全可以实现。

对Haar小波和Daubechies D小波的分解,几乎都用到了置换矩阵,因此,置换矩阵在建立量子小波变换的算法中扮演了一个很重要的角色。而本文所提到的Π2n、P2n和Q2n这样的置换矩阵在经典计算中很少见到,也很难实现,与之相对的量子计算中实现却比经典计算容易得多。

参考文献

[1]Hoyer P.Efficient quantum transforms.Los Alamos preprint archive,http://xxx.lanl.gov/archive/quant-ph/9702028,Feb.1997.

[2]Van Loan C.Computational Frameworks for the Fast Fourier Trans-form.SIAMPublications,Philadelphia,1992.

[3]Nielson M A,Chuang I L.Quantum Computation and Quantum Infor-mation.Cambridge:Cambridge University Press,2000.

[4]Press W H,Teukolsky S A,Vetterling W T,Flannery B P.Numerical Recipes in C:The Art of Scientific Computing.2nd Edition,Cam-bridge Univ.Press,1992.

[5]Glassman J A.A Generalization of the Fast Fourier Transform.IEEE Transactions on Computers,1970,C-19(2):105116.

[6]Meir Drubin.Kronecker Product Factorization of the FFTMatrix.IEEE Transactions on Computers,May1971:590593.

[7]Daubechies I,Sweldens W.Factoring wavelet transforms into lifting steps.J of Fourier Analysis and Application,1998,4(3):247269.

[8]Hardle W,Kerkyacharian G,Picard D.Wavelets,Approximation and Statistical Applications.New York:Springer,1998.

[9]Barenco A,Ekert A,Suominen K A,et al.Torma.Approximate quan-tum Fourier transform and decoherence.Physical Review,1996,A(54):139146.

[10]张旭俊.用小波变换矩阵作小波分析.电力系统自动化,1999,23:3638.

[11]何雨果,孙吉贵.基于Haar小波的多尺度分析量子电路.科学通报,2005,50(20):23142316.

量子算法 第6篇

遗传算法GA(Genetic Algorithm)在处理红外图像时容易陷入局部最优、早熟收敛和收敛速度慢的困境。量子遗传算法QGA(Quantum Genetic Algorithm)存在收敛速度慢和易陷入局部极值等问题[2]。后来发展出现两种模型：一类是基于量子多宇宙特征的多宇宙量子衍生遗传算法QIGA(Quantum Inspired Genetic Algorithm)，多宇宙是通过分别产生多个种群获得，并没有利用量子态，因而仍属于常规遗传算法;另一类是基于量子比特和量子态登加特性的量子态遗传算法GSGA(Quantum State Genetic Algorithm)，由于所有量子个体都朝一个目标演化，如果没有交叉操作，极有可能陷入局部最优[3]。

本文提出的改进算法有别于传统旋转门策略，采用动态调整角度幅度值和方向，由收敛因子、适应度因子和变异加速因子共同决定变异概率。其最大特点是保持种群多样性的能力强，收敛速度快，可提高全局寻优能力。

1 改进量子遗传算法描述

1.1 量子旋转角大小调整

旋转角的幅度不但对算法收敛的速度有一定的影响，而且会影响到算法收敛的效果，不合适的幅度值导致算法容易陷入局部最优解的适应值差值。

量子旋转角θi为：

αi、βi为第i个量子比特的概率幅对，△θ为每个量子bit的旋转角度，调整如下：

式中,fb为搜索到的最优个体b的适应度，f(x)为当前个体x的适应度。若当前个体与最优个体较远时，△θ的值较大，即扩大搜索域;反之当△θ的值较小时，可以实现细搜索，有利于得到最优解。本文动态调整旋转角在0,0.25π之间。

对个体qj′进行测量，得到一个确定解x，计算出其适应度f(x)并与该个体的当前适应度f(b)比较，若f(x)>f(b)，则旋转每个向量αi、βi，使其向着有利于出现xi的方向旋转;若f(x)

1.2 量子旋转角方向调整

设染色体二进制形式为xt，当前的最优解为bt。令θit表示染色体的第i(i=1,2,,m)个基因位，先将旋转门Rδ作用到该基因位上。Rδ如下：

式中，η(i)为位影响因子，表示染色体各基因位的取值对其在搜索空间上所处位置的影响程度的不同，位越高影响力越大，η(i)∈(0,1)=i/ei;θit为旋转角度的大小;θi0为基因初始位，取值为45°;D(θit,bit)为差距度量函数，定义为：

则有：

其中，S(△θit)用来决定旋转方向，具体操作如下：当xt不优于bt时，以bt来控制旋转方向,有S(△θit)=-1;当xt优于bt时，以xt来控制旋转方向，有S(△θit)=(-1)xit：。当基因位距离演化目标远时，旋转角度大，则旋转快，从而进行粗粒度搜索;当距离演化目标近时，旋转角度小，旋转慢，从而进行细粒度搜索。Rδ门通过定义位影响因子和差距度量函数，使得基因位的更新更加快速高效。

1.3 量子染色体变异更新体制

采用全干扰交叉进行量子交叉操作时，种群中所有染色体均参与交叉。

通过染色体间的汉明距来描述改进后当前群的每个染色体观测态与最优染色体观测态的相似度，然后通过相似度计算收敛因子S:

其中,为平均汉明距，即平均相似度;dmax为最大汉明距dmin为最小汉明距，即最大相似度和最小相似度。

染色体的适应度因子为：

其中，fj表示第j个个体的适应度。

染色体间变异加速因子h(n)为：

式中，n为进化代数;fmax(n)为第n代的最大适应度值;常数a∈(0,1)。

根据每个染色体观测的收敛因子，适应度因子和变异加速因子确定该染色体的量子变异概率为：

pmj为第j个个体的量子变异概率。

收敛因子和适应度因子能够保持优势种群的稳定性[6]。当种群收敛时，收敛因子能提供精确的搜索能力，使适应度因子便于优良个体朝更优方向进化;变异加速因子可提高全局寻优能力。

1.4 图像检测

设图像的检测域T、宽度P和高度Q在源图像S上平移，检测域覆盖下的源图像区域为子图Si,j，(i,j)为子图左上角相对S上的坐标，称为最佳检测参考点，归一化互相关函数定义如下：

如果将源图像认为是二维网格结构，则归一化互相关函数就可以视作三维空间中一个仅在网格上取值的曲面，最佳检测就是寻求与曲面极值点对应的最佳参考点(i,j)的坐标值，这样检测问题转化为最优化问题。

检测性能评价函数使用了三个指标：漏检率、误检率和检测时间消耗。假设用Pmiss表示漏检率，Pfalse表示误检率，Nmiss表示未检测到的数目，Nallture表示总的真实重复图像数目，Nfalse表示错误的检测数目，N表示检测到的数目，则：

检测时间消耗T用秒来衡量。

1.5 算法流程

算法步骤完整地描述如下：

(1)初始化个体，按量子基因比特编码方式对个体进行编码，得到第一代种群;

(2)对个体进行图像检测，获得空间图像归一化互相关函数。归一化互相关函数即作为对个体进行评价的适应度评价函数，并保留此代中的最优个体。若得到满意解，则算法终止并输出结果，否则继续迭代计算;

(3)使用旋转门调整策略更新量子群;

(4)使用交叉操作更新量子群;

(5)遗传代数n=n+1，算法转至步骤(2)继续进行，直到算法结束;

(6)计算检测图像评价指标函数，输出检测结果。

2 实验仿真

实验中选用与之相同的红外图像如图1所示，运行环境都是P4,3.0 GHz,2 048 MB DDR3。编程软件为Matlab7.0，运行蒙特卡洛50次随机仿真实验。

对图1作边缘检测，用本文方法对图像进行检测的轮廓与图像真实形状最接近，边缘最清晰，具有良好的检测结果,如图2所示。GA的目标函数要经过不断尝试才能得出结果，同时后期数据存在局部局限，如图3所示;QGA的量子旋转门需要多次寻找，一旦错过导致染色体无法更新到最优解，如图4所示。QIGA中的多宇宙是通过分别产生多个种群获得的，并没有利用量子态，如图5所示。GSGA中所有量子个体都朝一个目标演化，最终陷入局部最优，如图6所示。本文算法保持种群多样性的能力强及收敛速度快，提高全局寻优，因此检测结果最好。

为验证本文方法的有效性,对图1进行指标检验，实验结果如表1所示。实验结果表明，本文算法检测方法都要明显优于其他的检测方法。这是因为在量子门更新后，由于计算了当代种群的每一个个体最适合自身进化的量子变异概率，且收敛因子提供了精确搜索能力，适应度因子考虑个体差异，便于优良个体朝更优方向进化，变异加速因子增强了全局搜索能力。

从时间消耗的角度分析，本文算法收敛因子、适应度因子和变异加速因子共同决定的量子变异能弥补单独量子门更新所带来的不足，消除了量子比特与量子门调整作用的计算过程对算法执行时间的影响，因此算法运行速度快，适合实时应用。

通过对量子旋转门大小和方向的调整，同时对量子染色体变异操作，使得改进后的QGA很适合于求解最优解。本文基于改进量子遗传算法的红外图像检测，通过量子Rδ门定义位影响因子和差距度量函数，使得基因位的更新更加快速高效，同时对收敛因子、适应度因子和变异加速因子的操作，引入染色体交叉机制，维护了群体的稳定性与多样性，提高了优良个体朝更优方向进化，提高了全局寻优能力。

参考文献

[1]张莎莎,谷延锋,张钧萍,等.一种基于量子遗传算法的红外图像检测方法[J].哈尔滨工业大学学报,2007,39(9):1427-1430.

[2]冯巍巍,魏庆农,汪世美,等.基于混合遗传算法的偏振双向反射分布函数优化建模[J].红外与激光工程,2008,37(4):743-747.

[3]朱明,金炜东,普运伟,等.基于Chirplet原子的雷达辐射源信号特征提取[J].红外与毫米波学报,2007,26(4):302-306.

[4]张宗飞.一种改进型量子遗传算法[J].计算机工程,2010,36(6):181-183.

[5]郭荣华,李斌,庄镇泉.基于混合量子遗传算法的嵌入式系统软硬件协同综合算法[J].量子电子学报,2008,25(4):443-451.

量子算法 第7篇

校车问题属于车辆运输问题, 同时还受两个因素约束:车辆载重约束和时限约束。这类问题可描述如下:给定有向图G= (V, E) , 其中V为校车往返经过的停靠点的集合, E为边的集合, 是带权边, 且每条边都有一个服务需求量qij≥0 (i, j为两个相邻停靠点, 且) , 如何寻找一条回路, 使该回路所有边的需求量都得到满足且总服务费用最少?关于该问题的解法有精确算法和启发式算法, 精确算法有动态规划、非线性规划[1]等;启发式算法有:SFC法[2], 禁忌搜索法, 遗传算法[3]等。在解决实际的大规模问题时一般采用启发式算法。

1 校车问题的数学模型

数学模型如下:

其中:cij表示有服务时停靠点i到j的平均运输费用;c/ij表示无服务时停靠点i到j的平均运输费用;xijk是服务边决策变量, 当车辆k由停靠点i到停靠点j时取1, 否则取0;F为驾驶员的平均固定年费用;ρi为停靠点i的服务量;Qk为车辆k的最大容量;zi表示是否在停靠点i停靠, 有停靠取1, 否则取0;V为所有停靠点的集合;S为所有车辆的集合。

式 (1) 满足所需服务最小;式 (2) 为运输工具容量的约束条件, 满足在路线上行驶的每台校车都不超过其容量;式 (3) 保证路线连续;式 (4) 保证每个需要停靠的停靠点至少有一个客户;式 (5) 保证车辆行走路线不形成内部闭环;式 (6) 和式 (7) 保证满足取整数约束。

2 改进的量子行为粒子群算法

量子行为粒子群算法是一种启发式算法, 如今在解决网络路由, 非线性方程组[4]等方面得到广泛应用。本文根据校车运行规律, 在传统的量子行为粒子群算法的基础上, 加入回路扫描思想和分解思想, 提出了一种解决校车问题的改进量子行为粒子群算法。具体算法可以表示为:

设定参数, 包括最大迭代次数, 种群大小P (τ) ={a1 (t) , a2 (t) , , an (τ) }, 其中τ为迭代次数。

(1) 初始化种群P (0) ={a1 (0) , a2 (0) , , an (0) }及种群中每个粒子的位置向量;

(2) 根据适应值函数计算所有粒子的适应值P (0) ={f (a1 (0) ) , f (a2 (0) ) , , f (an (0) ) }。适应值函数为:

(3) 根据粒子适应值, 由高到低的顺序排列粒子;

(4) 根据粒子适应值, 把当前所有粒子划分成许多子群, 每个子群中的粒子围绕在本群体中具有最优适应值的粒子周围;

(5) 运用文献[5]提到的回路点扫描法对每个子群进行扫描;

(6) 根据式改变粒子的位置, 其中t为迭代次数, β为收缩扩张系数, 调节它的值可以控制算法的收敛速度, pi其中为个位极值, pg为全局极值, mbest是局部最好位置和平均值。

(7) 转 (2) , 直到条件满足。

本文通过大量的实验仿真确定相应的参数, 图1, 图2和图3 是本算法中三个参数对算法性能的影响曲线, 从图中可以看出选取b=1.3, u=1, 是较合理的选择。

3仿真实例分析

数据来自甘肃民族师范学院所在的合作市, 校车运行网点由甘肃民族师范学院新、老校区出发并最终返回甘肃民族师范学院所行驶的全部网点构成。

校车运行区域为合作市区, 停靠点为16个, 设单位距离运输费用为1元, 车辆载客量为80, 算法最大迭代代数为2000, 图4为最后的计算结果, 图5为本文算法和基本粒子群算法最优解进化的比较, 图6为本算法采用粒子数为10个, 迭代代数为100, 目标值的变化曲线。从上面的仿真数据可知:本文提出的算法求解校车问题是非常有效的。

4 小结

本文提出了基于校车问题的改进量子行为粒子群算法, 该算法保持了种群的多样性, 有效地避免了算法陷入局部最优, 并通过实例验证, 证明了该算法是可行和有效的。

参考文献

[1]汪寿阳、赵秋红、夏国平.集成物流管理系统中定位—运输路线安排问题的研究[J].管理科学学报, 6, 69-75 (2000) .

[2]Chan Y, Carter W B, Burnes M D.随机处理的多车辆的路由问题[J]。计算机与运营研究, 28, 803-826 (1999) .

[3]李敏强, 寇纪淞, 李丹。遗传算法及其应用[M].北京:科学出版社, 1-47 (2002) .

[4]赵佶, 徐文伯, 孙钧。解决非线性方程组的粒子群优化算法[J].计算机应用研究, 24, 56-59 (2007) .

量子算法 第8篇

在智能方法研究领域, 大部分问题都可以归结为优化问题。常用的经典优化算法都对问题有一定的约束条件, 如要求优化函数可微等。粒子群优化算法作为一种仿生算法是一种模拟生物智能行为的优化算法, 由于其几乎不存在对问题的约束, 同遗传算法等其他人工生命计算相比, 粒子群算法概念简单, 容易实现, 调节参数较少。因此, 粒子群优化算法在各种优化问题中得到广泛应用[1,2]。

但经典的粒子群优化算法存在着在搜索后期容易陷入局部极值点, 过早成熟收敛的问题。针对这些问题, 文中讨论了一种新型的基于量子优化的粒子群优化算法, 并对其性能进行了对比分析。

2. 量子粒子群优化算法

2.1 基本粒子群优化算法

我们经常能够看到成群的鸟、鱼或其它生物, 这些生物的聚集行为有利于它们觅食和逃避捕食者。生物的群落动辄以十、百、千甚至万计, 它们是如何迅速完成聚集、移动等行为呢?这些群落一般都不存在一个统一的指挥者, 那么一定有某种潜在的能力或者规则保证了这些行为的同步。科学家们普遍认为上述行为是基于不可预知的种群社会行为中的群集智能。

粒子群优化 (Particle Swarm Optimization, PSO) 算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解, 它包含有进化计算和群集智能的特点。

基本粒子群优化算法可描述如下:设在一个D维的目标搜索空间中, 有m个粒子组成一个群落, 第i个粒子的位置用向量Xi=[Xi1, Xi2, ..., Xi D]表示, 飞行速度用Vi=[Vi1, Vi2, ..., Vi D]表示, 第i个粒子搜索到的最优位置为Pi=[Pi1, Pi2, …, Pi D], 整个群体搜索到的最优位置为Pg=[Pi1, Pi2, ..., Pi D], 则用下式更新粒子的速度和位置:

式中, i=1, 2, ..., m, 分别表示不同的粒子。c1, c2为大于零的学习因子或称作加速系数, 分别调节该粒子向自身己寻找到的最优位置和同伴已寻找到的最优位置方向飞行的最大步长, 通常情况下取cl=c2=2;rl, r2为介于[[0, 1]之间的随机数;n为迭代次数, 即粒子的飞行步数。将V, 限定一个范围, 使粒子每一维的运动速度都被限制在[-Vmax., Vmax]之间, 以防止粒子运动速度过快而错过最优解, 这里的Vmax根据实际问题来确定。当粒子的飞行速度足够小或达到预设的迭代步数时, 算法停止迭代, 输出最优解。

2.2 标准粒子群优化算法

在基本粒子群优化算法的基础上, Shi等学者对前面的公式 (1) 进行了修正, 引入惯性权重因子ω:

惯性权重是用来控制粒子以前速度对当前速度的影响, 它将影响粒子的全局和局部搜索能力。选择一个合适的ω可以平衡全局和局部搜索能力, 这样可以使算法以最少的迭代次数, 迅速找到最优解。采用公式 (3) 的粒子群优化算法被称为标准粒子群优化算法。在标准PSO粒子群算法中, 粒子的收敛是以轨道的形式实现的, 并且粒子的速度总是有限的, 因此粒子的搜索空间是一个有限的区域, 不能覆盖整个搜索空问, 所以标准PSO算法也存在不能保证收敛到全局最优解的问题。

2.3 基于量子优化的粒子群算法

在量子优化计算中, 最小的信息单元用量子位表示, 如果从量子力学的角度, 将粒子定义在由概率密度函数决定的一个量子空间内, 就可以得到一种新型的PSO算法-量子粒子群优化 (QPSO) 算法[5]。这种算法中, 认为粒子具有量子行为, 每一个粒子在搜索空间移动时, 存在着一个以Pbest为中心的Delta势阱。由于在量子空间中的粒子满足聚集态的性质完全不同, 粒子移动时没有确定的轨迹, 这使粒子可以在整个可行解空间中进行探索寻找全局最优解, 因而QPSO算法的全局搜索能力远远优于经典的PSO算法。

在QPSO算法中, 设种群规模为M, 在进化过程中, 粒子以一定概率取加或减, 更新每个粒子的位置, 并生成新的粒子群体, 由公式 (5) 至 (8) 决定:

其中, a, u为0至1之间的随机数, mbest是粒子群pbest的中间位置, 即平均值, b为收缩扩张系数, 在QPSO收敛过程中线性减小, generation为当前进化代数, maxgeneration为设定的最大进化代数。

3、量子粒子群算法的性能评价

为了测试量子粒子群算法的优化效果, 本文使用Sphere、Rastrigin两个常用的标准测试函数来评价算法的性能。

Sphere函数形式为

这是一个简单的单峰函数, 各类优化算法都能较为容易地发现全局最优解, 它的简单性有助于研究优化算法在问题维度上的效果。

Rastrigin函数形式为

它是Sphere类函数的多峰版本, 具有大量按正弦拐点排列的、很深的局部最优点。全局最优值为f3 (x) =0在点x={0, ..., 0}处获得。优化算法很容易在通往全局最优点的路径上陷入一个局部最优点。

本文所使用的测试函数的初始化均使用标准初始化范围, 在基本的PSO中取ω=1, 在标准的PSO中, ω∈[0.9, 0.4], 其他参数:c1=c2=2, 三种算法群体规模大小为40, 优化变量的维数为40, 最大迭代次数数为1000。

图1给出了量子粒子群优化算法与基本粒子群、标准粒子群算法的优化结果比较。

通过观察以上结果, 可以看到, 无论是单峰函数, 还是多峰函数, 基于量子行为的PSO它具有更强的全局收缩能力, 能在后期找到全局最优值。对于标准的PSO来说, 早期收敛速度快, 容易陷入"早熟", 得不到全局最优值。而对基本的PSO, 其整体性能是最差的。

4、结论

粒子群优化算法是对问题的约束较少的一种仿生算法, 但经典的PSO算法存在着早熟和不能保证全局最优的问题。针对上述问题我们提出讨论了一种新型量子粒子群优化算法。通过标准测试函数进行的性能评价证明文中讨论的量子粒子群优化算法能较好地克服上述问题。

摘要：本文在简要介绍基本粒子群优化 (PSO) 算法的基础上, 讨论了一种新型量子粒子群优化算法, 并给出了其实现方式, 并通过标准测试函数对其进行性能对比评价。仿真结果表明, 这种量子粒子群优化算法能给出很好的优化结果。

关键词：粒子群算法,量子优化,性能评价

参考文献

[1]沈林成, 霍霄华, 牛轶峰.离散粒子群优化算法研究现状综述[J].系统工程与电子技术, 2008, 30 (10) :1986-1990.

[2]赵会洋, 王爽, 杨志鹏.粒子群优化算法研究综述[J].福建电脑, 2007 (3) :40-41.

[3]崔光照, 李小广, 张勋才, 等.基于改进的粒子群遗传算法的DNA编码序列优化[J].计算机学报, 2010, 33 (02) :311-317.

[4]袁小芳, 王耀南.基于混沌优化算法的支持向量机参数选取方法[J].控制与决策:2006, 21 (1) :111-114.