量子遗传进化算法的收敛性研究.pdf

《量子遗传进化算法的收敛性研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2013牟glO期文章编号：1009—2552(2013)10—0161—04中图分类号：T~01．6文献标识码：A量子遗传进化算法的收敛性研究沈微微，华明正，李敏(1．宿迁学院，江苏宿迁223800；2．宿迁广电网络公司，江苏宿迁223800)摘要：量子遗传算法建立在量子的态矢量表达基础上，染色体的编码用量子比特的几率幅表示，使得一条染色体表达多个态的叠加，再利用量子门实现染色体更新操作，从而达到目标的优化求解。它具有种群规模小而不影响算法性能，收敛速度快和全局优化能力强等特点。但是遗传算法的随机性不好把握，收敛方向不好控制，针对遗传算法的种种问题，通过多种

2、方法来对收敛性进行研究。关键词：量子遗传算法；收敛性；背包问题；量子旋转门StudyonconvergenceofquantumgeneticevolutionalgorithmSHENWei-wei，HUAMing-zheng，LIMin(1．SuqianCollege，Suqian223800，JiangsuProvince，China；2．SuqianRadioandTVNetworkCompany，Suqian223800，JiangsuProvince，China)Abstract：Quantumgeneticalgorithmforquantums

3、tatevectorfortheexpression，theprobabilityamplitudeofquantumbitsexpresschromosomecoding，achromosomecanexpressmultiplestate．Thenupdatechromosomebyquantumgates，togainobjectiveoptimalsolution．Ithasasmallpopulationsizewithoutaffectingalgorithmperformance，fastconvergenceandglobaloptimizat

4、ionabilityandothercharacteristics．However，therandomnessofgeneticalgorithmsgoodgrasp，poorcontrolofthedirectionofconvergence．Geneticalgorithmsfortheproblems，thispaperthroughavarietyofwayscarriesoutastudyontheconvergence．Keywords：quantumgeneticalgorithm；convergence；knapsackproblem；quan

5、tumgate0引言行调节来改进算法收敛性_2J。本文针对背包问题提出引入惩罚函数来对收敛性进行研究，并通过实量子计算与遗传算法的结合量子遗传算法验来对比效果。(QuantumGeneticAlgorithm，简称QGA)从2O世纪9O年代后期开始，Narayanan将量子多宇宙理论1量子遗传算法引入遗传算法，提出了多宇宙量子衍生遗传算法，’遗传算法的缺点包括：编码不规范及编码存Han等提出量子衍生演化算法，它首次将量子的概在表示的不准确性；单一的遗传算法编码不能全面率幅表达引入遗传算法⋯。后来许多研究者在算地将优化问题的约束表示出来；效率比其他传统的法上又进

6、行了相应改进，并用实验结果证明更好。优化方法低；容易出现过早收敛；对算法的精度、可但是遗传算法的随机性不好把握，收敛方向无法进信度、计算复杂性等方面，还没有有效的定量分析行有效控制，容易陷入局部最优等问题还是不易克方法。服。面对遗传算法的各种问题，学者们开始探索并量子遗传进化算法是量子计算与遗传算法相结构建新的算法模型。近年来，学者们相继提出多种合的产物。目前，这一领域的研究主要集中在两类方法来改进量子遗传算法收敛性。比如引入免疫算收稿日期：2013—03—25子，或者通过对量子旋转门的旋转角及旋转参数进作者简介：沈微微(1983一)，女，硕士研究生，助理实验

7、师，研究方向为遗传算法。模型上：一类是基于量子多宇宙特征的多宇宙量子种，根据量子遗传算法的计算特点，选择量子旋转门衍生遗传算法(QuantumInspiredGeneticAlgo．较为合适。(，)为染色体的第i个量子比特，0rithm)，另一类是基于量子比特和量子态叠加特性为旋转角，其大小和方向根据一个事先设计的调整的遗传量子算法(GeneticQuantumAlgorithm，策略而确定。公式如下：GQA)。1．1量子遗传算法流程U(ao~=[【。in△c咖=(△]J㈩(1)量子遗传进化算法求解问题的基本步骤I6]：①进化代数初始化：t=0。【】=。cio

8、s△A0i-。ss△inA‘]‘【主]