具有能級穩定過程的MQHOA優化算法

王鵬，黃焱

（1. 西南民族大學計算機科學與技術學院，四川 成都 610225；2. 淮陰師范學院計算機科學與技術學院，江蘇 淮安 223300）

具有能級穩定過程的MQHOA優化算法

王鵬1，黃焱2

（1. 西南民族大學計算機科學與技術學院，四川 成都 610225；2. 淮陰師范學院計算機科學與技術學院，江蘇 淮安 223300）

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

優化算法；函數優化；多尺度量子諧振子算法；波函數；基態

1 引言

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

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

2 MQHOA算法的基本物理模型

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

圖1 經典電子軌道和量子電子云

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

定態薛定諤方程描述了粒子在勢阱V( x)約束下的運動情況。MQHOA算法將優化問題中的目標函數f( x)作為薛定諤方程中的勢阱 V( x) =f( x)，函數優化問題在這一對應條件下就轉變為了求粒子在勢阱 V( x) =f( x)約束下的基態波函數ψ0(x)問題，量子系統處于基態時粒子將以最大的概率出現在勢阱最低點附近，基態波函數的概率分布就是目標函數最優解的概率分布。但通常復雜的勢阱利用薛定諤方程是無法求出精確波函數的。在量子物理中經常會采用諧振子勢來近似描述粒子在平衡位置附近的復雜振動。同樣，復雜目標函數f( x)在全局最小值位置x0附近也可以采用泰勒序列進行展開

在f( x)的泰勒展開中f( x0)為常數，在最小值位置x0處目標函數的一階導數 f′(x0) = 0，同時去除高次項保留二次項，可以得到因此，在最小值位置x0附近，可以利用諧振子勢阱來近似表示復雜目標函數f( x)，在這一近似條件下求解目標函數f( x)最小值的問題就可以轉變為求解在諧振子勢阱約束下的基態波函數問題（諧振子約束態問題），此時薛定諤方程為

根據量子理論，諧振子勢阱約束下的波函數是可以準確獲得的，其不同能級波函數如圖2所示。

圖2 不同能級下的諧振子波函數

量子諧振子波函數從高能態到基態由多個正態分布的概率振動逐步聚集到一起，其基態波函數就是一個正態分布，因此，MQHOA算法的基本采樣概率函數為正態分布函數。本文引入了能級穩定過程，使MQHOA算法在高能級的亞穩態能進行充分的搜索，保證了解的多樣性，從而更準確地定位所有局部最優區域。

MQHOA算法的物理模型可以歸納為以下幾點。

1) 勢阱等效：將復雜目標函數等效于量子勢阱V( x) =f( x)，從而將優化問題轉化為求解約束態下量子基態波函數的問題。

2) 泰勒近似：在目標函數極值附近利用諧振子勢對目標函數進行近似。

3) 量子波函數：利用波函數來描述目標函數最優解當前的概率分布。

4) 量子能級：目標函數的局部最優對應于量子系統中的高能級亞穩態，全局最優對應于量子系統中的基態。

在這一物理模型下優化問題就被轉變為求解量子系統基態波函數的問題，利用量子退火方法實現系統由高能級亞穩態向基態的能級逐步躍遷。量子理論完整的數學體系為算法分析提供了數學工具。

3 MQHOA算法的基本迭代過程

根據算法的物理模型，本文提出了一種具有能級穩定過程的MQHOA算法流程，算法流程的偽代碼如下（二維目標函數）。

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)

偽代碼中目標函數的定義域為[min,max]，算法的初始尺度 σs=max?min ，算法需要主觀指定的參數只有采樣區域個數k，k值越大對應于算法初始能級越高，而σmin則是優化算法在每一個維度上的收斂精度，MQHOA算法可以以指定的位置精度自動實現算法的收斂，也可人為指定最大迭代次數。算法初始化時在目標函數定義域內的每一個維度分別隨機生成k個采樣位置xi，并計算出這k個采樣位置的標準差σk′。為描述方便，下面以二維函數為例說明算法包括3個迭代過程。

1) 能級穩定過程

這一迭代過程對所有的k個采樣位置xi分別按正態分布 N( xi,)生成一個新的采樣位置，總共生成k個新的采樣位置，如果新采樣位置對應目標函數的值較小 f()

2) 能級降低過程

當算法處于穩定能級狀態后，以k個采樣位置的平均值xmean=x替換x中最差解的位置 xworst，實

i

i現了系統能級的下降并進入下一個低能級上的能級穩定過程。相比利用最優解位置取代最差解位置的能級降低策略，本策略保證了解空間采樣的多樣性。MQHOA算法的能級下降過程要一直持續到當前k個采樣位置的標準差σk小于等于當前尺度σs（ σk≤σs），這時k個采樣位置xi收縮到了正態分布N( x,σ2)區域內，此時算法認為已達到尺度σ下

i ss

的能量基態，即最低能量狀態。

3) 尺度降低過程

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

MQHOA算法流程與物理模型的對應關系如表1所示，從表中可以看出MQHOA算法很好地符合了量子理論模型。

表1 MQHOA算法與物理模型的對應關系

4 MQHOA算法的波函數和能量

4.1 MQHOA算法的波函數定義

MQHOA算法在整個搜索過程中其采樣操作的核心機制就是當前k個采樣位置xi所對應的k個正態概率分布 N( xi,，定義算法當前波函數為k個正態概率分布 N( xi)的疊加

高斯函數可以作為小波分析函數，受小波二進分析的啟發，為實現更高分辨率的搜索，MQHOA算法將尺度σs逐步減半，尺度減小后算法在大尺度下的基態轉變為在小尺度下的高能態，算法以更高的精度對解空間進行搜索，算法在最后結束時的波函數為

4.2 MQHOA算法的能量和零點能

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

當算法滿足亞穩態判據時，此時的能量即為該亞穩態的能級。

依據能量Eσs的定義，MQHOA算法在尺度σs基態時的零點能可以近似由下式計算

其中，ψ0(x)為算法基態波函數，fmin為目標函數的理論最小值，f( xopt)是基態時當前的最優解。通常在當前尺度σs較大時零點能會較大。零點能的存在正是算法量子特性的一個重要表現，零點能也可作為算法收斂特性的指標。

5 實驗結果與討論

為確保本文實驗數據的可靠性，所有實驗數據均為重復 30次計算所得到的統計值，測試函數如表2所示。本文MQHOA算法的參數k=30，算法的優化位置精度 σmin= 0.000 001，優化成功率的判斷是以目標函數最終優化值與理論最優值差的絕對值小于等于0.001作為判斷標準，優化目標函數的維度用D來標識，優化目標均是尋找目標函數的全局最小值，本文所有標準測試函數的理論最優值均為0。

表2 7種測試函數的名稱與編號

5.1 MQHOA算法基本優化實驗結果

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

5.2 MQHOA算法與其他算法的對比實驗結果

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

5.3 MQHOA算法對高維函數的優化實驗結果

在函數優化問題中隨著目標函數維度的增加，搜索空間的大小是呈指數級增長的，因此，優化算法對高維目標函數特別是百維以上的超高維目標函數的優化性能是優化算法的一個重要評價指標。

表3 MQHOA算法對7種常見目標函數的優化結果

表4 MQHOA與其他算法對高維目標函數的優化效果對比

表5為MQHOA算法對5個200～500維的超高維目標函數優化的結果，搜索定義域在各個維度均為[-2.048, 2.048]，數據表明MQHOA算法在目標函數為200～500維時，仍以100%的成功率獲得了目標函數的全局最優解。總的來看，MQHOA算法具有出色的高維函數優化能力，這表明其有望應用于高復雜度的優化應用領域，是一個有很好應用前景的智能優化算法。

5.4 MQHOA算法的波函數

根據本文對算法波函數的定義，波函數是MQHOA算法量子特性的重要體現，它反映了當前目標函數全局最優解的概率分布，算法的收斂過程也是波函數在不同尺度向基態收斂的過程。

表5 MQHOA對超高維目標函數的優化實驗結果

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

圖3 Griewank 函數在不同尺度下的采樣中心及基態波函數圖像（D=2）

6 結束語

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

[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] 王鵬, 黃焱, 任超, 等. 多尺度量子諧振子高維函數全局優化算法[J].電子學報, 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] 王鵬, 黃焱. 多尺度量子諧振子優化算法物理模型[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] 劉峰, 王鵬, 黃焱, 等. 多尺度量子諧振子優化算法實現方法研究[J].成都信息工程學院學報, 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] 陸志軍, 安俊秀, 王鵬. 基于劃分的多尺度量子諧振子算法多峰優化[J]. 自動化學報, 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]. 計算機應用, 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]. 電子學報, 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] 王鵬, 黃焱, 安俊秀, 等. 多尺度量子諧振子算法在組合優化問題中的性能分析[J]. 電子科技大學學報, 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方法的數據中心需量費用優化算法[J].通信學報, 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]. 計算機研究與發展, 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

國家自然科學基金資助項目（No.60702075）；模式識別與智能信息處理四川省高校重點實驗室開放基金資助項目（No.MSSB-2015-9）

王鵬（1975-），男，四川樂山人，西南民族大學教授、博士生導師，主要研究方向為智能算法、大數據、云計算、并行計算。

黃焱（1982-），男，江蘇泗陽人，博士，淮陰師范學院講師，主要研究方向為智能算法、并行計算。