一种新型量子粒子群算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇一种新型量子粒子群算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要： 本文提出一种基于量子的连续粒子群算法(Quantum Continuous Particle Swarm Optimization - QCPSO)，使用量子比特编码粒子，模拟量子粒子坍塌的随机观察方法以生成种群，运用量子旋转门来产生新的种群，引入自适应变异算子保证种群多样性。性能测试表明，对于高维优化问题，本文提出的QCPSO比经典粒子群算法(PSO)和经典量子粒子群算法(AQPSO)具有更高的精度。

Abstract： In this paper，a novel algorithm，called the Quantum Continuous Particle Swarm Optimization algorithm - QCPSO，is proposed, based on the combination of the quantum theory with the evolutionary theory． By adopting the qubit particle as the representation，QCPSO can represent a linear superposition of solutions and bring diverse individuals by imitating the quantum collapse to random observation the new populations. The evolution of quantum particles can also pilot the evolution with better diversity than the classical particle swarm optimization method by adopting adaptive mutation．The performance test indicates that the QCPSO possesses better global search capacity than the basic PSO and QPSO when confronting high dimension problems.

关键词： 粒子群；量子理论；比特；自适应变异

Key words： PSO；quantum theory；bit；adaptive mutation

中图分类号：TP39 文献标识码：A文章编号：1006-4311（2011）01-0181-02

0引言

粒子群优化算法是由Kennedy和Eberhart等于1995年提出的一种基于种群搜索的自适应进化计算技术[1-2]。算法最初受到飞鸟和鱼类集群活动的规律性启发，利用群体智能建立了一个简化模型，用组织社会行为代替了进化算法的自然选择机制，通过种群间个体协作来实现对问题最优解的搜索。

量子计算特点主要体现在量子态的叠加（Superposition）、纠缠（Entanglement ）以及干涉（Interference）等性质上，许多计算上的优势如量子并行（Quantum Parallelism）等皆由此而产生。近年来很多学者基于此提出了一些基于量子理论的进化算法。它以量子计算的一些概念和理论为基础，用量子位编码来表示染色体，用量子门作用和量子门更新来完成进化搜索，具有种群规模小而不影响算法性能、同时兼有“勘探”和“开采”的能力、收敛速度快和全局寻优能力强的特点。文献[3-4]分别提出了量子遗传算法、遗传量子算法和并行量子遗传算法，并用来求解组合优化问题，结果表明，遗传量子算法的性能大大优于传统遗传算法，但该算法不适于用来求解连续函数的优化问题，特别是多峰连续函数优化问题。受此启发，本文将量子编码和量子坍塌等性质与粒子群进化思想融合，提出一种基于量子理论的连续粒子群算法(QCPSO)，并对该算法进行参数影响分析和性能测试。

1量子粒子群算法(QCPSO)

和经典的PSO算法不同，QCPSO是将经典PSO算法与量子理论相结合，基于量子计算的概念和理论，使用量子比特编码粒子，由粒子的概率幅表示，一个量子粒子包含了多个基本粒子状态的信息。通过模拟量子粒子坍塌的随机观察可以带来更加丰富的种群，极大的丰富了种群的多样性。通过量子的叠加特性和量子变迁的理论，运用量子旋转门来产生新的种群。粒子的更新是根据粒子的相位变化以及和全局最优粒子、粒子历史最优的相位差来进行的。具体算法描述如下：

1.1 粒子编码粒子位采用量子比特表示，称为量子位，量子位具有两个基本态,分别是?Z0>态和?Z1>态，在任意时刻，量子位的状态可以是基本态的线性组合，被称为叠加态，如式所示：

φ>=α0>+β?Z1>（1）

其中α和β是复数，并被称为概率幅，也就是说，我们得到量子位状态?Z0>的概率是α，得到量子位状态?Z1>的概率是β。α和β的关系如式：φ>=cosθ0>+sinθ?Z1>（2）

其中θ为量子位的相位，并且和概率幅之间的关系满足下式：

θ=arctan（3）

因此，粒子的量子表示方式可以通过使用概率幅或相位加已表示，如（4）式和（5）式。

α α α… αβ β β… β（4）

θ?佐θ?佐θ?佐…?佐θ（5）

在初始化的时候，首先将粒子在[0，1]的区间内初始化，然后再映射到定义域空间内。映射关系表达为：

Swarm=Swarm12*（ub-lb）+lb（6）

其中Swarm1为初始化后带有两种状态信息的种群，ub，lb为变量上下限。

借鉴基本的粒子群算法的速度更新方式，QCPSO算法中粒子的更新方式是粒子本身根据种群中最优粒子GBest和该粒子历史最优PBest的相位差值来更新自己的相位的，如下所示：

（7）

其中，θ为t+1代迭代中第j个粒子的第d维的相移量；θ为第t代第j个粒子的第d维的相移量；θ为当前相位；θ为全局最优粒子的相位；θ为该粒子历史最优相位；ω为惯性权重系数；C，C为加速系数；R，R为[0，1]内的随机数。

根据相位的更新计算出量子旋转门，更新粒子，如下式：

αβ=cosθ-sinθsinθ cosθαβ（8）

其中：θ为在第t+1次迭代中第j个粒子d维的相移量，α、β为在第t次迭代中第j个粒子d维的概率幅，α、β是第t+1次迭代中第j个粒子d维的概率幅。

1.2 粒子评估当粒子坍塌成某一个基本态时，将该基本态发生的概率表达出来，并且用来参加粒子适应度评估，即用一个粒子选择概率来选择粒子的基本态，选择好该粒子后，将该粒子按式（6）映射到寻优空间中，参加适应度评估；评估好了粒子来参加种群的更新。

1.3 自适应变异种群一旦陷入局部最优陷阱中后，粒子更新的相位很快就会趋于0，种群几乎不再更新，为了解决这个问题，本节设计了自适应概率，自适应的变异概率定义为：

P=μ+Re*σ（9）

其中μ和σ是变异率的调节参数，Re是最优值连续不更新或者更新不明显的代数。若种群连续更新，则不对种群进行任何调节；如不顺利（Re将累计增大），对种群进行调节的概率则加大。

1.4 算法流程本文提出的算法QCPSO的具体流程如下所示：

Step1：初始化种群；设定参数；

Step2：在[0,1]范围内初始化第一代种群（包括

Step3：按照式(4)对量子态进行表达，并进行第一次适应度评估；粒子历史最优值就为粒子本身；种群全局最优值为适应度最好的值；如满足跳出条件，则转Step9；否则转Step4；如式(5)随机初始化第一代粒子的相位变化量为(0,1)中的随机数；

Step4：计算粒子历史最优的相位；全局最优粒子相位；按照式(4)对量子态进行表达，并进行适应度评估；迭代次数加1；如满足跳出条件则转Step9；否则，转Step5；

Step5：根据式(7)更新粒子相位变化量，并运用量子旋转门来更新粒子式(8)；

Step6：判断是否对粒子的相位进行跳变；是，则执行式（9），Step7；否，直接转Step7；

Step7：根据预设的粒子状态观测概率选择粒子的状态，将粒子坍塌；并根据式(6)将粒子映射到预设空间中来。

Step8：对坍塌好的粒子进行适应度评价；是否满足退出条件：是，转Step9；否，更新全局最优和历史最优，转Step4；

Step9：跳出算法，输出最优值，结束。

1.5 算法性能测试为了验证算法的性能，将算法QCPSO与经典的粒子群算法、量子粒子群算法的代表AQPSO[5-6]进行实验比较。QCPSO参数选择为：惯性权重为0.7，加速常数分别为C1=1.4、C2=1.4，选择概率P=0.95，跳变概率σ=0.005，种群规模为40。经典PSO算法参数选择为惯性权重为0.7，加速常数分别为C1=2.0、C2=2.0，种群规模为40。具体测试结果如表1所示。

对于2维的测试函数：Camel函数上三种测试方法都能找到全局最优，AQPSO和QCPSO的达优率（100％）明显好于PSO算法。但是耗时上AQPSO较PSO差，QCPSO较AQPSO算法差。对于Levy F3函数，三种算法也都能找到全局最优值，在达优率上AQPSO算法稍微差于PSO算法，而QCPSO算法明显好于AQPSO算法。对于Levy F5函数，三种算法也都能找到全局最优值，但是AQPSO算法在达优均值上差于PSO算法； QCPSO在达优均值和达优率上都好于其他两种算法。

对于10维的测试函数Rastrigin和Schwefel、Sphere函数：对于Rastrigin函数，PSO不能找到全局最优，均达优值上也明显差于其他两个算法。QPSO明显好于其他两种算法。对于Schwefel测试函数上，虽然三种算法都没有找到全局最优值，但是QCPSO算法寻找到全局最优值能达到在1.3725e-004。达优均值上，QCPSO较其他两种算法都有明显进步。对于Sphere函数，AQPSO算法在全局最优值和达优均值上都差于PSO算法，QCPSO以较高的达优率得到高精度解。

对于高维的测试函数Ackley，AQPSO算法在全局最优值和达优均值上稍微好于PSO算法，而QCPSO算法则在两项指标上优于AQPSO和PSO算法。但是三种算法都没有找到全局最优值。而对于Griewangk的测试中，AQPSO和QCPSO算法都能找到全局最优值，但是在均达优值上，AQPSO效果差于PSO算法，QCPSO好于其他两种算法。

2结束语

本文对经典PSO算法以及在此基础之上的改进算法进行详细分析后，提出基于量子理论的连续粒子群算法，经过实验验证，QCPSO表现出了良好的性能，在高维问题的优化中SCPSO则表现出了良好的性能。

参考文献：

[1]Kennedy, R.C.Eberhart. Swarm Intelligence. Morgan Kaufmann Publishers, Inc. San Francisco, CA, 2001.

[2]R.C.Eberhart, J. Kennedy. A new optimizer using particle swarm theory. Proc of the 6th international symposium on Micro Machine and Human Science, Nagoya, Japan, IEEE Service Center, Piscataway, NJ, 1995:39-43.

[3]Narayanan A,Moore M, Quantum-inspired genetic algorithm. Proc of IEEE International Conference on Evolutionary Computation．Piscataway: IEEE Press, 1996: 61-66.

[4]Han K H, Kim J H. Genetic quantum algorithm and its application to combinatorial optimization problems. Proc of IEEE Conference on Evolutionary computation. Piscataway: IEEE Press, 2000. 1354-l360.

[5]Jun Sun, Wenbo Xu, Wei Fang. Quantum-Behaved Particle Swarm Optimization Algorithm with Controlled Diversity. ICCS 2006, Part III, Lecture Notes in Computer Science, Springer-Verlag Berlin Heidelberg, 2006:847-854.

[6]Jun Sun, Wenbo Xu, Jjing Liu. Parameter Selection of Quantum-Behaved Particle Swarm Optimization. ICNC 2005, Lecture Notes in Computer Science, Springer-Verlag Berlin Heidelberg, 2005: 543-552.