文獻(xiàn)綜述--基于量子遺傳算法的函數(shù)尋優(yōu)算法設(shè)計(jì)

1、<p>　　畢業(yè)論文（設(shè)計(jì)）文獻(xiàn)綜述</p><p>　　題 目： 基于量子遺傳算法的函數(shù)尋優(yōu)算法設(shè)計(jì) </p><p>　　學(xué) 院： 數(shù)理與信息學(xué)院 </p><p>　　學(xué)生姓名： </p><p>　　專

2、 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　班 級(jí)： </p><p>　　指導(dǎo)教師： </p><p>　　起止日期： 2014年11月28日至2015年1月16日 </p&

3、gt;<p>　　2015年 1月 15 日</p><p><b>　　文獻(xiàn)綜述</b></p><p><b>　　一、前言</b></p><p>　　量子遺傳算法（Quantum Genetic Algorithm，QGA）[1]是量子計(jì)算（Quantum Computing，QC）[2]與遺傳算法(

4、Genetic Algorithm，GA )[3]相結(jié)合的產(chǎn)物。</p><p>　　量子計(jì)算中采用量子態(tài)[4]作為基本的信息單元，利用量子態(tài)的疊加、糾纏和干涉等特性，可以解決經(jīng)典計(jì)算中的NP問題。如1994年Shor提出第一個(gè)量子算法，求解大數(shù)質(zhì)因子分解的經(jīng)典計(jì)算難題，該算法可用于公開秘鑰系統(tǒng)RSA[5]；1996年Crover提出隨機(jī)數(shù)據(jù)庫(kù)搜索的量子算法，在量子計(jì)算機(jī)上可實(shí)現(xiàn)對(duì)未加整理的數(shù)據(jù)庫(kù)量級(jí)的加速搜索[

5、6]。</p><p>　　遺傳算法是處理復(fù)雜優(yōu)化問題的一種方法，其基本思想是模擬生物進(jìn)化的優(yōu)勝劣汰規(guī)則與染色體的交換機(jī)制，通過選擇、交叉、變異三種基本操作尋找最優(yōu)個(gè)體。</p><p><b>　　二、遺傳算法概述</b></p><p>　　遺傳算法通過模仿生物的選擇、交叉、變異操作，并遵循優(yōu)勝劣汰的準(zhǔn)則及個(gè)體染色體的互相交叉這些特點(diǎn)處理問

6、題的一種方法。遺傳算法通過目標(biāo)函數(shù)進(jìn)行全局自適應(yīng)的概率搜索操作[7]，可以解決傳統(tǒng)算法不能解決的難題，它與優(yōu)化規(guī)則、問題的特性沒有任何關(guān)系。由于它有著較好的適用性和魯棒特性[8]，因此它具有誘人的研究和應(yīng)用前景。然而，若遺傳算法中的選擇、交叉及變異的操作方式選取不當(dāng)，那么算法將會(huì)在迭代次數(shù)、收斂速度方面受到影響，且容易產(chǎn)生局部極值的現(xiàn)象。</p><p>　　三、量子遺傳算法概述</p><p

7、>　　量子遺傳算法就是基于量子計(jì)算原理[9,10]的一種遺傳算法，將量子的態(tài)矢量表達(dá)引入了遺傳編碼[11]，利用量子邏輯門[12]實(shí)現(xiàn)染色體的演化，實(shí)現(xiàn)了比常規(guī)遺傳算法更好的效果。</p><p>　　量子遺傳算法建立在量子的態(tài)矢量表示的基礎(chǔ)之上，將量子比特的概率幅[13]表示應(yīng)用于染色體的編碼，使得一條染色體可以表達(dá)多個(gè)態(tài)的疊加，并利用量子邏輯門實(shí)現(xiàn)染色體的更新操作，具有種群規(guī)模小而不影響算法性能、同時(shí)兼

8、有“勘探”和“開采”的能力、收斂速度快和全局尋優(yōu)能力強(qiáng)的特點(diǎn)[13]。此算法已在多種優(yōu)化問題中有所應(yīng)用[14]</p><p>　　四、量子比特編碼相關(guān)概述</p><p>　　在量子遺傳算法中使用的編碼方式是基于量子比特的編碼。最小信息單兒元一個(gè)量子位一一量子比特。一個(gè)量子比特的狀態(tài)可以取0或1，其狀態(tài)可以表示為|Ψ>=α|0>+β|1>,式中：α，β為代表相應(yīng)狀態(tài)出現(xiàn)

9、概率的兩個(gè)復(fù)數(shù)（|α|2+|β|2=1）；|α|2，|β|2分別為量子比特處于狀態(tài)0和狀態(tài)1的概率。所以量子位可以同時(shí)包含|0>和|1>兩種狀態(tài)的信息，一般地，用n個(gè)量子位就可以同時(shí)表示2n個(gè)狀態(tài)[15]</p><p>　　五、量子門更新相關(guān)概述</p><p>　　在量子計(jì)算中，通過對(duì)量子位狀態(tài)進(jìn)行一系列的酉變換來實(shí)現(xiàn)某些邏輯變換功能。因此，在一定時(shí)間間隔內(nèi)實(shí)現(xiàn)邏輯變換的

10、量子裝置，稱其為量子門。量子們是在物理上實(shí)現(xiàn)量子計(jì)算的基礎(chǔ)。量子門的更新操作是優(yōu)化過程中最重要的單元，傳統(tǒng)量子遺傳算法基本包含量子旋轉(zhuǎn)門更新。其旋轉(zhuǎn)的大小、方向根據(jù)事先設(shè)計(jì)的調(diào)整策略而確定[16]。</p><p><b>　　六、量子交叉概述</b></p><p>　　量子遺傳算法中最能體現(xiàn)個(gè)體結(jié)構(gòu)信息的是其進(jìn)化目標(biāo)，即個(gè)體當(dāng)前最優(yōu)確定解以及對(duì)應(yīng)的適應(yīng)度值。因此

11、，考慮互換個(gè)體進(jìn)化目標(biāo)以實(shí)現(xiàn)個(gè)體間信息的交換，從而實(shí)現(xiàn)量子交叉的目的。其基本操作就是在個(gè)體之間暫時(shí)交換最優(yōu)確定解和最優(yōu)適應(yīng)度值，個(gè)體接受交叉操作后，它的進(jìn)化方向?qū)⑹艿狡渌麄€(gè)體的影響，從而獲取新的進(jìn)化信息。</p><p><b>　　七、退火算法概述</b></p><p>　　模擬退火（simulated annealing ,SA）算法的思想最早是由Metrop

12、olis等提出的。其出發(fā)是基于物理中固體物質(zhì)的退火過程與一般的組合優(yōu)化問題之間的相似性。模擬退火法是一種通用的優(yōu)化算法，其物理退火過程由以下三部分組成：</p><p>　?。?）加溫過程。其目的是增強(qiáng)粒子的熱運(yùn)動(dòng)，使其偏離平衡位置。當(dāng)溫度足夠高的時(shí)候，固體將融為液體，從而消除系統(tǒng)原先存在的非均勻狀態(tài)。</p><p>　?。?）等溫過程。對(duì)于與周圍環(huán)境交換熱量而溫度不變的封閉系統(tǒng)，系統(tǒng)狀

13、態(tài)的自發(fā)變化總是朝自由減少的方向進(jìn)行的，當(dāng)自由能減少到最小時(shí)，系統(tǒng)達(dá)到平衡狀態(tài)。</p><p>　?。?）冷卻過程。使粒子熱運(yùn)動(dòng)減弱，系統(tǒng)能量下降，得到晶體結(jié)構(gòu)。</p><p>　　其中，加溫過程對(duì)應(yīng)算法的設(shè)定初溫，等溫過程對(duì)應(yīng)算法的Metropolis抽樣過程，冷卻過程對(duì)應(yīng)控制參數(shù)的下降，這里能量的變化就是目標(biāo)函數(shù)，要得到的最優(yōu)解就是能量最低態(tài)。Metropolis準(zhǔn)則是SA算法收斂

14、于全局最優(yōu)解關(guān)鍵所在，Metropolis準(zhǔn)則以一定的概率接受惡化解，這樣就使得算法跳離局部最優(yōu)的陷阱。</p><p>　　八、函數(shù)優(yōu)化相關(guān)概述</p><p>　　函數(shù)優(yōu)化問題是量子遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對(duì)量子遺傳算法進(jìn)行性能評(píng)價(jià)的常用算法.對(duì)于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，用其他方法較難求解，而用量子遺傳算法卻可以方便地得到較好的結(jié)果。</p>&l

15、t;p>　　函數(shù)優(yōu)化[17]問題是指對(duì)象在一定區(qū)間的連續(xù)變量，通常可描述為：設(shè)S為Rn上的有界子集，：S->R為n維實(shí)值函數(shù)。函數(shù)f在域上全局最小化，就是尋找點(diǎn)使得在S域上全局最小，即。</p><p>　　函數(shù)優(yōu)化問題是一個(gè)復(fù)雜的優(yōu)化問題，特別是不可微或者多峰的函數(shù)，往往不能有效地求解。而遺傳算法作為一種高度并行、隨機(jī)、自適應(yīng)的全局優(yōu)化概率搜索算法，它將每個(gè)可能的問題表示為“染色體”，從而得到一個(gè)由

16、染色體組成的“群體，然后按遺傳學(xué)規(guī)律進(jìn)行選擇、交叉、變異操作，直到滿足終止條件為止。</p><p><b>　　九、總結(jié)</b></p><p>　　量子遺傳算法在許多應(yīng)用領(lǐng)域發(fā)揮著重要作用，量子遺傳算法與遺傳算法一樣，都是一種基于生物和進(jìn)化機(jī)制的適合復(fù)雜系統(tǒng)優(yōu)化計(jì)算的自適應(yīng)概率優(yōu)化[18]技術(shù).相比于經(jīng)典遺傳算法具有種群規(guī)模小、收斂速度夸、全局搜索能力強(qiáng)的優(yōu)點(diǎn)。

17、目前的量子遺傳算法主要存在如下問題：首先，通過測(cè)量量子位的狀態(tài)獲得二進(jìn)制解，這是個(gè)概率操作過程，具有很大的隨機(jī)性和盲目性，因此在種群進(jìn)化的同時(shí)，部分個(gè)體將不可避免地產(chǎn)生退化；其次，二進(jìn)制編碼對(duì)于連續(xù)優(yōu)化，由于頻繁解碼操作加大了計(jì)算量，嚴(yán)重降低了優(yōu)化效率；第三，對(duì)于量子旋轉(zhuǎn)門的轉(zhuǎn)角方向、大小，一視同仁，沒有考慮染色體之間的差異。因此，應(yīng)加注重量子遺傳的種群大小的選擇，進(jìn)化策略[19]的設(shè)計(jì)與實(shí)施。如何讓量子遺傳算法更好的發(fā)揮性能，未來還需

18、要做進(jìn)一步研究</p><p><b>　　參考文獻(xiàn) </b></p><p>　　[1] Han K-H. Genetic Quantum Algorithm and its Application to Combinatorial Optimization Problem. In: IEEE Proc. Of the 2000 Congress on Evolut

19、ionary Computation. San Diego. USA. IEEE Press. July 2000.1354~1360</p><p>　　[2] Melanie Mitchell. An introduction to genetic algorithms. Cambridge, MA: The MIT Press, 1996</p><p>　　[3] Holland

20、J H. Genetic algorithms and classifier systems: foundations and their application[C]// Proceedings of the Second International Conference on Genetic Algorithms. Hillsdale, NJ: Lawrence Erlbaum Associates, 1987: 82-89<

21、/p><p>　　[4] Bennett C H, DiVincenzo D Y. Quantum Information and Computation. Nature, 2000. 404.247一255</p><p>　　[5] Shor P W. Algorithms for Quantum Computation: Discrete Logarithms and Factori

22、ng. In: Goldwasser S, ed. Proc. of the 35th Annual Symposium on the Foundation of Computer Sciences, Los Alamitos: IEEE Computer Society Press.1994.20一22</p><p>　　[6] Grover L K. A Fast Quantum Mechanical Al

23、gorithm for Database Search.In:Proc.28th Annual ACM Symposium on the Theory of Computing .Philadelphia, Pennsylvania, ACM Press. 1996，212一22I</p><p>　　[7] Zalka C. Grover's quantum searching algorithm is

24、 optimal [J].Physical Reuiew A, 1999, 60:2746-2751</p><p>　　[8] Jen E. Stable or Robust? What’s the difference?[J].Complexity,2003,8(3):12-18</p><p>　　[9] Tony H.Quantum computing:An introduct

25、ion[J].Computing&Control Engineering Journal,1996,10(3):105-112.</p><p>　　[10] Narayanan A. An introductory tutorial to quantum computing[A].Proc of IEE Colloquium on Quantum Computing: Theory, Applicati

26、ons and Implications[C].London: IEE Press,1997.1/1-1/3.</p><p>　　[11] Michalewicz Z, Janikow C, and Kjrawczyk, J.A modified genetic algorithm for optimal control problems. Computers and Mathematical Applian

27、cations, 1992, 23(12): 83-94</p><p>　　[12] Deutsch D. Quantum computational networks. Proc Roy Soc London A,1989,425:73-90</p><p>　　[13] Han Kuk-Hyun and Kim Jong-Hwan. Quantum-inspired Evoluti

28、onary Algorithm for a Class of Combinatorial Optimization.IEEE Transaction son Evolutionary Computation，IEEE Press, 2002, 6 (6):580-593</p><p>　　[14] Han Kuk-Hvun and Kim Jong-Hwan. Quantum一Inspired Evolutio

29、nary Algorithms With a New Termination Criterion, Gate, and Two-Phase Scheme. Transactions on Evolutionary Computation, 2004, 8 (2):156-169</p><p>　　[15] Nielsen M A, Chuang I L量子計(jì)算與量子信息(一)量子計(jì)算部分[M ].趙千川，譯.

30、北京:清華人學(xué)出版社，2004:13-17.</p><p>　　[16] 楊俊安，莊鎮(zhèn)泉，史亮.多宇宙并行量子遺傳算法[j].電子學(xué)報(bào)，2004, 32(6):923-928</p><p>　　[17] 李士勇.智能優(yōu)化算法原理與應(yīng)用.哈爾濱工業(yè)大學(xué)出版社，2012.12</p><p>　　[18] J.N. Siddall. Probabilistic En