無能級穩定判據的多尺度量子諧振子算法

王德志 王鵬

摘 要：多尺度量子諧振子算法是一種基于量子理論構建的智能優化算法。能級穩定過程是該算法的核心迭代過程之一，能級穩定判據是判斷算法是否達到暫穩態的條件。通過對算法物理模型的分析，可知算法在初始采樣階段每一次迭代操作都是能級下降的過程，所以取消能級穩定判據，也可實現算法從高能態過渡到暫穩態直至基態的進化過程。無能級穩定判據的算法在6個標準測試函數上的結果顯示其在求解精度、成功率、迭代次數上均表現出了優異的性能，算法的波函數顯示無能級穩定判據的算法仍然可以完成從高能態到基態的收斂，且無能級穩定判據的算法在結構上更加簡潔，易用性更高，實現難度更低。無能級穩定判據的多尺度量子諧振子算法能夠以更加簡潔且有效的方式進行應用。

關鍵詞：多尺度量子諧振子算法;優化算法;能級穩定;量子模型;成功率;波函數

中圖分類號：TP301.6

文獻標志碼：A

Multi-scale quantum harmonic oscillator algorithm without energy level stability criterion

WANG Dezhi， WANG Peng*

School of Computer Science and Technology， Southwest Minzu University， Chengdu Sichuan 610041， China

Abstract：

Multi-scale quantum harmonic oscillator algorithm is an intelligent optimization algorithm based on quantum theory. The energy level stabilization process is one of the core iterative processes of the algorithm， and the energy level stability criterion is the condition for judging whether the algorithm reaches metastable state. Through the analysis of the physical model of the algorithm， it was considered that each iteration of the algorithm in the initial sampling stage is a process of energy level descent， so that the algorithm without energy level stability criterion was also able to realize the evolution from high energy state to metastable state until ground state. The results of the algorithm without energy level stability criterion on six standard test functions show the excellent performance of the algorithm in terms of solution accuracy， success rate and number of iterations. The wave function of the algorithm shows that the algorithm without energy level stability criterion can still converge from the high-energy state to the ground state， and is simpler in structure， easier to use and less difficult to implement. Multi-scale quantum oscillator algorithm without energy level stability criterion can be applied in a more concise and efficient way.

Key words：

multi-scale quantum harmonic oscillator algorithm; optimization algorithm; energy level stability; quantum model; success rate; wave function

0 引言

利用物理模型構建智能優化算法是一種非常有效的方法，例如模擬退火算法（Simulated Annealing Algorithm， SAA）是基于1953年提出的Metropolis選擇準則構造的[1]，核心思想是當算法陷入局部最優時，接受一個比當前解更差的解，以此跳出局部最優。量子粒子群優化（Quantum-behaved Particle Swarm Optimization， QPSO）算法利用δ勢阱下的量子波函數構造粒子進化公式，通過不斷減小特征長度逐步實現局域化的新解采樣，從而達到算法收斂的目的[2]。多尺度量子諧振子算法（Multi-Scale Quantum Harmonic Oscillator Algorithm， MQHOA）也是一種利用物理模型構建的智能優化算法，MQHOA利用量子波函數的概率解釋來模擬算法的采樣過程，從而完成算法的求解。文獻[3]給出了MQHOA的完整實現方法，并對算法進行了詳細的介紹。另外MQHOA在多峰優化問題上也表現出了較好的性能，并提出了一種用于多模優化的MQHOA的變種[4]。文獻[5]詳細闡述了MQHOA的物理模型和數學分析，通過與遺傳算法、模擬退火算法、粒子群算法和量子粒子群算法進行對比，結果表明，MQHOA在收斂速度和最優解精度方面具有競爭優勢和優越性。2016年，研究團隊提出了具有能級穩定過程的多尺度量子諧振子算法，算法的基本框架包括能級穩定過程、能級降低過程和尺度降低過程[6]。MQHOA的特別之處在于采樣的方式是利用高斯分布的中心位置進行采樣，這種采樣方式是非均勻采樣中的重要采樣方法，可以使重要區域的采樣密度相對較高，靠近最優解的采樣密度相對較高，從而提高采樣效率、減少采樣次數。同時，MQHOA在實際工程領域也得到了應用，在云計算任務調度[7]、相空間聚類[8]中都取得了

較好的效果。近期，算法又得到了進一步的改進，文獻[9]提出了一種具有嚴格亞穩態約束MQHOA并在多模態優化中得到應用，MQHOA利用群統計策略來評估群體的狀態并忽略個體狀態，引入了嚴格的亞穩態約束策略。增強了在局部區域找到更好質量解決方案的能力。文獻[10]提出了一種具有截斷平均穩定策略的MQHOA，并用于求解全局數值優化問題。理論和實驗分析表明，三重均值穩定策略能在一定程度上提高收斂效率。

從構建算法的物理模型來分析[11]，能級穩定判據并不是算法整體框架內的必須條件。能級穩定判據的存在并沒有對應的物理意義可以解釋，反而增加了算法采樣過程中不必要的動作。本文嘗試將MQHOA中的能級穩定判據去除，進一步簡化MQHOA的基本框架，提出了一種無能級穩定判據的MQHOA，文中將有能級穩定判據的算法成為多尺度量子諧振子算法A版本（Multi-scale Quantum Harmonic Oscillator Algorithm A， MQHOA-A），無能級穩定判據的算法成為多尺度量子諧振子算法B版本（Multi-scale Quantum Harmonic Oscillator Algorithm B， MQHOA-B）。

1 MQHOA物理模型

多尺度量子諧振子算法以量子理論中波函數的物理意義為基礎，模擬諧振子的運動過程，建立了算法的基本思想。在量子力學中粒子出現的機率可以用波函數（wave function）進行描述，但波函數既不能描述粒子的軌跡也不能描述粒子的形狀，對于任意粒子只能依據波函數給出其位置分布的概率。描述量子系統的方程稱為薛定諤方程，它可以寫成如下的形式：

-h2m2x2+V（x） ψ（x）=Eψ（x）（1）

MQHOA算法將優化問題中的目標函數f（x）看作薛定諤方程中的勢阱V（x），復雜目標函數f（x）在全局最小值位置x0附近可以采用泰勒序列進行展開：

V（x）=f（x）=f（x0）+f′（x0）（x-x0）+12f″（x0）（x-x0）2+…（2）

在f（x）的泰勒展開中f（x0）為常數，在最小值位置x0處目標函數f′（x0）=0，去除高次項，可以得到：

V（x）=f（x）f（x0）+（1/2） f″（x0）（x-x0）2（3）

函數優化問題在這一對應條件下就轉變為求粒子在勢阱約束條件下的基態波函數問題?；鶓B波函數代表了量子系統中粒子在能量的基態時的概率分布，而在函數優化中，采樣種群在目標函數可行解空間內不斷向最優解的方向收斂的過程可以看作是能量不斷向基態遷移的過程，因此，基態波函數的概率分布可以看作是目標函數最優解的概率分布。定義算法當前波函數ψ（x）2為k個正態概率分布N（xi，σ2s）的疊加。

ψ（x）2=∑ki=1N（xi，σ2s）=∑ki=112πσs e-（x-xi）22σ2s（4）

從概率上理解波函數ψ（x）2就是當前迭代過程中全局最優解的概率分布，MQHOA算法的全部迭代過程都是為了使波函數的概率分布向最優解的位置集中。能級穩定過程的基本操作是k個正態分布產生的新解不斷替換差解的過程。當算法在迭代過程中滿足一定約束條件時即認為算法在當前能級下進入暫穩態，這一約束條件就是能級穩定判據。

從物理模型來看，算法在向最優解收斂的過程本身就是能級不斷下降的過程。MQHOA中的能級穩定過程在算法的整體框架下顯得冗余。能級穩定的判據是人為設定的，在一定程度上與物理模型的實際過程不相符，算法在高能級時的穩定狀態對應于物理中的亞穩態，此時采樣位置的概率分布一般是位于目標函數的局部最優位置附近，只有算法處于能量較低的基態時，算法才能在當前尺度穩定。本文提出的MQHOA-B算法，在新的框架下，算法更為簡潔且更符合量子物理中能級變化的規律。無能級穩定過程及其判據也能實現算法從高能態到基態的收斂。

2 MQHOA基本流程

2.1 MQHOA-A算法流程

MQHOA-A為有能級穩定判據的版本。算法包括能級穩定過程、能級降低過程和尺度降低過程，分別對應于偽代碼中的三個while循環。算法迭代的基本操作包括高斯采樣和3個收斂判據，需要主觀設定的參數只有采樣種群個數k，避免了多個控制參數造成的參數設定的困難。能級穩定過程的引入，使MQHOA能在高能級的亞穩態能進行充分的搜索，保證了解的多樣性。雖然能級穩定判據的存在，可以增強粒子在尋優過程中搜索能力，但是能級穩定判據是人為設定的，在一定程度上使算法在搜索過程中具有主觀性，并對尋優結果有一定的影響。MQHOA-A的偽代碼如下所示。

有序號的程序——————————Shift+Alt+Y

程序前

1）

initialize k， σmin， MAX， MIN， σs=MAX-MIN

2）

randomly generate xi （i=1，2，…，k） in [MIN，MAX]

3）

calculate fi=f（xi），? fbest=fmin（xi）， xbest=xi

4）

calculate the standard deviation σk for all xi

5）

while （σs>σmin） do

6）

while （σk>σs） do

7）

while （Δσk>σs） do

8）

xi， generate xi′～N（xi，σs2）

9）

xi and xi′， if? f（xi′）

10）

calculate the standard deviation σk for all xi′

11）

Δσk=|σk-σk′|

12）

end

13）

update the worst solution： xworst=xmean

14）

end

15）

σs=σs/2

16）

end

17）

output xbest， f（xbest）

程序后

2.2 MQHOA-B算法流程

MQHOA-B為無能級穩定判據的版本。算法無需能級穩定判據即可實現第一階段的采樣過程，從代碼上看，直接帶來的改變就是減少一層循環。算法從三層循環變成兩層循環，新版本的算法在一個更加簡潔的框架下同樣能完成算法的基本搜索過程。算法在無能級穩定過程判據的情況下仍然實現了算法初始階段的采樣過程。無能級穩定判據的算法的整體流程更加符合量子體系中能量變化的特點，更加地貼合物理模型。去掉能級穩定判據，使算法在采樣過程中避免了主觀的人為干預，算法的求解過程更加客觀，提高了結果的可靠性。MQHOA-B的偽代碼如下所示。

有序號的程序——————————Shift+Alt+Y

程序前

1）

initialize k，σmin，MIN，MAX，σs=MAX-MIN

2）

randomly generate xi （i=1，2，…，k） in [MIN，MAX]

3）

calculate fi=f（xi）， fbest=fmin（xi），xbest=xi

4）

while （σs>σmin）? do

5）

while （σk>σs）? do

6）

xi，generate x′i～N（xi，σ2s）

7）

xi and x′i， if f（x′i）

8）

calculate the standard deviation σk for all x′i

9）

update the worst solution： xworst=xmean

10）

end

11）

σs=σs/2

12）

end

13）

output? xbest， f（xbest）

程序后

無能級穩定判據的算法具體迭代過程如下：

其中：k是可以人為設置的采樣種群個數，σmin表示每個維度上的收斂精度，目標函數的定義域為[MIN，MAX]，初始尺度σs=MAX-MIN，算法的結束條件為σs≤σmin。

步驟1 對于每個xi各自按正態分布N（xi，σ2s）生成k個采樣位置x′i。

步驟2 計算新位置的函數值，若f（x′i）

變化的絕對值，Δσk=σk-σ′k。對方差進行更新σ′k：

σ′k ← σk。

步驟3 用k個當前最優采樣位置的均值替換最差解的位置：xworst=xmean。

步驟4 計算當前最優解位置方差σk，如果（σk<σs），

能級降低過程結束，否則轉到步驟1。

步驟5 尺度下降過程，尺度減半σs=σs/2，使算法在更小尺度下重復能級的不斷從高到低的過程，直至滿足收斂條件。

3 實驗分析

3.1 實驗說明

選擇了6個常用的標準測試函數來檢測新框架下算法的性能，測試了所有函數在100維以內的情況，對于Griewank函數的測試達到了500維，函數的定義域取值均為[-10，10]。算法的初始采樣個數為k=30，算法的收斂精度均為σmin=1×10-6，當求解的目標函數最優值與理論最優值的差的絕對值小于等于1×10-6則認為在這一次的求解成功，成功次數所占51次的比例即為成功率，用GDpercent表示。優化目標函數的維度用DIM表示，在一個維度為d的空間內的粒子xi（i=1～k）可以寫為Xi=[xi1，xi2，…，xid]，表示該粒子在d個方向上都是有信息分量的。優化目標均是尋找目標函數的全局最小值，本文所選的測試函數理論最優值均為0。實驗主要關注算法的成功率、收斂情況以及波函數。所有仿真實驗均在Intel Xeon CPU E5-1630 v3 @3.7GHz，16GB內存的計算機上進行，程序采用Matlab 2016a實現。實驗選用了6個標準測試函數： f1（Ackley）、 f2（Levy）、 f3（Griewank）、 f4（Quadric）、 f5（Sum Square）、 f6（Zakharov）。

3.2 實驗結果與分析

3.2.1 實驗結果

在實驗的初始階段，對比了MQHOA-A和MQHOA-B的性能，并引入了QPSO算法作為參照。實驗設置了相同的迭代次數，三種算法均設置最大迭代次數為10000×DIM。QPSO的種群規模為30，收縮擴張系數α=1～0.5。主要關注三種算法求解的平均值、最優值和方差，且每種算法得到的結果均是通過重復51次實驗得到的統計結果。如表1所示，其中下劃線數字為相對較優的結果。實驗發現MQHOA-B算法的基本測試結果與MQHOA-A的測試結果相比均表現出良好的性能。兩個版本算法的結果在平均值、最優值和方差上無明顯差別。QPSO算法在函數f1的優化中表現出較好的收斂性，但是在其他函數的收斂精度表現較差，總體的收斂能力不如MQHOA-A和MQHOA-B。由于QPSO采用的是δ勢阱模型，QPSO的優勢在于收斂速度快，但是帶來的問題是容易導致算法早熟和停滯，特別是在高維函數優化中比較明顯。MQHOA-B在6個測試函數的30維和50維上的表現均與MQHOA-A保持在同一水平。兩個版本的算法均能以相對較高的精度找到函數的最優解。MQHOA-B在一個更加簡潔的框架下運行，依舊能保證較高的求解精度和具有競爭性的收斂能力。從實驗結果來看，能級穩定判據并不是MQHOA的必要條件，去掉能級穩定判據，對算法的基本性能并沒有大幅度的影響，但是無能級穩定判據的算法（MQHOA-B）在結構上更加清晰，更加符合物理模型，減少了人為干預帶來的不客觀因素。

3.2.2 成功率分析

如圖1（a）、圖1（b）、圖1（c）、圖1（d）、圖1（e）、圖1（f）所示，分別是MQHOA-A和MQHOA-B在函數f1、 f2、 f3、 f4、 f5、 f6上的成功率情況。從6個標準測試函數的結果來看，10維是一個臨界點，其中f1、 f2、 f3在10維以后成功率呈現下降趨勢。而在其他函數的優化過程中并沒有出現明顯的變化，均能以100%的成功率找到最優解。隨著函數維度的升高，兩個版本的算法的成功率逐漸下降，最后趨于零，總體趨勢基本一致。圖1（c）為算法在函數f3高維情況下的成功率變化情況，MQHOA-A與MQHOA-B在高維情況下均出現了較大的波動，但是MQHOA-B要相對穩定，總體的波動較小。圖1（d）、圖1（e）、圖1（f）則分別反映了函數f4、 f5、 f6成功率情況，成功率均為100%。從圖1中可以看出，MQHOA-B和MQHOA-A的成功率變化基本呈現相同的趨勢，但是在高維情況下，MQHOA-B的成功率較為穩定，波動較小。

3.2.3 收斂性分析

收斂性是評價算法的重要指標，本節對比了MQHOA-A和MQHOA-B在6個基本測試函數上的收斂情況。如圖2（a）和圖2（b）所示，分別是函數f1和f2在10維的時候收斂曲線，MQHOA-B算法均比MQHOA-A收斂得更快，且收斂精度均可達到1×10-5和1×10-10以上。

如圖3（a）和圖3（b）所示，分別是函數f5和f6在50維的時候的收斂曲線。MQHOA-B同樣能以較快的速度收斂，尤其在函數f5上，在迭代次數上比MQHOA-A大概少20萬次便收斂到最優解的位置。在函數f6上MQHOA-B與MQHOA-A基本保持在相同的收斂速度，但是在總的迭代次數依舊較少。

如圖4（a）和圖4（b）所示，分別是函數f3和f4在100維時的收斂曲線。MQHOA-B與MQHOA-A的收斂速度基本一致，但是總的收斂次數仍然較少。

綜上，MQHOA-B在收斂速度上基本與MQHOA-A持平，但是總的迭代次數較少。說明MQHOA-B能夠以較少的迭代次數收斂到最優解位置，尤其是在高維函數上，體現了MQHOA-B在高維函數優化上的競爭力。

3.2.4 波函數分析

MQHOA的波函數代表了算法在尋優過程中解的概率分布，反映了算法的能級變化過程。在采樣的初始階段，算法處于高能級狀態，隨著迭代的進行，算法逐漸向最優解的方向移動，能級逐漸下降，當算法到達最優解的位置時，能級處于基態。如圖5（a）、圖5（b）、圖5（c）、圖5（d）表示MQHOA-A在優化2維Griewank函數時，尺度收縮過程中的三維波函數變化情況;圖5（e）、圖5（f）、圖5（g）、圖5（h）為對應的三維波函數平面投影。如圖6（a）、圖6（b）、圖6（c）、圖6（d）表示MQHOA-B在優化2維Griewank函數時，尺度收縮過程中的三維波函數變化情況;圖6（e）、圖6（f）、圖6（g）、圖6（h）為對應的三維波函數平面投影。

算法的波函數表示了函數可行解區域中最優解的概率分布，根據式（4），當xi和σs已知時，即可得到算法在當前尺度下的波函數，即目標函數自變量x的概率分布。

如圖5所示，隨著尺度的下降，MQHOA-A算法從高能態迅速下降到基態，算法在σs=0.625的尺度下迅速收斂到最優解位置附近，由于能級穩定判據的約束，算法能夠較快地收斂至基態，從而獲取目標函數的最優解。如圖6所示，從圖6（a）到圖6（b）可以看出，MQHOA-B較MQHOA-A能級下降得較緩慢，在能級下降的初始階段，跳出局部最優解的能力較弱。但是，在能級下降后期，MQHOA-B與MQHOA-A同樣收斂到基態，獲取目標函數的最優解。兩個版本算法的波函數再一次印證了能級穩定判據的非必要性，雖然能級穩定判據能夠在一定程度上加強算法從高能態下降到基態的能力，但是在無能級穩定判據約束的情況下，算法依然能夠完成能級下降操作并收斂至目標函數的最優解位置。

4 結語

本文針對具有能級穩定判據的MQHOA提出了一種更加簡潔的算法框架，新算法無能級穩定判據也能表現出較好的性能。通過實驗分析，無能級穩定判據的算法在部分函數上的成功率和收斂情況均比有能級穩定判據的算法更加優異。無能級穩定判據的算法更加符合量子理論體系的物理模型，在算法的尋優過程中，可以認為每一次迭代都是算法向著能級較低的方向收斂，即向著目標函數最優解的方向移動。無能級穩定判據的算法結構更簡單，實現更容易，可以更好地應用于實際問題的求解。在實際解決實際工程問題或者復雜問題時候，推薦使用更加簡潔的MQHOA-B算法。

參考文獻

[1]LAARHOVEN P J M， AARTS E H L. Simulated Annealing： Theory and Applications [M]. Dordrecht： Kluwer Academic Publishers， 1987： 16-48.

[2]孫俊，方偉，吳小俊，等.量子行為粒子群優化：原理及其應用[M].北京：清華大學出版社，2011：19-30.（SUN J， FANG W， WU X J， et al. Quantum Behavior Particle Swarm Optimization： Principle and Its Application [M]. Beijing： Tsinghua University Press， 2011：19-30.）

[3]王鵬，黃焱，李波，等.多尺度量子諧振子優化算法[M].北京：人民郵電出版社，2016：23-30.（WANG P， HUANG Y， LI B， et al. Multi-scale Quantum Harmonic Oscillator Optimization Algorithm [M]. Beijing： Posts and Telecom Press， 2016：23-30.）

[4]WANG P， CHENG K， HUANG Y， et al. Multiscal quantum harmonic oscillator algorithm for multimodal optimization [J]. Computational Intelligence Neuroscience， 2018， 2018： Article No. 8430175.

[5]WANG P， YE X， LI B， et al. Multi-scale quantum harmonic oscillator algorithm for global numerical optimization [J]. Applied Soft Computing， 2018， 69： 655-670.

[6]王鵬，黃焱.具有能級穩定過程的MQHOA優化算法[J]. 通信學報，2016，37（7）：79-86.（WANG P， HUANG Y. MQHOA optimization algorithm with energy level stabilization process [J]. Journal on Communications， 2016， 37（7）： 79-86.）

[7]韓虎，王鵬，程琨，等.基于多尺度量子諧振子算法的云計算任務調度[J].計算機應用，2017，37（7）：1888-1892.（HAN H， WANG P， CHENG K， et al. Task scheduling algorithm for cloud computing based on multi-scale quantum harmonic oscillator algorithm [J]. Journal of Computer Applications， 2017， 37（7）： 1888-1892.）

[8]王梓懿，安俊秀，王鵬.基于多尺度量子諧振子算法的相空間概率聚類算法[J].計算機應用，2017，37（8）：2218-2222.（WANG Z Y， AN J X， WANG P. Phase space probabilistic clustering algorithm based on multi-scale quantum harmonic oscillator algorithm [J]. Journal of Computer Applications， 2017， 37（8）： 2218-2222.）

[9]LI B， WANG P， JIN J. Multiscale quantum harmonic oscillator algorithm with strict metastability constraints for multi-modal optimization [J]. IEEE Access， 2019， 7： 17377-17388.

[10]YE X， WANG P， XIN G， et al. Multi-scale quantum harmonic oscillator algorithm with truncated mean stabilization strategy for global numerical optimization problems [J]. IEEE Access， 2019， 7： 18926-18939.

[11]王鵬，黃焱.多尺度量子諧振子優化算法物理模型[J].計算機科學與探索，2015，9（10）：1271-1280.（WANG P， HUANG Y. Physical model of multiscale quantum harmonic oscillator optimization algorithm [J]. Journal of Frontiers of Computer Science and Technology， 2015， 9（10）： 1271-1280.）

This work is partially supported by the National Natural Science Foundation of China （60702075， 71673032）， the Fundamental Research Funds for the Central Universities ， Southwest Minzu University（2019NYB22）.

WANG Dezhi， born in 1992， M. S. candidate. His research interests incude parallel computing， quantum computing.

WANG Peng， born in 1975， Ph. D.， professor. His research interests include parallel computing， quantum computing.