多尺度量子諧振子算法的收斂特性

王 鵬,黃 焱,袁亞男,都 政,安俊秀

(1.西南民族大學(xué),四川成都 610225;2.中國科學(xué)院成都計算機(jī)應(yīng)用研究所,四川成都 610041;3.中國科學(xué)院大學(xué),北京 100049;4.國家超級計算深圳中心,廣東深圳518055;5.成都信息工程大學(xué)并行計算實驗室,四川成都 610225)

?

多尺度量子諧振子算法的收斂特性

王 鵬1,黃 焱2,3,袁亞男2,3,都 政4,安俊秀5

(1.西南民族大學(xué),四川成都 610225;2.中國科學(xué)院成都計算機(jī)應(yīng)用研究所,四川成都 610041;3.中國科學(xué)院大學(xué),北京 100049;4.國家超級計算深圳中心,廣東深圳518055;5.成都信息工程大學(xué)并行計算實驗室,四川成都 610225)

多尺度量子諧振子算法的收斂特性證明單一尺度的收斂過程不能同時獲得良好的全局搜索精度和局部搜索精度,只有采用多尺度迭代才能實現(xiàn)對全局最優(yōu)解的逐步精確定位,所以MQHOA算法利用量子諧振子收斂過程(QHO收斂)和多尺度收斂過程(M收斂)兩個嵌套的收斂過程實現(xiàn)對優(yōu)化問題的求解.QHO收斂過程按諧振子波函數(shù)由高能態(tài)向低能態(tài)的變化實現(xiàn)搜索區(qū)域的收縮,M收斂過程以2的倍數(shù)逐步減小尺度提高搜索精度.算法的波函數(shù)收斂定理證明QHO收斂時采樣分布為高斯分布.QHO收斂過程算法模型中不同能級和不同尺度下的波函數(shù)圖像為跟蹤研究算法的迭代收斂過程提供了直觀的具有物理含義的手段.實驗證明算法在收斂過程中基態(tài)波函數(shù)形態(tài)和基態(tài)時零點能的存在都與算法物理模型的理論描述和預(yù)言是高度吻合的.

優(yōu)化算法;量子算法;收斂;量子諧振子

電子學(xué)報URL:http://www.ejournal.org.cn DOI:10.3969/j.issn.0372-2112.2016.08.031

1 引言

多尺度量子諧振子算法(Multi-scale Quantum Harmonic Oscillator Algorithm,MQHOA)是2009年提出的一種模仿量子諧振子波函數(shù)能級模型的優(yōu)化算法[1,2].文獻(xiàn)[2]中的結(jié)果表明MQHOA算法能以較少的迭代次數(shù)準(zhǔn)確地獲得全局最優(yōu)解,對于15種2維標(biāo)準(zhǔn)測試函數(shù)分別進(jìn)行1000次重復(fù)計算都能以100%的概率獲得全局最優(yōu)解,同時對于高維測試函數(shù)如6維Griewank函數(shù),8維Rastrigrin函數(shù),10維Levy函數(shù)、Zakharov函數(shù)、Sum Square函數(shù),15維Sphere函數(shù)也都能以100%的概率獲得全局最優(yōu)解.該算法在2009年首次提出后(最初版本稱為模擬諧振子算法SHO),就引起了國內(nèi)一些學(xué)者的關(guān)注和研究,并將這一算法成功應(yīng)用于多個領(lǐng)域[3～7].MQHOA算法作為一種新的優(yōu)化算法,在近期研究中還被成功地應(yīng)用到組合優(yōu)化、聚類及大規(guī)模數(shù)據(jù)中心相空間分析方法中,預(yù)計將具有廣闊的應(yīng)用前景.

近年提出的與MQHOA結(jié)構(gòu)最為相似的優(yōu)化算法是文獻(xiàn)[8,9]所提出的具有很好收斂性的量子粒子群算法(QPSO),QPSO取消了傳統(tǒng)粒子群算法的速度參數(shù)并利用δ勢阱所得到的量子波函數(shù)構(gòu)造算法[10],而本文所提出的MQHOA算法則直接利用諧振子勢阱所得到的量子波函數(shù)構(gòu)造算法,通過多尺度收斂實現(xiàn)對目標(biāo)函數(shù)的全局搜索,本文算法的收斂過程具有更為精巧的數(shù)學(xué)結(jié)構(gòu)和更為明確的物理意義,其收斂過程完全符合量子諧振子物理模型的預(yù)言.

MQHOA算法的收斂過程是由量子諧振子收斂(Quantum Harmonic Oscillator,QHO收斂)和多尺度收斂(Multi-scale,M收斂)兩個嵌套的迭代過程構(gòu)成,這兩個收斂過程的特性決定了整個算法的性能,本文從MQHOA算法的收斂特性入手,發(fā)現(xiàn)MQHOA的收斂過程的理論和實驗結(jié)果與量子諧振子物理模型所預(yù)言的收斂特性高度吻合.

2 MQHOA算法的基本收斂過程和參數(shù)選擇

2.1 MQHOA算法的基本收斂過程

MQHOA算法的收斂過程包含兩個迭代步驟,一個是在同一尺度下的量子諧振子收斂過程,一個是多尺度收斂過程.QHO收斂過程實現(xiàn)對搜索空間的逐步收縮定位,M收斂過程實現(xiàn)對采樣精度的逐步提高,MQHOA算法從數(shù)學(xué)的角度也可以認(rèn)為是一種多尺度高斯鄰域采樣群體算法.由于整個算法在迭代過程中只采用了不同尺度下的高斯鄰域采樣,使MQHOA與其他自然算法相比具有簡單的數(shù)學(xué)描述和算法結(jié)構(gòu).我們在文獻(xiàn)[2]中對MQHOA算法的基本過程進(jìn)行了詳細(xì)描述.

在MQHOA算法收斂過程中當(dāng)前k個最優(yōu)解位置的方差σk是一個十分重要的參數(shù),算法在QHO收斂時每一次迭代都是以σk作為收斂判據(jù)的.σk在收斂過程中的變化反映了算法的整體收斂狀態(tài),圖1為二維Levy函數(shù)和Griewank函數(shù)求最優(yōu)解迭代時σk與迭代次數(shù)的關(guān)系(縱軸是以2為底的對數(shù)坐標(biāo)).對于Levy函數(shù)，迭代總次數(shù)為7,x方向的σk在第6次迭代時為0,y方向的σk在第7次迭代時為0,x方向首先實現(xiàn)收斂,而算法的結(jié)束條件是所有采樣坐標(biāo)位置都同時滿足收斂條件,所以算法總收斂次數(shù)為迭代次數(shù)最多的變量方向;對于Griewank函數(shù)，迭代總次數(shù)為11,x、y方向的σk均在第11次迭代時變?yōu)?,最后收斂時σk為0表明算法收斂時k個較優(yōu)解的位置全部相同.σk在整個收斂過程中通常都是逐步減小的,σk與迭代次數(shù)的曲線關(guān)系能反映算法的基本收斂進(jìn)程.

2.2k、m參數(shù)的選擇對算法收斂性的影響

MQHOA算法的控制參數(shù)非常少,主要就是群體參數(shù)k和采樣參數(shù)m,群體參數(shù)k是實驗中算法每次迭代保留的高斯采樣區(qū)域數(shù)量,采樣參數(shù)m是一個采樣區(qū)域內(nèi)按N(xi,σ2)生成新的采樣位置的個數(shù),適量的采樣區(qū)域數(shù)量和采樣區(qū)域內(nèi)的采樣密度是精確求解全局優(yōu)化問題的前提,作為MQHOA算法中的重要參數(shù)對算法的收斂特性有重要影響,所以首先需要確定參數(shù)k、m的數(shù)值.

圖2(a)、(b)、(c)所示為2維、3維和4維Griewank函數(shù)在不同k、m組合下獲得最優(yōu)解時總的迭代次數(shù)變化曲線,當(dāng)m<100時,隨著m的增大,每個采樣區(qū)域采樣密度逐漸增大,算法迭代次數(shù)快速降低,當(dāng)m大于100后繼續(xù)增大時,迭代次數(shù)逐漸趨于穩(wěn)定,m>100后m的值對迭代次數(shù)的影響不大,這說明對于一個高斯采樣區(qū)域進(jìn)行100次采樣就能基本符合形成概率波函數(shù)的要求.綜合以上對k,m參數(shù)的收斂特征研究,本文在實驗中通常統(tǒng)一取k=20,m=100.MQHOA算法控制參數(shù)少而且通常不需要人為進(jìn)行調(diào)整正是由于算法具有簡潔的數(shù)學(xué)結(jié)構(gòu).

3 MQHOA算法的QHO收斂過程研究

3.1 QHO收斂過程的收斂性分析

MQHOA算法包含QHO和M兩個收斂過程,但M收斂過程是確定的2倍收縮過程,因此只需證明QHO收斂過程在任意尺度σs下的收斂性即可.

QHO收斂過程的收斂條件為σk≤σs,只需證明在QHO收斂過程中k個高斯鄰域采樣區(qū)域的中心點位置的標(biāo)準(zhǔn)差σk一定能滿足收斂條件即可.

假設(shè)在σs尺度下k個高斯鄰域采樣區(qū)域的中心點xi中當(dāng)前最優(yōu)解位置為xmin,則根據(jù)高斯采樣的定義,xmin所對應(yīng)的采樣區(qū)域在下一次迭代進(jìn)行m個采樣時,如果存在一個ε鄰域,使在區(qū)間[xmin-ε,xmin+ε]內(nèi)的采樣位置對應(yīng)的目標(biāo)函數(shù)值均小于其他k-1個采樣區(qū)域,根據(jù)采樣函數(shù)的概率含義,則出現(xiàn)這一結(jié)果的概率可以用下式計算得到:

(1)

其中ε鄰域不存在的情況為:被優(yōu)化函數(shù)有多個全局最優(yōu)位置,此時在某一尺度的k個采樣中心有可能會向多個全局最優(yōu)位置聚集,使在區(qū)間[xmin-ε,xmin+ε]內(nèi)的采樣函數(shù)值均小于其他k-1個采樣區(qū)域的條件有可能無法滿足,從而σk≤σs的QHO收斂條件也無法滿足,QHO收斂過程將無法退出并入下一個尺度的迭代.

上面的分析表明MQHOA的基本算法在目標(biāo)函數(shù)有多個全局最優(yōu)解時是有可能不收斂的,但在一些應(yīng)用場合我們反而需要算法能找到多個全局最優(yōu)解,甚至是找到多個極值區(qū)域.如在聚類應(yīng)用中就希望算法能找到多個可能的聚類區(qū)域.

3.2 QHO收斂過程中的波函數(shù)收斂定理

在QHO收斂過程中我們把每次迭代時k個標(biāo)準(zhǔn)差為σ的高斯采樣函數(shù)的疊加稱為算法的波函數(shù),歸一化的算法波函數(shù)定義如下式:

(2)

算法波函數(shù)的概率分布ψQHO(x)就是對目標(biāo)函數(shù)在定義域上進(jìn)行采樣的概率分布,單尺度量子諧振子算法迭代過程中標(biāo)準(zhǔn)差σ的值保持不變,算法對最小值的搜索只能在一個尺度上進(jìn)行,算法波函數(shù)在收斂過程中將呈現(xiàn)出與量子諧振子波函數(shù)相似的波函數(shù)能級圖像.

在QHO迭代過程中算法波函數(shù)都扮演了重要的角色,算法的采樣概率分布、算法向量子基態(tài)單一高斯分布的收斂、算法的量子隧道效應(yīng)都是在波函數(shù)的作用下形成的,具有概率含義的算法波函數(shù)反映了量子諧振子算法的收斂過程與其物理模型是非常吻合的,波函數(shù)直觀地描述了算法的運行狀態(tài).

因此在尺度σs下QHO過程收斂到基態(tài),滿足σk≤σs時可以得出:

算法的物理模型表明QHO收斂過程就是系統(tǒng)能級從高能態(tài)不斷降低到基態(tài)的過程,為了研究算法在QHO收斂過程中的能量變化情況,可以對QHO迭代中的能量定義如下:

(3)

根據(jù)零點能的定義在尺度σs下QHO收斂到基態(tài)時零點能的理論值可以由下式計算:

(4)

3.4 QHO收斂過程的波函數(shù)特性

MQHOA算法的物理模型認(rèn)為在同一尺度的QHO收斂過程中可以觀察到與量子諧振子相似的不同能級的波函數(shù)圖像.圖4中所示為對2維Griewank函數(shù)在尺度σs=0.625進(jìn)行QHO迭代時x方向的波函數(shù)投影.

4 MQHOA算法的M收斂過程研究

4.1 M收斂過程分析

(5)

雙尺度方程提示我們在M收斂過程中為了更精確地進(jìn)行采樣并保證信息的完整可以在每次尺度M迭代時將采樣概率函數(shù)收縮1倍.由于MQHOA算法所使用的采樣概率函數(shù)為高斯函數(shù),可以得到以下定理.

定理2 (尺度變換定理):高斯函數(shù)收縮1倍與標(biāo)準(zhǔn)差σ減小1倍是等效的.

根據(jù)這一定理在算法設(shè)計時可以通過改變高斯函數(shù)的σ參數(shù)來實現(xiàn)采樣函數(shù)尺度的變化,從而實現(xiàn)對目標(biāo)函數(shù)更為精確的采樣和探查.

4.2 M收斂過程實驗

MQHOA算法的M收斂過程是QHO收斂過程的外層迭代,M收斂過程在QHO收斂過程結(jié)束時實現(xiàn)了搜索區(qū)域的收縮和改變采樣函數(shù)的尺度,從而實現(xiàn)在更小區(qū)域內(nèi)更高的搜索精度.

圖5為二維Griewank函數(shù)在σs=5和σs=2.5兩個尺度間的M收斂過程波函數(shù)圖,圖中第一排為波函數(shù)在搜索空間中的波函數(shù)圖像,第二排為波函數(shù)搜索空間中的等高投影,各維變量位置的定義域都取[-10,10].

圖5(a1),(b1)為尺度σs=5,QHO迭代開始時高能態(tài)波函數(shù)圖像,此時量子諧振子波函數(shù)處于高能態(tài),圖5(a2),(b2)為尺度σs=5時QHO迭代在基態(tài)收斂時的波函數(shù)圖,由于此時σs較大收斂時部分細(xì)節(jié)信息被混迭,通過將σs減小為σs/2的M迭代操作,使算法進(jìn)入尺度為σs/2的QHO收斂過程,圖5(a3),(b3)就是尺度σs/2的高能態(tài),此時可以看到在大尺度下被混迭的搜索空間細(xì)節(jié)情況.圖5(a4),(b4)為尺度σs/2收斂過程的基態(tài)波函數(shù),對比圖5(a2),(b2)可以看到在尺度σs/2下收斂后采樣區(qū)域明顯縮小,只出現(xiàn)了較少的細(xì)節(jié)混迭現(xiàn)象.MQHOA算法的M收斂過程會一直持續(xù)到σs<σmin時停止,采樣精度逐步提高,搜索區(qū)域逐步縮小,此時獲得的最優(yōu)解即是滿足精度σmin要求的全局最優(yōu)解.

5 總結(jié)

本文以MQHOA算法的收斂特性為研究對象,分別對MQHOA算法的QHO收斂和M收斂兩個重要嵌套收斂過程進(jìn)行了研究.QHO收斂實現(xiàn)了對搜索區(qū)域的逐步收縮,M收斂實現(xiàn)了采樣精度的逐步提高,因此MQHOA算法的整個收斂過程就是由QHO收斂過程和M收斂過程相互嵌套,逐步實現(xiàn)對最優(yōu)解位置的精確定位.MQHOA算法收斂過程的理論和實驗結(jié)果表明MQHOA具有精巧的數(shù)學(xué)結(jié)構(gòu)并與物理模型符合較好.

[1]王鵬.云計算的關(guān)鍵技術(shù)與應(yīng)用實例[M].北京:人民郵電出版社,2010:168-194.

[2]王鵬,黃焱,任超,郭又銘.多尺度量子諧振子高維函數(shù)全局優(yōu)化算法[J].電子學(xué)報,2013,41(12):2468-2473.

Wang P,Huang Y,Ren C,Guo YM.Multi-scale quantum harmonic oscillator for high-dimensional function global optimization algorithm[J].Acta Electronica Sinica,2013,41(12):2468-2473.(in Chinese)

[3]王培崇,錢旭.模擬諧振子算法及其全局收斂性分析[J].計算機(jī)工程,2013,39(3):209-212.

Wang PC,Qian X.Simulated harmonic oscillator algorithm and its global convergence analysis[J].Computer Engineering,2013,39(3):209-212.(in Chinese)

[4]倪霖,段超,鐘輝.基于模擬諧振子算法的多項目調(diào)度[J].計算機(jī)應(yīng)用,2011,31(9):2559-2562.

Ni L,Duan C,Zhong H.Multi-project scheduling based on simulated harmonic oscillator algorithm[J].Journal of Computer Applications,2011,31(9):2559-2562.(in Chinese)

[5]姚明.模擬諧振子算法在求解整數(shù)規(guī)劃問題中的應(yīng)用[J].微型機(jī)與應(yīng)用,2013,32(7):77-79.

Yao M.Application of simulated harmonic oscillator algorithm in integer programming[J].Microcomputer &Its Application,2013,32(7):77-79.(in Chinese)

[6]于海濤,王慧強(qiáng),李梓,韓立娟.基于模擬諧振子的優(yōu)化K-means聚類算法[J].計算機(jī)工程與應(yīng)用,2012,48(30):122-127.

Yu HT,Wang HQ,Li Z,et al.Optimized k-means clustering algorithm based on simulated harmonic oscillator[J].Computer Engineering and Application,2012,48(30):122-127.(in Chinese)

[7]程勖,李文輝,劉裕斌.基于模擬諧振子算法的服務(wù)調(diào)度技術(shù)[J].大連海事大學(xué)學(xué)報(自然科學(xué)版),2013,39 (2):78-81.

Cheng X,Li WH,Liu YB.Service scheduling technique based on simulated harmonic oscillator algorithm[J].Journal of Dalian Maritime University,2013,39(2):78-81.(in Chinese)

[8]Feng B,Sun J,Xu WB.A global search strategy of quantum-behaved particle swarm optimization[A].IEEE Conference on Cybernetics and Intelligent Systems[C].Singapore:IEEE,2004.111-116.

[9]Sun J,Wu XJ,Vasile Palade,et al.Convergence Analysis and improvements of quantum-behaved particle swarm optimization[J].Information Sciences,2012,193(15):81-103.

[10]Sun J,Fang W,Wu XJ,et al.Quantum-behaved particle swarm optimization:analysis of the individual particle behavior and parameter selection[J].Evolutionary Computation,2012,20(3):349-393.

王 鵬(通信作者) 男,1975年8月出生于四川省犍為縣.現(xiàn)為西南民族大學(xué)教授、博士生導(dǎo)師,研究方向為智能算法、云計算、并行計算.

E-mail:wp002005@163.com

黃 焱 男,1982年7月出生于江蘇省泗陽縣.博士研究生.主要研究方向為智能算法、云計算、并行計算.

E-mail:16481339@qq.com

Convergence Characteristics of Multi-scale Quantum Harmonic Oscillator Algorithm

WANG Peng1,HUANG Yan2,3,YUAN Ya-nan2,3,DU Zheng4,AN Jun-xiu5

(1.SouthwestUniversityforNationalities,Chengdu,Sichuan610225,China;2.ChengduInstituteofComputerApplication,ChineseAcademyofSciences,Chengdu,Sichuan610041,China;3.UniversityofChineseAcademyofSciences,Beijing100049,China;4.NationalSupercomputingCenterinShenzhen,Shenzhen,Guangdong518055,China;5.ParallelComputingLaboratory,ChengduUniversityofInformationTechnology,Chengdu,Sichuan610225,China)

The convergence characteristics of Multi-scale Quantum Harmonic Oscillator Algorithm (MQHOA) prove that single scale convergence process cannot simultaneously get global search accuracy and local search accuracy.Only by multi-scale iteration can we gradually get the accurate position of the global optimum solution.MQHOA solves the optimization problem by two nested convergence processes:Quantum Harmonic Oscillator convergence process (QHO process) and Multi-scale convergence process (M process).QHO process shrinks the searching areas by the manner harmonic oscillator's wave function moving from high-energy state to low-energy state.M process shrinks the search areas by half cutting to improve searching precision.The wave function convergence theorem proves that sampling distribution is Gauss distribution when QHO process is convergent.By the wave function diagram in different energy level and scale,we can track the algorithm iterative process explicitly.The experiments demonstrate the shape of ground-state wave function,the existence of zero-point energy on the ground state,all of which exactly match the physical model of MQHOA.

optimization algorithm;quantum algorithm;convergence;quantum harmonic oscillator

2014-12-17;

2015-08-09;責(zé)任編輯:馬蘭英

國家自然科學(xué)基金(No.60702075);廣東省科技廳高新技術(shù)產(chǎn)業(yè)化科技攻關(guān)項目(No.2011B010200007);四川省青年科學(xué)基金(No.09ZQ026-068);成都市科技局創(chuàng)新發(fā)展戰(zhàn)略研究項目(No.11RXYB016ZF)

TP301

A

0372-2112 (2016)08-1988-06