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

胡小祥, 劉漫丹

(華東理工大學化工過程先進控制和優(yōu)化技術教育部重點實驗室,上海 200237)

?

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

胡小祥, 劉漫丹

(華東理工大學化工過程先進控制和優(yōu)化技術教育部重點實驗室,上海 200237)

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

量子遺傳算法; 濃度; 改進型量子遺傳算法; 對比測試

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

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

1 QGA簡介

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

(1)

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

(2)

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

2 IQGA設計思路

2.1 剔除高濃度個體

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

(3)

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

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

(4)

(5)

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

2.2 剔除劣個體

3 IQGA流程

IQGA流程如下:

(2) 對初始化種群Q(t0)中的每個個體實施一次測量轉換,得到對應的測量值P(t0);

(3) 計算每個測量值對應的適應度值;

(4) 記錄最優(yōu)個體及其適應度值,并將這個最優(yōu)個體作為下一代進化目標;

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

(7) 計算每個測量值對應的適應度值;

(8) 記錄最優(yōu)個體及其適應度值,并將這個最優(yōu)個體作為下一代進化目標;

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

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

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

(12) 利用量子旋轉門U(t)對種群個體進行更新,得到子代種群Q(t+1);

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

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

4.1 算法分析

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

圖1 QGA的迭代過程Fig.1 Iteration process of QGA

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

圖2 IQGA的迭代過程Fig.2 Iteration process of IQGA

選取IQGA在迭代演化過程中對某一代的種群在進入下一代迭代前的種群個體適應度分布情況進行分析。圖3示出了迭代到某一代的種群個體的適應度分布,其中高濃度個體分別為[-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]。對于這些個體,先判斷是否為精英個體,對于高濃度且為非精英的個體進行剔除,對于高濃度且為精英的個體進行保留。這樣的操作增加了種群的多樣性,有利于種群尋優(yōu)。

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

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

4.2 參數(shù)選擇

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

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

表1 ε取不同值的計算結果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對函數(shù)進行優(yōu)化,ε=0.09,h=0.05，s=0.05,運行結果見表2。從計算結果可知,w為0.10時效果較好。

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

表2 w取不同值的計算結果Table 2 Calculation results of different w

表3 h取不同值的計算結果Table 3 Calculation results of different h

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

表4 s取不同值的計算結果Table 4 Calculation results of different s

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

5 算法測試

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

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

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

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

表5 測試函數(shù)計算結果Table 5 Calculation results of test functions

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

表6 測試函數(shù)計算結果Table 6 Calculation results of test functions

6 結 論

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

[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].計算機應用,2008,28(2):286-288.

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

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

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

[7] 張宗飛.一種改進型量子遺傳算法[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].昆明理工大學學報(理工版),2003,28(5):72-76.

[11] 赫然,王永吉,王青.一種改進的自適應逃逸微粒群算法及實驗分析[J].軟件學報,2005,12(16): 2036-2044.

[12] 許鑫.細菌覓食優(yōu)化算法研究 [D].長春： 吉林大學,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] 魏玉霞.改進的差分進化算法[D].廣州： 華南理工大學,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

中央高校基本科研業(yè)務費專項資金(WH1213010)

胡小祥(1991-),男,安徽宿松人，碩士生,主要研究方向為污水處理過程建模、智能優(yōu)化計算。E-mail：hxxjesse@163.com

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

X703.1; TP301.6

A