畢業(yè)論文（設(shè)計(jì)）外文翻譯題目基于量子遺傳算法的函數(shù)尋優(yōu)算法設(shè)計(jì)學(xué)院數(shù)理與信息學(xué)院學(xué)生姓名張晨專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)班級A11計(jì)算機(jī)指導(dǎo)教師譚小球起止日期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量子遺傳算法的改進(jìn)郭建，孫麗娟，王茹川，于忠根南京郵電大學(xué)計(jì)算機(jī)學(xué)院摘要量子遺傳算法（QGA）是結(jié)合遺傳算法和量子計(jì)算。在本文中，量子遺傳的染色體被視為一個節(jié)點(diǎn)和染色體種群被認(rèn)為是一個網(wǎng)絡(luò)。然后，從網(wǎng)絡(luò)結(jié)構(gòu)的角度分析得出的兩個原因是量子遺傳的早熟與停滯。為了解決這兩個問題,提出了一種基于小世界理論的改進(jìn)的量子遺傳算法IQGA。在改進(jìn)的量子遺傳算法中,基于量子比特的染色體編碼被分為一些子群體和NW網(wǎng)絡(luò)模型被引入種群結(jié)構(gòu)。當(dāng)更新染色體時，把一個最優(yōu)染色體位置作為其他群體進(jìn)化時基于一定概率所選擇的的目標(biāo)。新的染色體種群網(wǎng)絡(luò)結(jié)構(gòu)有相對溫和的聚類系數(shù)和有利于個體染色體的多樣性。測試三個經(jīng)典函數(shù)證明IQGA的有效性和優(yōu)越性。關(guān)鍵詞改進(jìn)量子遺傳算法量子遺傳算法NW網(wǎng)絡(luò)模型小世界1引言遺傳算法GA是一種基于進(jìn)化理論適者生存15的隨機(jī)搜索算法。他具有并行性和通用性的特點(diǎn)。然而,在實(shí)際應(yīng)用中,遺傳算法會有收斂速度慢、陷入局部最優(yōu)解的現(xiàn)象。為此做了很多改進(jìn)。其中,在90年代提出的量子遺傳算法QGA613有了很大進(jìn)步。量子遺傳算法實(shí)現(xiàn)了將量子計(jì)算思想運(yùn)用到遺傳算法,大大提高了并行遺傳操作和加速收斂的過程。量子遺傳算法同樣也有缺點(diǎn)。因?yàn)樵诿看辛孔舆z傳算法是選擇一個最佳的量子染色體指導(dǎo)所有染色體的進(jìn)化,這種方法破壞了種群的多樣性,使結(jié)果趨向局部最優(yōu)解。本文中，從染色體種群的結(jié)構(gòu)的角度來和缺陷進(jìn)行了分析。為了克服這種缺點(diǎn),一種基于小世界理論1416的改進(jìn)的量子遺傳算法IQGA被提出。IQGA介紹了NW網(wǎng)絡(luò)模型15和改善種群結(jié)構(gòu),因此種群具有多樣性。IQGA的有效性和優(yōu)越性通過典型函數(shù)的測試演示了。2量子遺傳算法量子遺傳算法是結(jié)合遺傳算法和量子計(jì)算。它是基于量子向量的量子位編碼的染色體,染色體的更新通過量子門旋轉(zhuǎn)門和量子非門。最終找到期望的最優(yōu)解。21量子位編碼在量子遺傳中量子位是信息的最小單位。量子位可以在1或0態(tài),或任何態(tài)的疊加,即量子位可以|0,|1,或是他們的任何疊加態(tài)。因此,它可以表示為|0|1,1和兩個復(fù)數(shù)滿足|2|2|1|2|和|2|分別表示|0和|1的概率。在量子遺傳算法中,量子比特位用于表示一個基因可能表達(dá)的所有可能的信息,而不是一系列確定的信息。對這種基因的任何操可能對所有可能的信息同時施加影響。此外,可以將染色體編碼為K代表每個基因在染色體上的位置,而M是每個染色體的基因數(shù)量。XY和XY1XM,1YK是兩個復(fù)數(shù)滿足|XY|2|XY|21。22進(jìn)化操作進(jìn)化操作是量子旋轉(zhuǎn)門實(shí)現(xiàn)的。它是IIT和I,IT是第I個1MK分別更新前和更新后處理染色體的量子位。I旋轉(zhuǎn)角,其大小和方向可以通過調(diào)節(jié)對策7,10,11來改變。23工作流的實(shí)現(xiàn)量子遺傳算法詳細(xì)運(yùn)行過程如下101初始化種群。所有基因的染色體是初始化,這意味著一個染色體所表達(dá)的是21其全部可能狀態(tài)的等概率疊加；2最初觀察所有的個體,一組解集為PTPT1PT2,。得到了PTN,。PTJ表示第J個染色體的第T代即第J個染色體的觀察結(jié)果。表示為一個二進(jìn)制字符串,每個位是0或1。通過生成一個在01的隨機(jī)數(shù)。如果它是大于概率振幅的平方,位設(shè)置為1,否則為0。然后算出每個方案的值,記錄最優(yōu)個體和對應(yīng)的適應(yīng)度作為下一代進(jìn)化的目標(biāo)；3進(jìn)入算法的迭代階段。首先,結(jié)束迭代的條件是否得到滿足。如果滿足,那么算法結(jié)束。否則,對種群中的每個個體實(shí)施一次測量，得到相應(yīng)的確定解，對各確定解進(jìn)行適應(yīng)度評估4基于當(dāng)前最優(yōu)個體,利用量子旋轉(zhuǎn)門對個體實(shí)施調(diào)整，得到新的種群。在更新的過程中,計(jì)算種群個體適應(yīng)度。與當(dāng)前目標(biāo)的適應(yīng)度相比,相應(yīng)調(diào)整個別量子位的染色體；5將前一代的最優(yōu)解與現(xiàn)在的比較。更好的選擇一個作為下一代進(jìn)化的目標(biāo),返回步驟3；3網(wǎng)絡(luò)似乎分析標(biāo)準(zhǔn)的實(shí)現(xiàn)如果每個量子染色體被視為一個節(jié)點(diǎn),然后量子遺傳算法標(biāo)準(zhǔn)的種群相當(dāng)于一個完全連接網(wǎng)絡(luò)的聚類系數(shù)和平均路徑長度短,如圖1所示。這種網(wǎng)絡(luò)結(jié)構(gòu)有利于染色體的信息共享,但是對于量子遺傳算法,它削弱了個體染色體的多樣性。原因是只有一個最好的染色體作為所有染色體的進(jìn)化更新的目標(biāo)。每個染色體進(jìn)化按照最好的。結(jié)果,算法局部最優(yōu)和不成熟的現(xiàn)象出現(xiàn),即整個種群收斂到第一個近似最優(yōu)解。相反,如果采用另一個拓?fù)浣Y(jié)構(gòu),即多群結(jié)構(gòu)。如圖2所示,染色體分為成一些子群體,他們每個人都建立自己的進(jìn)化目標(biāo)。所有的群體是相互獨(dú)立的。在這種情況下,染色體是選為進(jìn)化的目標(biāo),這有利于種群的多樣性。然而,這種新結(jié)構(gòu)相對平均路徑較長和群體不能交換信息。因此該算法缺乏適當(dāng)?shù)男畔砀路N群和收斂緩慢。因此,上述兩種結(jié)構(gòu)都不適合量子遺傳算法。4小世界理論小世界網(wǎng)絡(luò)的現(xiàn)象是在現(xiàn)實(shí)網(wǎng)絡(luò)的集群表現(xiàn)。1967年,哈佛大學(xué)的教授STANLEYMILGRAM通過連鎖信實(shí)驗(yàn)，發(fā)現(xiàn)“六度分離”現(xiàn)象,也被稱為“小世界”。在此基礎(chǔ)上,1998年WATTS和STROGATZ提出了一個小世界網(wǎng)絡(luò)模型WS模型14，它以概率P重新連接固定網(wǎng)絡(luò)中的每一個環(huán)節(jié)。之后,NEWMAN和WATTS改進(jìn)WS模型和提出了先進(jìn)的NW網(wǎng)絡(luò)模型15。模型增加了任意選擇兩個長距離節(jié)點(diǎn)連接,并保留原始連接。這個過程如圖3所示。原始連接在網(wǎng)絡(luò)被稱為緊密聯(lián)系，添加連接被稱為無力連接。研究表明,無力連接很難改變聚類系數(shù),但他們可以大大減少網(wǎng)絡(luò)的平均路徑長度。5一種改進(jìn)的量子遺傳算法51鳥眼視圖在根據(jù)第三節(jié)的分析，為了迅速收斂和避免早熟，染色體種群網(wǎng)絡(luò)應(yīng)該有相對溫和的聚類系數(shù)和平均路徑短的特點(diǎn)。因此，將小世界理論引用到量子遺傳算法提出了IQGA。種群網(wǎng)絡(luò)轉(zhuǎn)化為一個小世界網(wǎng)絡(luò)。因此,上述問題得到解決。52IQGA的設(shè)計(jì)IQGA主要通過以下幾方面改進(jìn)傳統(tǒng)量子遺傳算法。1所有染色體分成一些子群體。2之后的一輪進(jìn)化操作,每一個子群體中選擇最好的染色體作為下一輪的進(jìn)化的目標(biāo)。在這個過程中,所有染色體的子群體參加競爭。所以每個子群是一個完全連接的網(wǎng)絡(luò)。每個染色體通過強(qiáng)連接連接其他染色體。3進(jìn)化操作的實(shí)現(xiàn)過程,染色體不是簡單地選擇其子種群最好的染色體作為進(jìn)化目標(biāo),而是有一定的概率選擇其他群體最好的染色體。所以在這個染色體和其他群體之間的無力連接被改變。群體之間的信息交換和收斂速度都有提高。IQGA的種群結(jié)構(gòu)如圖4所示。53工作流的IQGAIQGA的詳細(xì)工作過程如下1種群被分為一些子群體和所有染色體都初始化。2觀察每一個在子種群的的實(shí)現(xiàn)的染色體,分別計(jì)算子群的每個適應(yīng)度值。然后保存最好的個體為下一代進(jìn)化的目標(biāo)。3進(jìn)入算法的迭代階段，首先,結(jié)束迭代的條件是否得到滿足。如果滿足,那么算法結(jié)束。否則,對種群中的每個個體實(shí)施一次測量，得到相應(yīng)的確定解，對各確定解進(jìn)行適應(yīng)度評估。4基于當(dāng)前最優(yōu)個體,利用量子旋轉(zhuǎn)門對個體實(shí)施調(diào)整，得到新的種群。在更新的過程中,計(jì)算種群個體適應(yīng)度。與當(dāng)前目標(biāo)的適應(yīng)度相比,相應(yīng)調(diào)整個別量子位的染色體。5將前一代的最優(yōu)解與現(xiàn)在的比較。更好的選擇一個作為下一代進(jìn)化的目標(biāo),返回步驟3。6、實(shí)驗(yàn)和測試61實(shí)驗(yàn)的設(shè)計(jì)為了驗(yàn)證的有效性IQGA,將三個經(jīng)典測試函數(shù)用于實(shí)驗(yàn)。對比實(shí)驗(yàn)與標(biāo)準(zhǔn)QGA的結(jié)果得出結(jié)論。這三個函數(shù)是1RASTRIGRIN”函數(shù)最優(yōu)解F10,0,002GRIEWANK函數(shù)最優(yōu)解F20,0,003ACKLEY函數(shù)XI32，32最優(yōu)解F30,0,00IQGA和QGA在WINDOWSXP環(huán)境下用C語言實(shí)現(xiàn)。染色體的總數(shù)是200和迭代的次數(shù)是2000次。在IQGA中,種群分為20組。進(jìn)行了兩個實(shí)驗(yàn)。以概率P對IQGA無力連接測試的性能在實(shí)驗(yàn)1進(jìn)行測試和實(shí)驗(yàn)2中是對兩個算法進(jìn)行了比較。62結(jié)果與分析621實(shí)驗(yàn)1P的值被設(shè)置為0,01,021。根據(jù)這個值,每個函數(shù)測試10次。然后平均計(jì)算。結(jié)果如圖5至7所示。有上面的三幅圖表明,如果P很小,小組互相學(xué)習(xí)的概率很小和信息共享的程度很低。因此,種群停滯。當(dāng)P值范圍在06和08之間,信息充分共享,IQGA獲得更好的解。因此,在接下來的實(shí)驗(yàn)中,P值設(shè)置為07。632實(shí)驗(yàn)2每個函數(shù)測試分別用IQGA和QGA測試20次。表1顯示了測試20次的平均解。表2顯示了兩種算法的最優(yōu)解的比較。發(fā)現(xiàn)解決方案通過IQGA總是比那些通過QGA的好,特別是F3。每個函數(shù)的進(jìn)化的最優(yōu)方案,顯示在圖8到10。從這個數(shù)據(jù)，通過QGA的方法比IQGA也要快,在初始階段。但他們通常經(jīng)過400輪停止。會掉入不成熟的狀態(tài)和停滯不前的狀態(tài)。相比之下,通過IQGA解決方案發(fā)展速度仍然緩慢甚至經(jīng)過700輪后,因此好多了。7、結(jié)論種群結(jié)構(gòu)對算法的性能有很大的影響。和標(biāo)準(zhǔn)的QGA缺點(diǎn)來源于結(jié)構(gòu)上的缺陷。引入NW模型后,新的種群結(jié)構(gòu)有一個相對溫和的聚類系數(shù)和較短的平均路徑長度,這是有利于種群的多樣性以及信息的交換。因此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