學(xué)位論文--基于量子遺傳算法的函數(shù)尋優(yōu)算法設(shè)計

畢業(yè)論文（設(shè)計）題目：基于量子遺傳算法的函數(shù)尋優(yōu)算法設(shè)計學(xué)院：數(shù)理與信息學(xué)院學(xué)生姓名：專業(yè)：計算機科學(xué)與技術(shù)班級：指導(dǎo)教師：起止日期：2014年11月16日至2015年6月12日2015年5月13日浙江海洋學(xué)院畢業(yè)論文PAGEII基于量子遺傳算法的函數(shù)尋優(yōu)算法設(shè)計摘要量子遺傳算法(QGA)是20世紀90年代后期興起的一種嶄新的遺傳進化算法。該算法主要是將量子計算的概念引入其中，將量子的態(tài)矢量表達引入了遺傳編碼，使一條染色體可以表達多個信息態(tài)的疊加，同時利用量子旋轉(zhuǎn)門實現(xiàn)染色體的演化，實現(xiàn)了目標解的進化。相比傳統(tǒng)遺傳算法，量子遺傳算法能夠在較小的種群規(guī)模下，快速的收斂到全局最優(yōu)解。本文首先介紹了量子遺傳算法的基本原理與算法結(jié)構(gòu)，然后對量子遺傳算法提出疑問。雖然量子遺傳算法的優(yōu)化性能大大優(yōu)于傳統(tǒng)遺傳算法，但是，對于一些多峰函數(shù)的優(yōu)化問題，該類算法依舊容易陷入“局部最優(yōu)”。在實際的應(yīng)用中有很多優(yōu)化問題都是多變量的連續(xù)優(yōu)化問題，現(xiàn)有的量子遺傳算法不能有效的解決這些問題。針對量子遺傳算法容易陷入局部最優(yōu)和未成熟收斂的缺陷，我們提出了一種新的優(yōu)化算法——含有退火操作的量子遺傳算法，該優(yōu)化算法能夠以可變的概率選擇性地接受惡化的優(yōu)化函數(shù)解，使種群解集的進化方向改變，不在依靠當(dāng)前解進行遺傳演化。從而使算法不易“早熟收斂”。而且在該算法中加入了全干擾的量子交叉操作，使各染色體能進行遺傳信息的交換，使種群染色體更具有代表性。最后根據(jù)改進后的方案，對改進的量子遺傳算法進行了數(shù)值仿真。有效地證明了改進算法在函數(shù)尋優(yōu)方面的優(yōu)越性?！娟P(guān)鍵詞】量子遺傳算法，量子編碼，退火思想，量子交叉，函數(shù)尋優(yōu)浙江海洋學(xué)院畢業(yè)論文PAGE1DiscoveryofFunctionExtremeValueBasedonQuantumGeneticAlgorithmAbstractQuantumgeneticalgorithm(QGA)wasoriginatedinthelate1990sasanewgeneticevolutionalgorithm,whichintroducestheconceptofquantumcomputationintogeneticalgorithm,i.e.,introducingquantumstatevectorexpressionofthegeneticcodesothatachromosomecanexpressthesuperpositionofmultiplekindsofinformation.Moreover,theevolutionofthechromosomebyusingquantumrevolvingdoor,realizethegoalofevolution.Comparedwiththetraditionalgeneticalgorithm,Thequantumgeneticalgorithmcansrapidlyconvergencetotheglobaloptimalsolutionunderthesmallerpopulationsize.Thispaperfirstintroducesthebasicprincipleofquantumgeneticalgorithmandalgorithmstructure.Andthenthedefectsexistinginthecurrentquantumgeneticalgorithmisproposed.Althoughquantumgeneticalgorithmtooptimizeperformancegreatlysuperiortothetraditionalgeneticalgorithm.Especiallyformultimodalfunctionoptimizationproblems,QGAalsohasthetendencytofallintolocaloptimum.Asformanymultivariatecontinuousoptimizationproblemsinactualapplication,theexistingQGAcannotsolvetheseproblemseffectively.SinceQGAmaybetrappedinlocaloptimumandthedefectofprematureconvergence,weproposedanewalgorithm,QuantumGeneticAlgorithmwithAnnealingOperation(QGAAO).Thealgorithmcanselectivelyacceptdeterioratingatacertainprobabilitysothatpopulationhasmorechancetojumpoutthelocaloptimaltoavoidprematureconvergence.Moreover,globaldisturbhasbeenaddedtothealgorithmofthequantumcrossoveroperation,itcanmakechromosomesexchangemoregeneticinformation.Itcanbetterrepresentthechromosomepopulation.Finally,accordingtotheimprovedscheme,theimprovedquantumgeneticalgorithmwascommittedforthenumericalsimulation.Thetestprovedthattheimprovedalgorithmeffectivelysuperiorityintermsoffunctionoptimization.【Keywords】quantumgeneticalgorithm,quantumcoding,annealingthought,quantumcrossover,functionoptimization

目錄摘要 IAbstract II1.緒論 11.1遺傳算法 11.2量子計算 11.3函數(shù)優(yōu)化 11.4選題背景和意義 22.量子遺傳算法 32.1量子遺傳算法概述 32.2量子遺傳算法研究意義 32.3量子遺傳算法的基本原理 42.3.1.量子比特 42.3.2染色體表示方法 52.3.3量子旋轉(zhuǎn)門 62.5量子遺傳算法步驟及流程圖 72.5.1量子遺傳算法的步驟流程 72.5.2量子遺傳算法的流程圖 73量子遺傳算法的改進 93.1量子遺傳算法存在問題 93.2改進方案的基本思想 93.2.1全局量子交叉 93.2.2模擬退火思想 103.2.3模擬退火算法的概念 113.2.4模擬退火算法的基本流程 123.3改進的量子遺傳算法的具體實現(xiàn) 123.3.1模擬退火算子及參數(shù)選取 133.3.2基于模擬退火的量子遺傳算法具體實現(xiàn) 133.3.3基于模擬退火的量子遺傳算法流程圖 133.4改進的量子遺傳算法的優(yōu)點 144算法性能測試及分析 164.1典型測試函數(shù) 164.1.1簡單平方和函數(shù) 164.1.2Rastrigrin函數(shù) 164.1.3DeJong函數(shù)F2 174.1.4Goldsten-Price函數(shù) 174.1.5Six-humpCamelBack函數(shù) 184.2算法參數(shù)設(shè)定 184.3測試結(jié)果即分析 195總結(jié)與展望 245.1論文總結(jié) 245.2展望 24參考文獻 261.緒論1.1遺傳算法在20世紀70年代美國密西根大學(xué)教授J.Holland第一個提出了基于概率的優(yōu)化算法——遺傳算法[1]（GA）。遺傳算法的原理跟自然界的遺傳進化演化原因是一致的。遺傳算法根據(jù)優(yōu)化函數(shù)的目標函數(shù)來進行全局自適應(yīng)的概率搜索[2]，尋找優(yōu)化函數(shù)的最優(yōu)值。由于遺傳算法可以不依靠優(yōu)化函數(shù)的形式與不受外界因素的影響，所以，遺傳算法在實際優(yōu)化應(yīng)用中得到了良好的應(yīng)用。因為遺傳算法具有良好的適用性、全局性、并行高效的優(yōu)化性能與魯棒性[3]，所以它具有誘人的吸引力，吸引人們前去研究。對于現(xiàn)實中的應(yīng)用，它對外界的要求不嚴格，能夠廣泛的應(yīng)用，所以它具有很好的應(yīng)用前景。但是，如果在遺傳算法中的選擇、交叉和變異的操作方式選取不當(dāng)，那么算法在迭代次數(shù)、收斂速度、優(yōu)化性能等方面都會輕易地受到影響，并且，這都會使優(yōu)化函陷入局部極值的這一陷阱。1.2量子計算量子計算[4]（QC）的概念是在二十世紀七十年代提出來的。那時的主要研究內(nèi)容是計算三個特性之間相互的關(guān)系。P.Benioff與八十年代率先提出了量子計算可以用來進行仿真數(shù)據(jù)的計算[5]。在1994年，美國的Shor教授第一次將量子計算運用到了大數(shù)的因子分解中，從那時開始，量子計算的研究方向有了充分的拓寬[6]。量子計算有新的研究動力。使用量子態(tài)[4]作為計算中的基本的信息的存儲單位，是量子計算的一大特色。使用量子態(tài)具有的疊加、糾纏和干涉等特點可以很好的解決一些常見的經(jīng)典問題。通常信息是用一種物質(zhì)或存在的狀態(tài)來表示的。計算機最早是使用紙帶的穿孔方式來表示二進制的，但隨著科學(xué)技術(shù)的發(fā)展，到后來計算機開始使用晶體管的開關(guān)狀態(tài)來表示二進制的信息。現(xiàn)在隨著量子力學(xué)的發(fā)展，其揭示了微觀粒子的運動狀態(tài)。開始使用原子的運動狀態(tài)來表示二進制。量子計算就是利用原子中電子的兩種自旋狀態(tài)來表示信息的[7]。量子計算要想實現(xiàn)其真正意義上的并行計算就必須在量子計算機上面，但是我們可以將量子計算機制和量子信息運用到智能算法中，或者是將已有的優(yōu)化算法和量子算法相結(jié)合，使算法的優(yōu)化性能得到提高，使它具有傳統(tǒng)優(yōu)化算法所不具有的優(yōu)異性能。1.3函數(shù)優(yōu)化函數(shù)優(yōu)化問題是量子遺傳算法的經(jīng)典應(yīng)用領(lǐng)域[19]，也是對量子遺傳算法進行性能評價的常用算法.對于一些不規(guī)則或者是多變的與多值的函數(shù)的優(yōu)化問題，使用其它方法去優(yōu)化解決它們，是比較麻煩的，但是如果我們使用量子遺傳算法就可能很好的解決這些問題，輕易地得到較好的優(yōu)化結(jié)果。函數(shù)優(yōu)化[8]問題簡單講就是求取一個函數(shù)中的最小值或者是最大值。函數(shù)的優(yōu)化問題通常的描述是：設(shè)S是上的有界的子集，：S->R是n維的實值函數(shù)。如果在領(lǐng)域內(nèi)能找到一個點的值小于該領(lǐng)域內(nèi)其它所有點的值，那么我們就稱該點是該函數(shù)在領(lǐng)域內(nèi)的最小值所在的點。通常，此點就是我要求的最優(yōu)值的點。函數(shù)優(yōu)化問題通常是一個非常復(fù)雜的優(yōu)化問題，特別是對于那些不可微的或者多極值的函數(shù)優(yōu)化，常常是不能很好的求到有效解的。但是，對于新出現(xiàn)的量子遺傳算法來講，它可以較好的避免此類情況，在處理一些復(fù)雜的優(yōu)化函數(shù)時，依舊能保持較好的性能，原因在于量子遺傳算法能很好的描繪出全局最優(yōu)的解集，它將每種可能的最優(yōu)解都可由一個染色體來描述，相比傳統(tǒng)的遺傳算法的染色體只能表示一個確定的解，但對于量子遺傳算法的一個染色體，卻可以表示多個優(yōu)化解，有如此特性的染色體組成的種群，能更好的代表優(yōu)化解集。之后它在按遺傳進化學(xué)的規(guī)律來進行選擇、交叉與變異操作，使染色體根據(jù)每代的進化目標來進行遺傳“進化”，直到最后滿足終止條件為止。1.4選題背景和意義量子遺傳算法在現(xiàn)代的許多的應(yīng)用優(yōu)化領(lǐng)域發(fā)揮著至關(guān)重要的作用。量子遺傳算法與傳統(tǒng)的遺傳算法的內(nèi)在原理是一樣，它們都是一種基于自然界生物“優(yōu)勝劣汰”的生存規(guī)則的一種進化優(yōu)化算法。它是一種適合復(fù)雜系統(tǒng)優(yōu)化計算的優(yōu)化技術(shù).然而現(xiàn)在的量子遺傳算法也存在著種種的問題。它的不足方面有：第一，由于算法是通過概率搜索來獲得最優(yōu)值的，因此會不可避免的產(chǎn)生概率搜索[7]所具有的普遍問題——盲目性與隨機性，部分個體將不可避免的產(chǎn)生退化，從而會大大降低算法的尋優(yōu)能力。第二，由于要進行大量的適應(yīng)度值的計算與個體染色體的進化操作，這些操作大大的增加了算法的計算量，因而影響算法的運行時間，降低了算法的性能；第三，對于量子旋轉(zhuǎn)門的轉(zhuǎn)角方向、大小，一視同仁，沒有考慮染色體之間的差異。因此，應(yīng)加注重量子遺傳的種群大小的選擇，即進化策略的設(shè)計與實施。第四，在算法優(yōu)化的后期，優(yōu)化算法可能會處于停滯階段或進化的速度很緩慢，因此那是算法容易陷入“早熟收斂”這一缺陷。第五，算法每次進化的方向都是以最優(yōu)值適應(yīng)度值的個體。容易陷入局部的最優(yōu)解。第六，現(xiàn)有的量子遺傳算法缺少染色體之間的信息交流，不能充分的使用染色體的進化的特點。對于存在的問題，本課題進行了詳細的研究，并且提出了一些解決方案。本課題提出了一種基于退火思想和量子交叉的量子遺傳算法。這個算法使量子遺傳算法的種群具有更好的代表性，通過這種算法極大的提高了量子遺傳算法的性能。2.量子遺傳算法2.1量子遺傳算法概述將經(jīng)典量子計算（QC）與傳統(tǒng)遺傳算法它們的算法操作方式相互的融合之后產(chǎn)生了新的優(yōu)化算法——量子遺傳算法（QuantumGeneticAlgorithm，QGA）[9]。它既具有傳統(tǒng)遺傳算法所具有的優(yōu)化算法的普遍性與通用性，又能利用量子計算中信息存儲方式的優(yōu)點，使算法具有比以往更好的優(yōu)化性能。是一種21世紀新發(fā)展起來的概率自優(yōu)化的進化算法。量子遺傳算法與傳統(tǒng)的遺傳算法相比較它的優(yōu)點在染色體的表示方式上，傳統(tǒng)的遺傳算法的染色體是一個確定的值，只能代表一個優(yōu)化解，然而，量子遺傳算法中的染色體不是一個確定值，一個普通的染色體能表示該優(yōu)化函數(shù)所需要的所有的優(yōu)化解，因此，量子遺傳算法中的染色體對于優(yōu)化解集具有更好的代表性，更能完整地描述優(yōu)化函數(shù)的優(yōu)化解集，而且，相比傳統(tǒng)的遺傳算法的進化方向與進化的值是唯一確定的，但對于量子遺傳算法來講，它的進化操作是通過量子旋轉(zhuǎn)門來實現(xiàn)的，而且旋轉(zhuǎn)門的大小與方向都是隨著遺傳的迭代次數(shù)可以改變的，所以通過此類操作能更好的使染色體進行優(yōu)化演化?？傊?，實現(xiàn)了比傳統(tǒng)的遺傳算法更好的效果。它基于量子計算的原理，使用量子的特性來表達優(yōu)化函數(shù)的解集，即染色體，所以相比普通算法的優(yōu)化解集它能攜帶更多的信息。也因為如此，他能更好的表達全體優(yōu)化函數(shù)的解集。使優(yōu)化解集種群更加地多樣化，最后，使用旋轉(zhuǎn)門來實現(xiàn)染色體的進化演化操作，通過旋轉(zhuǎn)門的演化操作使染色體的進化過程更加地穩(wěn)定，從而使算法性能更加的優(yōu)越。2.2量子遺傳算法研究意義傳統(tǒng)的遺傳算法在對于處理一些簡單的優(yōu)化函數(shù)問題時，表現(xiàn)了優(yōu)越的優(yōu)化性能。通過最基本的三個遺傳操作選擇、交叉、變異來尋找最優(yōu)的優(yōu)化解。特別是遺傳算法所具有的不受優(yōu)化問題的性質(zhì)，大小以及優(yōu)化的依據(jù)等外界因素的影響。它只是通過概率的普遍搜索來獲得優(yōu)化函數(shù)的優(yōu)化解，所以，他能具有良好的通用性能，在社會實踐中得到了廣泛的應(yīng)用。但隨著應(yīng)用范圍的增加，人們也逐漸的發(fā)現(xiàn)遺傳算法所具有的一些缺陷。由于傳統(tǒng)遺傳操作的隨機性，如選擇、交叉與變異都是基于概率的選擇的操作[10]，所以不可避免的會存在概率優(yōu)化算法的缺點。傳統(tǒng)遺傳算法會表現(xiàn)出遺傳次數(shù)增加卻依舊得不到較好的優(yōu)化解集，對于全局的優(yōu)化搜索能力較弱，而且容易陷入局部極值這一缺點。在傳統(tǒng)的遺傳算法中如果種群的大小選擇不當(dāng)，對于優(yōu)化的效果的影響將會非常地明顯，種群小將會使優(yōu)化算法的選擇領(lǐng)域受到限制，不能很好地搜索全局的優(yōu)化解集，影響尋優(yōu)能力，然而種群過大則會使優(yōu)化算法的計算復(fù)雜度急速的上升。，傳統(tǒng)的遺傳算法的染色體優(yōu)化解是一個確定的值，只能代表一個優(yōu)化函數(shù)的優(yōu)化解，然而，量子遺傳算法中的染色體優(yōu)化解不是一個確定值，一個普通的染色體能表示該優(yōu)化函數(shù)所需要的所有的優(yōu)化解，因此，量子遺傳算法中的染色體對于優(yōu)化函數(shù)的全局優(yōu)化解集具有更好的代表性，更能充分的描繪優(yōu)化函數(shù)的優(yōu)化解集，并且，利用旋轉(zhuǎn)門來實現(xiàn)每個染色體解的進化操作，使算法的遺傳進化演化操作更加的穩(wěn)定，算法性能更加優(yōu)越。量子遺傳算法是利用量子計算表示信息的特點，來構(gòu)成它特有的染色體的形態(tài)，使得量子遺傳算法的染色體具有更多地優(yōu)化函數(shù)的優(yōu)化解集的信息。更好的表達了全局函數(shù)優(yōu)化解集的樣貌。最后則是再通過量子的概率幅交叉操作來實現(xiàn)種群解的多樣性。2.3量子遺傳算法的基本原理2.3.1.量子比特在傳統(tǒng)的遺傳算法中，我們使用計算機中的二進制表示方式來表示優(yōu)化解集的遺傳信息。我們將存儲遺傳信息的二進制稱之為比特(Bit)。而在量子遺傳算法中，我們采用|0>和|1>的單量子比特的疊加態(tài)來表示遺傳信息[11]。它們跟傳統(tǒng)的信息表達的方式的區(qū)別在于它不止止只有兩種狀態(tài)可以選擇，而且它們可以是兩種基本狀態(tài)的任意的疊加，所以使用此種的信息表示方式編碼組成染色體也是一個不定值，能更好的代表函數(shù)的優(yōu)化解集。在量子遺傳算法中的量子位可以是|0>到|1>中的任意的值，所以一個量子位的狀態(tài)的表達式可以為：(2.1)其中量子態(tài)的概率幅與是一對平方和1的復(fù)數(shù)，對優(yōu)化種群進行一次測量操作，可能會以2的概率大小坍縮到|0>狀態(tài)，或者它會以||2的概率坍縮到|1>的狀態(tài)，并且它們會滿足下面的表達式條件：2+||2=1(2.2)在式(2.2)中，2表示|0>的概率，||2表示|1>的概率，量子態(tài)坍縮是為了結(jié)合適應(yīng)度值來優(yōu)選種源，因此，如果一個系統(tǒng)有m個量子位，則該系統(tǒng)可同時描述2m個狀態(tài)，然而，對于量子態(tài)[12]的每一次觀察，該量子位都只會坍縮到一個確定的狀態(tài)。在這里會得到量子態(tài)的確定值，此值的形體都是由量子比特概率的大小所決定的的。產(chǎn)生|0>或|1>狀態(tài)的具體過程如下：首先，先生成一個在零到一之間的隨機數(shù)r,如果r>2，則坍縮到|0>的狀態(tài)，否則坍縮到|1>的狀態(tài).2.3.2染色體表示方法在傳統(tǒng)遺傳算法中，染色體的表示方式在進化演化計算之前就是確定的（使用確定的二進制表示優(yōu)化函數(shù)的染色體解集），所以在優(yōu)化解集的表示方面，會存在一些缺陷。然而，在現(xiàn)在的量子遺傳算法中，一個基因采用的是量子比特來表示[13]。該基因可以是“0”態(tài)或“1”態(tài)，也可以是它們之間的任意疊加態(tài)。即每一個基因位不再代表地是某一確定的遺傳信息，而是包含該優(yōu)化函數(shù)所需要的所有的優(yōu)化解集信息，因此，我們對于任意基因位的任一操作都可能會使種群中所有的優(yōu)化解集信息產(chǎn)生變化。這里將繼續(xù)使用傳統(tǒng)遺傳算法中的二進制，對于優(yōu)化函數(shù)的目標解集采用量子比特編碼，這樣就可以用一個量子比特來表示解集的兩個狀態(tài)，兩個量子比特就可以表示四種狀態(tài)。此種編碼方式具有通用性好，且實現(xiàn)簡單等優(yōu)點。量子遺傳是使用量子比特來表達一個基因，由若干個基因來組成一個染色體解。這里將會使用一對平方和為1的復(fù)數(shù)對來表示染色體中的一個量子比特，則c個j位基因構(gòu)成的一個染色體可以表示為：(2.3)式中：i是染色體的編號，n是染色體當(dāng)前進化的代數(shù)，c是基因位的個數(shù)，第n代第i個個體的染色體用qtj描述的，j是每個用二進制表示的每個優(yōu)化解中含有的量子比特數(shù)。在剛開始的初始化情況下，都會以的形式來初始化種群中的全部染色體解集的所有基因，等概率的疊加是量子遺傳算法中染色特初始化的一中特殊情況。如果是在一個以3個量子比特位的染色體中，那么它會具有3對概率幅，如下所示：（2.4）則這個系統(tǒng)的狀態(tài)可以描述為：(2.5)從上面的系統(tǒng)狀態(tài)描述可以知道優(yōu)化函數(shù)的染色體解集的狀態(tài)：|000>、|001、|010>、|011>、|100>、|101>、|110>、|111>的狀態(tài)的概率大小分別為：3/32，1/32，9/32，3/32，3/32，1/32，9/32，3/32。所以上式（2.4）描述的三個比特量子系統(tǒng)能同時包含8個狀態(tài)，如果用傳統(tǒng)的表示方法那么至少需要8條的染色體來表示，這就是量子遺傳染色體組少，卻能擁有豐富種群的關(guān)鍵，并且隨著趨近與1或0，染色體收斂于一個確定的狀態(tài)。2.3.3量子旋轉(zhuǎn)門量子旋轉(zhuǎn)門作為量子遺傳算法中進化演化操作的執(zhí)行機構(gòu)[14]，在優(yōu)化算法中具有重要的地位。所以對于不同的優(yōu)化函數(shù)的優(yōu)化問題我們要區(qū)別的對待，在了解需要優(yōu)化函數(shù)的特性之后才能正確的選擇合適的量子旋轉(zhuǎn)門操作[15]。量子旋轉(zhuǎn)門的功能結(jié)構(gòu)如下所示：(2.6)它的更新過程如下：(2.7)其中，第i個染色體進行旋轉(zhuǎn)門演化操作前后的概率幅由描述；為旋轉(zhuǎn)角的大小，其大小由事先定好的調(diào)整策略決定，該調(diào)整策略是一種通用的。與優(yōu)化問題無關(guān)的調(diào)整策略，如表2-1表2-1旋轉(zhuǎn)角度選擇表00FALSE0000000TRUE0000001FALSE0.01+1-1001TRUE0.01-1+1010FALSE0.01-1+1010TRUE0.01+1-1011FALSE0000011TRUE00000表中中i來表示當(dāng)前值是染色體的第幾位；中的i表示的是為當(dāng)前的最優(yōu)染色體的第i位上的表示情況；適應(yīng)度函數(shù)為；為旋轉(zhuǎn)角方向；旋轉(zhuǎn)角的大小用來描述，它的大小的取值通常是在0.005到0.05之間的某一值，旋轉(zhuǎn)角的大小可以是某一確定值，也可以根據(jù)進化的實際情況來進行動態(tài)微調(diào)整，同過此類操作能很好的達到函數(shù)優(yōu)化效果的要求。它們的值都是根據(jù)表2-1中所列的選擇策略確定的。量子旋轉(zhuǎn)門的運行過程如下所示：首先，將通過適應(yīng)度函數(shù)計算出當(dāng)前的個體的適應(yīng)度值，然后與當(dāng)前優(yōu)化種群最佳的適應(yīng)度值進行比較，如果當(dāng)代優(yōu)化種群個體的適應(yīng)度值大于現(xiàn)有的最優(yōu)優(yōu)化適應(yīng)度值,那么就應(yīng)該調(diào)整中相應(yīng)的量子比特位，能夠讓概率幅的演化方向是朝著向著量子位的，不然，如果<,那么就應(yīng)該中量子比特位進行微調(diào)，確保概率幅的演化方向是朝著的方向。2.5量子遺傳算法步驟及流程圖2.5.1量子遺傳算法的步驟流程量子遺傳算法的步驟流程：對初始種群Q（）進行函數(shù)優(yōu)化解集種群的初始化操作,描述的是所有優(yōu)化解集種群中每個染色體上的一個基因位，是它們初始的大小，這就表明一個染色體所描述地是其全部可能的優(yōu)化解集狀態(tài)的等概率的組合。染色體使用的是隨機生成的n個量子比特的編碼；對出使種群中的每個個體進行一次測量，得到對應(yīng)確定的解P，測量過程為：隨機產(chǎn)生一個在0~1之間的隨機數(shù)，若它的大于概率幅的平方，那么測量結(jié)果取值為1，反之，測量結(jié)果取值為0；對各確定染色體優(yōu)化解P進行適應(yīng)度評估操作，以此來得到每個解的適應(yīng)度值的大小，以此來進行下一步的遺傳淘汰選擇操；記錄最優(yōu)個體和對應(yīng)的適應(yīng)度；判斷優(yōu)化算法是否可以結(jié)束優(yōu)化操作，如果現(xiàn)有的優(yōu)化解集滿足優(yōu)化結(jié)束的條件則退出優(yōu)化算法，不然繼續(xù)執(zhí)行優(yōu)化操作；對優(yōu)化解集種群Q中的每個個體即染色體優(yōu)化解進行一次染色體基因位大小的確定操作，通過此操作來得到對應(yīng)遺傳代數(shù)種群的函數(shù)優(yōu)化解集；對各確定解進行適應(yīng)度評估；利用量子旋轉(zhuǎn)門U(t)對每個染色體個體進行一次遺傳演化操作，以此得到新的優(yōu)化函數(shù)的最優(yōu)解集種群Q(t+1);記錄最優(yōu)個體和對應(yīng)的適應(yīng)度；將迭代次數(shù)t加1，返回步驟(5);2.5.2量子遺傳算法的流程圖對應(yīng)的流程圖如圖2-1所示。初始化種群Q(t初始化種群Q(t0)開始評價Q(t0)的各個個體的適應(yīng)度以最優(yōu)個體作為下一代進化目標滿足終止條件測試Q(t)的各個個體評價Q(t)各個個體的適應(yīng)度量子旋轉(zhuǎn)門更新種群，得到下代種群Q(t+1)記錄最優(yōu)個體與適應(yīng)度值t=t+1結(jié)束YN圖2-1量子遺傳算法運行流程框圖

3量子遺傳算法的改進3.1量子遺傳算法存在問題現(xiàn)有的量子遺傳算法在優(yōu)化某些不規(guī)則函數(shù)時，能擁有較好的優(yōu)化性能。但，對于一些特別復(fù)雜的、病態(tài)的優(yōu)化函數(shù)卻不能很好的發(fā)揮其優(yōu)越的性能。量子遺傳算法海存在較多需改進的內(nèi)容：比如說現(xiàn)有的算法中沒有加入量子交叉操作，使得染色體之間的信息不能充分的被利用。而且，與傳統(tǒng)的遺傳算法相比較，雖然現(xiàn)在的量子遺傳算法的性能有了巨大的飛躍，但依舊存在許多缺陷，如下：對于一些多峰值函數(shù)的優(yōu)化問題，普通的量子遺傳算法不能很好的求其最優(yōu)解，然而，現(xiàn)實生活中的很多地實際優(yōu)化應(yīng)用問題都是多峰值、不規(guī)則與變態(tài)的優(yōu)化函數(shù)。并且，對于染色體的演化操作太過單一化，不能充分表達生物的進化過程。而且當(dāng)我們采用經(jīng)典的輪盤賭[16]的方式來決定染色體中基因位的形態(tài)時，很容易讓在進化選擇的早起產(chǎn)生的個別好的個體，在優(yōu)化算法演化地后期產(chǎn)生嚴重的影響，從而使優(yōu)化算法的優(yōu)化性能降低。此類操作也會在優(yōu)化算法演化的后期產(chǎn)生嚴重后果，使染色體演化的操作變得緩慢，使量子旋轉(zhuǎn)門的功能效果不夠明顯。這也會降低函數(shù)優(yōu)化的性能。為了能在實際的優(yōu)化應(yīng)用中更好的發(fā)揮量子遺傳算法的優(yōu)化作用。急需我們改進量子遺傳算法。將模擬退火與量子交叉引入量子遺傳算法中以此來提高算法的優(yōu)化性能。該算法在量子個體上實施量子交叉，增加各染色體之間的信息交流，引入退火思想盡量避免算法在早期時陷入局部的最優(yōu)。使得算法很好的避免了早熟與進化停滯不前的情況。3.2改進方案的基本思想3.2.1全局量子交叉優(yōu)化函數(shù)的解集（染色體）的演化方向是量子遺傳算法中最能體現(xiàn)優(yōu)化種群染色體的現(xiàn)有量子位信息的，即在現(xiàn)有的優(yōu)化解集種群中的當(dāng)前染色體解個體的最優(yōu)確定解以及其對應(yīng)的優(yōu)化適應(yīng)度值的大小。在染色體之間考慮某些基因位的互換有利于實現(xiàn)染色體之間信息的交流，增強種群遺傳的信息利用率[17]。在量子遺傳算法中，由于染色體的狀態(tài)處于疊加的狀態(tài)，不同于傳統(tǒng)的遺傳算法，交叉僅僅局限于兩個染色體之間進行。在量子遺傳算法中我們不能使用傳統(tǒng)的交叉操作，但我們可以采用一種叫做全局干擾交叉的交叉操作，在該交叉操作中使所有的染色體都參于到其中，下面的圖表是我們用來簡單的描述該交叉方式的，即該種群的大小值為3，染色體的個數(shù)為3個，每個染色體的長度為5，該種群結(jié)構(gòu)如表3.1表3.1量子染色體結(jié)構(gòu)1A(1)A(2)A(3)A(4)A(5)2B(1)B(2)B(3)B(4)B(5)3C(1)C(2)C(3)C(4)C(5)其中第二個染色體的第2個量子比特用B（2）來表示，用遞歸的方式來進行全局干擾操作。交叉后的染色體的基因位的確定方法是：交叉前的基因位以現(xiàn)在的基因位序號大小減一在種群中向下移動幾位，如果移動的位數(shù)超過種群染色體數(shù)則除以現(xiàn)在種群的大小后取得的余數(shù)減1就是該基因為向下移動的位數(shù)。表3.2表示的是經(jīng)過全局干擾交叉操作后的染色體組。表3.2交叉后量子量子染色體結(jié)構(gòu)1A(1)C(2)B(3)A(4)C(5)2B(1)A(2)C(3)B(4)A(5)3C(1)B(2)A(3)C(4)B(5)上表展示了染色體解集的的另外一種演化方式，其中新的交叉后的函數(shù)優(yōu)化解是用大寫字母來描述的，如：B（1）—A（2）—C（3）—B（4）—A（5）。通過此類操作，優(yōu)化種群中每個染色體上的量子位信息將會被充分的利用，在種群演化的后期能夠充分保持優(yōu)化解集的多樣性，從而改進了算法的性能。同過量子交叉演化，它會產(chǎn)生個多的新個體使種群更加的多樣化，進而使進化的過程更具有活力，使算法不易陷入局部的最優(yōu)。此操作是借用了量子計算中的量子相干的特性來實現(xiàn)的，在加入該操作后量子遺傳算法的早熟現(xiàn)象能夠很好地得到改善。3.2.2模擬退火思想Metropolis由自然界的高溫退火操作進而得到啟發(fā)，提出了一種模擬自然界退火操作的算法，它也是全局優(yōu)化算法中的一種，通過一種可變的突跳概率使算法跳出局部最優(yōu)這一致命性的缺陷。退火算法的思想是模仿金屬冶煉操作過程來尋找優(yōu)化函數(shù)的全局的最優(yōu)優(yōu)化解。模擬退火法是一種通用的優(yōu)化算法。以下兩個操作是模擬退火算法的主要操作：熱靜力學(xué)操作，用于安排降溫過程；隨機張弛操作，用于搜索在特定溫度下的平衡態(tài)；從金屬冶煉的退火過程，我們可以對退火操作進行簡單的描述，加入模擬退火操作的算法不僅會接受比現(xiàn)在好的優(yōu)化解，還以一定的可變概率接受比現(xiàn)有的解不好的優(yōu)化解，使算法在剛開始演化時不是一直向著最優(yōu)解的方向演化，而且，在剛開時進行優(yōu)化算法演化操作時，設(shè)置的初始溫度會比較高，所以它接受惡化的概率也就比較大，但當(dāng)溫度降低到一定程度的時候，接受惡化解的概率就會接近0，則只會接受優(yōu)化解，算法就趨于最優(yōu)。算法的主要特點有一下幾點：以一定的概率接受惡化的解。溫度控制參數(shù)T，它會將優(yōu)化算法的尋優(yōu)過程劃分為幾個階段，通過使用Metropolis準則計算得到地值來決定各個階段狀態(tài)的取舍。含有退火操作的優(yōu)化算法最優(yōu)能否尋找到全局的最優(yōu)值，Metropolis準則是非常關(guān)鍵的起到?jīng)Q定性作用，通過使用Metropolis準則能較好地避免陷入局部最優(yōu)。模擬退火算法的最顯著的優(yōu)點在于它能夠成功地避免陷入局部的最優(yōu)這一缺陷。形象的形容：好比一名登山運動員要攀登該地區(qū)最高的山峰，在剛剛開始的時候運動員先登上山，但他不知道這山峰是不是附近最高的，所以他還要以一定的概率，下山，嘗試攀登有沒有別的山峰比現(xiàn)在的要更高。3.2.3模擬退火算法的概念溫度（temperature）是一個重要的參數(shù)，對于含有退火操作的優(yōu)化算法而言。它隨著算法的演化時間而逐步的降低，用來模擬金屬冶煉過程中的降溫過程，剛開始，溫度用于限制算法產(chǎn)生的新解與當(dāng)代解之間的差距，即使算法的搜索范圍；其次，接受現(xiàn)有解的概率的大小由現(xiàn)有的溫度所決定的。優(yōu)化算法中溫度的下降速度用退火進度表(annealingschedule)來描述的，要使算法尋找到較好的全局優(yōu)化解，那么就應(yīng)該不退火過程設(shè)置得緩慢一些，這樣就能更好地尋找到函數(shù)的最優(yōu)解，但相應(yīng)的程序運行的時間也會增加。退火進度表包括初始溫度(initialtemperature)以及溫度的更新函數(shù)(temperatureupdatefunction)等參數(shù)。Meteopolis準則：決定著每代函數(shù)優(yōu)化解的保留情況。對于要獲得全局最小值的函數(shù)優(yōu)化尋優(yōu)問題，優(yōu)化算法能夠接受新的優(yōu)化解的概率為：（3.1）其中，x是當(dāng)前的解；為新的解；f(x)為x解的適應(yīng)度的值；T為溫度。式（3.1）的含義是：對于當(dāng)前的解x與新的解，如果f(x)>f(),那么就接受新解為當(dāng)前解；如果大于(0,1)區(qū)間的隨機數(shù)，則依舊接受新的解為當(dāng)前的解，否則，就會拒絕新的解而保留現(xiàn)在的解。該過程會不斷的重復(fù)，可以知道，開始的溫度比較高，算法接受差解的概率也會比較高，這就讓算法有更大的機會跳出局部的最優(yōu)解，隨著退火的進行，溫度會逐漸降低，算法接受差解的概率就會變小。3.2.4模擬退火算法的基本流程模擬金屬冶煉退火操作的主要操作有兩個：第一個，溫度下降的大小值是由固體冷卻過程中的熱靜力學(xué)操作來實現(xiàn)確定的，第二個，在每個的溫度下進行隨機搜索的次數(shù)。在實際應(yīng)用中，退火算法必須有時間的限制，這個需要的條件有：第一，一個起始溫度；第二，一個控制溫度下降的函數(shù)；第三，一個決定在每個溫度下狀態(tài)轉(zhuǎn)移參數(shù)的標準；第四，一個停止溫度；第五，算法停止的條件。模擬退火算法實際上是一種迭代求解的過程，算法反復(fù)執(zhí)行“產(chǎn)生新狀態(tài)->計算目標函數(shù)->判斷是否接受新狀態(tài)->接受/舍棄的”過程，它的基本流程如下：初始化，初始溫度T，初始解S，每個T值的迭代次數(shù)；對種群完成第（3）到第（6）；產(chǎn)生新的解;計算增量,其中E(S)為目標函數(shù)；若，則接受作為新的現(xiàn)在的解，不然以概率接受為新的當(dāng)前的解；如果滿足終止條件則輸出當(dāng)前的解作為最優(yōu)解，結(jié)束循環(huán)；T（溫度）會逐步的降低，而且T會慢慢的趨近于0，轉(zhuǎn)到步驟（2）。在算法的執(zhí)行過程中，為了保證算法的收斂能力，要保證退火的初始溫度T盡可能的大，一般情況下T取值為100，L表示對于每一個溫度取值T進行的遺傳進化的演化次數(shù)，考慮到運行算法的時間，我們通常取值在10—20之間。3.3改進的量子遺傳算法的具體實現(xiàn)模擬退火操作的尋優(yōu)過程是通過設(shè)置初始溫度的大小與現(xiàn)實降溫過程的速率來實現(xiàn)的，在溫度較高時候，算法能夠以較高的概率接受比現(xiàn)在不好的優(yōu)化解，通過此操作能避免算法陷入局部極值，而能較好的接受好的優(yōu)化解是在溫度較低的時候，模擬退火的這種搜索模式增強了算法的搜索能力和效率。量子遺傳算法通過使用量子計算中存儲信息的方式，充分的描述了優(yōu)化函數(shù)所有的解集，進而大大的提升了優(yōu)化算法的尋優(yōu)能力。量子遺傳算法是使用量子位來表示遺傳的信息，利用量子計算的一些特性，進行染色體的量子編碼。實現(xiàn)了比傳統(tǒng)的遺傳算法更好的效果。將量子遺傳能充分的描述優(yōu)化的解集的特點與退火操作尋找全局最優(yōu)的能力相結(jié)合，我們稱這種算法為基于模擬退火的量子遺傳算法[20]，算法中，兩種搜索性能相互互補，能使新算法獲得質(zhì)量較高的優(yōu)化解。3.3.1模擬退火算子及參數(shù)選取在模擬退火算子中，初始溫度越大，退回系數(shù)越大（退回系數(shù)小于1的正數(shù)），收斂到全局最優(yōu)解的概率就越大，收斂的時間也就會越長。所以進行參數(shù)選擇的同時要考慮搜索的效率與求解的質(zhì)量。在執(zhí)行完模擬退火操作后，需要把每個染色體個體的量子位信息反應(yīng)到量子編碼上，以便進行量子遺傳算法的操作。在算法的運行過程中退火的溫度系數(shù)一般取為0.95。3.3.2基于模擬退火的量子遺傳算法具體實現(xiàn)引入模擬退火思想后的量子遺傳算法，在每一次迭代進化的時候引入模擬退火算法，來確定每個個體的進化方向?；谀M退火操作的量子遺傳算法具體步驟如下：隨機生成種群并進行初始化；對種群進行測量得到一組確定的狀態(tài)；記錄最佳適應(yīng)度值和對應(yīng)的個體將其作為下一步種群進化的目標；查看優(yōu)化算法是否可以停止，若滿足結(jié)束條件則退出，否則繼續(xù)進行計算；模擬退火操作；當(dāng)溫度過高時，是算法以一定的概率讓量子旋轉(zhuǎn)門不朝著種群目標值的進化方向進化，當(dāng)溫度較低時，是算法接受目標值的進化方向，利用量子旋轉(zhuǎn)門對種群進行更新，然后按照全局交叉的策略對種群進行量子交叉操作，得到子代Q(t+1)記錄最優(yōu)個體和對應(yīng)的適應(yīng)度值；將迭代的次數(shù)加1，返回步驟(4)；3.3.3基于模擬退火的量子遺傳算法流程圖對應(yīng)的流程圖如圖3-1迭代數(shù)加1迭代數(shù)加1開始結(jié)束隨機生成種群并進行初始化記錄最佳適應(yīng)度值和對應(yīng)的個體作為下一步種群更新的目標值滿足終止條件模擬退火算法根據(jù)模擬退火算法的返回值確定種群進化的方向，利用量子旋轉(zhuǎn)門更新種群進行全局交叉，改變種群形態(tài)，得到Q（t+1）記錄最優(yōu)個體和對應(yīng)的適應(yīng)度值NY圖3-1基于模擬退火算法的量子遺傳算法流程圖引入模擬退火思想后的新量子遺傳算法，對個體的進化方向進行模擬退火的操作，然后將整個迭代過程中的最優(yōu)解保留作為下一次進化迭代的目標值。3.4改進的量子遺傳算法的優(yōu)點將改進好的量子遺傳算法跟傳統(tǒng)的量子遺傳算法進行性能的比較，可以發(fā)現(xiàn)它具有以下幾方面的優(yōu)點：加入量子交叉操作。在這個函數(shù)的優(yōu)化過程中，為量子遺傳算法添加了“全干擾的交叉”量子遺傳交叉方式。在使用這種遞歸的量子交叉后，算法中的染色體的量子位的信息可以得到充分地交流，使得解集種群更加的多樣化。通過此操作可以很好的克服算法的“早熟收斂”。該操作的原理是借用量子計算中的相干性，較好的克服了染色體進化過程中易陷入局部最優(yōu)的缺陷。加入模擬退火思想。在現(xiàn)有的量子遺傳算法中，添加了模擬退火算子，其新染色體狀態(tài)的產(chǎn)生依靠現(xiàn)有的溫度的大小來決定是否接受惡化解的能力大小，該操作使進化算法從局部最優(yōu)的局限中脫離出來，繼續(xù)進行遺傳進化，搜索于全局，然后逐步趨近于最優(yōu)的解。加入了“全干擾交叉”的量子交叉方式與模擬退火思想的之后量子遺傳算法能夠?qū)τ谝恍┒喾搴瘮?shù)的優(yōu)化問題，體現(xiàn)出很好的優(yōu)越性，就算量子遺傳算法早期演化時產(chǎn)生的個體優(yōu)化解的差異性比較大，該算法也能夠很好地收斂到全局的最優(yōu)解或近似全局最優(yōu)解。就算是使用輪盤賭方式選擇優(yōu)化函數(shù)的染色體解集，對優(yōu)化算法的影響也不會太大。

4算法性能測試及分析為了檢驗上面改進好的量子遺傳算法的可行性與有效性，我們將會改進好的算法對5個典型的函數(shù)進行算法優(yōu)化性能的驗證，通過與傳統(tǒng)的量子遺傳算法在運行時間、收斂效率、優(yōu)化性能等方面的比較。4.1典型測試函數(shù)4.1.1簡單平方和函數(shù)圖4-1簡單平方和函數(shù)此函數(shù)具有多個局部的最小值，但只有一個全局的最小值。4.1.2Rastrigrin函數(shù)圖4-2Rastrigrin多極值函數(shù)此函數(shù)具有多個局部的最小值，但只有一個全局的最小值。4.1.3DeJong函數(shù)F2圖4-3DeJong函數(shù)F2DeJong函數(shù)F2是一個變態(tài)函數(shù)，很難尋找全局最小值，它具有全局最小值。4.1.4Goldsten-Price函數(shù)圖4-4Goldstren-Price函數(shù)這個函數(shù)在其定義域內(nèi)只有一個極小值點。4.1.5Six-humpCamelBack函數(shù)圖4-5Six-humpCamelBack函數(shù)Six-humpCamelBack函數(shù)共有多個相似極小值點，很難準確地取得最小值點，其中(-0.0898，0.7126)和(0.0898，-0.7126)為全局最小點，最小值為。4.2算法參數(shù)設(shè)定普通量子遺傳算法的參數(shù)設(shè)定：將每個初始種群規(guī)模的大小都設(shè)置為40，最大的遺傳代數(shù)設(shè)為200，函數(shù)的每一個變量的二進制長度設(shè)為20。含量子交叉的量子遺傳算法的參數(shù)設(shè)定：將每個初始種群規(guī)模的大小都設(shè)置為40，最大的遺傳代數(shù)設(shè)為200，函數(shù)的每一個變量的二進制長度設(shè)為20。量子交叉采用的是量子全干擾交叉算法。含退火思想的量子遺傳算法參數(shù)設(shè)定：將每個初始種群規(guī)模的大小都設(shè)置為40，最大的遺傳代數(shù)設(shè)為200，函數(shù)的每一個變量的二進制長度設(shè)為20，初始的溫度設(shè)置為100度。退火系數(shù)設(shè)置為0.9.含量子交叉和退火思想的量子遺傳算法參數(shù)設(shè)定：將每個初始種群規(guī)模的大小都設(shè)置為40，最大的遺傳代數(shù)設(shè)為200，函數(shù)的每一個變量的二進制長度設(shè)為20，初始的溫度設(shè)置為100度。退火系數(shù)設(shè)置為0.9.并且采用量子全干擾交叉操作。4.3測試結(jié)果即分析對于每個測試的函數(shù)，普通量子遺傳算法、含量子交叉的量子遺傳算法、含退火思想的量子遺傳算法、含量子交叉和退火思想的量子遺傳算法他們各自獨立的運行20次，他們的最優(yōu)搜索值與搜索平均值的統(tǒng)計結(jié)果如下表4.1所示。表4.1仿真實驗數(shù)據(jù)統(tǒng)計表優(yōu)化函數(shù)優(yōu)化算法最優(yōu)搜索值平均搜索值迭代次數(shù)理論最優(yōu)值簡單平方和函數(shù)QGA1.00021.0012401CQGA1.00121.0017501SQGA1.00011.0005971SCQGA1.00001.00091251Rastrigrin函數(shù)QGA0.00520.0501710CQGA0.00190.0180780SQGA0.00660.0147920SCQGA0.00300.0147980DeJong函數(shù)F2QGA0.00360.2472120CQGA0.00670.068070SQGA0.00280.0088160SCQGA0.00040.0052180Goldsten-Price函數(shù)QGA3.09394.0303443CQGA3.05423.8750173SQGA3.50733.645343SCQGA3.0143.352563Six-humpCamelBack函數(shù)QGA-1.0315-1.0311119-1.031628CQGA-1.0316-1.031071-1.031628SQGA-1.0315-1.030086-1.031628SCQGA-1.0315-1.0314104-1.031628對于上面的5個優(yōu)化性能測試函數(shù)，它們都采用了二進制的編碼，染色體的長度設(shè)置為20，分別用普通量子遺傳、含量子交叉的量子遺傳、含退火思想的量子遺傳算法和含量子交叉與退火思想的量子遺傳的四種算法進行20次的函數(shù)優(yōu)化尋優(yōu)，種群的規(guī)模設(shè)置為40，最大的迭代的次數(shù)為200，采用全局量子交叉，模擬退火的初始溫度設(shè)置為100度，退火系數(shù)設(shè)置為0.9。1.對于第一個簡單平方和測試函數(shù)的算法性能比較圖：圖4-6簡單平方和函數(shù)量子遺傳進化過程由上面圖4-6可以得知，對于簡單的平方函數(shù)在種群的大小與迭代的次數(shù)一樣的情況下，普通的量子遺傳算法的尋優(yōu)迭代次數(shù)是最短的，但是它尋優(yōu)能力都不如其它的三種優(yōu)化算法的能力，由圖中得知，基于量子交叉與退火操作的量子遺傳算法是尋優(yōu)能力最強的取得了全局的最小值1，相比其他的優(yōu)化函數(shù)最優(yōu)值都只有取到1.0012與1.0001，由此可以說明含退火算法與量子交叉操作的量子遺傳算法對于簡單的函數(shù)有化具有更好的性能，但我們也從中看出，相比于其它的優(yōu)化操作，它進行的迭代時間是最長的。2.Rastrigrin測試函數(shù)的算法性能比較圖：圖4-7Rastrigrin函數(shù)量子遺傳進化過程由上面圖4-7可以得知，對于多峰值的優(yōu)化函數(shù)在種群的大小與迭代的次數(shù)一樣的情況下，加入量子交叉操作的量子遺傳算法的尋優(yōu)性能是最好的，其它的優(yōu)化算法在一般的情況下，都不如它的優(yōu)化能，雖然在一些算法中加入了退火操作以此來使染色體種群的具有更好的多樣性，但似乎沒有達到預(yù)期的目標，原因可能是，多個峰值間隔太近，導(dǎo)致算法一直在實行退火操作，在冷卻是算法并沒有很好的跳出局部最優(yōu)這一陷阱，導(dǎo)致了算法性能的降低。3.DeJong函數(shù)F2的測試函數(shù)的算法性能比較圖:圖4-8DeJong函數(shù)F2量子遺傳進化過程由上面圖4-8可以得知，對于一些病態(tài)的函數(shù)優(yōu)化能力，采用了量子交叉與退火操作的量子遺傳算法的性能是最優(yōu)的，可以將全局的最小值搜索到0.002，相比其它的優(yōu)化算法只能搜索到0.3,0.15與0.36。它的性能是遠遠的優(yōu)于其它的優(yōu)化算法。由此，可以得出含有退火思想與量子交叉操作的量子遺傳算法對于病態(tài)的函數(shù)尋優(yōu)具有更好的性能。4.Goldstren-Price測試函數(shù)的算法性能比較圖:圖4-9Goldstren-Price函數(shù)量子遺傳進化過程由上面圖4-9可以得知，對于一些連續(xù)的多元的函數(shù)的優(yōu)化能力，采用了量子交叉與退火操作的量子遺傳算法的性能是最優(yōu)的，可以將全局的最小值搜索到3.014，與其它的優(yōu)化算法相比較它搜索到的最優(yōu)值是5.2,3.5與4.7。它的性能是遠遠的優(yōu)于其它的優(yōu)化算法。由此，可以得出含有退火思想與量子交叉操作的量子遺傳算法對于一些連續(xù)的多元的函數(shù)尋優(yōu)具有更好的性能。5.Goldstren-Price測試函數(shù)的算法性能比較圖:圖4-10Six-humpCamelBack函數(shù)量子遺傳進化過程由上面圖4-10可以得知，對于一些含有多個極值點的函數(shù)的優(yōu)化能力，采用了量子交叉與退火操作的量子遺傳算法的性能是最優(yōu)的，可以將全局的最小值搜索到-1.0315，其它的優(yōu)化算法只能搜索到的最優(yōu)值是-1.0307與-1.0309?？梢詮臄?shù)據(jù)判斷得知，它的性能是遠遠的優(yōu)于其它的優(yōu)化算法。由此，可以得出含有退火思想與量子交叉操作的量子遺傳算法對于一些含有多個極值點的函數(shù)的尋優(yōu)具有更好的性能。從上面的仿真實驗可以了解到，含量子交叉與退火思想的量子遺傳算法在求最優(yōu)解的時，發(fā)現(xiàn)首次最優(yōu)解的能力是最強的，相比其它的算法它的性能有了很大的提高。含量子交叉與退火思想的量子遺傳算法能夠在早起發(fā)現(xiàn)最優(yōu)解，并且在早期與其他的量子算法相比較，它的種群更加地具有多樣性，它同過量子交叉操作與退火操作使其種群的種類更加的多樣，使其能更加完整、全面的表達種群的樣貌，通過此種群搜索所有的染色體，獲得最佳適應(yīng)度值也就更加地能代表該算法的最優(yōu)值的大小。因此，從最優(yōu)解的收斂概率上來看，含量子交叉與退火思想的量子遺傳是在這些算法中性能最好的。但是，含量子交叉與退火思想的量子遺傳算法在搜索最優(yōu)的上花費的時間也比其他的量子遺傳算法要多得多。這是由于我們在該算法中添加了適用于全局的量子全干擾交叉的量子交叉與退火操作。這些操作增加了算法的復(fù)雜度，影響了算法的搜索能力。對于全干擾的量子遞歸交叉操作，該操作讓種群中所有的染色體的基因位進行一次循環(huán)對調(diào)操作，以此來打亂原有染色體解集的樣貌，使其能更好的描述優(yōu)化函數(shù)全局解集的樣貌。退火操作不僅使該算法能在子代的產(chǎn)生過程中接受適應(yīng)度值高的個體，它還以一定的概率接受適應(yīng)度值較差的個體，因此增加了該算法的搜索范圍，雖然在優(yōu)化算法中引入這些操作會在一定的程度上增加算法尋優(yōu)的運行的時間，但它卻有效的避免了算法的“早熟收斂”這一問題。根據(jù)這些我們可以得出含量子交叉與退火思想的量子遺傳算法是一種尋優(yōu)能力較好的搜索算法。以此算法我們能很好的得到連續(xù)的多峰函數(shù)的最優(yōu)值。

5總結(jié)與展望量子遺傳算法是將量子計算中信息存儲的優(yōu)點與傳統(tǒng)遺傳算法具有的通用性相結(jié)合，從而提升了優(yōu)化算法的尋優(yōu)能力。本文通過在原有的量子遺傳中添加全干擾的量子交叉與退火操作，從而提升了原有量子遺傳算法的搜索尋優(yōu)能力，通過在算法中添加交叉與退火操作，使算法在多元連續(xù)的多峰函數(shù)中，具有更好的適應(yīng)性，能有效的避免陷入傳統(tǒng)算法易陷入的“早熟收斂”這一問題。5.1論文總結(jié)本文的研究內(nèi)容主要包括以下幾個方面：對于傳統(tǒng)的遺傳算法與量子遺傳算法進行簡單的學(xué)習(xí)，包括對于量子比特的特點與概率幅的疊加態(tài)的表現(xiàn)形式，量子旋轉(zhuǎn)門的性質(zhì)與功能，并且簡單的介紹了量子旋轉(zhuǎn)的策略選擇。通過對于量子遺傳算法的研究發(fā)現(xiàn)，基本的量子遺傳算法還具有較多的問題，有許多可以改進的方面。對最近幾年改進過的量子遺傳算法進行研究與總結(jié)，并且提出了一種新的優(yōu)化進化算法，通過仿真數(shù)據(jù)的仿真實驗證明，經(jīng)過改進的量子遺傳算法具有更好的優(yōu)化尋優(yōu)能力，能夠在多元的連續(xù)多峰函數(shù)中搜索到較好的最優(yōu)值。對于量子遺傳的改進研究主要時集中在現(xiàn)有的理論基礎(chǔ)之上，其思想就是充分的表達種群的樣貌，使種群能更好的代表函數(shù)的優(yōu)化解。因此，在該算法中添加了量子全干擾的交叉與退火操作，將退火操作引入量子遺傳算法，使其在子代中能以一定的概率接受父代中適應(yīng)度較差的個體，有效地抑制了子代種群容易陷入局部最優(yōu)的確點，并且以退火溫度T來控制算法的選擇壓力，有效地保證了算法在后期的全局收斂性。這些操作可以有效的使染色體之間的信息交互。使染色體更具有多樣性。這一性能在隨后的仿真實驗中充分得到了證明。是用5個經(jīng)典的優(yōu)化函數(shù)測試改進后的量子遺傳算法的性能，并且有效證明了改進的優(yōu)化算法的優(yōu)越性能。5.2展望文中的改進量子遺傳算法--基于全干擾與退火操作的量子遺傳算法，在多元連續(xù)的多峰函數(shù)中取得了一定的成果，彌補了傳統(tǒng)量子遺傳方面的一些缺點，但它依然存在著一些不完善的地方，需要在今后的學(xué)習(xí)與研究中繼續(xù)地努力改進。基于量子交叉與退火操作的量子遺傳算法在搜索的速度上有待改進，需要一種既能很好的搜索全局，又不會影響函數(shù)運行的時間的搜索策略。在量子遺傳算法中的演化操作過程，需要使用到量子旋轉(zhuǎn)門進行演化操作，在確定基因位時，需要進行大量的計算操作，非常消耗尋優(yōu)的運行時間，影響了優(yōu)化算法的尋優(yōu)性能，所以需要我們姨現(xiàn)有的量子旋轉(zhuǎn)門進行改進，以此來提高算法尋優(yōu)的速度。可以在后續(xù)的改進算法中，實行順序與逆序染色體分別作為一個初始化個體，這樣，對個體的量子位進行測量一次就能得到兩條染色體，大大加快了初始化的速度可以在以后的算法中加入精英庫與干擾庫，精英庫在進化的早起大大提高了種群的搜索速度，干擾庫可以在進化的一定情況下，對種群進行人為的干擾，使其避免算法的早熟收斂[18]。在以后的改進算法中，把量子旋轉(zhuǎn)門的旋轉(zhuǎn)角能根據(jù)不同的情況而改變，這樣對于適應(yīng)度值高的個體，就能更好的進入到下一代的計算中，而對于適應(yīng)度值低的個體就會盡快的淘汰。算法自適應(yīng)的旋轉(zhuǎn)角，既能保證群體解集的多樣性，也維護算法的收斂性。

參考文獻[1]HollandJH.Geneticalgorithmsandclassifiersystems:foundationsandtheirapplication[C]//ProceedingsoftheSecondInternationalConferenceonGeneticAlgorithms.Hillsdale,NJ:LawrenceErlbaumAssociates,