胡小祥, 劉漫丹

(華東理工大學(xué)化工過(guò)程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,上海 200237)

?

一種基于濃度調(diào)節(jié)的改進(jìn)型量子遺傳算法

胡小祥, 劉漫丹

(華東理工大學(xué)化工過(guò)程先進(jìn)控制和優(yōu)化技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室,上海 200237)

針對(duì)量子遺傳算法(QGA)優(yōu)化多峰函數(shù)時(shí)存在收斂速度慢、容易陷入局部最優(yōu)的缺陷,提出了改進(jìn)型量子遺傳算法(IQGA)。引入個(gè)體濃度的概念,在量子門(mén)更新之前對(duì)種群進(jìn)行篩選并剔除高濃度個(gè)體和劣個(gè)體,并用新的個(gè)體代替它們,增強(qiáng)了量子遺傳算法全局搜索能力。通過(guò)典型復(fù)雜連續(xù)函數(shù)的對(duì)比測(cè)試,驗(yàn)證了該改進(jìn)型量子遺傳算法的可行性和有效性。

量子遺傳算法; 濃度; 改進(jìn)型量子遺傳算法; 對(duì)比測(cè)試

量子遺傳算法(QGA)是20世紀(jì)90年代后期新興的一種進(jìn)化算法,在過(guò)去的幾年里一直是人們研究的熱點(diǎn)問(wèn)題。它是在遺傳算法(GA)的基礎(chǔ)上,引入量子計(jì)算[1]的概念,將染色體的編碼采用量子比特的概率幅來(lái)表示,這樣可以使一條染色體不再表示一個(gè)單一態(tài),而是可以表示多個(gè)態(tài)的疊加。量子遺傳算法利用量子門(mén)作用來(lái)更新染色體,從而實(shí)現(xiàn)目標(biāo)函數(shù)的優(yōu)化求解[2]。為了提高量子遺傳算法的性能,眾多學(xué)者提出了很多對(duì)基本算法的優(yōu)化改進(jìn)方法。周傳華等[3]提出在初始化量子種群時(shí),引入小生境協(xié)同進(jìn)化策略,并通過(guò)移民操作把各種群中最優(yōu)個(gè)體組合在一起,形成一個(gè)新的最優(yōu)種群,并用這個(gè)新的最優(yōu)種群來(lái)指導(dǎo)量子門(mén)的全局最優(yōu)搜索方向;高穎慧等[4]提出采用角度編碼染色體的方法,用一個(gè)實(shí)數(shù)來(lái)表示量子染色體的基因位,大大減少了存儲(chǔ)量;沙林秀等[5]在目標(biāo)適應(yīng)度函數(shù)的基礎(chǔ)上,進(jìn)一步建立了反映目標(biāo)適應(yīng)度函數(shù)變化率的數(shù)學(xué)模型,并用調(diào)整當(dāng)前搜索點(diǎn)處適應(yīng)度相對(duì)變化率步長(zhǎng)系數(shù)的策略,從而達(dá)到優(yōu)化搜索過(guò)程的目的;劉衛(wèi)寧等[6]提出用實(shí)數(shù)編碼代替量子位的二進(jìn)制編碼,并用旋轉(zhuǎn)策略和變異算子等方法保證算法的收斂性。

針對(duì)QGA對(duì)多峰函數(shù)優(yōu)化問(wèn)題仍存在著收斂速度慢、容易陷入局部最優(yōu)的缺陷[7],本文提出了改進(jìn)型量子遺傳算法(IQGA)。在量子門(mén)更新之前,對(duì)種群進(jìn)行篩選并剔除高濃度個(gè)體和劣個(gè)體,并用新的個(gè)體來(lái)替換被剔除的個(gè)體。通過(guò)典型復(fù)雜連續(xù)函數(shù)的對(duì)比測(cè)試,驗(yàn)證了該改進(jìn)型量子遺傳算法的可行性和有效性。

1 QGA簡(jiǎn)介

QGA主要是用量子比特的概率幅表示染色體的編碼,量子比特編碼包含n維變量的個(gè)體如下:

(1)

QGA對(duì)種群的更新主要是利用量子門(mén)調(diào)整概率幅對(duì)的演化方向[9],多采用量子旋轉(zhuǎn)門(mén)。量子旋轉(zhuǎn)門(mén)U(t)的調(diào)整操作如下:

(2)

其中:(αij,βij)T和(αij′,βij′)T分別代表染色體第ij(i=1,2,…,n; j=1,2,…,k)位量子比特在旋轉(zhuǎn)門(mén)更新前后的概率幅;θij為第ij位的旋轉(zhuǎn)角。

2 IQGA設(shè)計(jì)思路

2.1 剔除高濃度個(gè)體

濃度概念來(lái)自人工免疫算法[10]。QGA在整個(gè)算法流程中,缺少對(duì)高濃度個(gè)體的抑制步驟,若尋優(yōu)陷入局部最優(yōu),就很難跳出這個(gè)局部最優(yōu),不利于搜索全局最優(yōu)。為增強(qiáng)量子遺傳算法全局搜索能力,本文對(duì)QGA進(jìn)行了改進(jìn), 首先引入幾個(gè)概念:

(3)

其中:kv,s為個(gè)體v和個(gè)體s中對(duì)應(yīng)的變量差值小于一個(gè)極小數(shù)ε的個(gè)數(shù);n為個(gè)體的維度。

(2) 個(gè)體濃度。個(gè)體的濃度Cv即種群中與個(gè)體v相似的個(gè)體占種群的比例。

(4)

(5)

其中:N為種群中的個(gè)體總數(shù);T為預(yù)先設(shè)定的一個(gè)相似度閾值;Zv,l為判斷相似的標(biāo)志位。

2.2 剔除劣個(gè)體

3 IQGA流程

IQGA流程如下:

(2) 對(duì)初始化種群Q(t0)中的每個(gè)個(gè)體實(shí)施一次測(cè)量轉(zhuǎn)換,得到對(duì)應(yīng)的測(cè)量值P(t0);

(3) 計(jì)算每個(gè)測(cè)量值對(duì)應(yīng)的適應(yīng)度值;

(4) 記錄最優(yōu)個(gè)體及其適應(yīng)度值,并將這個(gè)最優(yōu)個(gè)體作為下一代進(jìn)化目標(biāo);

(5) 判斷迭代演化過(guò)程是否可以結(jié)束,若滿足終止條件則輸出結(jié)果并退出,否則繼續(xù)計(jì)算;

(7) 計(jì)算每個(gè)測(cè)量值對(duì)應(yīng)的適應(yīng)度值;

(8) 記錄最優(yōu)個(gè)體及其適應(yīng)度值,并將這個(gè)最優(yōu)個(gè)體作為下一代進(jìn)化目標(biāo);

(9) 篩選出精英和劣個(gè)體及高濃度個(gè)體;

(10) 判斷高濃度個(gè)體是否為精英個(gè)體,對(duì)于高濃度且為精英的個(gè)體進(jìn)行保留,對(duì)于高濃度且為非精英的個(gè)體進(jìn)行剔除,并引入相同數(shù)目的新個(gè)體;

(11) 剔除劣個(gè)體,并引入相同數(shù)目的新個(gè)體;

(12) 利用量子旋轉(zhuǎn)門(mén)U(t)對(duì)種群個(gè)體進(jìn)行更新,得到子代種群Q(t+1);

(13) 將迭代次數(shù)t+1,返回步驟(5)。

4 算法分析及參數(shù)選擇

4.1 算法分析

以Ackley[11]函數(shù)為例,分別用QGA和IQGA測(cè)試Ackley函數(shù),觀察最優(yōu)個(gè)體的濃度變化。算法參數(shù)設(shè)計(jì)如下:QGA的種群規(guī)模N=100,每個(gè)量子基因的量子比特位數(shù)k=20,迭代次數(shù)為500。IQGA的種群規(guī)模N=100,每個(gè)量子基因的量子比特位數(shù)k=20,ε=0.1,相似度閾值T=1,濃度閾值w=0.1,精英比例h=0.05,劣個(gè)體比例s=0.05,迭代次數(shù)為500。取種群的適應(yīng)度為目標(biāo)函數(shù)值(適應(yīng)度值越小越好),兩種算法各運(yùn)行50次,分別取兩種算法某次(優(yōu)化結(jié)果能代表運(yùn)行50次優(yōu)化結(jié)果平均值)優(yōu)化過(guò)程作比較。圖1和圖2分別示出了兩種算法的優(yōu)化過(guò)程。

圖1 QGA的迭代過(guò)程Fig.1 Iteration process of QGA

對(duì)比圖1和圖2可以看出,IQGA的優(yōu)化結(jié)果明顯優(yōu)于QGA。對(duì)比兩種算法中最優(yōu)個(gè)體的濃度變化發(fā)現(xiàn),QGA最優(yōu)個(gè)體的濃度只是在迭代的前期波動(dòng)比較大,隨著迭代的進(jìn)行,算法陷入局部最優(yōu)后,最優(yōu)個(gè)體的濃度不斷上升,算法很難跳出這個(gè)局部最優(yōu)。IQGA的最優(yōu)個(gè)體濃度在整個(gè)迭代演化中,在濃度閾值范圍內(nèi)變化比較劇烈,這樣更有利于算法跳出局部最優(yōu),搜尋全局最優(yōu)。

圖2 IQGA的迭代過(guò)程Fig.2 Iteration process of IQGA

選取IQGA在迭代演化過(guò)程中對(duì)某一代的種群在進(jìn)入下一代迭代前的種群個(gè)體適應(yīng)度分布情況進(jìn)行分析。圖3示出了迭代到某一代的種群個(gè)體的適應(yīng)度分布,其中高濃度個(gè)體分別為[-0.252 5 0.199 7]、[-0.254 5 0.198 3]、[-0.255 2 0.201 8]、[-0.251 0 0.202 7]、[-0.253 5 0.204 4]、[-0.253 3 0.202 5]、[-0.248 8 0.198 8]、[-0.255 2 0.200 2]、[-0.255 4 0.209 0]、[-0.253 3 0.199 5]、[-0.253 3 0.206 1]、[-0.253 3 0.199 1]、[-0.252 6 0.209 3]。對(duì)于這些個(gè)體,先判斷是否為精英個(gè)體,對(duì)于高濃度且為非精英的個(gè)體進(jìn)行剔除,對(duì)于高濃度且為精英的個(gè)體進(jìn)行保留。這樣的操作增加了種群的多樣性,有利于種群尋優(yōu)。

圖3 某一代的種群適應(yīng)度分布Fig.3 Population fitness of one generation

算法的復(fù)雜度是改進(jìn)算法需要考慮的一個(gè)重要因素。算法的時(shí)間復(fù)雜度可以從平均計(jì)算時(shí)間分析。仍以上述優(yōu)化過(guò)程為例,在相同的參數(shù)選擇前提下,QGA的平均計(jì)算時(shí)間為19.26 s,IQGA的平均計(jì)算時(shí)間為26.58 s,IQGA在一定程度上增加了算法的時(shí)間復(fù)雜度。這是因?yàn)镮QGA在QGA中加入了濃度計(jì)算以及精英個(gè)體、劣個(gè)體判斷等步驟。由于IQGA仍然采用量子比特編碼染色體,對(duì)算法的空間復(fù)雜度并無(wú)太大的影響。

4.2 參數(shù)選擇

IQGA中參數(shù)主要包含相似度閾值T、濃度閾值w、ε、精英比例h、劣個(gè)體比例s。對(duì)于相似度閾值T,由于不能忽略某一個(gè)分量不同而引起整個(gè)個(gè)體的適應(yīng)度不同,所以T一般取1。濃度閾值w、ε、精英比例h、劣個(gè)體比例s的參數(shù)選擇需要通過(guò)實(shí)驗(yàn)確定。選取不同的參數(shù)值對(duì)Ackley函數(shù)進(jìn)行優(yōu)化,種群規(guī)模N為100,每個(gè)量子基因的量子比特位數(shù)k為20,迭代次數(shù)為500,分別運(yùn)行100次,取100次的最終優(yōu)化結(jié)果的平均值為平均優(yōu)化值。

ε的選取主要考慮個(gè)體分量的變化幅度,分別選取ε為0.05、0.06、0.07、0.08、0.09、0.10、0.11、0.12、0.13、0.14、0.15對(duì)函數(shù)進(jìn)行優(yōu)化,w=0.1,h=0.05，s=0.05,運(yùn)行結(jié)果見(jiàn)表1。從計(jì)算結(jié)果可知,ε=0.09時(shí)效果較好。

表1 ε取不同值的計(jì)算結(jié)果Table 1 Calculation results of different ε

分別選取w為0.05、0.06、0.07、0.08、0.09、0.10、0.11、0.12、0.13、0.14、0.15、0.16、0.17、0.18、0.19、0.20對(duì)函數(shù)進(jìn)行優(yōu)化,ε=0.09,h=0.05，s=0.05,運(yùn)行結(jié)果見(jiàn)表2。從計(jì)算結(jié)果可知,w為0.10時(shí)效果較好。

分別選取h為0.05、0.10、0.15、0.20、0.25對(duì)函數(shù)進(jìn)行優(yōu)化,ε=0.09,w=0.10,s=0.05,運(yùn)行結(jié)果見(jiàn)表3。從計(jì)算結(jié)果可知,h為0.05時(shí)效果較好。

表2 w取不同值的計(jì)算結(jié)果Table 2 Calculation results of different w

表3 h取不同值的計(jì)算結(jié)果Table 3 Calculation results of different h

分別選取s為0.05、0.10、0.15、0.20、0.25對(duì)函數(shù)進(jìn)行優(yōu)化,ε=0.09,w=0.10,h=0.05,運(yùn)行結(jié)果見(jiàn)表4。從計(jì)算結(jié)果可知,s為0.05時(shí)效果較好。

表4 s取不同值的計(jì)算結(jié)果Table 4 Calculation results of different s

綜上所述,IQGA的參數(shù)選擇為T(mén)=1、w=0.1、ε=0.09、h=0.05、s=0.05。這里的參數(shù)討論雖然只針對(duì)Ackley函數(shù),參數(shù)分析存在一定的不完備性,但從以上的參數(shù)分析可以得出這是一組可行的、合理的參數(shù)。

5 算法測(cè)試

為了評(píng)價(jià)IQGA的有效性和可行性,選擇5個(gè)典型的復(fù)雜連續(xù)測(cè)試函數(shù)[11],其中f1為Sphere函數(shù)、f2為Ackley函數(shù)、f3為Rastrigin函數(shù)、f4為Griewank函數(shù)、f5為Six-Hump Camel-Back函數(shù),分別用QGA、IQGA求解它們的最小值,以此測(cè)試算法求解復(fù)雜連續(xù)函數(shù)優(yōu)化問(wèn)題的性能。

算法參數(shù)為4.2節(jié)實(shí)驗(yàn)所得參數(shù),其中QGA種群規(guī)模為100,每個(gè)量子基因的量子比特位數(shù)k為20,迭代次數(shù)為2 000。IQGA的種群規(guī)模為100,每個(gè)量子基因的量子比特位數(shù)k為20,ε=0.09,T=1,w=0.1,h=0.05,s=0.05,迭代次數(shù)為2 000。

對(duì)上述5個(gè)典型復(fù)雜連續(xù)函數(shù)分別用IQGA、QGA計(jì)算100次,計(jì)算結(jié)果見(jiàn)表5。其中平均優(yōu)化值為兩種算法分別計(jì)算100次的最終優(yōu)化結(jié)果的平均值;標(biāo)準(zhǔn)差為兩種算法分別計(jì)算100次的最終優(yōu)化結(jié)果的標(biāo)準(zhǔn)差;成功率為計(jì)算100次中,成功(優(yōu)化結(jié)果與理論最優(yōu)值差值小于0.0001)次數(shù)占總優(yōu)化次數(shù)(100次)的比例;平均成功迭代次數(shù)為成功優(yōu)化需要迭代次數(shù)的平均值;期望迭代次數(shù)=平均成功迭代次數(shù)/成功率。

算法的性能從尋優(yōu)能力和尋優(yōu)速度兩方面來(lái)考慮,其中算法的尋優(yōu)能力用平均優(yōu)化值和標(biāo)準(zhǔn)差來(lái)衡量,尋優(yōu)速度用平均成功迭代次數(shù)衡量。成功率和尋優(yōu)速度是衡量?jī)?yōu)化算法的重要指標(biāo),然而這兩者在一定程度上相互制約,尤其是對(duì)于多峰問(wèn)題，所以本文采用期望迭代次數(shù)。期望迭代次數(shù)越小說(shuō)明對(duì)應(yīng)的算法具有比較平衡的性能,表示該算法具有較高的成功率和較小的平均成功迭代次數(shù)。比較這兩種算法運(yùn)行結(jié)果可以發(fā)現(xiàn),對(duì)于f1,由于該函數(shù)為非線性對(duì)稱單峰函數(shù),在定義域內(nèi)只有一個(gè)極小值,所以兩種算法都有較高的成功率;但從尋優(yōu)能力上看,IQGA比QGA強(qiáng),期望的迭代次數(shù)也比較少。對(duì)于f2、f3、f4、f5,它們是復(fù)雜的多峰函數(shù),函數(shù)有大量的局部最優(yōu)點(diǎn),QGA容易陷入局部最優(yōu),算法的成功率都只有75%左右;IQGA的成功率是95%左右,尋優(yōu)能力比QGA強(qiáng),期望迭代次數(shù)比QGA少,體現(xiàn)了改進(jìn)型量子遺傳算法的優(yōu)勢(shì)。對(duì)于有大量局部最優(yōu)點(diǎn)的多峰函數(shù),IQGA的性能遠(yuǎn)遠(yuǎn)強(qiáng)于QGA。

表5 測(cè)試函數(shù)計(jì)算結(jié)果Table 5 Calculation results of test functions

為了進(jìn)一步驗(yàn)證IQGA的性能,將IQGA與文獻(xiàn)[12-14]提出的算法進(jìn)行比較。文獻(xiàn)[12]提出了一種基于場(chǎng)的自適應(yīng)細(xì)菌覓食優(yōu)化算法(ABFOF);文獻(xiàn)[13]提出了一種改進(jìn)的粒子群優(yōu)化算法(HPSO);文獻(xiàn)[14]提出了一種改進(jìn)的差分進(jìn)化算法(DE)。ABFOF、HPSO、DE的參數(shù)選擇詳見(jiàn)文獻(xiàn)[12-14],IQGA的參數(shù)選擇不變,IQGA中調(diào)用測(cè)試函數(shù)次數(shù)(FES)小于ABFOF、HPSO、DE。測(cè)試結(jié)果見(jiàn)表6。從測(cè)試結(jié)果可知,IQGA的算法精度和尋優(yōu)能力優(yōu)于ABFOF、HPSO、DE。

表6 測(cè)試函數(shù)計(jì)算結(jié)果Table 6 Calculation results of test functions

6 結(jié) 論

針對(duì)基本的量子遺傳算法優(yōu)化多峰函數(shù)時(shí)存在收斂速度慢、容易陷入局部最優(yōu)的缺陷,提出了改進(jìn)型量子遺傳算法(IQGA),增強(qiáng)了量子遺傳算法全局搜索的能力。將其和QGA對(duì)比,求解復(fù)雜連續(xù)函數(shù)的優(yōu)化問(wèn)題,計(jì)算結(jié)果顯示了IQGA的良好性能。由于IQGA是一種比較新的優(yōu)化算法,許多方面有待改進(jìn),需要今后進(jìn)一步學(xué)習(xí)和研究。

[1] TONY H.Quantum computing:An introduction[J].Computing & Control Engineering,1996,10(3):105-112.

[2] YANG Shuyuan,LIU fang,JIAO Licheng.A novel genetic algorithm based on the quantum chromosome[J].Journal of Xidian University,2004,31(1):76-81.

[3] 周傳華,錢鋒.改進(jìn)量子遺傳算法及其應(yīng)用[J].計(jì)算機(jī)應(yīng)用,2008,28(2):286-288.

[4] 高穎慧,沈振康.角度編碼染色體量子遺傳算法[J].計(jì)算機(jī)工程與科學(xué),2009,31(03):75-79.

[5] 沙林秀,賀昱曜,陳延偉.一種變步長(zhǎng)雙鏈量子遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(20):59-63.

[6] 劉衛(wèi)寧,靳洪兵,劉波.基于改進(jìn)量子遺傳算法的云計(jì)算資源調(diào)度[J].計(jì)算機(jī)應(yīng)用,2013,33(8):2151-2153.

[7] 張宗飛.一種改進(jìn)型量子遺傳算法[J].計(jì)算機(jī)工程,2010,36(6):181-183.

[8] HAN K H,KIM J H.On setting the parameters of quantum-inspired evolutionary algorithm for practical applications[J].Congress on Evolutionary Computation,2004,1(3):178-194.

[9] NARAYANAN A,MOORE M.Quantum-inspired genetic algorithm[C]//Proceedings of IEEE International Conference on Evolutionary Computation.Piscataway:IEEE,1996:61-66.

[10] 梁鴻生,郝勇娜,王凱.免疫算法[J].昆明理工大學(xué)學(xué)報(bào)(理工版),2003,28(5):72-76.

[11] 赫然,王永吉,王青.一種改進(jìn)的自適應(yīng)逃逸微粒群算法及實(shí)驗(yàn)分析[J].軟件學(xué)報(bào),2005,12(16): 2036-2044.

[12] 許鑫.細(xì)菌覓食優(yōu)化算法研究 [D].長(zhǎng)春： 吉林大學(xué),2012.

[13] SANCHEZ D,MOREND A.Learning non-taxonomic relationships from Web documents for domain ontology[J].Data and Knowledge Engineering,2008,64(3):600-623.

[14] 魏玉霞.改進(jìn)的差分進(jìn)化算法[D].廣州： 華南理工大學(xué),2013.

An Improved Quantum Genetic Algorithm Based on Concentration Adjusting

HU Xiao-xiang, LIU Man-dan

(Key Laboratory of Advanced Control and Optimization for Chemical Processes,Ministry of Education, East China University of Science and Technology,Shanghai 200237,China)

There are shortcomings of slow convergence and easily falling into local optimum using quantum genetic algorithm (QGA) to optimize multimodal functions.This paper proposes an improved quantum genetic algorithm (IQGA) by introducing the concept of concentration.Before updating quantum gates,IQGA screens and culls the individuals of high concentrations and inferior individuals,and then utilizes new individuals to replace them so as to improve the global search capability.The comparison test among five typical complex continuous functionst verifies the feasibility and effectiveness of the proposed IQGA.

quantum genetic algorithm; concentration; improved quantum genetic algorithm; comparison test

1006-3080(2016)05-0690-06

10.14135/j.cnki.1006-3080.2016.05.016

2015-12-10

中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金(WH1213010)

胡小祥(1991-),男,安徽宿松人，碩士生,主要研究方向?yàn)槲鬯幚磉^(guò)程建模、智能優(yōu)化計(jì)算。E-mail：hxxjesse@163.com

劉漫丹，E-mail:liumandan@ecust.edu.cn

X703.1; TP301.6

A