量子統(tǒng)計(jì)力學(xué)演化算法

1、量子統(tǒng)計(jì)力學(xué)演化算法    2012-04-19     論文導(dǎo)讀:將進(jìn)化理論和量子統(tǒng)計(jì)力學(xué)理論相結(jié)合,提出一種新的量子統(tǒng)計(jì)力學(xué)演化算法.將整個(gè)遺傳系統(tǒng)作為一個(gè)量子統(tǒng)計(jì)系統(tǒng),并借鑒量子信息論中量子比特的疊加性,采用量子編碼表征染色體,使系統(tǒng)中的量子能夠表示多種線性疊加狀態(tài).算法類(lèi)比量子統(tǒng)計(jì)力學(xué)中的相關(guān)概念,定義了.    將進(jìn)化理論和量子統(tǒng)計(jì)力學(xué)理論相結(jié)合,提出一種新的量子統(tǒng)計(jì)力學(xué)演化算法.將整個(gè)遺傳系統(tǒng)作為一個(gè)量子統(tǒng)計(jì)系統(tǒng),并借鑒量子信息論中量子比特的疊加性,采用量子編碼表

2、征染色體,使系統(tǒng)中的量子能夠表示多種線性疊加狀態(tài).算法類(lèi)比量子統(tǒng)計(jì)力學(xué)中的相關(guān)概念,定義了量子系統(tǒng)的能量和熵,并利用量子系統(tǒng)中能量和熵競(jìng)爭(zhēng)的模式系統(tǒng)地協(xié)調(diào)進(jìn)化理論中選擇壓力和種群多樣性間的沖突,使算法在提高選擇壓力和維持種群多樣性之間保持了適當(dāng)?shù)钠胶?可以快速的收斂到全局最優(yōu)解.實(shí)驗(yàn)結(jié)果表明,該算法有較高的執(zhí)行效率和求解能力.基金項(xiàng)目:國(guó)家科技攻關(guān)項(xiàng)目基金(批準(zhǔn)號(hào): 2004BA907A20)和吉林省科技發(fā)展計(jì)劃重大項(xiàng)目基金(批準(zhǔn)號(hào): 20060328).傳統(tǒng)的遺傳算法(GeneticAlgorithm, GA)存在著收斂速度慢和早熟兩個(gè)。GA中最重要的兩個(gè)因素是選擇壓力和種群多樣性,并且兩者

3、相互制約。為了使算法具有良好的性能,必須在提高選擇壓力和保持種群多樣性之間保持適當(dāng)?shù)钠胶?量子遺傳算法(Quantum GeneticAlgorithm, QGA)就是在GA中引入量子計(jì)算的概念,是一種基于量子計(jì)算原理的概率化優(yōu)化方法.量子遺傳算法采用幾率幅(量子態(tài))表示信息單元(量子比特),從而實(shí)現(xiàn)了信息的量子化,這種表示縮小了種族規(guī)模,增加了種群多樣性;量子雜交利用了量子的糾纏性使信息可以在整個(gè)種群中進(jìn)行交流,加大搜索范圍,增加了種群發(fā)現(xiàn)優(yōu)秀演化方向的個(gè)體。文獻(xiàn)將GA中的種群視為一個(gè)動(dòng)力學(xué)系統(tǒng),個(gè)體視為粒子,遺傳操作視為粒子的碰撞或移動(dòng),提出了動(dòng)力學(xué)演化算法(DynamicalEvolut

4、ionaryAlgorithm, DEA),該算法基于普通統(tǒng)計(jì)物理中的自由能極小化原理,通過(guò)引入動(dòng)量和活動(dòng)量的概念,提出一個(gè)新的選擇策略,用于保持種群的多樣性.本文結(jié)合QGA和DEA提出一種新的量子統(tǒng)計(jì)力學(xué)演化算法(QSEA),該算法將整個(gè)遺傳系統(tǒng)作為一個(gè)量子統(tǒng)計(jì)系統(tǒng),將遺傳算法中的個(gè)體視為量子系統(tǒng)中的量子,整個(gè)算法的收斂過(guò)程模擬了量子系統(tǒng)由非平衡向平衡狀態(tài)轉(zhuǎn)變的過(guò)程.算法根據(jù)量子信息理論,借鑒量子比特的疊加性,采用量子編碼。表征染色體,使一個(gè)量子能夠表示多種線性疊加狀態(tài),同時(shí)使用量子門(mén)實(shí)現(xiàn)變異操作.利用量子編碼的特性,定義了量子系統(tǒng)的熵與量子的能量,并借鑒動(dòng)力學(xué)中能量和熵競(jìng)爭(zhēng)的模式系統(tǒng)地協(xié)調(diào)

5、進(jìn)化理論中選擇壓力和種群多樣性之間的沖突。數(shù)值實(shí)驗(yàn)表明, QSEA有很好的穩(wěn)定性和計(jì)算效率.預(yù)備知識(shí)熵增法則和自由能極小化原理為了描述物理系統(tǒng)的熱力學(xué)狀態(tài),克勞休斯和玻爾茲曼從宏觀和微觀兩個(gè)角度以及二者之間的必然聯(lián)系中,定義了熱力學(xué)系統(tǒng)中物理熵的概念.克勞休斯將熱力學(xué)第二定律表示為孤立系統(tǒng)內(nèi)的不可逆過(guò)程總是指向熵增加的方向.克勞休斯熵作為系統(tǒng)的宏觀狀態(tài)函數(shù),它的變化可以直接反映出系統(tǒng)自發(fā)不可逆過(guò)程的方向.玻爾茲曼統(tǒng)計(jì)熵則定義為:S=kln,其中k為玻爾茲曼常數(shù),一般取為1.381×10-3J/K;是熱力學(xué)系統(tǒng)某一個(gè)宏觀狀態(tài)所包含的微觀狀態(tài)數(shù),稱(chēng)為熱力學(xué)幾率.處于非平衡狀態(tài)的孤立狀態(tài)具

6、有較小的熱力學(xué)幾率和熵,它自發(fā)地朝熵增加的方向發(fā)展,即有dS0.達(dá)到平衡狀態(tài)時(shí)系統(tǒng)最無(wú)序、最混亂,此時(shí)的熵最大.因此,熵的大小可以衡量系統(tǒng)混亂的程度.自由能定義為: F=E-TS,其中E表示內(nèi)能, T表示系統(tǒng)的溫度, S表示系統(tǒng)的熵.自由能極小化原理描述如下:對(duì)于一個(gè)只與外界有熱交換的封閉恒溫系統(tǒng),總是朝著自由能減小的方向發(fā)展.當(dāng)自由能達(dá)到極小值時(shí),系統(tǒng)就達(dá)到了平衡狀態(tài).系統(tǒng)狀態(tài)從非平衡態(tài)自發(fā)變化到平衡態(tài),是一個(gè)內(nèi)能減少和熵增加的競(jìng)爭(zhēng)過(guò)程,而溫度決定了它們之間的相對(duì)權(quán)重.從演化算法的觀點(diǎn)考慮,對(duì)于一個(gè)優(yōu)化問(wèn)題,目標(biāo)函數(shù)的最小化(即收斂)和得到解的多樣性(即避免陷入局部最優(yōu))均為一個(gè)有效全局優(yōu)化

7、算法的兩個(gè)核心指標(biāo).這種觀點(diǎn)和動(dòng)力學(xué)中的自由能極小化狀態(tài)變化非常相似,可以將能量的減小看作算法種群收斂到最小值,而熵增即為算法種群保持多樣性的過(guò)程.量子比特編碼在量子信息論中,信息的載體是一個(gè)一般的二態(tài)量子體系.這個(gè)二態(tài)量子體系稱(chēng)為量子比特即量子位.區(qū)別于經(jīng)典比特,量子比特可以是處于0,1這兩個(gè)本征態(tài)的任意疊加狀態(tài),而且在對(duì)量子比特的操作過(guò)程中,0,1二態(tài)的疊加振幅可以相互干涉,這就是量子的相干性;量子計(jì)算機(jī)對(duì)每個(gè)疊加分量(本征態(tài))的實(shí)現(xiàn)變換相當(dāng)于一種經(jīng)典計(jì)算,所有這些經(jīng)典計(jì)算同時(shí)完成,并按一定的概率振幅疊加,給出量子計(jì)算的計(jì)算結(jié)果,這種計(jì)算稱(chēng)為量子并行計(jì)算.一個(gè)量子比特的狀態(tài)可以取值0或1,

8、其狀態(tài)表示為:量子變異GA中采用交叉、變異等操作保持種群的多樣性, QGA采用量子門(mén)10作用于量子態(tài)概率幅的方式保持種群多樣性,因而,量子門(mén)的更新方法是QGA的關(guān)鍵.本文選擇量子旋轉(zhuǎn)門(mén)作為演化的執(zhí)行機(jī)構(gòu),使用量子旋轉(zhuǎn)門(mén)的旋轉(zhuǎn)角度同樣可以表征量子染色體的變異,進(jìn)而變異中加入最優(yōu)個(gè)體信息,加速算法收斂.用U()=cos-sinsincos表示旋轉(zhuǎn)門(mén), m表示量子染色體的長(zhǎng)度.表1列出了值的變化范圍,由表1可見(jiàn)的變化情況.表1中xi表示量子q衍生粒子x的第i個(gè)比特, bi表示當(dāng)前最優(yōu)染色體的第1位; f(x)表示適應(yīng)度函數(shù),表示旋轉(zhuǎn)角度,控制算法收斂速度.量子門(mén)變換方法描述如下:量子統(tǒng)計(jì)力學(xué)演化算法

9、量子系統(tǒng)由非平衡到平衡的過(guò)程和GA種群收斂過(guò)程之間存在相似性,例如GA中的種群可以視為量子系統(tǒng),種群中的個(gè)體可以視為量子系統(tǒng)中的量子.種群的平均適應(yīng)值和種群的多樣性可以擔(dān)當(dāng)量子系統(tǒng)中能量和熵的角色.表2列出了量子系統(tǒng)遺傳算法的諸多相似點(diǎn).表2GA和量子系統(tǒng)的相似性比較Table 2Sim ilarities between GA and quantum system量子系統(tǒng)遺傳算法由若干量子組成的統(tǒng)計(jì)系統(tǒng)若干個(gè)體組成的進(jìn)化種群系統(tǒng)中的能量種群的平均適應(yīng)值系統(tǒng)中的熵種群的多樣性能量和熵的競(jìng)爭(zhēng)選擇壓力和種群多樣性的競(jìng)爭(zhēng)自由能減少種群收斂非平衡狀態(tài)到平衡狀態(tài)算法求解基于二者的相似性,本文提出一種量子

10、統(tǒng)計(jì)力學(xué)演化算法,該算法利用量子系統(tǒng)從非平衡狀態(tài)到平衡狀態(tài)的變換過(guò)程模擬遺傳算法的收斂過(guò)程,并采用量子編碼機(jī)制,借鑒量子系統(tǒng)中能量和熵的競(jìng)爭(zhēng)關(guān)系協(xié)調(diào)種群進(jìn)化過(guò)程中選擇壓力和種群多樣性之間的沖突,定義了量子系統(tǒng)的統(tǒng)計(jì)能量和量子熵.算法在統(tǒng)計(jì)能量和量子熵相互競(jìng)爭(zhēng)的驅(qū)動(dòng)下,可以有效而快速地收斂到全局最優(yōu).量子熵的度量當(dāng)將量子系統(tǒng)的競(jìng)爭(zhēng)機(jī)制引入到GA中時(shí),如何度量種群的多樣性是一個(gè)關(guān)鍵問(wèn)題. DEA算法未對(duì)系統(tǒng)的熵給出定量計(jì)算,只近似的將粒子的活動(dòng)量看作自由能定義公式中的熵.此方法在統(tǒng)計(jì)物理上的解釋不合理.在新算法中,本文采用量子編碼,用1122mm表示一個(gè)量子染色體,2和2表示量子處于狀態(tài)0和狀態(tài)1

11、的概率.利用2,2的意義定義量子系統(tǒng)中的熵.表明了量子系統(tǒng)的混亂程度,隨著算法的進(jìn)行,2,2逐漸趨于0或1,此時(shí)H(qr, t)逐漸取到最大值,表明系統(tǒng)在算法收斂時(shí)達(dá)到最大量子熵值,而且量子熵隨算法的運(yùn)行而不斷增大,符合熱力學(xué)中的熵增法則.統(tǒng)計(jì)能量的度量由于量子的不確定性,因此無(wú)法精確衡量一個(gè)量子的能量,本文采用量子坍塌方法,使得一個(gè)量子生成k個(gè)普通粒子,然后對(duì)這k個(gè)普通粒子進(jìn)行統(tǒng)計(jì)觀察,得到原量子的能量.定義(統(tǒng)計(jì)能量)qr在第t時(shí)間的統(tǒng)計(jì)能量定義為E(qr, t) =tk=1e(qr,k) -e(qr,k-1) .量子選擇策略根據(jù)熵增法則和自由能極小化原理及上面的定義,可以定義如下一種新的適應(yīng)函數(shù).定義