具有能級(jí)穩(wěn)定過程的MQHOA優(yōu)化算法

王鵬，黃焱

（1. 西南民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川 成都 610225；2. 淮陰師范學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 淮安 223300）

具有能級(jí)穩(wěn)定過程的MQHOA優(yōu)化算法

王鵬1，黃焱2

（1. 西南民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，四川 成都 610225；2. 淮陰師范學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 淮安 223300）

在量子模型下將優(yōu)化問題轉(zhuǎn)化為求解約束態(tài)的基態(tài)波函數(shù)問題，通過泰勒近似采用諧振子勢(shì)阱對(duì)目標(biāo)函數(shù)進(jìn)行逼近，類比量子諧振子的波函數(shù)圖像提出了一種改進(jìn)的多尺度量子諧振子優(yōu)化算法。算法包括3個(gè)基本迭代收斂過程：能級(jí)穩(wěn)定過程、能級(jí)降低過程和尺度降低過程，算法的收斂過程與物理模型基本吻合。改進(jìn)算法將主觀控制參數(shù)減少為1個(gè)，同時(shí)參照量子模型定義了算法的波函數(shù)和零點(diǎn)能。實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法的復(fù)雜函數(shù)優(yōu)化性能優(yōu)于多種常見優(yōu)化算法，對(duì)于Ackley、Griewank、Sphere、Sum Squares、Zakharov等高維標(biāo)準(zhǔn)測(cè)試函數(shù)均能以100%的概率獲得全局最優(yōu)解。

優(yōu)化算法；函數(shù)優(yōu)化；多尺度量子諧振子算法；波函數(shù)；基態(tài)

1 引言

利用自然現(xiàn)象和自然規(guī)律構(gòu)造新的計(jì)算智能算法是一種常用的方法，如蟻群算法、遺傳算法、粒子群算法、神經(jīng)網(wǎng)絡(luò)算法。但計(jì)算智能算法所面臨的問題是大量算法缺少完整的數(shù)學(xué)理論基礎(chǔ)，不能充分地利用數(shù)學(xué)工具對(duì)算法進(jìn)行研究和分析，這一點(diǎn)制約了這一研究領(lǐng)域的發(fā)展。20世紀(jì)初量子物理打破了幾百年來牛頓力學(xué)對(duì)世界確定性的描述，使人類認(rèn)識(shí)到不確定性才是這個(gè)世界的本質(zhì)，量子理論成熟完備的理論體系為算法的研究提供了方便，利用量子理論來構(gòu)造和改進(jìn)算法受到了大家的廣泛重視。如量子退火算法（QA, quantum annealing）就是一種利用含時(shí)薛定諤方程的演化原理逐步向基態(tài)收斂，從而實(shí)現(xiàn)對(duì)全局最優(yōu)解搜索的算法[1～4]；文獻(xiàn)[5～7]也提出了一種利用δ勢(shì)阱波函數(shù)構(gòu)造的量子粒子群（QPSO）算法，由于QPSO算法采用了δ勢(shì)阱，所以收斂速度較快，但算法容易早熟，而且人為控制參數(shù)多，需要指定最大迭代次數(shù)實(shí)現(xiàn)對(duì)算法進(jìn)行強(qiáng)行終止。以上算法都利用了量子波函數(shù)的概率解釋，基于量子波函數(shù)構(gòu)造的智能優(yōu)化算法通常都是以向能級(jí)基態(tài)進(jìn)化為目標(biāo)，通過量子隧道效應(yīng)避免陷入局部最優(yōu)區(qū)域。

受到量子退火理論的啟發(fā)，2013年，王鵬等[8]首次提出了多尺度量子諧振子算法（C-MQHOA）的基本物理模型和算法框架，C-MQHOA算法類比量子諧振子不同能級(jí)波函數(shù)構(gòu)造了一個(gè)以多個(gè)正態(tài)采樣為基本操作的多尺度采樣搜索方法，利用多個(gè)正態(tài)采樣的迭加作為算法波函數(shù)來描述當(dāng)前最優(yōu)解的概率分布，這一算法被成功應(yīng)用于函數(shù)優(yōu)化問題；文獻(xiàn)[9]對(duì) C-MQHOA算法的物理模型從經(jīng)典諧振子和量子諧振子角度進(jìn)行了分析，利用量子算符方法證明了優(yōu)化算法的測(cè)不準(zhǔn)關(guān)系，測(cè)不準(zhǔn)關(guān)系從理論上指出了一般優(yōu)化算法進(jìn)行多尺度迭代的必要性；文獻(xiàn)[10]給出了C-MQHOA算法的程序?qū)崿F(xiàn)方法；文獻(xiàn)[11]和文獻(xiàn)[12]分別將 C-MQHOA算法成功應(yīng)用于多峰函數(shù)和整數(shù)優(yōu)化問題。文獻(xiàn)[13]和文獻(xiàn)[14]將C-MQHOA算法的基本思想應(yīng)用于聚類分析和TSP組合優(yōu)化問題，這意味著C-MQHOA算法有望在非函數(shù)優(yōu)化領(lǐng)域，如數(shù)據(jù)中心優(yōu)化[15]、集群調(diào)度[16]等實(shí)際工程問題中得到成功應(yīng)用。但文獻(xiàn)[8]所提出的C-MQHOA算法框架需要有2個(gè)主觀控制參數(shù)，缺乏能級(jí)穩(wěn)定過程，與物理模型存在不一致的地方，算法每次迭代需要對(duì)較多的位置進(jìn)行采樣，算法效率較低，不能實(shí)現(xiàn)對(duì)超高維復(fù)雜函數(shù)的優(yōu)化。針對(duì)文獻(xiàn)[8]中 C-MQHOA算法存在的問題，本文提了C-MQHOA算法的改進(jìn)模型，引入了能級(jí)穩(wěn)定過程，使新的MQHOA算法與物理模型符合的更好，在減少主觀控制參數(shù)個(gè)數(shù)的同時(shí)實(shí)現(xiàn)了算法效率的大幅度提高，可以高效地求解超高維復(fù)雜函數(shù)的優(yōu)化問題，因此，本文所提出的算法模型可以取代文獻(xiàn)[8]中原有 C-MQHOA算法作為新的MQHOA算法的基本模型，因此，本文直接稱新算法為MQHOA算法。

2 MQHOA算法的基本物理模型

量子理論的出現(xiàn)使人們認(rèn)識(shí)到了一個(gè)由概率所統(tǒng)治的世界，大家所生活的世界并不是確定的。如圖1所示，經(jīng)典物理中按照盧瑟福的原子模型通常將電子的運(yùn)動(dòng)用確定的軌道來進(jìn)行描述，但這一模型無法解釋原子結(jié)構(gòu)的穩(wěn)定性，帶電粒子做圓周運(yùn)動(dòng)時(shí)會(huì)輻射能量，按照這一模型電子將最終落入原子核中。量子力學(xué)的出現(xiàn)使人們對(duì)微觀粒子的運(yùn)動(dòng)有了新的認(rèn)識(shí)，依據(jù)量子力學(xué)理論原子核外電子的運(yùn)動(dòng)并沒有確定的方向和軌跡，只能用電子云描述它在原子核外空間某處出現(xiàn)幾率的大小，在量子力學(xué)中粒子出現(xiàn)的幾率可以利用波函數(shù)（wave function）來進(jìn)行描述，但波函數(shù)既不能描述粒子的軌跡也不能描述粒子的形狀，對(duì)于任意粒子只能依據(jù)波函數(shù)給出其位置分布概率。

圖1 經(jīng)典電子軌道和量子電子云

描述量子系統(tǒng)的方程被稱為薛定諤方程，它可以被寫為如下的形式

定態(tài)薛定諤方程描述了粒子在勢(shì)阱V( x)約束下的運(yùn)動(dòng)情況。MQHOA算法將優(yōu)化問題中的目標(biāo)函數(shù)f( x)作為薛定諤方程中的勢(shì)阱 V( x) =f( x)，函數(shù)優(yōu)化問題在這一對(duì)應(yīng)條件下就轉(zhuǎn)變?yōu)榱饲罅Ｗ釉趧?shì)阱 V( x) =f( x)約束下的基態(tài)波函數(shù)ψ0(x)問題，量子系統(tǒng)處于基態(tài)時(shí)粒子將以最大的概率出現(xiàn)在勢(shì)阱最低點(diǎn)附近，基態(tài)波函數(shù)的概率分布就是目標(biāo)函數(shù)最優(yōu)解的概率分布。但通常復(fù)雜的勢(shì)阱利用薛定諤方程是無法求出精確波函數(shù)的。在量子物理中經(jīng)常會(huì)采用諧振子勢(shì)來近似描述粒子在平衡位置附近的復(fù)雜振動(dòng)。同樣，復(fù)雜目標(biāo)函數(shù)f( x)在全局最小值位置x0附近也可以采用泰勒序列進(jìn)行展開

在f( x)的泰勒展開中f( x0)為常數(shù)，在最小值位置x0處目標(biāo)函數(shù)的一階導(dǎo)數(shù) f′(x0) = 0，同時(shí)去除高次項(xiàng)保留二次項(xiàng)，可以得到因此，在最小值位置x0附近，可以利用諧振子勢(shì)阱來近似表示復(fù)雜目標(biāo)函數(shù)f( x)，在這一近似條件下求解目標(biāo)函數(shù)f( x)最小值的問題就可以轉(zhuǎn)變?yōu)榍蠼庠谥C振子勢(shì)阱約束下的基態(tài)波函數(shù)問題（諧振子約束態(tài)問題），此時(shí)薛定諤方程為

根據(jù)量子理論，諧振子勢(shì)阱約束下的波函數(shù)是可以準(zhǔn)確獲得的，其不同能級(jí)波函數(shù)如圖2所示。

圖2 不同能級(jí)下的諧振子波函數(shù)

量子諧振子波函數(shù)從高能態(tài)到基態(tài)由多個(gè)正態(tài)分布的概率振動(dòng)逐步聚集到一起，其基態(tài)波函數(shù)就是一個(gè)正態(tài)分布，因此，MQHOA算法的基本采樣概率函數(shù)為正態(tài)分布函數(shù)。本文引入了能級(jí)穩(wěn)定過程，使MQHOA算法在高能級(jí)的亞穩(wěn)態(tài)能進(jìn)行充分的搜索，保證了解的多樣性，從而更準(zhǔn)確地定位所有局部最優(yōu)區(qū)域。

MQHOA算法的物理模型可以歸納為以下幾點(diǎn)。

1) 勢(shì)阱等效：將復(fù)雜目標(biāo)函數(shù)等效于量子勢(shì)阱V( x) =f( x)，從而將優(yōu)化問題轉(zhuǎn)化為求解約束態(tài)下量子基態(tài)波函數(shù)的問題。

2) 泰勒近似：在目標(biāo)函數(shù)極值附近利用諧振子勢(shì)對(duì)目標(biāo)函數(shù)進(jìn)行近似。

3) 量子波函數(shù)：利用波函數(shù)來描述目標(biāo)函數(shù)最優(yōu)解當(dāng)前的概率分布。

4) 量子能級(jí)：目標(biāo)函數(shù)的局部最優(yōu)對(duì)應(yīng)于量子系統(tǒng)中的高能級(jí)亞穩(wěn)態(tài)，全局最優(yōu)對(duì)應(yīng)于量子系統(tǒng)中的基態(tài)。

在這一物理模型下優(yōu)化問題就被轉(zhuǎn)變?yōu)榍蠼饬孔酉到y(tǒng)基態(tài)波函數(shù)的問題，利用量子退火方法實(shí)現(xiàn)系統(tǒng)由高能級(jí)亞穩(wěn)態(tài)向基態(tài)的能級(jí)逐步躍遷。量子理論完整的數(shù)學(xué)體系為算法分析提供了數(shù)學(xué)工具。

3 MQHOA算法的基本迭代過程

根據(jù)算法的物理模型，本文提出了一種具有能級(jí)穩(wěn)定過程的MQHOA算法流程，算法流程的偽代碼如下（二維目標(biāo)函數(shù)）。

MQHOA算法偽代碼如下。

Initialize：k, σmin, σs=max ?min

Randomly generate xi( i =1,… ,k) in domain[min,max]

Calculate the standard deviation σk′ for all xi

Do

Do

Do

?xi, generate

?xiandif f()

Calculate the standard deviation σk

While( ?σk> σs)

Update the worst solution xworst=xmean

While (σk>σs)

While(σs>σmin)

Output xbestand f( xbest)

偽代碼中目標(biāo)函數(shù)的定義域?yàn)閇min,max]，算法的初始尺度 σs=max?min ，算法需要主觀指定的參數(shù)只有采樣區(qū)域個(gè)數(shù)k，k值越大對(duì)應(yīng)于算法初始能級(jí)越高，而σmin則是優(yōu)化算法在每一個(gè)維度上的收斂精度，MQHOA算法可以以指定的位置精度自動(dòng)實(shí)現(xiàn)算法的收斂，也可人為指定最大迭代次數(shù)。算法初始化時(shí)在目標(biāo)函數(shù)定義域內(nèi)的每一個(gè)維度分別隨機(jī)生成k個(gè)采樣位置xi，并計(jì)算出這k個(gè)采樣位置的標(biāo)準(zhǔn)差σk′。為描述方便，下面以二維函數(shù)為例說明算法包括3個(gè)迭代過程。

1) 能級(jí)穩(wěn)定過程

這一迭代過程對(duì)所有的k個(gè)采樣位置xi分別按正態(tài)分布 N( xi,)生成一個(gè)新的采樣位置，總共生成k個(gè)新的采樣位置，如果新采樣位置對(duì)應(yīng)目標(biāo)函數(shù)的值較小 f()

2) 能級(jí)降低過程

當(dāng)算法處于穩(wěn)定能級(jí)狀態(tài)后，以k個(gè)采樣位置的平均值xmean=x替換x中最差解的位置 xworst，實(shí)

i

i現(xiàn)了系統(tǒng)能級(jí)的下降并進(jìn)入下一個(gè)低能級(jí)上的能級(jí)穩(wěn)定過程。相比利用最優(yōu)解位置取代最差解位置的能級(jí)降低策略，本策略保證了解空間采樣的多樣性。MQHOA算法的能級(jí)下降過程要一直持續(xù)到當(dāng)前k個(gè)采樣位置的標(biāo)準(zhǔn)差σk小于等于當(dāng)前尺度σs（ σk≤σs），這時(shí)k個(gè)采樣位置xi收縮到了正態(tài)分布N( x,σ2)區(qū)域內(nèi)，此時(shí)算法認(rèn)為已達(dá)到尺度σ下

i ss

的能量基態(tài)，即最低能量狀態(tài)。

3) 尺度降低過程

尺度降低過程與量子退火算法的退火過程類似，根據(jù)文獻(xiàn)[9]中證明的優(yōu)化算法測(cè)不準(zhǔn)關(guān)系，要實(shí)現(xiàn)對(duì)全局最優(yōu)解的高精度搜索必須采用多尺度迭代。尺度決定了搜索的精度，當(dāng)算法達(dá)到尺度σs下的基態(tài)時(shí)，尺度降低過程將當(dāng)前尺度減半使算法在更小的尺度下重復(fù)能級(jí)由高到低的迭代過程，從大尺度到小尺度的變化過程對(duì)應(yīng)于算法逐步從全局搜索過渡到局部搜索，尺度減半的原理來自于小波二進(jìn)變換的啟發(fā)，按尺度減半在大多數(shù)目標(biāo)函數(shù)上都表現(xiàn)出了良好的性能。最小搜索尺度σmin就決定了算法結(jié)果的位置精度，當(dāng)前尺度σs≤σmin時(shí)，算法停止并輸出xi中的最優(yōu)結(jié)果。對(duì)于不同的目標(biāo)函數(shù)只需指定σmin，MQHOA算法的迭代次數(shù)是不同的，算法可以自動(dòng)適應(yīng)并不需要人為指定。

MQHOA算法流程與物理模型的對(duì)應(yīng)關(guān)系如表1所示，從表中可以看出MQHOA算法很好地符合了量子理論模型。

表1 MQHOA算法與物理模型的對(duì)應(yīng)關(guān)系

4 MQHOA算法的波函數(shù)和能量

4.1 MQHOA算法的波函數(shù)定義

MQHOA算法在整個(gè)搜索過程中其采樣操作的核心機(jī)制就是當(dāng)前k個(gè)采樣位置xi所對(duì)應(yīng)的k個(gè)正態(tài)概率分布 N( xi,，定義算法當(dāng)前波函數(shù)為k個(gè)正態(tài)概率分布 N( xi)的疊加

高斯函數(shù)可以作為小波分析函數(shù)，受小波二進(jìn)分析的啟發(fā)，為實(shí)現(xiàn)更高分辨率的搜索，MQHOA算法將尺度σs逐步減半，尺度減小后算法在大尺度下的基態(tài)轉(zhuǎn)變?yōu)樵谛〕叨认碌母吣軕B(tài)，算法以更高的精度對(duì)解空間進(jìn)行搜索，算法在最后結(jié)束時(shí)的波函數(shù)為

4.2 MQHOA算法的能量和零點(diǎn)能

類比量子理論MQHOA算法的能量Esσ定義如下

當(dāng)算法滿足亞穩(wěn)態(tài)判據(jù)時(shí)，此時(shí)的能量即為該亞穩(wěn)態(tài)的能級(jí)。

依據(jù)能量Eσs的定義，MQHOA算法在尺度σs基態(tài)時(shí)的零點(diǎn)能可以近似由下式計(jì)算

其中，ψ0(x)為算法基態(tài)波函數(shù)，fmin為目標(biāo)函數(shù)的理論最小值，f( xopt)是基態(tài)時(shí)當(dāng)前的最優(yōu)解。通常在當(dāng)前尺度σs較大時(shí)零點(diǎn)能會(huì)較大。零點(diǎn)能的存在正是算法量子特性的一個(gè)重要表現(xiàn)，零點(diǎn)能也可作為算法收斂特性的指標(biāo)。

5 實(shí)驗(yàn)結(jié)果與討論

為確保本文實(shí)驗(yàn)數(shù)據(jù)的可靠性，所有實(shí)驗(yàn)數(shù)據(jù)均為重復(fù) 30次計(jì)算所得到的統(tǒng)計(jì)值，測(cè)試函數(shù)如表2所示。本文MQHOA算法的參數(shù)k=30，算法的優(yōu)化位置精度 σmin= 0.000 001，優(yōu)化成功率的判斷是以目標(biāo)函數(shù)最終優(yōu)化值與理論最優(yōu)值差的絕對(duì)值小于等于0.001作為判斷標(biāo)準(zhǔn)，優(yōu)化目標(biāo)函數(shù)的維度用D來標(biāo)識(shí)，優(yōu)化目標(biāo)均是尋找目標(biāo)函數(shù)的全局最小值，本文所有標(biāo)準(zhǔn)測(cè)試函數(shù)的理論最優(yōu)值均為0。

表2 7種測(cè)試函數(shù)的名稱與編號(hào)

5.1 MQHOA算法基本優(yōu)化實(shí)驗(yàn)結(jié)果

表3給出了MQHOA算法對(duì)7種標(biāo)準(zhǔn)測(cè)試函數(shù)在10維和30維時(shí)的優(yōu)化結(jié)果，搜索定義域在各個(gè)維度均為[-2.048, 2.048]。對(duì)這7種標(biāo)準(zhǔn)測(cè)試函數(shù)，除f2函數(shù)之外，MQHOA算法均以較高的精度獲得了全局最優(yōu)值。其函數(shù)進(jìn)化次數(shù)通常只需要103～104次，并且隨維度的增加變化不明顯，這表明算法迭代次數(shù)對(duì)于目標(biāo)函數(shù)的維度并不敏感，可以應(yīng)用于高維函數(shù)的優(yōu)化問題。在本次實(shí)驗(yàn)中除f2函數(shù)之外，其余測(cè)試函數(shù)MQHOA算法在30次重復(fù)實(shí)驗(yàn)中都以100%的概率找到了全局最優(yōu)值。

5.2 MQHOA算法與其他算法的對(duì)比實(shí)驗(yàn)結(jié)果

表4中的數(shù)據(jù)為MQHOA算法與其他3種常見優(yōu)化算法 ABC（artificial bee colony algorithm）、JDE（differential evolution algorithm）、CLPSO（comprehensive learning PSO）對(duì)5種100維的標(biāo)準(zhǔn)測(cè)試函數(shù) 30次重復(fù)實(shí)驗(yàn)中獲得的全局最優(yōu)值的平均值。實(shí)驗(yàn)結(jié)果表明，MQHOA算法的實(shí)驗(yàn)結(jié)果全部優(yōu)于CLPSO算法，對(duì)4種測(cè)試函數(shù)（f3, f5, f6, f7）的實(shí)驗(yàn)結(jié)果優(yōu)于ABC、JDE算法；對(duì)比算法對(duì)函數(shù)f7的實(shí)驗(yàn)結(jié)果從精度上看可以認(rèn)為 ABC、JDE、CLPSO算法在30次實(shí)驗(yàn)中并未能有效地找到最優(yōu)解位置，事實(shí)上其成功率為0，而MQHOA算法卻以10-8的精度找到了全局最優(yōu)解。如果以0.001為標(biāo)準(zhǔn)，MQHOA在30次實(shí)驗(yàn)中共找到了4種函數(shù)（f3, f5, f6, f7）的全局最優(yōu)解位置，優(yōu)于其他3種對(duì)比算法。

5.3 MQHOA算法對(duì)高維函數(shù)的優(yōu)化實(shí)驗(yàn)結(jié)果

在函數(shù)優(yōu)化問題中隨著目標(biāo)函數(shù)維度的增加，搜索空間的大小是呈指數(shù)級(jí)增長的，因此，優(yōu)化算法對(duì)高維目標(biāo)函數(shù)特別是百維以上的超高維目標(biāo)函數(shù)的優(yōu)化性能是優(yōu)化算法的一個(gè)重要評(píng)價(jià)指標(biāo)。

表3 MQHOA算法對(duì)7種常見目標(biāo)函數(shù)的優(yōu)化結(jié)果

表4 MQHOA與其他算法對(duì)高維目標(biāo)函數(shù)的優(yōu)化效果對(duì)比

表5為MQHOA算法對(duì)5個(gè)200～500維的超高維目標(biāo)函數(shù)優(yōu)化的結(jié)果，搜索定義域在各個(gè)維度均為[-2.048, 2.048]，數(shù)據(jù)表明MQHOA算法在目標(biāo)函數(shù)為200～500維時(shí)，仍以100%的成功率獲得了目標(biāo)函數(shù)的全局最優(yōu)解。總的來看，MQHOA算法具有出色的高維函數(shù)優(yōu)化能力，這表明其有望應(yīng)用于高復(fù)雜度的優(yōu)化應(yīng)用領(lǐng)域，是一個(gè)有很好應(yīng)用前景的智能優(yōu)化算法。

5.4 MQHOA算法的波函數(shù)

根據(jù)本文對(duì)算法波函數(shù)的定義，波函數(shù)是MQHOA算法量子特性的重要體現(xiàn)，它反映了當(dāng)前目標(biāo)函數(shù)全局最優(yōu)解的概率分布，算法的收斂過程也是波函數(shù)在不同尺度向基態(tài)收斂的過程。

表5 MQHOA對(duì)超高維目標(biāo)函數(shù)的優(yōu)化實(shí)驗(yàn)結(jié)果

圖3為MQHOA算法在對(duì)Griewank函數(shù)進(jìn)行優(yōu)化時(shí)，在不同尺度下（ σs=10，σs=5，σs=1.25）收斂到基態(tài)時(shí)的波函數(shù)圖像。圖中的圓點(diǎn)為波函數(shù)對(duì)應(yīng)的k個(gè)采樣中心的位置，從圖中可以看出隨著尺度的降低算法波函數(shù)逐步向目標(biāo)函數(shù)的全局最優(yōu)位置聚集，波函數(shù)的這種聚集同時(shí)會(huì)使算法的采樣概率集中在全局最優(yōu)位置，從而提高最優(yōu)解附近的采樣密度。從圖中可以直觀地看出由于波函數(shù)的概率特性，算法在大尺度時(shí)可以實(shí)現(xiàn)對(duì)定義域的全局搜索，而在相對(duì)小的尺度下也能以一定的概率跳出局部最優(yōu)區(qū)域，這在量子理論中被稱為量子隧道效應(yīng)。波函數(shù)反映了算法當(dāng)前全局最優(yōu)解的概率分布，也是算法當(dāng)前的采樣概率分布。

圖3 Griewank 函數(shù)在不同尺度下的采樣中心及基態(tài)波函數(shù)圖像（D=2）

6 結(jié)束語

本文引入能級(jí)穩(wěn)定過程提出了一種改進(jìn)的MQHOA算法模型，新的模型包括能級(jí)穩(wěn)定過程、能級(jí)降低過程和尺度降低過程3個(gè)迭代過程，新的MQHOA算法實(shí)現(xiàn)了對(duì)超高維復(fù)雜函數(shù)優(yōu)化問題的快速求解，算法結(jié)構(gòu)簡單、實(shí)現(xiàn)容易。相比同類優(yōu)化算法，MQHOA算法的迭代過程具有簡單明確的數(shù)學(xué)過程，整個(gè)算法的基本操作只有正態(tài)采樣和 3個(gè)收斂判據(jù)，這種簡單明確的數(shù)學(xué)結(jié)構(gòu)特別有利于對(duì)其進(jìn)行收斂性分析。同時(shí)MQHOA算法需要主觀設(shè)定的控制參數(shù)只有采樣區(qū)域個(gè)數(shù)k，避免了多個(gè)控制參數(shù)所造成的算法參數(shù)設(shè)定時(shí)的困難。實(shí)驗(yàn)證明具有能級(jí)穩(wěn)定過程的 MQHOA算法在對(duì)高維函數(shù)的優(yōu)化中比其他算法具有明顯的優(yōu)勢(shì)。今后具有能級(jí)穩(wěn)定過程的MQHOA算法將作為MQHOA算法的基本算法對(duì)待。由于本文所提出的具有能級(jí)穩(wěn)定過程的 MQHOA優(yōu)化算法有著清晰完整的物理模型描述，目前已非常成熟的量子理論的數(shù)學(xué)體系為研究這一算法提供了強(qiáng)大的數(shù)學(xué)工具，解決了其他計(jì)算智能算法缺乏完備數(shù)學(xué)體系的問題。

[1] BATTAGLIA D A, SANTORO G E, TOSATTI E. Optimization by quantum annealing： lessons from hard satisfiability problems[J].Physical Review E Statistical Nonlinear & Soft Matter Physics, 2005,71(6)： 531-536.

[2] FINNILA A B, GOMEZ M A, SEBENIK C, et al. Quantum annealing：a new method for minimizing multidimensional functions[J]. Chem Phys Lett, 1994, 219 (5-6)： 343-348.

[3] SOMMA R D, BOIXO S, BARNUM H, et al. Quantum simulations of classical annealing processes[J]. Phys Rev Lett, 2008, 101(13)： 130504.[4] BROOKE J, BITKO D, ROSENBAUM T F, et al. Quantum annealing of a disordered spin system[J]. Science, 2001, 284(5415)： 779-781.

[5] SUN J, WU X J, VASILE P, et al. Convergence analysis and improvements of quantum-behaved particle swarm optimization[J]. Information Sciences, 2012, 193(15)： 81-103.

[6] FENG B, SUN J, XU W B. A global search strategy of quantum-behaved particle swarm optimization[C]//Proc of IEEE Conference on Cybernetics and Intelligent Systems, c2005： 111-116.

[7] SUN J, FANG W, WU X J, et al. Quantum-behaved particle swarm optimization： analysis of the individual particle behavior and parameter selection[J]. Evolutionary Computation, 2012, 20(3)： 349-393.

[8] 王鵬, 黃焱, 任超, 等. 多尺度量子諧振子高維函數(shù)全局優(yōu)化算法[J].電子學(xué)報(bào), 2013, 41(12)： 2468-2473.WANG P, HUANG Y, REN C, et al. Multi-scale quantum harmonic oscillator for high-dimensional function global optimization algorithm[J].Acta Electronica Sinica, 2013, 41(12)： 2468-2473.

[9] 王鵬, 黃焱. 多尺度量子諧振子優(yōu)化算法物理模型[J]. 計(jì)算機(jī)研究與探索, 2015, 9(10)： 1271-1280.WANG P, HUANG Y. Physical model of multi-scale quantum harmonic oscillator optimization algorithm[J]. Journal of Frontiers of Computer Science & Technology, 2015, 9(10)： 1271-1280.

[10] 劉峰, 王鵬, 黃焱, 等. 多尺度量子諧振子優(yōu)化算法實(shí)現(xiàn)方法研究[J].成都信息工程學(xué)院學(xué)報(bào), 2015, 30(5)： 433-438.LIU F, WANG P, HUANG Y, et al. Research on algorithm implementation of multi-scale quantum harmonic oscillator algorithm[J]. Journal of Chengdu University of Information Technology, 2015, 30(5)： 433-438.

[11] 陸志軍, 安俊秀, 王鵬. 基于劃分的多尺度量子諧振子算法多峰優(yōu)化[J]. 自動(dòng)化學(xué)報(bào), 2016, 42(2)： 235-245.LU Z J, AN J X, WANG P. Partition-based MQHOA for multimodal optimization[J]. Acta Automatica Sinica, 2016, 42(2)： 235-245.

[12] 袁亞男, 王鵬, 劉峰. 多尺度量子諧振子算法性能分析[J]. 計(jì)算機(jī)應(yīng)用, 2015, 35(6)： 1600-1604.YUN Y N, WANG P, LIU F. Performance analysis of multi-scale quantum harmonic oscillator algorithm[J]. Journal of Computer Applications, 2015, 35(6)： 1600-1604.

[13] 燕京京, 王鵬, 范家兵, 等. 基于量子諧振子模型的聚類中心選取算法[J]. 電子學(xué)報(bào), 2016, 44(2)： 405-412.YAN J J, WANG P, FAN J B, et al. Clustering center selecting algorithm based on quantum harmonic oscillator model[J]. Acta Electronica Sinica, 2016, 44(2)： 405-412.

[14] 王鵬, 黃焱, 安俊秀, 等. 多尺度量子諧振子算法在組合優(yōu)化問題中的性能分析[J]. 電子科技大學(xué)學(xué)報(bào), 2016, 45(3)： 469-474.WANG P, HUANG Y, AN J X, et al. MQHOA used in TSP problem[J].Journal of University of Electronic Science and Technology of China,2016, 45(3)： 469-474.

[15] 黃焱, 王鵬, 謝高輝. 基于 PE方法的數(shù)據(jù)中心需量費(fèi)用優(yōu)化算法[J].通信學(xué)報(bào), 2016, 37(3)： 90-97.HUANG Y, WANG P, XIE G H. Optimizing demand charge of data center base on PE method[J]. Journal on Communications, 2016, 37(3)：90-97.

[16] 王鵬, 黃焱, 李坤, 等. 云計(jì)算集群相空間負(fù)載均衡度優(yōu)先調(diào)度算法研究[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(5)： 1095-1107.WANG P, HUANG Y, LI K, et al. Load balancing degree first algorithm on phase space for cloud computing cluster[J]. Computer Research and Development, 2014, 51(5)： 1095-1107.

[17] CHEN D B, ZOU F, LI Z, et al. An improved teaching-learning-based optimization algorithm for solving global optimization problem[J].Information Sciences, 297(2015)： 171-190.

MQHOA algorithm with energy level stabilizing process

WANG Peng1, HUANG Yan2
(1. School of Computer Science and Technology, Southwest University for Nationalities, Chengdu 610225, China;2. School of Computer Science and Technology, Huaiyin Normal University, Huaian 223300, China)

An improved multi-scale quantum harmonic oscillator algorithm (MQHOA) with energy level stabilizing process was proposed analogizing to quantum harmonic oscillator’s wave function. Inspired by quantum model, the optimization problem was transformed to finding ground state wave function of bound state. Harmonic oscillator potential well was used to approach objective function under the condition of Taylor approximation. Energy level stabilization, energy level reduction, scale reduction were the basic iterative convergence processes of MQHOA, coinciding with its physical model. Only one subjective control parameter was needed in MQHOA whose wave function and zero-point energy were defined with reference to quantum model. Experimental results show that MQHOA’s performance is superior to several other common optimization algorithms. For high dimensional testing functions including Ackley、Griewank、Sphere、Sum Squares、Zakharov, etc, the global optimums can be obtained precisely with 100% probability.

optimization algorithm, function optimization, MQHOA, wave function, ground state

s: The National Natural Science Foundation of China (No.60702075), Sichuan Key Laboratory Open Foundation of Pattern Recognition and Intelligent Information Processing (No.MSSB-2015-9)

TP301.6

A

10.11959/j.issn.1000-436x.2016136

2016-04-11；

2016-06-15

國家自然科學(xué)基金資助項(xiàng)目（No.60702075）；模式識(shí)別與智能信息處理四川省高校重點(diǎn)實(shí)驗(yàn)室開放基金資助項(xiàng)目（No.MSSB-2015-9）

王鵬（1975-），男，四川樂山人，西南民族大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)橹悄芩惴ā⒋髷?shù)據(jù)、云計(jì)算、并行計(jì)算。

黃焱（1982-），男，江蘇泗陽人，博士，淮陰師范學(xué)院講師，主要研究方向?yàn)橹悄芩惴ā⒉⑿杏?jì)算。