量子啟發(fā)式優(yōu)化算法的尺度動(dòng)態(tài)調(diào)速機(jī)制

穆 磊，王 鵬

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

1 引言

優(yōu)化問(wèn)題是一種選擇特定方案以在特定條件下實(shí)現(xiàn)最佳目標(biāo)的方法，被廣泛用于軍事、工程、管理等領(lǐng)域，是人工智能和其他技術(shù)領(lǐng)域的基石［1］.

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

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

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

本文的主要貢獻(xiàn)如下：（1）將適應(yīng)度進(jìn)化利用率作為尺度動(dòng)態(tài)調(diào)速的依據(jù)，通過(guò)尺度調(diào)節(jié)因子動(dòng)態(tài)改變尺度調(diào)節(jié)速度，以達(dá)到探索與開(kāi)發(fā)的平衡；（2）根據(jù)映射點(diǎn)、采樣中心點(diǎn)和生成點(diǎn)之間的位置關(guān)系，定義了2種不同的邊界映射策略，測(cè)試了不同尺度調(diào)節(jié)因子參數(shù)組合對(duì)性能的影響；（3）采用一種動(dòng)態(tài)可接受誤差的評(píng)估機(jī)制，通過(guò)數(shù)據(jù)自身特征來(lái)計(jì)算可接受誤差，以此計(jì)算成功率，評(píng)估算法穩(wěn)定性；（4）將改進(jìn)算法與MQHOA 及對(duì)比算法在基準(zhǔn)測(cè)試函數(shù)上進(jìn)行了比較，實(shí)驗(yàn)結(jié)果表明改進(jìn)算法有效地提高了MQHOA的性能.

2 多尺度量子啟發(fā)式諧振子優(yōu)化算法

MQHOA 的理論基礎(chǔ)的核心思想是優(yōu)化空間中的搜索過(guò)程與量子空間中的粒子運(yùn)動(dòng)具有相似性［12］.根據(jù)QA 派生的量子優(yōu)化理論［3］，當(dāng)量子系統(tǒng)收斂到基態(tài)時(shí)可以得到目標(biāo)函數(shù)的極值［13，14］.因此，優(yōu)化問(wèn)題可以理解為在有約束勢(shì)阱的量子系統(tǒng)中尋找基態(tài).

2.1 量子運(yùn)動(dòng)與優(yōu)化問(wèn)題的映射

量子系統(tǒng)中，波函數(shù)隨時(shí)間和空間變化的方程被稱(chēng)為薛定諤方程.其中，定態(tài)薛定諤方程描述了粒子在勢(shì)阱中受不含時(shí)Hamiltonian 約束的運(yùn)動(dòng)，它可以看作從量子力學(xué)的角度來(lái)描述優(yōu)化問(wèn)題的工具，形式如下［15］：

其中，? 表示簡(jiǎn)化的普朗克常數(shù)，m表示粒子質(zhì)量，狀態(tài)ψ(x)的能量特征值表示為E.波函數(shù)ψ(x)的二次方對(duì)應(yīng)于粒子的概率分布，可以被認(rèn)為與最優(yōu)解的概率分布相關(guān)［12～14］.

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

從圖1 可以看出，MQHOA 采用勢(shì)阱等效和諧振子勢(shì)能近似，使薛定諤方程可以近似求解.定態(tài)薛定諤方程變?yōu)?/p>

圖1 MQHOA基本原理框圖

其中，k是彈性系數(shù).

2.2 MQHOA算法流程

MQHOA 的具體實(shí)現(xiàn)框架由3 部分組成，即能級(jí)穩(wěn)定、能級(jí)下降和尺度調(diào)整，具體流程如圖2所示.

圖2 MQHOA算法流程圖

從圖2 可以看出，能級(jí)穩(wěn)定是算法的基本進(jìn)程，達(dá)到能級(jí)穩(wěn)定條件后將轉(zhuǎn)入能級(jí)下降階段，依此類(lèi)推，直到在該尺度下達(dá)到基態(tài).尺度調(diào)整后，在新搜索粒度下重復(fù)該循環(huán)過(guò)程.通過(guò)這樣的機(jī)制，全局優(yōu)化問(wèn)題轉(zhuǎn)換為多尺度的基態(tài)收斂問(wèn)題.

關(guān)于MQHOA 的詳細(xì)理論推導(dǎo)和實(shí)現(xiàn)細(xì)節(jié)可以參考文獻(xiàn)［14］.

3 尺度調(diào)整速度調(diào)節(jié)的改進(jìn)方法

本節(jié)定義了尺度調(diào)節(jié)因子以及進(jìn)化效率的評(píng)估指標(biāo)，改進(jìn)了邊界映射策略以提高算法性能，隨后，詳細(xì)闡述了MQHOA中尺度調(diào)整速度調(diào)節(jié)的改進(jìn)算法.

3.1 術(shù)語(yǔ)

定義1fs定義為尺度調(diào)節(jié)因子，用作尺度調(diào)節(jié)的控制量.

定義2適應(yīng)度進(jìn)化利用率rfe定義為下式中適應(yīng)度變化與進(jìn)化次數(shù)變化的比率：

3.2 邊界反彈映射策略

進(jìn)化算法中一般使用邊界映射策略處理候選解超出定義域的情況.MQHOA 中采用直接截?cái)嗖呗?本方法將越界點(diǎn)根據(jù)其與臨近邊界點(diǎn)的位置關(guān)系，反彈回定義域特定區(qū)域.根據(jù)映射點(diǎn)、采樣中心點(diǎn)和越界點(diǎn)的位置，可以定義2種不同策略.

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

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

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

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

圖3 邊界映射策略

3.3 尺度調(diào)整的速度調(diào)節(jié)

進(jìn)化算法的探索和開(kāi)發(fā)存在均衡問(wèn)題.如果使用固定尺度調(diào)節(jié)因子fs調(diào)整尺度，則可能會(huì)丟失某些尺度上的測(cè)量值，也有可能在某個(gè)尺度浪費(fèi)過(guò)多資源.MQHOA 中尺度減半策略對(duì)應(yīng)的尺度調(diào)節(jié)因子是2，該策略以此作為速度調(diào)整變化的基準(zhǔn).

本方法通過(guò)尺度調(diào)節(jié)因子來(lái)改變尺度調(diào)整的速度.當(dāng)適應(yīng)度值變小時(shí)，獲得適應(yīng)度值并記錄對(duì)應(yīng)的進(jìn)化數(shù)，通過(guò)式（4）來(lái)計(jì)算適應(yīng)度進(jìn)化利用率.一旦適應(yīng)度進(jìn)化利用率發(fā)生變化，尺度調(diào)整速度將動(dòng)態(tài)調(diào)節(jié).

如果新適應(yīng)度進(jìn)化利用率小于原有適應(yīng)度進(jìn)化利用率rfe，則表明進(jìn)化平均收益在下降.此時(shí)，尺度應(yīng)迅速下降，以加強(qiáng)新尺度下的探索，尺度調(diào)整采用加速因子fa，其值應(yīng)大于2.如果大于rfe，則表明進(jìn)化平均收益在增加.此時(shí)，尺度應(yīng)緩慢下降，以促進(jìn)該尺度附近的開(kāi)發(fā)，尺度調(diào)整采用減速因子fd，其值應(yīng)小于2.

定義a為尺度調(diào)整因子的控制向量，尺度調(diào)整基向量為f，則尺度調(diào)整因子fs可以表示為a和f的內(nèi)積：

3.4 算法實(shí)現(xiàn)框架

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

4 數(shù)值模擬討論

PSR 和NSR 分別表示具有正向和負(fù)向反彈策略的尺度動(dòng)態(tài)調(diào)速方法，與以下優(yōu)化算法進(jìn)行綜合比較：MQHOA，精簡(jiǎn)煙花算法（Bare Bone FireWorks Algorithm，BBFWA）［16］，量子行為粒子群優(yōu)化算法（Quantum Particle Swarm Optimization，QPSO）［12］和標(biāo)準(zhǔn)粒子群優(yōu)化算法2011（Standard Particle Swarm Optimization 2011，SPSO2011）［17］.

4.1 基準(zhǔn)測(cè)試函數(shù)

基準(zhǔn)測(cè)試函數(shù)用來(lái)驗(yàn)證不同優(yōu)化算法的總體性能，它們都被表述為最小化問(wèn)題，并根據(jù)其重要物理特性和形狀相似性進(jìn)行分組，如表1所示.

表1 基準(zhǔn)測(cè)試函數(shù)

這些基準(zhǔn)測(cè)試函數(shù)分為2 類(lèi).函數(shù)f1～f6是多模函數(shù)，它們都具有許多局部最小值，可以測(cè)試優(yōu)化算法跳出局部最優(yōu)值的能力.函數(shù)f7～f14是單模函數(shù)，它們只有一個(gè)全局最小值，具有不同的形狀，例如碗形、谷形等，主要測(cè)試算法對(duì)不同問(wèn)題的快速收斂能力.

4.2 實(shí)驗(yàn)參數(shù)設(shè)置

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

4.3 尺度調(diào)節(jié)因子參數(shù)分析

在比較算法之前，應(yīng)先確定合適的尺度調(diào)節(jié)因子fs.本文使用不同取值下尺度調(diào)節(jié)因子來(lái)求解30維問(wèn)題基準(zhǔn)測(cè)試函數(shù)的實(shí)驗(yàn)，統(tǒng)計(jì)分析參數(shù)組合對(duì)兩種邊界映射策略的影響.

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

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

圖4 尺度調(diào)節(jié)因子統(tǒng)計(jì)結(jié)果

如圖4所示，根據(jù)尺度調(diào)節(jié)因子的定義以及基準(zhǔn)參考值的選取不難看出，當(dāng)尺度調(diào)節(jié)因子與2越接近的時(shí)候，加速或減速越慢；當(dāng)尺度調(diào)節(jié)因子與2差距越大時(shí)，加速或減速越快.

對(duì)于負(fù)向反彈策略，當(dāng)fa較大時(shí)，僅在較少數(shù)量的測(cè)試函數(shù)上實(shí)現(xiàn)性能提升.fd較小時(shí)也會(huì)發(fā)生相同的情況.數(shù)據(jù)表明，大幅度的加速和減速不利于負(fù)向反彈策略的性能提升.負(fù)向反彈策略位置調(diào)整相對(duì)較大，快速調(diào)整尺度會(huì)導(dǎo)致特定尺度下的搜索不足.

正向反彈策略顯示出相反的趨勢(shì).當(dāng)fa較大時(shí)，在大量測(cè)試函數(shù)上實(shí)現(xiàn)性能提升.fd的值與實(shí)現(xiàn)性能改進(jìn)的函數(shù)數(shù)量負(fù)相關(guān).結(jié)果表明，在正向反彈策略中，尺度調(diào)整應(yīng)相對(duì)較快地加速和減速.該映射策略將點(diǎn)映射到越界點(diǎn)附近的定義域內(nèi)，如果速度調(diào)節(jié)相對(duì)較慢，則會(huì)在特定尺度上消耗資源，從而影響多樣性和進(jìn)化利用率，使性能受到影響.

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

將2 種改進(jìn)算法與一些常見(jiàn)優(yōu)化方案在基準(zhǔn)測(cè)試函數(shù)的30 維問(wèn)題中進(jìn)行比較，評(píng)估不同優(yōu)化算法的誤差和成功率.在NSR 中fa和fd設(shè)置為2.1 和1.7，在PSR中fa和fd設(shè)置為2.3 和1.1.這些參數(shù)值參考第4.3 節(jié)中的實(shí)驗(yàn)結(jié)果進(jìn)行設(shè)置.

4.4.1 誤差分析

不同優(yōu)化算法的誤差結(jié)果顯示在表2 中.每個(gè)單元格中的數(shù)據(jù)均由3部分組成：平均值、標(biāo)準(zhǔn)差（第一個(gè)括號(hào)中）以及該誤差在所有算法中的排名順序（最后一個(gè)括號(hào)中的數(shù)字）.

表2 基準(zhǔn)測(cè)試函數(shù)上的誤差結(jié)果

為了更清楚地觀察整體性能，將每個(gè)算法誤差均值的排名按照單模函數(shù)、多模函數(shù)和所有函數(shù)分類(lèi)進(jìn)行平均.

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

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

圖5 基準(zhǔn)測(cè)試函數(shù)上的誤差均值平均排名

圖6 顯示了部分基準(zhǔn)函數(shù)上不同算法平均誤差的統(tǒng)計(jì)信息.其中MQHOA 和BBFWA 分別用M 和BBF表示.

圖6 部分基準(zhǔn)測(cè)試函數(shù)誤差均值箱形圖

根據(jù)箱形圖的分析結(jié)果，NSR 在除f2之外的所有基準(zhǔn)測(cè)試函數(shù)上均具有良好的穩(wěn)定性.NSR 在f1，f3，f4，f7，f9，f10，f12，f13上表現(xiàn)出穩(wěn)定性和良好性能之間的平衡.在f5和f11上，NSR在性能和穩(wěn)定性方面的表現(xiàn)并不是最好的，但也排在前列.

4.4.2 成功率分析

成功率rs可用于衡量算法的可靠性，它被定義為達(dá)到可接受誤差范圍內(nèi)的運(yùn)行次數(shù)占運(yùn)行總次數(shù)的比例，可以按下式計(jì)算：

其中，naccept和ntotal分別表示達(dá)到可接受誤差范圍內(nèi)的運(yùn)行次數(shù)和運(yùn)行總次數(shù).對(duì)于每個(gè)函數(shù)，計(jì)算所有算法誤差均值的平均數(shù)，將其作為可接受誤差eaccept：

其中，nalg表示對(duì)比算法總數(shù)表示第i個(gè)算法的誤差均值.

成功率結(jié)果顯示在表3中，括號(hào)中的數(shù)字表示其在測(cè)試函數(shù)上的排名.

表3 基準(zhǔn)測(cè)試函數(shù)成功率

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

各個(gè)算法按照不同的基準(zhǔn)測(cè)試函數(shù)進(jìn)行成功率排名，并分別按照單模函數(shù)、多模函數(shù)以及所有函數(shù)的類(lèi)別分別計(jì)算成功率的平均排名，結(jié)果顯示在圖7中.

圖7 基準(zhǔn)測(cè)試函數(shù)上成功率平均排名

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

4.4.3 計(jì)算復(fù)雜度

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

將每個(gè)算法在相同的基準(zhǔn)測(cè)試函數(shù)上執(zhí)行51 次，然后計(jì)算該基準(zhǔn)測(cè)試函數(shù)上算法的平均執(zhí)行時(shí)間，結(jié)果顯示在表4中，括號(hào)中的數(shù)字表示其在基準(zhǔn)測(cè)試函數(shù)上的排名.

表4 基準(zhǔn)測(cè)試函數(shù)平均執(zhí)行時(shí)間（單位：s）

從表4 中可以看出，BBFWA 的平均執(zhí)行時(shí)間在各種基準(zhǔn)測(cè)試函數(shù)中顯示出絕對(duì)的優(yōu)勢(shì).NSR 在大多數(shù)基準(zhǔn)測(cè)試函數(shù)中排名第二，在3個(gè)基準(zhǔn)測(cè)試函數(shù)中排名第三.因此，NSR的排名仍然不錯(cuò).PSR在平均執(zhí)行時(shí)間上也表現(xiàn)良好，它在14個(gè)函數(shù)的8個(gè)函數(shù)中排名前三.

各個(gè)算法的平均執(zhí)行時(shí)間排名按照單模函數(shù)、多模函數(shù)和所有函數(shù)上的分類(lèi)計(jì)算平均值，結(jié)果如圖8所示.

圖8 基準(zhǔn)測(cè)試函數(shù)執(zhí)行時(shí)間均值平均排名

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

4.4.4 討論

這些對(duì)比算法具有不同的特性.SPSO2011 對(duì)原始粒子群優(yōu)化有兩大改進(jìn)，即自適應(yīng)隨機(jī)拓?fù)浜托D(zhuǎn)不變性.這些措施帶來(lái)了良好的全局搜索能力，并阻止了早熟現(xiàn)象的產(chǎn)生.BBFWA 的結(jié)構(gòu)非常簡(jiǎn)單.它使用動(dòng)態(tài)爆炸半徑進(jìn)行搜索，并采用貪婪策略來(lái)更新候選解.QPSO通過(guò)壓縮-擴(kuò)展系數(shù)來(lái)調(diào)整算法的收斂過(guò)程，從而可以在全局搜索和局部搜索之間取得平衡.其候選解的采樣函數(shù)是對(duì)應(yīng)于δ勢(shì)阱的雙指數(shù)分布.該采樣分布的累積效應(yīng)強(qiáng)于高斯分布，因此局部搜索能力強(qiáng)于MQHOA.MQHOA 利用高斯分布的波函數(shù)生成候選解，并通過(guò)調(diào)整尺度以不同的分辨率搜索解空間.本文所提出的算法主要在邊界映射策略和尺度調(diào)整速度調(diào)節(jié)方面改進(jìn)了MQHOA.

邊界映射策略可以使算法具有更大的概率在定義域內(nèi)有效搜索.負(fù)向反彈策略將越界點(diǎn)反彈到采樣中心的另一側(cè)并遠(yuǎn)離采樣中心，具有更強(qiáng)的量子隧穿作用，并探索了更廣闊的區(qū)域，獲得了更好的多樣性.通過(guò)分析rfe的變化，動(dòng)態(tài)選擇fa和fd以調(diào)節(jié)尺度調(diào)整的速度.負(fù)向反彈策略將點(diǎn)出界映射到遠(yuǎn)離采樣點(diǎn)的區(qū)域，在該區(qū)域采樣的可能性很小.應(yīng)該緩慢減小尺度，以微調(diào)搜索分辨率進(jìn)行開(kāi)發(fā).較小的fa和較大的fd可以獲得更好的結(jié)果.正向反彈策略將外部越界點(diǎn)映射到采樣點(diǎn)附近，該區(qū)域被采樣的可能性更高.如果速度調(diào)節(jié)相對(duì)較慢，則可能會(huì)消耗過(guò)多的搜索資源，從而影響rfe和候選解的多樣性，導(dǎo)致性能下降.因此，應(yīng)迅速進(jìn)行尺度調(diào)整，這可以通過(guò)較大的fa和較小的fd來(lái)實(shí)現(xiàn).第4.3節(jié)中的實(shí)驗(yàn)結(jié)果驗(yàn)證了上述分析.

為了更直觀地觀察各算法排名對(duì)比情況，把不同算法在各個(gè)評(píng)估指標(biāo)上的整體排名進(jìn)行綜合統(tǒng)計(jì)分析，如表5所示.

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

可以看出，在所有算法中，NSR 在平均誤差方面排名最高，NSR 和SPSO2011 在成功率方面排名最高.BBFWA 在平均執(zhí)行時(shí)間方面有很大的優(yōu)勢(shì)，其次是NSR.在多個(gè)維度的綜合評(píng)價(jià)中，NSR 獲得了最高的平均綜合排名.從性能，效率和穩(wěn)定性的總體平衡來(lái)看，排名結(jié)果顯示了NSR的優(yōu)勢(shì).總體而言，NSR與對(duì)比算法相比具有較強(qiáng)的競(jìng)爭(zhēng)力.

5 結(jié)論

本研究的重點(diǎn)是改善尺度資源的利用效率和解的多樣性，以提高算法性能.具體而言，采用適應(yīng)度進(jìn)化利用率表征特定尺度下的資源利用效率，用作動(dòng)態(tài)調(diào)節(jié)尺度調(diào)整速度的標(biāo)準(zhǔn).提出了2種不同的邊界映射策略來(lái)提高多樣性.通過(guò)使用不同參數(shù)組合的實(shí)驗(yàn)，統(tǒng)計(jì)分析尺度調(diào)節(jié)因子對(duì)算法的影響，實(shí)驗(yàn)結(jié)果表明2種改進(jìn)算法通過(guò)適當(dāng)?shù)乃俣日{(diào)節(jié)可以提升MQHOA的性能.

為了評(píng)估所提出方法的整體性能，與MQHOA 以及其他流行算法在基準(zhǔn)測(cè)試函數(shù)上針對(duì)30維問(wèn)題進(jìn)行了實(shí)驗(yàn)比較.計(jì)算平均誤差、成功率和平均執(zhí)行時(shí)間并分別進(jìn)行排名.實(shí)驗(yàn)結(jié)果表明，尺度動(dòng)態(tài)速度調(diào)節(jié)可以通過(guò)平衡探索和開(kāi)發(fā)來(lái)提高M(jìn)QHOA的性能，邊界映射策略對(duì)性能改進(jìn)有積極作用，負(fù)向反彈策略會(huì)帶來(lái)更大的競(jìng)爭(zhēng)力.

本文提出的算法仍然存在一些局限性.首先，改進(jìn)算法的平均執(zhí)行時(shí)間仍有提升空間.此外，增加了算法中的參數(shù)數(shù)量，參數(shù)的各種組合會(huì)帶來(lái)不同的效果，因此有必要分析參數(shù)組合以獲得更好的性能.另外，尺度反映了優(yōu)化算法搜索粒度，多種尺度調(diào)整策略和規(guī)則值得進(jìn)一步研究.這些問(wèn)題都是未來(lái)的研究重點(diǎn).