基于采樣尺度自適應(yīng)的多尺度量子諧振子優(yōu)化算法并行化

焦育威，王 鵬,2，辛 罡

(1.西南民族大學(xué)計算機科學(xué)與技術(shù)學(xué)院,四川 成都 610225；2.廣東省國產(chǎn)服務(wù)器工程中心,廣東 廣州 510000；3.中國科學(xué)院大學(xué)，北京 100049；4.中國科學(xué)院成都計算機應(yīng)用研究所，四川 成都 610041)

1 引言

近些年大量的啟發(fā)式算法被提出[1]，這些算法在參數(shù)優(yōu)化、控制與決策等問題上都表現(xiàn)出色。多尺度量子諧振子優(yōu)化算法MQHOA(Multi-scale Quantum Harmonic Oscillator Algorithm)是一種量子啟發(fā)式算法，它以Schr?dinger方程為基礎(chǔ)，建立了優(yōu)化問題與量子系統(tǒng)之間的關(guān)系，將優(yōu)化問題轉(zhuǎn)換為求解粒子在約束下的基態(tài)波函數(shù)，且該算法在云計算、任務(wù)調(diào)度和空間聚類等方向都得到了廣泛的應(yīng)用[2]。

為了提高MQHOA的算法性能，近年來學(xué)者對MQHOA遷移策略和參數(shù)設(shè)置進行了研究，文獻[3]分析了能級穩(wěn)定過程中判據(jù)的變化對算法性能的影響，表明嚴(yán)格的判據(jù)可提高算法的全局搜索能力，在此基礎(chǔ)上提出了性能更好的版本(MQHOA-AS)。文獻[4,5]通過研究算法的遷移策略對MQHOA進行了改進。另一方面有學(xué)者對MQHOA背后的物理背景進行了研究，MQHOA是以波動方程在諧振子勢阱下的波函數(shù)為采樣函數(shù)指導(dǎo)算法迭代過程中的采樣行為，不同的勢阱下，算法采樣行為具有差異性，針對的優(yōu)化對象也不盡相同。基于量子系統(tǒng)中不同的勢阱，MQHOA開始衍生出不同的版本，如：基于自由粒子的多尺度量子自由粒子優(yōu)化算法MFPOA(Multi-scale Free Particle Optimization Algorithm)，并且相較同類型的優(yōu)化算法，MFPOA在求解近100個城市節(jié)點數(shù)的TSP問題時，在求解時間上具有競爭力[6]。

而上述針對MQHOA的改進中，存在一個共性，處于同一代的種群中，每一個采樣個體的約束尺度相同，但不同個體間的采樣情況具有差異性。尺度的大小決定了當(dāng)前的搜索狀態(tài)，也影響了下一次采樣解的多樣性，對算法采樣精度和成功率具有較大的影響，采樣情況不同的個體使用相同的采樣尺度，這一點本身不具有合理性。由此，本文根據(jù)不同的個體采樣情況差異化其采樣尺度，每一個體所使用的采樣尺度可以根據(jù)自身采樣情況動態(tài)調(diào)節(jié)，不同個體間的采樣尺度彼此獨立。

當(dāng)算法所面對的目標(biāo)函數(shù)結(jié)構(gòu)復(fù)雜或維度較高時，解空間不可避免地呈指數(shù)級增加，算法求解所需時間也隨之增加，算法執(zhí)行效率不可避免地會降低。此時傳統(tǒng)的串行計算模式已經(jīng)不能滿足需求，需要對算法流程進行并行化處理。對算法并行化，進程間的通信對算法的性能影響較大，MPI并行程序在運行過程中，通信等待時間占整個算法運行時間的比重較大[7 - 9]，為實現(xiàn)對通信開銷的合理折衷，本文提出具有星型拓撲通信結(jié)構(gòu)的多尺度量子諧振子優(yōu)化算法MQHOA-PS(Multi-scale Quantum Harmonic Oscillator Algorithm Parallelization by Scale)，該算法實現(xiàn)了采樣尺度間的并行化。

在華為鯤鵬920處理器上實現(xiàn)了改進后的算法的并行化，并將其與原算法進行了對比分析。選擇華為鯤鵬920的原因在于它是一款國產(chǎn)的高性能處理器。QHOA提出以來，相關(guān)的研究都是基于Intel或AMD系列處理器的，將MQHOA-PS和MQHOA移植在華為鯤鵬920處理器上實驗，一方面是為了測試改進后算法的性能；另一方面更是為了探究華為鯤鵬920處理器的高性能計算能力，為以后的國產(chǎn)處理器研發(fā)和軟件適配提供數(shù)據(jù)參考。

2 標(biāo)準(zhǔn)MQHOA

2.1 MQHOA物理模型

MQHOA受量子力學(xué)中波函數(shù)的物理意義啟發(fā)，通過模擬諧振子運動，構(gòu)建出算法模型。波函數(shù)可以用于描述量子系統(tǒng)中粒子位置分布概率，具體描述量子系統(tǒng)的方程被稱為Schr?dinger方程，不隨時間變化的Schr?dinger方程表示如式(1)所示：

(1)

(2)

其中，x0為全局最優(yōu)解。這樣求解目標(biāo)函數(shù)最小值的問題就可以轉(zhuǎn)換為求解諧振子勢阱下的基態(tài)波函數(shù)問題，此時的優(yōu)化問題的Schr?dinger方程，如式(3)所示：

(3)

此時波函數(shù)在基態(tài)的概率密度函數(shù)如式(4)所示：

(4)

從算法的物理模型上看，MQHOA共有3個迭代過程，分別是能級穩(wěn)定、能級下降和采樣尺度下降。在能級穩(wěn)定的過程中，對k個采樣點區(qū)域進行固定次數(shù)的采樣，用采樣過程中較優(yōu)的解替換當(dāng)前的解，在高能級狀態(tài)下搜索解空間，從而定位全局最優(yōu)區(qū)域。當(dāng)能級達到暫穩(wěn)態(tài)后，將最差解的位置用k個采樣位置的均值替換，以此實現(xiàn)能級下降。當(dāng)k個采樣點的標(biāo)準(zhǔn)差小于當(dāng)前采樣尺度時，算法即達到基態(tài)，此時采樣尺度減半，即為采樣尺度下降。算法在更小的采樣尺度下重復(fù)高能級到低能級的迭代過程，直到滿足迭代終止條件。MQHOA偽代碼如算法1所示：

算法1MQHOA

輸入：k(種群個體數(shù))，σmin(最小尺度)，S=[LB,LU](定義域)，σs(采樣尺度)，max_fe(最大迭代次數(shù))。

輸出：最優(yōu)解。

初始化(定義域內(nèi))xi(i=1,2,…,k) 。

步驟2判斷f(x′i)

步驟3計算標(biāo)準(zhǔn)差σk；

步驟4計算標(biāo)準(zhǔn)差變化量Δσk=|σk-σ′k|；

步驟5σ′k:σ′k←σk標(biāo)準(zhǔn)差更新；

步驟6判斷Δσk<σs是否滿足，如滿足則轉(zhuǎn)步驟7，否則轉(zhuǎn)步驟1；

步驟7差解替換xworst=xmean；

步驟8判斷σk<σs是否滿足，如滿足則轉(zhuǎn)步驟9，否則轉(zhuǎn)步驟1；

步驟9尺度減半σs=σs/2；

步驟10判斷σs>σmin是否滿足或是否超過最大迭代次數(shù)，二者皆不滿足則轉(zhuǎn)步驟1，否則輸出最優(yōu)解，算法結(jié)束。

上述算法中的步驟9為采樣尺度下降過程，這一過程決定了搜索精度，隨著采樣尺度下降的過程算法也從全局搜索逐步過渡到了局部搜索。從MQHOA算法中可以看出，同一代的所有采樣個體的采樣尺度相同，這也是傳統(tǒng)MQHOA所存在的缺陷。

2.2 MQHOA缺陷分析

由算法1中的算法流程可知，MQHOA在迭代過程中，采樣點收斂到一定程度后，采樣尺度將進行減半操作，在整個迭代過程中，采樣尺度的變化是單向的，是由大到小的變化，不存在采樣尺度擴大行為。隨迭代次數(shù)的增加，采樣尺度遞減到一定程度，算法進入局部搜索，此時不利于陷入局部最優(yōu)解的采樣點跳出當(dāng)前區(qū)域。

假設(shè)目標(biāo)函數(shù)f(x)為雙阱函數(shù)，其表達形式如式(5)所示：

(5)

其中，V0、a和δ為控制雙阱函數(shù)結(jié)構(gòu)的參數(shù)，V0用于調(diào)節(jié)勢壘的高度，a和δ分別控制極小值間的水平距離和高度差，在x=±a附近雙阱函數(shù)取得極值。當(dāng)V0=4.0，a=2.0，δ=0.3時，雙阱函數(shù)f(x)的二維圖像如圖1所示，此時目標(biāo)函數(shù)在x1=2.0附近存在一個局部最優(yōu)解。通過文獻[4]中的采樣函數(shù)可計算圖1中采樣點x1=2.0時跳出局部最優(yōu)的概率p為：

(6)

其中,σs為采樣尺度。圖1展示了采樣尺度從0.05擴張到0.1的過程，采樣的采樣尺度擴張后，由式(6)計算可知，該點在下一次迭代過程中跳出局部最優(yōu)解的概率也隨之增加，即p(x1,σs=0.1)>p(x1,σs=0.05)。

Figure 1 Schematic diagram of sampling scale expansion of two-dimensional double-well function圖1 二維雙阱函數(shù)采樣尺度擴張示意圖

因此，整個種群采用同一采樣尺度搜索是不合理的，不利于“陷入”局部最優(yōu)的采樣點跳出當(dāng)前區(qū)域。

2.3 改進方案

基于不同的采樣點在迭代過程中的采樣情況不同，可以根據(jù)采樣點自身差異性進行采樣尺度自適應(yīng)調(diào)節(jié)，該調(diào)節(jié)策略為雙向調(diào)節(jié)。與原采樣尺度縮減不同，采樣點可根據(jù)采樣情況擴大自身采樣尺度，當(dāng)采樣情況差時，自身采樣尺度以某一系數(shù)進行擴張?zhí)幚恚虼嗽诘^程中，除采樣尺度初始值相同外，經(jīng)過迭代，所有采樣點的采樣尺度都不盡相同，且相互保持獨立。采樣尺度調(diào)節(jié)流程如圖2所示，圖2中l(wèi)為采樣尺度擴張系數(shù)。此時每一個采樣點xi都具有獨立的采樣尺度σ(xi)，采樣情況不好的個體，經(jīng)過迭代其自身采樣尺度將增大，這樣更加有利于跳出局部最優(yōu)解。

該方案對采樣尺度的合理性擴張可以提高算法跳出局部最優(yōu)的概率，提高尋優(yōu)成功率，但增加采樣尺度擴張步驟無疑會提高算法時間復(fù)雜度，為了保證算法在尋優(yōu)成功率和時間上都具有競爭力，該方案的并行化十分重要。與此同時，該方案具備良好的并行特性，采樣點間采樣尺度的擴張過程無需與其他節(jié)點交換信息，迭代過程中具有獨立性，因此可將每一個采樣點的擴張過程并行化，即如圖2所示的迭代過程可分配到不同的節(jié)點上運算，而采樣尺度的縮減過程需要對全局采樣點的采樣尺度進行評估，對此過程設(shè)置一個獨立的節(jié)點進行相應(yīng)計算。

Figure 2 Flow chart of sampling scale expansion 圖2 采樣度擴張流程圖

3 MQHOA并行化

在串行模式下，MQHOA的能級穩(wěn)定過程中k個采樣點需要進行k次采樣運算，當(dāng)某一采樣點在進程上運算時，剩下的k-1個采樣點需要排隊等待，這一過程浪費了大量的時間，如果將采樣過程分配給不同的進程可以有效降低算法運行時間。文獻[10] 雖提出了分別具有3種不同并行粒度的MQHOA-P算法，但同一代的采樣點依舊使用相同的采樣尺度，采樣尺度的大小只取決于采樣尺度減半過程，沒有尺度自適應(yīng)過程，面對復(fù)雜函數(shù)或高維函數(shù)，解的多樣性只能以增加采樣點數(shù)量的方式得到保障，且實驗求解最優(yōu)區(qū)域的精度和成功率在文中并未說明，全文意在表達MQHOA并行化的可行性，并沒有提出具有高精度和高成功率的MQHOA并行化框架。本節(jié)具體闡述基于采樣尺度自適應(yīng)的MQHOA并行化框架，這一框架在保持較高尋優(yōu)精度的同時具有高成功率，它的核心在于采樣尺度的自適應(yīng)處理策略對解多樣性的提高。

采樣尺度的自適應(yīng)過程在從節(jié)點上進行，這一過程同時受到主節(jié)點的調(diào)控，主從節(jié)點間對采樣尺度的相互調(diào)控過程涉及進程間通信操作，通信時間如果過多，將對算法的性能造成負面影響，因此設(shè)計一種“多計算，少通信”的并行模式非常重要，這一點也是MPI所利用的“以計算換通信”的原則。MQHOA采樣過程中有k個采樣點，首先將采樣點分配到k個進程中，每一個采樣點占據(jù)獨立的節(jié)點，采樣點自身所占據(jù)的節(jié)點負責(zé)采樣操作和尺度擴張操作；然后，設(shè)置一個主節(jié)點，用于計算k個采樣點的標(biāo)準(zhǔn)差，用于處理能級穩(wěn)定過程中的替換操作和采樣尺度下降操作，主節(jié)點主要用于判斷算法是否滿足進入下一過程的條件，以及能級下降和采樣尺度下降操作。

并行后的MQHOA-PS流程如圖3所示，主節(jié)點完成初始化后，將采樣尺度信息和采樣點信息傳遞到從節(jié)點，從節(jié)點獨立進行m次采樣操作，期間采樣尺度依據(jù)采樣情況動態(tài)擴張，當(dāng)m次采樣完成后，將數(shù)據(jù)發(fā)送到主節(jié)點，此時主節(jié)點通過返回的采樣信息計算種群標(biāo)準(zhǔn)差σk，并判斷是否進入下一過程，以及通過返回的信息判斷全局采樣情況，是否對整體尺度進行減半操作，判斷算法是否滿足終止條件，同時輸出最優(yōu)解。

通過圖3可知，每一個采樣點占據(jù)一個獨立的節(jié)點，每一個采樣點的采樣尺度依據(jù)自身采樣情況在從節(jié)點上以系數(shù)l線性擴張，根據(jù)總體收斂情況在主節(jié)點上進行采樣尺度減半的操作。從信息利用的角度看，MQHOA-PS框架是利用k個采樣點的適應(yīng)度值判斷當(dāng)前采樣尺度是否擴張，k個采樣點的適應(yīng)度方差用于判斷當(dāng)前采樣尺度是否下降，以此實現(xiàn)k個采樣點的采樣尺度自適應(yīng)過程，避免了算法在迭代過程中采用相同的采樣尺度，不利于跳出局部最優(yōu)的缺陷。

由于該框架每一個采樣點占據(jù)一個進程，因此對進程間通信要求較高，若進程間通信時間會隨進程數(shù)量增加而呈數(shù)量級增加，則不適合此框架。

Figure 3 Flow chart of MQHOA-PS圖3 MQHOA-PS流程圖

4 實驗與結(jié)果分析

4.1 華為鯤鵬920通信測試

并行過程伴隨著通信過程，通信時間如果太長，反而會導(dǎo)致算法效率降低，實驗前對CPU進行通信測試可預(yù)估通信在算法迭代中的時間比重，初步判斷實驗可行性。MPI通信大致可分為2種：一種涉及物理機間的通信，進程1和進程2處于不同的物理機上，兩者間的通信除內(nèi)存讀寫外還包括網(wǎng)絡(luò)傳輸時間；另一種是同一機器內(nèi)的點對點通信，這一過程不涉及網(wǎng)絡(luò)傳輸，是通過操作系統(tǒng)進程間通信機制實現(xiàn)的。點對點通信可分為4大類[11]：(1)基于NIC(Network Interface Card)環(huán)路；(2)基于用戶態(tài)共享內(nèi)存；(3)基于核心態(tài)共享內(nèi)存；(4)基于I/OAT(I/O Acceleration Technology)。目前MPI支持軟件采用的點對點通信方式主要是基于用戶態(tài)共享內(nèi)存實現(xiàn)的，但上述不論哪種通信方式都涉及數(shù)據(jù)拷貝過程。

由于CPU間的通信受不同的服務(wù)器體系架構(gòu)和物理機間的連接方式影響，本節(jié)對不同物理機上的進程間通信不做討論，只對華為鯤鵬920做點對點通信測試[12]，這一測試可從側(cè)面反映華為鯤鵬920的讀寫能力，可預(yù)估華為鯤鵬920支持算法并行化的最大程度。

實驗平臺選用的是搭載華為鯤鵬920八核處理器的PC機，操作系統(tǒng)為UOS 20，華為鯤鵬920基于ARM架構(gòu)，采用RISC精簡指令集。利用MPI的消息傳遞功能實現(xiàn)不同進程間的點對點通信，然后記錄通信時間，對處理器的通信能力進行初步評估，看是否滿足MQHOA-PS并行框架的通信需求。本實驗在單機上進行，只測試處于同一物理機的核間通信，不涉及網(wǎng)絡(luò)傳輸，測試的傳輸數(shù)據(jù)包為雙精度浮點型數(shù)組，通過MPI_Send和MPI_Recv函數(shù)實現(xiàn)數(shù)據(jù)包在2個進程間的傳輸，每組實驗重復(fù)11次，將11次重復(fù)實驗所花費時間的平均值繪制成圖4。

Figure 4 Relationship between the size and time of sending and receiving packets 圖4 發(fā)送和接收數(shù)據(jù)包的大小與時間的關(guān)系

為了探究節(jié)點數(shù)量對傳輸時間的影響，分別設(shè)置大小為1 MB、2 MB、3 MB的數(shù)據(jù)包，節(jié)點數(shù)量為k，實驗記錄主節(jié)點接收由k-1個從節(jié)點發(fā)送數(shù)據(jù)包的時間，實驗重復(fù)11次，重復(fù)實驗的平均值繪制成圖5。

Figure 5 Relationship between node number and time when transmitting packets of different sizes圖5 傳輸不同大小數(shù)據(jù)包時節(jié)點數(shù)量與時間的關(guān)系

圖4的橫軸為數(shù)據(jù)包的大小，縱軸為發(fā)送和接收對應(yīng)大小數(shù)據(jù)包的時間，實驗結(jié)果顯示,發(fā)送和接收0.97 MB內(nèi)的雙精度浮點型數(shù)據(jù)包所用時間數(shù)量級為10-4s。MQHOA-PS以初始化30個采樣點為例，在函數(shù)維度為100的情況下，每一次迭代單一節(jié)點傳輸?shù)淖畲髷?shù)據(jù)量約為24 KB，此時表中的傳輸時間的數(shù)量級為10-4s。圖5中傳輸同樣大小的數(shù)據(jù)包，消耗的時間隨節(jié)點數(shù)線性增長，在工程設(shè)計中，可根據(jù)最大時間限制合理設(shè)置算法并行化程度；同時說明華為鯤鵬920可較好地支持MQHOA-PS并行化，不會因為節(jié)點數(shù)增加而發(fā)生時間“爆炸”現(xiàn)象，華為鯤鵬920進程間的通信滿足MQHOA-PS并行化框架對通信消耗的需求，且具備大規(guī)模運算能力。

4.2 實驗設(shè)置與數(shù)據(jù)

為了驗證MQHOA-PS的有效性，本文以MQHOA為對照組設(shè)計實驗，實驗選擇7組標(biāo)準(zhǔn)測試函數(shù)，維度為2,10,15的實驗組，實驗重復(fù)10次，維度為30的實驗組，實驗重復(fù)51次,測試函數(shù)信息如表1所示，包含3個多峰函數(shù)(f1～f3)和4個單峰函數(shù)(f4～f7)，MQHOA-PS與MQHOA在實驗中的迭代上限設(shè)置為n*10000,n為測試函數(shù)的維度。

實驗環(huán)境為一臺獨立的PC機，處理器為華為鯤鵬920 2249，核數(shù)為8，UOS 20操作系統(tǒng)，并行化工具為MPICH 3，在該設(shè)備下的實驗不涉及網(wǎng)絡(luò)通信。

首先對MQHOA-PS在2維和15維條件下實驗，其中尺度擴張系數(shù)l設(shè)置為1.2，節(jié)點數(shù)分別設(shè)置為3,5,8，實驗數(shù)據(jù)如表2所示，其中Fbest表示重復(fù)實驗中的解最小值，Mean為重復(fù)實驗的解均值，Time為重復(fù)實驗所消耗的平均時間，Sr為尋優(yōu)成功率，d代表函數(shù)維度，當(dāng)解小于1×10-5時判定成功，精度為1×10-14，當(dāng)解小于1×10-14時，輸出為0。

同時將改進后的算法(MQHOA-PS)與原算法(MQHOA)做對照實驗，實驗設(shè)置測試函數(shù)維度為10，分別測試不同的采樣點(節(jié)點)數(shù)量下算法的性能，實驗結(jié)果如表3所示，表中算法編號1為MQHOA-PS，編號2為MQHOA。

為了探究MQHOA-PS針對高維函數(shù)的尋優(yōu)能力，實驗設(shè)置節(jié)點數(shù)為8，重復(fù)實驗51次，遵循實驗對照原則，MQHOA的采樣點數(shù)量設(shè)置為8，2組算法對照實驗的迭代上限為3×105，51次重復(fù)實驗結(jié)果如表4所示，51次重復(fù)實驗所得的測試函數(shù)值如圖6所示。圖6的縱軸為函數(shù)值。

由于上述實驗在搭載華為鯤鵬920的PC上完成，PC所搭載的處理器核數(shù)為8，算法的并行規(guī)模受核數(shù)制約，因此將MQHOA-PS提交到由AMD構(gòu)建的超算中心進行實驗，實驗提交作業(yè)的隊列節(jié)點配置為：AMD EPYC 7452，單節(jié)點(這里的節(jié)點指物理機，與算法并行化節(jié)點不同) 64 核，主頻2.35 GHz，256 GB內(nèi)存，節(jié)點間采用InfiniBand網(wǎng)絡(luò)互連。實驗設(shè)置的維度為30，節(jié)點(采樣點)數(shù)分別為8,30，每組實驗重復(fù)11次，重復(fù)實驗的結(jié)果如表5所示。

Table 1 Names and expressions of seven test functions

Table 2 Optimization results of MQHOA-PS on 7 test functions with 2 and 15 dimensions

Table 3 Optimization results of MQHOA-PS and MQHOA on 7 test functions with 10 dimensions

4.3 結(jié)果分析

將相同的作業(yè)在單個處理器上運行消耗的時間定義為T1，由N個核并行處理消耗的時間定義為TN，加速比SN被定義為T1與TN的比值(SN=T1/TN)，可以用來衡量并行模式的有效性，若運行時間與核數(shù)成反比，則該并行框架為理想狀態(tài)[13]。

以表3的數(shù)據(jù)計算MQHOA-PS在目標(biāo)函數(shù)維度為10時的加速比，結(jié)果如表6所示。

通過表6可以明顯看到，伴隨計算節(jié)點的增加，算法的加速比開始下降，這是因為主節(jié)點每經(jīng)過一次循環(huán)，需要向k-1個從節(jié)點發(fā)送和接收一次數(shù)據(jù)，節(jié)點數(shù)的增加導(dǎo)致執(zhí)行通信操作的次數(shù)更加頻繁，主節(jié)點接收數(shù)據(jù)的大小與從節(jié)點數(shù)量成正比，從節(jié)點數(shù)量越多，越會增加主節(jié)點在每一次迭代過程中的I/O操作時間，因此對于MQHOA-PS而言，將節(jié)點數(shù)量控制在一定值內(nèi)可以有效提高算法效率。

節(jié)點數(shù)量增加相應(yīng)地采樣點數(shù)也會隨之增加，由表2可見，f4和f7的求解成功率會隨節(jié)點數(shù)(采樣點)的增加而上升，原因在于增加采樣點可以增加解的多樣性，有利于種群跳出局部最優(yōu)，這主要是由函數(shù)自身特征決定的。表2和表5中部分函數(shù)伴隨節(jié)點數(shù)的增加，求解精度反而下降，如表5中測試函數(shù)f2在8個節(jié)點的情況下，最優(yōu)解精度達到10-12，而節(jié)點數(shù)為30時，最優(yōu)解精度為102，已經(jīng)無法找到最優(yōu)解位置。導(dǎo)致這一現(xiàn)象的關(guān)鍵點在于實驗是有迭代上限的，在有限的迭代次數(shù)內(nèi)，增加節(jié)點數(shù)，勢必導(dǎo)致通信操作次數(shù)增加，采樣操作次數(shù)占總迭代次數(shù)比重下降，以計算換通信而節(jié)約時間的方法無疑會犧牲求解精度，算法并行化程度過高反而會降低算法性能(求解精度與求解時間)。由表5可見，當(dāng)節(jié)點數(shù)從8增加到30后，算法的求解時間明顯增加，漲幅在2個數(shù)量級。這是因為節(jié)點的增加導(dǎo)致通信操作更加頻繁，由于AMD超算隊列涉及網(wǎng)絡(luò)延遲，因此在編程過程中應(yīng)根據(jù)函數(shù)特征有針對性地設(shè)置節(jié)點數(shù)，以減少通信次數(shù)占迭代上限的比重。

Table 4 Optimization results of MQHOA-PS and MQHOA on 7 test functions with 30 dimensions and 8 nodes

Figure 6 Boxplot MQHOA-PS and MQHOA for 7 test functions with 30 dimensions and 8 nodes for 51 times repeat experiments圖6 函數(shù)維度為30，節(jié)點數(shù)(采樣點數(shù))為8時MQHOA-PS和MQHOA對7組測試函數(shù)重復(fù)51次實驗箱體圖

Table 5 Optimization results of MQHOA-PS on 7 test functions with 30 dimensions and different node numbers on AMD processors

Table 6 Acceleration ratio of test functions with 10 dimensions

通過表4和圖6可知，當(dāng)采樣點數(shù)量相同時，MQHOA-PS的求解成功率和消耗時間明顯優(yōu)于MQHOA的，且MQHOA-PS的解分布情況更加穩(wěn)定，解的精確性和穩(wěn)定性要優(yōu)于MQHOA，MQHOA-PS的求解時間與MQHOA求解時間相比，平均具有2個數(shù)量級的優(yōu)勢。其中MQHOA采樣點數(shù)為8時，對測試函數(shù)f6求解成功率為0，通過參考文獻[3]中的表1可知，MQHOA在30維時對測試函數(shù)f6的求解最優(yōu)值為7.03E-09，此時采樣點數(shù)量為20，而MQHOA-PS通過8個采樣點求解的最優(yōu)值為2.15E-12，求解精度遠優(yōu)于MQHOA，說明MQHOA-PS的采樣尺度自適應(yīng)策略有效增大了解的多樣性，用較少的采樣點即可達到較高的尋優(yōu)精度。針對測試函數(shù)f2,MQHOA的求解成功率為0，且文獻[4,5]中根據(jù)不同的遷移策略改進的MQHOA系列算法(CM-MQHOA和TS-MQHOA)在30維時對測試函數(shù)f2的求解成功率為0，而MQHOA-PS在8個采樣點的情況下，可將求解成功率提高到0.58。這說明針對結(jié)構(gòu)類似于f2的多峰函數(shù)，增加解的多樣性可提高尋優(yōu)成功率，也再一次驗證了采樣尺度自適應(yīng)策略的有效性。

結(jié)合表3和表4可見，并行化后的算法MQHOA-PS在8個節(jié)點內(nèi)，求解同樣的函數(shù)，所需要的時間都遠小于MQHOA的，這表明了本文并行方案的有效性，在15維以內(nèi)，除f4外的測試函數(shù)中，MQHOA-PS在8個節(jié)點內(nèi)的求解成功率都要優(yōu)于同一條件下的MQHOA。

總體而言，MQHOA-PS在保證成功率和精度的前提下整體性能要優(yōu)于MQHOA的，一方面是采樣尺度間相互獨立，增加解了的多樣性，不易陷入局部最優(yōu)，提高了尋優(yōu)精度；另一方面基于采樣尺度的并行化框架有效地對算法進行了“加速”，實驗結(jié)果也表明了本文并行框架的有效性。

5 結(jié)束語

本文提出采樣個體間使用獨立尺度采樣的策略，對MQHOA算法進行改進，提高了算法跳出局部最優(yōu)解的能力，同時對這一策略設(shè)計了并行化框架，提出基于尺度并行化的MQHOA-PS，通過實驗表明了這一并行化框架的有效性和合理性。將MQHOA算法和MQHOA-PS移植到華為鯤鵬920和AMD EPYC 7452處理器上進行測試實驗，實驗結(jié)果體現(xiàn)了華為鯤鵬920處理器點對點通信能力和計算能力，可以較好地支持算法并行化，同時展現(xiàn)了基于鯤鵬處理器開發(fā)有高性能計算需求應(yīng)用的可行性。