量子啟發式優化算法的尺度動態調速機制

穆 磊，王 鵬

（1.西南民族大學計算機科學與工程學院，四川成都 610041；2.電子科技大學計算機科學與工程學院，四川成都 611731）

1 引言

優化問題是一種選擇特定方案以在特定條件下實現最佳目標的方法，被廣泛用于軍事、工程、管理等領域，是人工智能和其他技術領域的基石［1］.

多尺度量子啟發式諧振子優化算法（Multiscale Quantum-inspired Harmonic Oscillator Algorithm，MQHOA）是一種受量子物理過程啟發的優化算法［2］，源于量子退火（Quantum Annealing，QA）派生的量子優化理論［3］，其理論體系和應用領域都得到了廣泛的關注，在數據聚類［4］、任務分配［5］、功率自適應控制［6］等方面都有應用.

王鵬等人［2］定義了MQHOA 算法波函數，提出了算法基本物理模型.隨后，零點能量和量子隧穿效應的分析極大地發展了該算法框架［7］.文獻［8］證明了波函數定理和尺度減半策略的有效性，通過量子算符從理論上解釋了多尺度的必要性.隨后，一些工作補充了算法理論體系［9］.應用方面，基于MQHOA 的具有多級分辨率的多模優化分區算法顯示出良好的性能［10］.MQHOA還被用于選擇聚類中心，通過波函數的概率變化將高能級降到低能級來找到最佳的聚類和聚類中心［4］.韓虎等人［11］將云計算任務調度方案與MQHOA 的采樣位置建立關聯，在CloudSim 平臺上實施并獲得了優于比較算法的調度方案.

尺度因素是大多數智能優化算法的重要組成部分，用于調整算法在解空間的搜索粒度.現有大量MQHOA 的研究工作使用尺度減半策略，即尺度除以2作為下一個尺度值.該方法可以實現不同粒度的搜索，但缺乏靈活性，未考慮實際進化過程中不同的算法狀態具有不同的搜索粒度要求，無法實現自適應調整.另外，由于高斯分布的聚集效應，高斯采樣生成的候選解會聚集在采樣中心區域附近.如果當前采樣中心位于定義域的邊界，可能導致采樣點因聚集效應以大概率集中在邊界附近，使得算法陷入早熟收斂.這也是本文要解決的問題.

本文的主要貢獻如下：（1）將適應度進化利用率作為尺度動態調速的依據，通過尺度調節因子動態改變尺度調節速度，以達到探索與開發的平衡；（2）根據映射點、采樣中心點和生成點之間的位置關系，定義了2種不同的邊界映射策略，測試了不同尺度調節因子參數組合對性能的影響；（3）采用一種動態可接受誤差的評估機制，通過數據自身特征來計算可接受誤差，以此計算成功率，評估算法穩定性；（4）將改進算法與MQHOA 及對比算法在基準測試函數上進行了比較，實驗結果表明改進算法有效地提高了MQHOA的性能.

2 多尺度量子啟發式諧振子優化算法

MQHOA 的理論基礎的核心思想是優化空間中的搜索過程與量子空間中的粒子運動具有相似性［12］.根據QA 派生的量子優化理論［3］，當量子系統收斂到基態時可以得到目標函數的極值［13，14］.因此，優化問題可以理解為在有約束勢阱的量子系統中尋找基態.

2.1 量子運動與優化問題的映射

量子系統中，波函數隨時間和空間變化的方程被稱為薛定諤方程.其中，定態薛定諤方程描述了粒子在勢阱中受不含時Hamiltonian 約束的運動，它可以看作從量子力學的角度來描述優化問題的工具，形式如下［15］：

其中，? 表示簡化的普朗克常數，m表示粒子質量，狀態ψ(x)的能量特征值表示為E.波函數ψ(x)的二次方對應于粒子的概率分布，可以被認為與最優解的概率分布相關［12～14］.

理論上，可以通過求解薛定諤方程得到基態波函數，然后得到最優解的概率分布.與量子計算機相比，經典計算機實際處理的優化問題通常涉及非常大的Hilbert 空間，薛定諤方程的推演在這種條件下是不可行的.MQHOA 將復雜目標函數f(x)的全局優化問題轉換為求解不同尺度下諧振子勢的基態波函數問題，使整個理論系統具有可操作性，原理如圖1所示.

從圖1 可以看出，MQHOA 采用勢阱等效和諧振子勢能近似，使薛定諤方程可以近似求解.定態薛定諤方程變為

圖1 MQHOA基本原理框圖

其中，k是彈性系數.

2.2 MQHOA算法流程

MQHOA 的具體實現框架由3 部分組成，即能級穩定、能級下降和尺度調整，具體流程如圖2所示.

圖2 MQHOA算法流程圖

從圖2 可以看出，能級穩定是算法的基本進程，達到能級穩定條件后將轉入能級下降階段，依此類推，直到在該尺度下達到基態.尺度調整后，在新搜索粒度下重復該循環過程.通過這樣的機制，全局優化問題轉換為多尺度的基態收斂問題.

關于MQHOA 的詳細理論推導和實現細節可以參考文獻［14］.

3 尺度調整速度調節的改進方法

本節定義了尺度調節因子以及進化效率的評估指標，改進了邊界映射策略以提高算法性能，隨后，詳細闡述了MQHOA中尺度調整速度調節的改進算法.

3.1 術語

定義1fs定義為尺度調節因子，用作尺度調節的控制量.

定義2適應度進化利用率rfe定義為下式中適應度變化與進化次數變化的比率：

3.2 邊界反彈映射策略

進化算法中一般使用邊界映射策略處理候選解超出定義域的情況.MQHOA 中采用直接截斷策略.本方法將越界點根據其與臨近邊界點的位置關系，反彈回定義域特定區域.根據映射點、采樣中心點和越界點的位置，可以定義2種不同策略.

在定義之前給出以下符號定義：越界采樣點位置為xb，采樣中心位置為xc，邊界反彈映射策略生成的點位置是xg.定義域上界為ub，下界為lb.2 種邊界反彈映射策略定義如下.

定義3生成點和越界采樣點在采樣中心的同一側，稱之為正向反彈策略.在這種情況下，(xb-xc) ×(xg-xc) ≥0.設α是均勻分布在（0，1）上的隨機數，則可以根據以下公式生成新點：

定義4生成點和越界采樣點在采樣中心的不同側，稱之為負向反彈策略.在這種情況下，(xb-xc) ×(xg-xc) ＜0，可以根據以下公式生成新點：

圖3 是2 種反彈映射策略的示例.圖3 中，淺色點表示采樣中心點，藍色點是越界采樣點，超出了定義域的范圍.正向反彈策略將點映射到采樣中心的同側，如圖3（a）所示的綠色點.負向反彈策略將點映射到采樣中心的相反一側，表示為綠色點，如圖3（b）所示.

圖3 邊界映射策略

3.3 尺度調整的速度調節

進化算法的探索和開發存在均衡問題.如果使用固定尺度調節因子fs調整尺度，則可能會丟失某些尺度上的測量值，也有可能在某個尺度浪費過多資源.MQHOA 中尺度減半策略對應的尺度調節因子是2，該策略以此作為速度調整變化的基準.

本方法通過尺度調節因子來改變尺度調整的速度.當適應度值變小時，獲得適應度值并記錄對應的進化數，通過式（4）來計算適應度進化利用率.一旦適應度進化利用率發生變化，尺度調整速度將動態調節.

如果新適應度進化利用率小于原有適應度進化利用率rfe，則表明進化平均收益在下降.此時，尺度應迅速下降，以加強新尺度下的探索，尺度調整采用加速因子fa，其值應大于2.如果大于rfe，則表明進化平均收益在增加.此時，尺度應緩慢下降，以促進該尺度附近的開發，尺度調整采用減速因子fd，其值應小于2.

定義a為尺度調整因子的控制向量，尺度調整基向量為f，則尺度調整因子fs可以表示為a和f的內積：

3.4 算法實現框架

本文提出的方法在MQHOA 的框架基礎上進行改進，其偽代碼如算法1所示.

4 數值模擬討論

PSR 和NSR 分別表示具有正向和負向反彈策略的尺度動態調速方法，與以下優化算法進行綜合比較：MQHOA，精簡煙花算法（Bare Bone FireWorks Algorithm，BBFWA）［16］，量子行為粒子群優化算法（Quantum Particle Swarm Optimization，QPSO）［12］和標準粒子群優化算法2011（Standard Particle Swarm Optimization 2011，SPSO2011）［17］.

4.1 基準測試函數

基準測試函數用來驗證不同優化算法的總體性能，它們都被表述為最小化問題，并根據其重要物理特性和形狀相似性進行分組，如表1所示.

表1 基準測試函數

這些基準測試函數分為2 類.函數f1～f6是多模函數，它們都具有許多局部最小值，可以測試優化算法跳出局部最優值的能力.函數f7～f14是單模函數，它們只有一個全局最小值，具有不同的形狀，例如碗形、谷形等，主要測試算法對不同問題的快速收斂能力.

4.2 實驗參數設置

本文針對每個基準測試函數的30維問題進行了實驗，最大進化次數設為10 000×維度，每個實驗重復運行51次.所有比較算法的種群規模均設置為40以進行公平比較.每種算法中的參數設置均基于相關文獻.BBFWA 中的Ca和Cr分別設置為1.2 和0.9，在QPSO 中考慮了線性遞減的收縮膨脹，其中a1和a2分別設置為1和0.5.SPSO2011 的參數選自文獻［17］.在MQHOA 及其改進算法中，k表示探針或個體的數量，設置為40.所有數值模擬都在8 GB 內存的Intel i7 6700 CPU（3.4 GHz）和Windows 10 的計算機上通過64 位版本的MATLAB R2018a實現.

4.3 尺度調節因子參數分析

在比較算法之前，應先確定合適的尺度調節因子fs.本文使用不同取值下尺度調節因子來求解30維問題基準測試函數的實驗，統計分析參數組合對兩種邊界映射策略的影響.

為了便于計算，限制了參數組合的數量，采用網格搜索確認參數組合.其中，fa從2.1 變化至2.9，步長為0.2；fd從1.1 變化至1.9，步長為0.2.在這種情況下，2 種邊界映射策略改進的MQHOA算法總計有5×5種參數組合.針對每個基準測試函數進行51次運行，計算每種參數組合對應的誤差.所有實驗運行完成后，統計2種改進算法的不同參數組合中，每種參數組合下誤差不高于原始MQHOA的函數數量.隨后，固定尺度調節因子組合中的一個參數值，然后將另一參數所有對應結果求平均值.由于函數數量為整數，向下取整直接保留整數部分.

2種邊界映射策略的結果以不同的顏色區分，如圖4所示，其中虛線是趨勢線.

圖4 尺度調節因子統計結果

如圖4所示，根據尺度調節因子的定義以及基準參考值的選取不難看出，當尺度調節因子與2越接近的時候，加速或減速越慢；當尺度調節因子與2差距越大時，加速或減速越快.

對于負向反彈策略，當fa較大時，僅在較少數量的測試函數上實現性能提升.fd較小時也會發生相同的情況.數據表明，大幅度的加速和減速不利于負向反彈策略的性能提升.負向反彈策略位置調整相對較大，快速調整尺度會導致特定尺度下的搜索不足.

正向反彈策略顯示出相反的趨勢.當fa較大時，在大量測試函數上實現性能提升.fd的值與實現性能改進的函數數量負相關.結果表明，在正向反彈策略中，尺度調整應相對較快地加速和減速.該映射策略將點映射到越界點附近的定義域內，如果速度調節相對較慢，則會在特定尺度上消耗資源，從而影響多樣性和進化利用率，使性能受到影響.

4.4 與其他方案的比較和討論

將2 種改進算法與一些常見優化方案在基準測試函數的30 維問題中進行比較，評估不同優化算法的誤差和成功率.在NSR 中fa和fd設置為2.1 和1.7，在PSR中fa和fd設置為2.3 和1.1.這些參數值參考第4.3 節中的實驗結果進行設置.

4.4.1 誤差分析

不同優化算法的誤差結果顯示在表2 中.每個單元格中的數據均由3部分組成：平均值、標準差（第一個括號中）以及該誤差在所有算法中的排名順序（最后一個括號中的數字）.

表2 基準測試函數上的誤差結果

為了更清楚地觀察整體性能，將每個算法誤差均值的排名按照單模函數、多模函數和所有函數分類進行平均.

圖5 顯示了所有平均誤差的平均排名（Average Ranking，AR）.根據中央極限定理，AR～N((k+1)/2，(k2-1)/12n)，其中k是對比算法數量，n是測試函數數量［18］.單模函數，多模函數以及所有函數上AR 的先驗標準差（Prior Standard Deviation，PSD）為0.6，0.69和0.46.

如圖5所示，BBFWA 在單模函數上排名第一，其次是NSR 和SPSO2011.NSR 在多模函數中排名第一，緊隨其后的是QPSO 和SPSO2011.在所有函數上，NSR 排名第一，BBFWA 排名第二，之后是SPSO2011.雖然BBFWA 在f7，f8，f9，f12，f14等函數中排名優勢顯著，但在某些函數上排名太低.NSR 由于在不同函數上的均衡排名而勝出.

圖5 基準測試函數上的誤差均值平均排名

圖6 顯示了部分基準函數上不同算法平均誤差的統計信息.其中MQHOA 和BBFWA 分別用M 和BBF表示.

圖6 部分基準測試函數誤差均值箱形圖

根據箱形圖的分析結果，NSR 在除f2之外的所有基準測試函數上均具有良好的穩定性.NSR 在f1，f3，f4，f7，f9，f10，f12，f13上表現出穩定性和良好性能之間的平衡.在f5和f11上，NSR在性能和穩定性方面的表現并不是最好的，但也排在前列.

4.4.2 成功率分析

成功率rs可用于衡量算法的可靠性，它被定義為達到可接受誤差范圍內的運行次數占運行總次數的比例，可以按下式計算：

其中，naccept和ntotal分別表示達到可接受誤差范圍內的運行次數和運行總次數.對于每個函數，計算所有算法誤差均值的平均數，將其作為可接受誤差eaccept：

其中，nalg表示對比算法總數表示第i個算法的誤差均值.

成功率結果顯示在表3中，括號中的數字表示其在測試函數上的排名.

表3 基準測試函數成功率

如表3 所示，SPSO2011 在所有算法中的10 個函數上表現最佳.NSR 再次顯示出其均衡性，它在7 個函數上表現最佳，在3 個函數上均獲得第二名，在11 個函數上獲得高于0.8 的成功率，這是所有算法中的最佳結果.SPSO2011在10個函數上的成功率都是1，但在其他函數上的成功率小于0.6.BBFWA 在8 個函數上的成功率均大于0.8.總體而言，NSR 在更多函數上獲得了更高的成功率.

各個算法按照不同的基準測試函數進行成功率排名，并分別按照單模函數、多模函數以及所有函數的類別分別計算成功率的平均排名，結果顯示在圖7中.

圖7 基準測試函數上成功率平均排名

該圖顯示了NSR 和SPSO2011 在單模函數、多模函數和所有函數上成功率的平均排名均優于其他方案.NSR在不同的測試函數上表現出更好的均衡性.BBFWA由于在多模函數上性能不佳而在所有函數上獲得第三名.

4.4.3 計算復雜度

算法1中生成候選解的時間復雜度為O(nprobendim)，其中，nprobe和ndim分別表示探針數量和問題維度.當探針數量固定時，此時間復雜度隨問題的維度線性增加，即時間復雜度為O(ndim).此外，尺度調整速度調節的時間復雜度不會隨問題的維度而變化，即時間復雜度為O(1).通過分析整個算法，可以看到其他部分的時間復雜度最多為O(ndim).從以上分析可以得出，在不考慮目標函數影響的情況下，本文提出的算法總體上具有線性時間復雜度.

將每個算法在相同的基準測試函數上執行51 次，然后計算該基準測試函數上算法的平均執行時間，結果顯示在表4中，括號中的數字表示其在基準測試函數上的排名.

表4 基準測試函數平均執行時間（單位：s）

從表4 中可以看出，BBFWA 的平均執行時間在各種基準測試函數中顯示出絕對的優勢.NSR 在大多數基準測試函數中排名第二，在3個基準測試函數中排名第三.因此，NSR的排名仍然不錯.PSR在平均執行時間上也表現良好，它在14個函數的8個函數中排名前三.

各個算法的平均執行時間排名按照單模函數、多模函數和所有函數上的分類計算平均值，結果如圖8所示.

圖8 基準測試函數執行時間均值平均排名

從圖8 可以看出，BBFWA 在所有函數中均排名第一，其次是NSR 和PSR.MQHOA 和QPSO 的平均執行時間平均排名接近，而SPSO2011 排名最后.對于每種算法，不同類型函數之間的排名得分差異很小.在不同類型函數中，所有算法的排名順序都沒有改變.

4.4.4 討論

這些對比算法具有不同的特性.SPSO2011 對原始粒子群優化有兩大改進，即自適應隨機拓撲和旋轉不變性.這些措施帶來了良好的全局搜索能力，并阻止了早熟現象的產生.BBFWA 的結構非常簡單.它使用動態爆炸半徑進行搜索，并采用貪婪策略來更新候選解.QPSO通過壓縮-擴展系數來調整算法的收斂過程，從而可以在全局搜索和局部搜索之間取得平衡.其候選解的采樣函數是對應于δ勢阱的雙指數分布.該采樣分布的累積效應強于高斯分布，因此局部搜索能力強于MQHOA.MQHOA 利用高斯分布的波函數生成候選解，并通過調整尺度以不同的分辨率搜索解空間.本文所提出的算法主要在邊界映射策略和尺度調整速度調節方面改進了MQHOA.

邊界映射策略可以使算法具有更大的概率在定義域內有效搜索.負向反彈策略將越界點反彈到采樣中心的另一側并遠離采樣中心，具有更強的量子隧穿作用，并探索了更廣闊的區域，獲得了更好的多樣性.通過分析rfe的變化，動態選擇fa和fd以調節尺度調整的速度.負向反彈策略將點出界映射到遠離采樣點的區域，在該區域采樣的可能性很小.應該緩慢減小尺度，以微調搜索分辨率進行開發.較小的fa和較大的fd可以獲得更好的結果.正向反彈策略將外部越界點映射到采樣點附近，該區域被采樣的可能性更高.如果速度調節相對較慢，則可能會消耗過多的搜索資源，從而影響rfe和候選解的多樣性，導致性能下降.因此，應迅速進行尺度調整，這可以通過較大的fa和較小的fd來實現.第4.3節中的實驗結果驗證了上述分析.

為了更直觀地觀察各算法排名對比情況，把不同算法在各個評估指標上的整體排名進行綜合統計分析，如表5所示.

表5 不同算法的平均綜合排名

可以看出，在所有算法中，NSR 在平均誤差方面排名最高，NSR 和SPSO2011 在成功率方面排名最高.BBFWA 在平均執行時間方面有很大的優勢，其次是NSR.在多個維度的綜合評價中，NSR 獲得了最高的平均綜合排名.從性能，效率和穩定性的總體平衡來看，排名結果顯示了NSR的優勢.總體而言，NSR與對比算法相比具有較強的競爭力.

5 結論

本研究的重點是改善尺度資源的利用效率和解的多樣性，以提高算法性能.具體而言，采用適應度進化利用率表征特定尺度下的資源利用效率，用作動態調節尺度調整速度的標準.提出了2種不同的邊界映射策略來提高多樣性.通過使用不同參數組合的實驗，統計分析尺度調節因子對算法的影響，實驗結果表明2種改進算法通過適當的速度調節可以提升MQHOA的性能.

為了評估所提出方法的整體性能，與MQHOA 以及其他流行算法在基準測試函數上針對30維問題進行了實驗比較.計算平均誤差、成功率和平均執行時間并分別進行排名.實驗結果表明，尺度動態速度調節可以通過平衡探索和開發來提高MQHOA的性能，邊界映射策略對性能改進有積極作用，負向反彈策略會帶來更大的競爭力.

本文提出的算法仍然存在一些局限性.首先，改進算法的平均執行時間仍有提升空間.此外，增加了算法中的參數數量，參數的各種組合會帶來不同的效果，因此有必要分析參數組合以獲得更好的性能.另外，尺度反映了優化算法搜索粒度，多種尺度調整策略和規則值得進一步研究.這些問題都是未來的研究重點.