量子概率编码遗传算法及其应用

《量子概率编码遗传算法及其应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第27卷第5期电子与信息学报Vo1.27No.52005年5月JournalofElectronics&InformationTechnologyMay2005量子概率编码遗传算法及其应用李斌谭立湘邹谊庄镇泉(中国科学技术大学电子科学与技术系合肥230026)摘要:该文提出了一种基于染色体量子概率编码的遗传算法—QCGA。与传统遗传算法不同，在QCGA中，单个个体不再表示某一个确定解，而是解的取值概率分布，覆盖整个解空间;各个个体独立并行演化，个体间通过一个新的交叉算子实现演化信息的交换，同时设计了一个新的变异算子以增强

2、算法的局部寻优能力。为了充分考察该算法的有效性和先进性，将其应用于典型函数优化、0-1背包问题和时间序列中频繁结构模式搜索等问题的求解。实验结果表明，与现有同类算法相比，该算法在具有很高搜索效率的同时，仍能维持很高的种群多样性，因而适用于复杂优化问题的求解。关键词:遗传算法，量子概率编码，交叉算子，变异算子中图分类号:TP18文献标识码:A文章编号:1009-5896(2005)05-0805-06QuantumProbabilityCodingGeneticAlgorithmandItsApplicationsLiBi

3、nTanLi-xiangZouYiZhuangZhen-quan(DepartmentofElectronicScienceandTechnology,UniversityofScienceandTechnologyofChina,Hefei230026,China)AbstractAQuantumprobabilityCodingGeneticAlgorithm-QCGAisproposed,whichisdiferentfromclassicalGAs.InQCGA,singleindividualrepresent

4、saprobabilitydistributionofsolutions,whichcoversthewholesolutionspace.IndividualsinQCGAevolveindependentlyandinparallel.Anewcrossoveroperatorisdesignedtoimplementtheinformationexchangeamongindividuals.Anewmutationoperatorisalsodesigntopreventthealgorithmfromfalli

5、ngintolocaloptima.TostudytheeficiencyandadvantageofQCGA,thealgorithmisappliedtosolvefunctionoptimizationproblems,knapsackproblems,andtodiscoverfrequentstructuresfromtimeseries.ExperimentalresultsshowthatQCGAhasgoodabilityofglobaloptimization,andgoodabilityofdiver

6、sityreservation,whichmakesitefficientforcomplexKeywordsGeneticalgorithm,Quantumprobabilitycoding,Crossoveroperator,Mutationoperator1引言宙量子衍生遗传算法(QIGA)[3]。从算法机理上看，它与一种隔离小生境遗传算法[41很相似。Han等提出了一种遗传量近年来在量子信息学领域的研究进展不仅向我们展示了未来量子信息处理的诱人前景[I]，同时也启发我们从量子子算法(GQA)151，后更名为量子衍

7、生演化算法(QEA)}6>>力学的角度出发重新研究一些传统算法，以达到改进其性能将量子的概率幅表达引入遗传编码。QEA在GQA的基础上的目的。遗传算法是一类借鉴生物界自然选择和自然遗传机增加了一个迁移机制。QEA和GQA本质上都属于概率演化制的随机化搜索算法[21。大量研究与实践证明，遗传算法是算法，在算法中并没有采用交叉、变异等遗传操作。此外，一种高效、稳健的全局优化算法，被广泛用于一些复杂问题通过实验分析我们发现，在求解一些复杂的优化问题时，该的求解。算法容易陷入局部最优。将量子计算与遗传算法结合的尝试开始于20世纪

8、90年本文首先对采用量子比特概率幅编码的染色体的概率代后期，迄今有两个算法模型给出了具体的实验结果。特性进行了分析，得出一个染色体所表达的是整个解空间中Narayanan等将量子多宇宙理论引入遗传算法，提出了多宇所有解的取值概率分布:在此基础上，提出了一个基于染色体量子概率编码的遗传算法(QCGA)，该算法以个体为单