基于量子遗传算法的函数寻优算法设计[文献翻译]

毕业论文（设计）外文翻译题目基于量子遗传算法的函数寻优算法设计学院数理与信息学院学生姓名张晨专业计算机科学与技术班级A11计算机指导教师谭小球起止日期20141128至20151162015年1月15日PAGER1ANIMPROVEDQUANTUMGENETICALGORITHMGUOJIAN,SUNLIJUAN,WANGRUCHUAN,YUZHONGGENCOLLEGEOFCOMPUTER,NANJINGUNIVERSITYOFPOSTSANDTELECOMMUNICATIONS,NANJING,CHINA,GUOJ96GMAILCOMABSTRACTQUANTUMGENETICALGORITHMQGAISTHECOMBINATIONBETWEENGENETICALGORITHMANDQUANTUMCOMPUTINGINTHISPAPER,ACHROMOSOMEOFTHESTANDARDQGAISSEENASANODEANDTHECHROMOSOMEPOPULATIONISREGARDEDASANETWORKTHENTHEREASONSFORTHEPREMATURITYANDTHESTAGNATIONOFTHESTANDARDQGAAREANALYZEDFROMTHEPERSPECTIVEOFNETWORKSTRUCTURETOSOLVETHETWOPROBLEMS,ANIMPROVEDQUANTUMGENETICALGORITHMIQGABASEDONTHESMALLWORLDTHEORYISPROPOSEDINIQGA,CHROMOSOMESENCODEDWITHQUBITSAREDIVIDEDINTOSOMESUBGROUPSANDTHENWNETWORKMODELISINTRODUCEDINTOTHEPOPULATIONSTRUCTUREWHENUPDATINGCHROMOSOMES,ANOPTIMALCHROMOSOMEINLOCALITYORINOTHERSUBGROUPSISCHOSENBASEDONACERTAINPROBABILITYASTHEEVOLUTIONTARGETFOREACHCHROMOSOMETHENEWNETWORKSTRUCTUREOFTHECHROMOSOMEPOPULATIONHASARELATIVELYMODERATECLUSTERINGCOEFFICIENTANDISFAVORABLETOTHEDIVERSITYOFINDIVIDUALCHROMOSOMESTESTSOFTHREECLASSICFUNCTIONSPROVETHEEFFECTIVENESSANDSUPERIORITYOFIQGAKEYWORDSIMPROVEDQUANTUMGENETICALGORITHMQUANTUMGENETICALGORITHMNWNETWORKMODELSMALLWORLD1INTRODUCTIONGENETICALGORITHMGAISARANDOMSEARCHALGORITHMBASEDONTHEEVOLUTIONTHEORYOFTHESURVIVALOFTHEFITTEST15ITHASCHARACTERISTICSOFPARALLELISMANDVERSATILITYHOWEVER,INPRACTICALAPPLICATIONS,GAHASASLOWCONVERGENCESPEED,ANDISSUBJECTTOALOCALOPTIMALSOLUTIONMANYIMPROVEMENTSHAVEBEENMADEAMONGTHESE,QUANTUMGENETICALGORITHMQGAPROPOSEDINTHELATENINETIESACHIEVEDSIGNIFICANTRESULTS613QGAINTRODUCEDSOMETHOUGHTSOFQUANTUMCOMPUTINGINTOGA,WHICHGREATLYIMPROVEDTHEPARALLELISMOFGENETICMANIPULATIONANDACCELERATEDTHECONVERGENCEPROCESSQGAHASSHORTCOMINGSASWELLASQGACHOOSESONEOPTIMALQUANTUMCHROMOSOMEEACHROUNDTOGUIDETHEEVOLUTIONOFALLCHROMOSOMES,THISAPPROACHUNDERMINESTHEDIVERSITYOFTHEPOPULATION,MAKINGTHEPROCESSSUBJECTTOALOCALOPTIMALSOLUTIONINTHISPAPER,ANALYSESAREGIVENFROMTHEPERSPECTIVEOFTHESTRUCTUREOFCHROMOSOMEPOPULATION,ANDDEFECTSAREANALYZEDTOOVERCOMETHEDEFECTS,ANIMPROVEDQUANTUMGENETICALGORITHMIQGABASEDONTHESMALLWORLDTHEORY1416ISPROPOSEDIQGAINTRODUCESTHENWNETWORKMODEL15ANDIMPROVESITSPOPULATIONSTRUCTURE,SOTHEDIVERSITYOFTHEPOPULATIONISMAINTAINEDTHEEFFECTIVENESSANDSUPERIORITYOFIQGAAREDEMONSTRATEDTHROUGHTHETESTSOFCLASSICFUNCTIONSIIQUANTUMGENETICALGORITHMQGAISTHECOMBINATIONBETWEENGAANDQUANTUMCOMPUTINGITISBASEDONTHEQUANTUMVECTORS,REPRESENTINGCHROMOSOMEBYQUBITCODING,ANDUPDATINGCHROMOSOMEBYQUANTUMROTATIONGATEANDQUANTUMNOTGATEEVENTUALLYTHEOPTIMALSOLUTIONISSUPPOSEDTOBEFOUNDOUTAQUBITENCODINGQUBITISTHESMALLESTUNITOFINFORMATIONINQGAAQUBITMAYBEINEITHER1OR0STATE,ORINANYSUPERPOSITIONOFTHEBOTH,IEAQUBITMAYBE|0,|1,ORINTHEINBETWEENSTATETHEREFORE,ITCANBEEXPRESSEDAS|0|1,1WHEREANDARETWOCOMPLEXNUMBERSSATISFYING|2|21|2AND|2DENOTETHEPROBABILITIESOF|0AND|1RESPECTIVELYINQGA,QUBITSAREUSEDTOREPRESENTAGENEWHICHEXPRESSESALLTHEPROBABLEINFORMATIONINSTEADOFASETOFDEFINITEINFORMATIONANDANYOPERATIONCARRIEDOUTONTHISGENEMAYEXERTINFLUENCEONALLPOSSIBLEINFORMATIONSIMULTANEOUSLYFURTHERMORE,ACHROMOSOMECANBEENCODEDASWHEREKDENOTESTHENUMBEROFQUBITSINEACHGENE,WHILEMISTHENUMBEROFGENESINEACHCHROMOSOMEXYANDXY1XM,1YKARETWOCOMPLEXNUMBERSSATISFYING|XY|2|XY|21BEVOLUTIONARYOPERATIONQUANTUMROTATIONGATEISTHEIMPLEMENTATIONOFEVOLUTIONOPERATIONITOPERATESASWHEREI,ITANDI,ITARETHEITH1IMKQUBITOFTHEPREUPDATEANDPOSTUPDATECHROMOSOMERESPECTIVELYIISTHEROTATIONANGLE,WHOSEVALUEANDDIRECTIONCANBEADJUSTEDBYSOMESTRATEGIES7,10,11CWORKFLOWOFQGATHEPROCESSOFTHESTANDARDQGAISDETAILEDASFOLLOWS101THEPOPULATIONISINITIALIZEDALLGENESOFCHROMOSOMESAREINITIALIZEDWITH,21WHICHMEANSTHATACHROMOSOMEREPRESENTSTHELINEARSUPERPOSITIONOFALLPOSSIBLESTATESWITHTHESAMEPROBABILITY2ALLINDIVIDUALSAREINITIALLYOBSERVED,ANDAGROUPOFSOLUTIONS,PTPT1,PT2,PTN,AREOBTAINEDPTJDENOTESTHEJTHSOLUTIONOFTHEPOPULATIONOFTHETTHROUNDNAMELYTHEOBSERVATIONRESULTOFTHEJTHINDIVIDUALITISREPRESENTEDASANMBITBINARYSTRING,EACHBITOFWHICHISEITHER0OR1THEOBSERVATIONPROCESSISTOGENERATEARANDOMNUMBERIN0,1IFITISGREATERTHANTHESQUAREOFTHEPROBABILITYAMPLITUDE,THEBITISSETAS1,OTHERWISE0THENEACHSOLUTIONOFTHEGROUPISVALUEDRESPECTIVELY,ANDTHEBESTSOLUTIONISSAVEDASTHETARGETVALUEOFNEXTEVOLUTION3THEALGORITHMENTERSINTOTHESTAGEOFITERATIONFIRST,WHETHERTHECONDITIONTOENDTHEITERATIONISMETISDETERMINEDIFMET,THENALGORITHMENDSOTHERWISE,ALLINDIVIDUALSOFCURRENTPOPULATIONEXPERIENCEANOTHEROBSERVATION,ANDTHECORRESPONDINGSOLUTIONSANDFITNESSAREOBTAINED4BASEDONTHECURRENTTARGETVALUE,THEPOPULATIONISUPDATEDWITHQUANTUMROTATIONGATE,ANDANEWPOPULATIONISGENERATEDDURINGTHEPROCESSOFUPDATING,INDIVIDUALSAREOBSERVEDANDTHEIRFITNESSVALUESARECALCULATEDCOMPAREDWITHTHEFITNESSOFTHECURRENTTARGETVALUE,CORRESPONDINGINDIVIDUALQUBITSOFCHROMOSOMESAREADJUSTED5THEOPTIMALSOLUTIONOFCURRENTGENERATIONWITHTHETARGETVALUEISCOMPAREDTHEBETTERONEISCHOSENASTHETARGETOFNEXTEVOLUTION,ANDSTEP3RECURSIIIANETWORKLIKEANALYSISOFTHESTANDARDQGAIFEACHQUANTUMCHROMOSOMEISSEENASANODE,THENTHEPOPULATIONOFTHESTANDARDQGAISEQUIVALENTTOAFULLYCONNECTEDNETWORKOFAHIGHCLUSTERINGCOEFFICIENTANDASHORTAVERAGEPATHLENGTH,ASSHOWNINFIG1THISKINDOFNETWORKSTRUCTUREISFAVORABLETOINFORMATIONSHARINGAMONGCHROMOSOMES,BUTTOQGA,ITUNDERMINESTHEDIVERSITYOFINDIVIDUALCHROMOSOMESTHEREASONISTHATONLYONEBESTCHROMOSOMEISPICKEDOUTASTHEEVOLUTIONTARGETOFALLCHROMOSOMESWHENUPDATINGTHEPOPULATIONEACHCHROMOSOMEEVOLVESINACCORDANCEWITHTHEBESTONEASARESULT,THEALGORITHMISSUBJECTTOLOCALOPTIMUMANDTHEPREMATUREPHENOMENONAPPEARS,IETHEWHOLEPOPULATIONCONVERGESTOTHEFIRSTAPPROXIMATEOPTIMALSOLUTIONCONVERSELY,IFANOTHERTOPOLOGYSTRUCTURE,NAMELYMULTIGROUPSTRUCTURE,ISADOPTED,ASSHOWNINFIG2,THECHROMOSOMESAREDIVIDEDINTOSOMESUBGROUPSANDEACHOFTHEMSETSUPTHEIROWNEVOLUTIONGOALSALLSUBGROUPSAREMUTUALLYINDEPENDENTINTHISCASE,CHROMOSOMESARESELECTEDASTHEEVOLUTIONTARGETS,WHICHISCONDUCIVETOTHEDIVERSITYOFTHEPOPULATIONHOWEVER,THISNEWSTRUCTUREHASARELATIVELYGREATAVERAGEPATHLENGTH,ANDSUBGROUPSCANNOTEXCHANGEINFORMATIONSOTHEALGORITHMLACKSADEQUATEGUIDESTOUPDATETHEPOPULATIONANDCONVERGESSLOWLYTHEREFORE,THEABOVETWOSTRUCTURESARENOTSUITABLEFORQGAIVSMALLWORLDTHEORYTHEPHENOMENAOFSMALLWORLDNETWORKAREMANIFESTATIONSOFCLUSTERINGINTHEREALNETWORKSIN1967,PROFESSORSTANLEYMILGRAMOFHARVARDUNIVERSITYFOUNDTHEPHENOMENON“SIXDEGREESOFSEPARATION“THROUGHTHECHAINLETTERSEXPERIMENTS,WHICHWASALSOKNOWNASTHE“SMALLWORLD“BASEDONTHIS,WATTSANDSTROGATZPROPOSEDASMALLWORLDNETWORKMODELWSMODELIN1998,WHICHRECONNECTEDEVERYLINKINREGULARNETWORKATPROBABILITYP14LATER,NEWMANANDWATTSIMPROVEDTHEWSMODELANDADVANCEDTHENWNETWORKMODEL15THEMODELADDSLONGDISTANCECONNECTIONSBETWEENRANDOMLYSELECTEDNODES,ANDORIGINALCONNECTIONSARERESERVEDTHEPROCESSISSHOWNINFIG3ORIGINALCONNECTIONSINTHENETWORKARECALLEDSTRONGLINKSWHILEADDEDCONNECTIONSARECALLEDWEAKLINKSSTUDIESHAVESHOWNTHATWEAKLINKSHARDLYCHANGETHECLUSTERINGCOEFFICIENT,BUTTHEYCANGREATLYREDUCETHEAVERAGEPATHLENGTHOFTHENETWORKVANIMPROVEDQUANTUMGENETICALGORITHMAABIRDEYEVIEWACCORDINGTOTHEANALYSISINSECTION3,TOCONVERGEQUICKLYANDAVOIDPREMATURITY,THENETWORKOFCHROMOSOMEPOPULATIONOUGHTTOHAVETHECHARACTERISTICSOFBOTHARELATIVELYMODERATECLUSTERINGCOEFFICIENTANDASHORTAVERAGEPATHTHEREFORE,THESMALLWORLDTHEORYISINTRODUCEDINTOQGAANDIQGAISPROPOSEDTHEPOPULATIONNETWORKISTRANSFORMEDINTOASMALLWORLDNETWORKCONSEQUENTLY,THEABOVEPROBLEMSARESOLVEDBTHEDESIGNOFIQGAIQGAIMPROVESTHESTANDARDQGAMAINLYFROMTHEFOLLOWINGASPECTS1ALLCHROMOSOMESAREDIVIDEDINTOSOMESUBGROUPS2AFTERONEROUNDOFEVOLUTIONOPERATION,EACHSUBGROUPCHOOSESTHEBESTCHROMOSOMEASTHEEVOLUTIONTARGETOFTHENEXTROUNDINTHISPROCESS,ALLCHROMOSOMESOFTHISSUBGROUPTAKEPARTINTHECOMPETITIONSOEACHSUBGROUPISAFULLYCONNECTEDNETWORKEACHCHROMOSOMECONNECTSOTHERCHROMOSOMESTHROUGHSTRONGLINKS3INTHEIMPLEMENTATIONPROCEDUREOFEVOLUTIONOPERATION,THECHROMOSOMEDOESNOTSIMPLYCHOOSEITSSUBGROUPSBESTCHROMOSOMEASITSEVOLUTIONTARGET,BUTSELECTSOTHERSUBGROUPSBESTCHROMOSOMEATACERTAINPROBABILITYSOAWEAKLINKBETWEENTHISCHROMOSOMEANDOTHERSUBGROUPSISFORMEDEXCHANGEOFINFORMATIONBETWEENSUBGROUPSISPROMOTEDANDTHECONVERGENCESPEEDISINCREASEDPOPULATIONSTRUCTUREOFIQGAISSHOWNINFIG4CWORKFLOWOFIQGATHEPROCESSOFIQGAISDETAILEDASFOLLOWS1THEPOPULATIONISDIVIDEDINTOSOMESUBGROUPSANDALLCHROMOSOMESAREINITIALIZED2THEOBSERVATIONFOREVERYCHROMOSOMEINALLSUBGROUPSISIMPLEMENTED,ANDEACHSOLUTIONOFTHESUBGROUPISVALUEDRESPECTIVELYTHENTHEBESTSOLUTIONISSAVEDASTHETARGETVALUEOFNEXTEVOLUTION3THEALGORITHMENTERSINTOTHESTAGEOFITERATIONFIRST,WHETHERTHETERMINATIONCONDITIONISMETISDETERMINEDIFMET,THENALGORITHMENDSOTHERWISE,ALLINDIVIDUALSAREOBSERVEDAGAIN,ANDTHECORRESPONDINGSOLUTIONSANDFITNESSAREOBTAINED4ATACERTAINPROBABILITY,THEBESTCHROMOSOMEFROMTHESUBGROUPOROTHERSUBGROUPSISCHOSENASTHEEVOLUTIONTARGETFOREACHCHROMOSOMETHENITISUPDATEDWITHQUANTUMROTATIONGATE5FOREACHSUBGROUP,ANOPTIMALSOLUTIONISFOUNDOUTAGAIN,ANDCOMPAREDWITHTHECURRENTTARGETVALUETHEBETTERONEISRESERVED,ANDSTEP3RECURSVIEXPERIMENTSANDTESTSATHEDESIGNOFEXPERIMENTSINORDERTOVERIFYTHEVALIDITYOFIQGA,THREECLASSICALTESTFUNCTIONSAREUSEDFOREXPERIMENTSCOMPARATIVETESTSWITHTHESTANDARDQGAARECARRIEDOUTTHESETHREEFUNCTIONSARE1RASTRIGRINFUNCTIONWITHTHEOPTIMALSOLUTIONF10,0,002GRIEWANKFUNCTIONWITHTHEOPTIMALSOLUTIONF20,0,003ACKLEYFUNCTIONXI32，32WITHTHEOPTIMALSOLUTIONF30,0,00IQGAANDQGAWEREREALIZEDWITHTHECLANGUAGEUNDERTHEWINDOWSXPENVIRONMENTTHETOTALNUMBEROFCHROMOSOMESWAS200ANDTHETIMEOFITERATIONSWAS2000INIQGA,THEPOPULATIONWASDIVIDEDINTO20SUBGROUPSTWOEXPERIMENTSWERECONDUCTEDTHEEFFECTOFTHEWEAKLINKPROBABILITYPTOIQGAWASTESTEDINEXPERIMENT1ANDTHEPERFORMANCEOFTHETWOALGORITHMSWASCOMPAREDINEXPERIMENT2BRESULTSANDANALYSIS1EXPERIMENT1THEVALUEOFPWASSETTO0,01,021ACCORDINGTOEACHVALUE,EACHFUNCTIONWASTESTED10TIMESTHENTHEAVERAGESWERECALCULATEDTHEOUTCOMESARESHOWNFROMFIG5TO7THEABOVETHREEFIGURESSHOWTHATIFPISSMALL,THEPROBABILITYOFSUBGROUPSLEARNINGFROMEACHOTHERWILLBESLIMANDTHEDEGREEOFSHARINGINFORMATIONWILLBELOWSOTHEPOPULATIONSTAGNATESEARLYWHENTHEPVALUERANGESBETWEEN06AND08,INFORMATIONISSHAREDADEQUATELY,ANDSOLUTIONSIQGAOBTAINEDAREBETTERTHEREFORE,INTHEFOLLOWINGEXPERIMENTS,THEPVALUEISSETTO072EXPERIMENT2EACHFUNCTIONWASTESTED20TIMESWITHIQGAANDQGARESPECTIVELYTABLE1SHOWSTHEAVERAGEOFSOLUTIONSOF20TIMESTABLE2SHOWSTHECOMPARISONOFOPTIMALSOLUTIONSGAINEDBYTWOALGORITHMSITISFOUNDTHATSOLUTIONSOBTAINEDBYIQGAAREALWAYSBETTERTHANTHOSEOBTAINEDBYQGA,ESPECIALLYTHOSEOFF3EVOLUTIONCOURSESOFOPTIMALSOLUTIONSTOEACHFUNCTIONARESHOWNFROMFIG8TO10JUDGEDFROMTHEFIGURES,SOLUTIONSGAINEDBYQGAEVOLVEFASTERTHANBYIQGAATTHEINITIALSTAGE,BUTTHEYGENERALLYDISCONTINUEDAFTERABOUT400ROUNDSQGAFALLSINTOPREMATURESTATEANDSTAGNATESINCONTRAST,SOLUTIONSOBTAINEDBYIQGASTILLEVOLVEATASLOWSPEEDEVENAFTER700ROUNDS,THUSMUCHBETTERVIICONCLUSIONTHEPOPULATIONSTRUCTUREHASAGREATIMPACTONTHEPERFORMANCEOFTHEALGORITHMANDSHORTCOMINGSOFTHESTANDARDQGAORIGINATEINITSSTRUCTURALFLAWSAFTERTHEINTRODUCTIONOFTHENWMODEL,THENEWPOPULATIONSTRUCTUREHASARELATIVELYMODESTCLUSTERINGCOEFFICIENTANDASHORTAVERAGEPATHLENGTH,WHICHISHELPFULFORTHEDIVERSITYOFPOPULATIONASWELLASTHEEXCHANGEOFINFORMATIONTHEREFORETHEPERFORMANCEOFIQGAISGREATLYIMPROVED量子遗传算法的改进郭建，孙丽娟，王茹川，于忠根南京邮电大学计算机学院摘要量子遗传算法（QGA）是结合遗传算法和量子计算。在本文中，量子遗传的染色体被视为一个节点和染色体种群被认为是一个网络。然后，从网络结构的角度分析得出的两个原因是量子遗传的早熟与停滞。为了解决这两个问题,提出了一种基于小世界理论的改进的量子遗传算法IQGA。在改进的量子遗传算法中,基于量子比特的染色体编码被分为一些子群体和NW网络模型被引入种群结构。当更新染色体时，把一个最优染色体位置作为其他群体进化时基于一定概率所选择的的目标。新的染色体种群网络结构有相对温和的聚类系数和有利于个体染色体的多样性。测试三个经典函数证明IQGA的有效性和优越性。关键词改进量子遗传算法量子遗传算法NW网络模型小世界1引言遗传算法GA是一种基于进化理论适者生存15的随机搜索算法。他具有并行性和通用性的特点。然而,在实际应用中,遗传算法会有收敛速度慢、陷入局部最优解的现象。为此做了很多改进。其中,在90年代提出的量子遗传算法QGA613有了很大进步。量子遗传算法实现了将量子计算思想运用到遗传算法,大大提高了并行遗传操作和加速收敛的过程。量子遗传算法同样也有缺点。因为在每代中量子遗传算法是选择一个最佳的量子染色体指导所有染色体的进化,这种方法破坏了种群的多样性,使结果趋向局部最优解。本文中，从染色体种群的结构的角度来和缺陷进行了分析。为了克服这种缺点,一种基于小世界理论1416的改进的量子遗传算法IQGA被提出。IQGA介绍了NW网络模型15和改善种群结构,因此种群具有多样性。IQGA的有效性和优越性通过典型函数的测试演示了。2量子遗传算法量子遗传算法是结合遗传算法和量子计算。它是基于量子向量的量子位编码的染色体,染色体的更新通过量子门旋转门和量子非门。最终找到期望的最优解。21量子位编码在量子遗传中量子位是信息的最小单位。量子位可以在1或0态,或任何态的叠加,即量子位可以|0,|1,或是他们的任何叠加态。因此,它可以表示为|0|1,1和两个复数满足|2|2|1|2|和|2|分别表示|0和|1的概率。在量子遗传算法中,量子比特位用于表示一个基因可能表达的所有可能的信息,而不是一系列确定的信息。对这种基因的任何操可能对所有可能的信息同时施加影响。此外,可以将染色体编码为K代表每个基因在染色体上的位置,而M是每个染色体的基因数量。XY和XY1XM,1YK是两个复数满足|XY|2|XY|21。22进化操作进化操作是量子旋转门实现的。它是IIT和I,IT是第I个1MK分别更新前和更新后处理染色体的量子位。I旋转角,其大小和方向可以通过调节对策7,10,11来改变。23工作流的实现量子遗传算法详细运行过程如下101初始化种群。所有基因的染色体是初始化,这意味着一个染色体所表达的是21其全部可能状态的等概率叠加；2最初观察所有的个体,一组解集为PTPT1PT2,。得到了PTN,。PTJ表示第J个染色体的第T代即第J个染色体的观察结果。表示为一个二进制字符串,每个位是0或1。通过生成一个在01的随机数。如果它是大于概率振幅的平方,位设置为1,否则为0。然后算出每个方案的值,记录最优个体和对应的适应度作为下一代进化的目标；3进入算法的迭代阶段。首先,结束迭代的条件是否得到满足。如果满足,那么算法结束。否则,对种群中的每个个体实施一次测量，得到相应的确定解，对各确定解进行适应度评估4基于当前最优个体,利用量子旋转门对个体实施调整，得到新的种群。在更新的过程中,计算种群个体适应度。与当前目标的适应度相比,相应调整个别量子位的染色体；5将前一代的最优解与现在的比较。更好的选择一个作为下一代进化的目标,返回步骤3；3网络似乎分析标准的实现如果每个量子染色体被视为一个节点,然后量子遗传算法标准的种群相当于一个完全连接网络的聚类系数和平均路径长度短,如图1所示。这种网络结构有利于染色体的信息共享,但是对于量子遗传算法,它削弱了个体染色体的多样性。原因是只有一个最好的染色体作为所有染色体的进化更新的目标。每个染色体进化按照最好的。结果,算法局部最优和不成熟的现象出现,即整个种群收敛到第一个近似最优解。相反,如果采用另一个拓扑结构,即多群结构。如图2所示,染色体分为成一些子群体,他们每个人都建立自己的进化目标。所有的群体是相互独立的。在这种情况下,染色体是选为进化的目标,这有利于种群的多样性。然而,这种新结构相对平均路径较长和群体不能交换信息。因此该算法缺乏适当的信息来更新种群和收敛缓慢。因此,上述两种结构都不适合量子遗传算法。4小世界理论小世界网络的现象是在现实网络的集群表现。1967年,哈佛大学的教授STANLEYMILGRAM通过连锁信实验，发现“六度分离”现象,也被称为“小世界”。在此基础上,1998年WATTS和STROGATZ提出了一个小世界网络模型WS模型14，它以概率P重新连接固定网络中的每一个环节。之后,NEWMAN和WATTS改进WS模型和提出了先进的NW网络模型15。模型增加了任意选择两个长距离节点连接,并保留原始连接。这个过程如图3所示。原始连接在网络被称为紧密联系，添加连接被称为无力连接。研究表明,无力连接很难改变聚类系数,但他们可以大大减少网络的平均路径长度。5一种改进的量子遗传算法51鸟眼视图在根据第三节的分析，为了迅速收敛和避免早熟，染色体种群网络应该有相对温和的聚类系数和平均路径短的特点。因此，将小世界理论引用到量子遗传算法提出了IQGA。种群网络转化为一个小世界网络。因此,上述问题得到解决。52IQGA的设计IQGA主要通过以下几方面改进传统量子遗传算法。1所有染色体分成一些子群体。2之后的一轮进化操作,每一个子群体中选择最好的染色体作为下一轮的进化的目标。在这个过程中,所有染色体的子群体参加竞争。所以每个子群是一个完全连接的网络。每个染色体通过强连接连接其他染色体。3进化操作的实现过程,染色体不是简单地选择其子种群最好的染色体作为进化目标,而是有一定的概率选择其他群体最好的染色体。所以在这个染色体和其他群体之间的无力连接被改变。群体之间的信息交换和收敛速度都有提高。IQGA的种群结构如图4所示。53工作流的IQGAIQGA的详细工作过程如下1种群被分为一些子群体和所有染色体都初始化。2观察每一个在子种群的的实现的染色体,分别计算子群的每个适应度值。然后保存最好的个体为下一代进化的目标。3进入算法的迭代阶段，首先,结束迭代的条件是否得到满足。如果满足,那么算法结束。否则,对种群中的每个个体实施一次测量，得到相应的确定解，对各确定解进行适应度评估。4基于当前最优个体,利用量子旋转门对个体实施调整，得到新的种群。在更新的过程中,计算种群个体适应度。与当前目标的适应度相比,相应调整个别量子位的染色体。5将前一代的最优解与现在的比较。更好的选择一个作为下一代进化的目标,返回步骤3。6、实验和测试61实验的设计为了验证的有效性IQGA,将三个经典测试函数用于实验。对比实验与标准QGA的结果得出结论。这三个函数是1RASTRIGRIN”函数最优解F10,0,002GRIEWANK函数最优解F20,0,003ACKLEY函数XI32，32最优解F30,0,00IQGA和QGA在WINDOWSXP环境下用C语言实现。染色体的总数是200和迭代的次数是2000次。在IQGA中,种群分为20组。进行了两个实验。以概率P对IQGA无力连接测试的性能在实验1进行测试和实验2中是对两个算法进行了比较。62结果与分析621实验1P的值被设置为0,01,021。根据这个值,每个函数测试10次。然后平均计算。结果如图5至7所示。有上面的三幅图表明,如果P很小,小组互相学习的概率很小和信息共享的程度很低。因此,种群停滞。当P值范围在06和08之间,信息充分共享,IQGA获得更好的解。因此,在接下来的实验中,P值设置为07。632实验2每个函数测试分别用IQGA和QGA测试20次。表1显示了测试20次的平均解。表2显示了两种算法的最优解的比较。发现解决方案通过IQGA总是比那些通过QGA的好,特别是F3。每个函数的进化的最优方案,显示在图8到10。从这个数据，通过QGA的方法比IQGA也要快,在初始阶段。但他们通常经过400轮停止。会掉入不成熟的状态和停滞不前的状态。相比之下,通过IQGA解决方案发展速度仍然缓慢甚至经过700轮后,因此好多了。7、结论种群结构对算法的性能有很大的影响。和标准的QGA缺点来源于结构上的缺陷。引入NW模型后,新的种群结构有一个相对温和的聚类系数和较短的平均路径长度,这是有利于种群的多样性以及信息的交换。因此IQGA的性能大大改善。原文PAGER2GENETICALGORITHMBASEDONTHEQUANTUMPROBABILITYBINLIANDZHENQUANZHUANGLABORATORYOFQUANTUMCOMMUNICATIONANDQUANTUMCOMPUTATION,UNIVERSITYOFSCIENCEANDTECHNOLOGYOFCHINA,HEFEI,230026,CHINAABSTRACTAGENETICALGORITHMBASEDONTHEQUANTUMPROBABILITYREPRESENTATIONGAQPRISPROPOSED,INWHICHEACHINDIVIDUALEVOLVESINDEPENDENTLYANEWCROSSOVEROPERATORISDESIGNEDTOINTEGRATESEARCHINGPROCESSESOFMULTIPLEINDIVIDUALSINTOAMOREEFFICIENTGLOBALSEARCHINGPROCESSANEWMUTATIONOPERATORISALSOPROPOSEDANDANALYZEDOPTIMIZATIONCAPABILITYOFGAQPRISSTUDIEDVIAEXPERIMENTSONFUNCTIONOPTIMIZATION,RESULTSOFEXPERIMENTSSHOWTHAT,FORMULTIPEAKOPTIMIZATIONPROBLEM,GAQPRISMOREEFFICIENTTHANGQA41INTRODUCTIONRESEARCHDEVELOPMENTINQUANTUMCOMPUTATIONPRESENTSUSNOTONLYWITHATEMPTINGPERSPECTIVEOFFUTURECOMPUTATIONALCAPABILITY1,BUTALSOWITHINSPIRATIONSOFIMPROVINGCLASSICALALGORITHMSBYRECONSIDERINGTHEMFROMASTANDPOINTOFQUANTUMMECHANICSGENETICALGORITHMISAWELLKNOWNHEURISTICSEARCHINGALGORITHM,ANDHASBEENPROVEDSUCCESSFULINMANYAPPLICATIONS2RESEARCHWORKONMERGINGGENETICALGORITHMANDQUANTUMCOMPUTATIONHASBEENSTARTEDBYSOMERESEARCHERSSINCE1990SONLYTWOPRACTICALMODELSHAVEBEENPROPOSEDTILLNOWQIGAQUANTUMINSPIREDGENETICALGORITHM,PROPOSEDBYAJITNARAYANAM,INTRODUCESTHETHEORYOFMANYUNIVERSESINQUANTUMMECHANICSINTOTHEIMPLEMENTATIONOFGENETICALGORITHM3THEMAINCONTRIBUTIONOF3ISTHATITPROVESTHEEFFICIENCYOFTHESTRATEGYTHATUSESMULTIPLECOLONIESTOSEARCHINPARALLEL,ANDUSESAJOINTCROSSOVEROPERATORTOENABLETHEINFORMATIONEXCHANGEAMONGCOLONIESKUKHYUNHANPROPOSEDAGENETICQUANTUMALGORITHMGQA4,INWHICHTHEPROBABILITYAMPLITUDEOFQUBITWASUSEDFORTHEFIRSTTIMETOENCODETHECHROMOSOME,ANDTHEFORMULAOFQUANTUMROTATIONGATEWASUSEDTOIMPLEMENTTHEUPDATINGOFCHROMOSOMEGQAISBASICALLYAPROBABILITYALGORITHM,NOTAGENETICALGORITHMALLINDIVIDUALSEVOLVETOWARDSONECONTEMPORARYEVOLUTIONARYTARGETCETIMPORTANTGENETICOPERATORS,SUCHASCROSSOVERANDMUTATION,ARENOTADOPTEDINITINTHISPAPER,ANEWGENETICALGORITHMBASEDONTHEQUANTUMPROBABILITYREPRESENTATIONGAQPRISPROPOSED,INWHICHEACHINDIVIDUALHASITSOWNCONTEMPORARYEVOLUTIONARYTARGETCETANDEVOLVESINDEPENDENTLYANEWCROSSOVEROPERATORISDESIGNEDTOENABLETHEEFFICIENTEXCHANGEOFEVOLUTIONINFORMATIONBETWEENDIFFERENTINDIVIDUALSANEWMUTATIONOPERATORISALSOPROPOSED,ITSEFFECTISSTUDIEDINEXPERIMENTSEXPERIMENTSONTWOTYPICALFUNCTIONOPTIMIZATIONPROBLEMSPROVETHAT,FORMULTIPEAKOPTIMIZATIONPROBLEM,GAQPRISMOREEFFICIENTTHANGQATHEREMAININGPARTOFTHISPAPERISORGANIZEDASFOLLOWSECTION2DESCRIBESTHEPRINCIPLEANDPROCEDUREOFGAQPR,WHICHINCLUDESTHEINTRODUCTIONOFREPRESENTATIONANDUPDATINGSTRATEGYOFCHROMOSOMES,MAINPROCEDUREOFGAQPR,ANDPROCEDUREOFTHENEWDESIGNEDCROSSOVERANDMUTATIONOPERATORSSECTION3ISTHEDESCRIPTIONOFEXPERIMENTSECTION4ISTHECONCLUSIONOFTHEWHOLEPAPER2GAQPR21REPRESENTATIONANDUPDATINGOFCHROMOSOMESINQUANTUMCOMPUTATION,THEELEMENTARYUNITFORSTORINGINFORMATIONISAQUANTUMSYSTEMWITHTWOSTATES,CALLEDQUANTUMBITQUBITTHEKEYCHARACTERISTICTHATMAKESQUBITDIFFERFROMCLASSICALBITISTHATITCANBEATTHESUPERPOSITIONOFTWOQUANTUMSTATESSIMULTANEOUSLYTHISSUPERPOSITIONCANBEEXPRESSEDASFOLLOW|0|1,1WHERE,ISAPAIROFCOMPLEXINVARIABLES,CALLEDPROBABILITYAMPLITUDEOFQUBIT,WHICHSATISFIES|2|212|0AND|1REPRESENTTWODIFFERENTSTATESOFQUBITRESPECTIVELY,SOONEQUBITCANSTORETHEINFORMATIONOFBOTHSTATESATTHESAMETIMEINGQA,EACHGENEHASONLYTWOSTATES,SOONEQUBITISENOUGHFORENCODINGONEGENEBUTITISOFTENTHECASEINAPPLICATIONSTHATONEGENEMAYHAVEMORETHANTWOSTATESINTHISPAPER,FOLLOWINGTHEBINARYCODINGMETHODSINCLASSICALGENETICALGORITHM,WEUSEMORETHANONEQUBITTOENCODEGENEWITHMORETHANTWOSTATESACHROMOSOMEISDEFINEDASFOLLOWWHEREQTJISTHEJTHCHROMOSOMEINTHECO