多尺度量子諧振子優(yōu)化算法的并行性研究

黃焱，王鵬，程琨，劉峰

(1. 淮陰師范學院計算機科學與技術(shù)學院，江蘇 淮安 223300；2. 西南民族大學計算機科學與技術(shù)學院，四川 成都 610225；3. 中國科學院成都計算機應用研究所，四川 成都 610041；4. 成都信息工程大學并行計算實驗室，四川 成都 610225)

多尺度量子諧振子優(yōu)化算法的并行性研究

黃焱1，王鵬2，程琨3，劉峰4

(1. 淮陰師范學院計算機科學與技術(shù)學院，江蘇 淮安 223300；2. 西南民族大學計算機科學與技術(shù)學院，四川 成都 610225；3. 中國科學院成都計算機應用研究所，四川 成都 610041；4. 成都信息工程大學并行計算實驗室，四川 成都 610225)

多尺度量子諧振子優(yōu)化算法(MQHOA, multi-scale quantum harmonic oscillator algorithm)是一種利用量子諧振子波函數(shù)構(gòu)造的新的智能算法，采樣運算是MQHOA算法的基本運算單元和主要運算量，采樣運算的獨立性賦予MQHOA算法內(nèi)在并行性。通過對MQHOA算法群體參數(shù)和采樣參數(shù)進行實驗，確定算法的并行粒度并提出多尺度量子諧振子并行算法（MQHOA-P, multi-scale quantum harmonic oscillator parallel algorithm）。在由10個計算節(jié)點構(gòu)成的集群上對6種標準測試函數(shù)進行實驗，通過改變計算節(jié)點數(shù)、函數(shù)維數(shù)和采樣參數(shù)測試MQHOA-P算法的加速比，實驗結(jié)果表明，MQHOA-P算法具有良好的加速比和擴展性，可以在大規(guī)模集群中部署、運行。

多尺度量子諧振子優(yōu)化算法；算法并行性；加速比；并行粒度；函數(shù)優(yōu)化

1 引言

MQHOA算法的基本思想是利用函數(shù)優(yōu)化問題與量子諧振子從高能態(tài)向基態(tài)收斂過程的相似性，結(jié)合高斯二進信息采樣方法，將函數(shù)優(yōu)化問題的求解過程分為量子諧振子（QHO, quantum harmonic oscillator）收斂和多尺度收斂（M 收斂）2個互相嵌套的收斂過程，通過QHO收斂實現(xiàn)在當前尺度對搜索空間的逐步收縮定位，通過M收斂逐漸提高搜索精度，使目標函數(shù)在指定精度找到全局最優(yōu)解[1]。

MQHOA算法在求解函數(shù)優(yōu)化[2]、組合優(yōu)化[3]等問題時具有良好的性能，并可以求解聚類中心點[4]等應用問題。文獻[1]介紹了 MQHOA算法的基礎模型，并對算法的收斂性進行研究；文獻[5]通過研究 MQHOA算法與經(jīng)典諧振子和量子諧振子物理模型之間的對應關系對 MQHOA算法的物理模型進行分析，介紹MQHOA算法中的量子隧道效應和測不準原理；文獻[6]將 MQHOA算法用于求解整數(shù)非線性規(guī)劃問題，與QPSO算法進行對比，驗證MQHOA算法的性能；文獻[7]通過將聚類數(shù)據(jù)集投影到基于劃分的網(wǎng)格，將聚類中心點問題轉(zhuǎn)化為離散函數(shù)優(yōu)化問題進行求解，使用MQHOA算法可以準確地找到聚類中心點位置，并且聚類數(shù)據(jù)集越大，找到的采樣中心點位置越準確，文獻[8]提出了具有能級穩(wěn)定過程的MQHOA算法。

采樣運算是MQHOA算法的基本運算單元，其運算量是MQHOA算法主要的運算量。采樣運算的獨立性賦予MQHOA算法內(nèi)在的并行性。當求解高維函數(shù)優(yōu)化問題時，隨著函數(shù)維數(shù)的增加，函數(shù)解空間呈指數(shù)級增加，求解目標函數(shù)最優(yōu)解所需的迭代次數(shù)也大幅增長，利用MQHOA算法的并行性可以有效地降低算法的運行時間。

本文通過對 MQHOA算法的采樣參數(shù)和群體參數(shù)進行實驗分析，分析MQHOA算法的3種并行粒度，提出MQHOA-P算法，該算法的核心思想是每次迭代運算時主節(jié)點將本次迭代的采樣中心點和當前尺度發(fā)送到從節(jié)點，從節(jié)點以接收到的采樣中心點位置和尺度進行采樣運算并在從節(jié)點內(nèi)更新最優(yōu)解位置，然后各從節(jié)點向主節(jié)點發(fā)起通信，將更新后的最優(yōu)解位置匯總到主節(jié)點，完成一次迭代運算。通過對6種測試函數(shù)在不同的函數(shù)維數(shù)、運行節(jié)點數(shù)的實驗分析，MQHOA算法具有較強的并行性和擴展性。

2 MQHOA算法流程與運行時間

2.1 MQHOA算法流程

MQHOA算法的基本流程如圖1所示。

1) 初始化：初始化群體參數(shù)k、采樣參數(shù)m、采樣范圍S、初始尺度σ0和最小尺度σmin，并在采樣范圍內(nèi)隨機生成k個初始采樣位置算法運行過程中將不斷地更新這些采樣位置，保留k個最優(yōu)解。

2) 迭代運算：假設當前為第p次迭代，尺度為σj，k個當前最優(yōu)解位置為以每個采樣位置為中心，分別按照高斯分布生成m個新的采樣位置，將km個新采樣位置的目標函數(shù)值分別與當前的k個最優(yōu)解位置的目標函數(shù)值進行比較，如果出現(xiàn)更優(yōu)解則替換原采樣位置，以上操作為一次迭代運算，完成本次迭代運算后的最優(yōu)解位置記為

圖1 MQHOA算法流程

以一個采樣位置為中心根據(jù)采樣參數(shù)和當前尺度生成m個新的高斯采樣位置并對目標函數(shù)值進行比較是一次采樣運算。采樣運算是MQHOA算法的基本運算單元。采樣運算僅取決于采樣位置和當前尺度，采樣運算之間沒有任何關聯(lián)關系，采樣運算的獨立性是MQHOA算法并行性的基礎。

5) 輸出結(jié)果：將當前k個采樣位置中的最優(yōu)位置和目標函數(shù)值作為結(jié)果輸出。

2.2 MQHOA算法的運行時間分析

根據(jù)如圖1所示的MQHOA算法流程，可將算法劃分為初始化、迭代運算、尺度判斷、尺度收縮、精度判斷和結(jié)果輸出6個部分，其編號、名稱、單位運行時間和運算次數(shù)如表1所示。其中，A1、A3、A4、A5、A6的單位運行時間為常數(shù)，A2的單位運行時間由算法的群體參數(shù)k和采樣參數(shù)m決定；A1、A4、A5、A6的運算次數(shù)為常數(shù)，A2、A3的運算次數(shù)為算法的迭代次數(shù)a1。

每次迭代運算A2包含k次獨立的采樣運算B1，每次采樣運算B1包含m次獨立的單位采樣B2，單位采樣的單位運行時間為D2，由此可得A2的單位運行時間為。

表1 MQHOA算法的運行時間

MQHOA算法的總運行時間為

迭代運算占總運行時間的比例為

MQHOA算法運行時間由算法迭代次數(shù)a1、群體參數(shù)k和采樣參數(shù)m共同決定。MQHOA算法的迭代次數(shù)取決于目標函數(shù)的復雜程度，隨著目標函數(shù)維度的增加，函數(shù)解空間的數(shù)量呈指數(shù)級增長，算法的迭代次數(shù)a1顯著增長，為了快速、準確地獲取全局最優(yōu)解需要加大k和m的數(shù)值，采樣參數(shù)的運行時間會相應地增加，由式(3)可知，迭代運算的占比增大，因此迭代運算是MQHOA算法最主要的運行時間。

3 MQHOA算法的并行化特性

3.1 MQHOA算法的并行方法

算法的并行方法取決于算法邏輯單元之間的依賴關系以及可并行化單元的內(nèi)部結(jié)構(gòu)[9]。對于MQHOA算法而言，其迭代運算單元間的串行依賴關系和互相獨立的采樣運算單元的可并行特性決定了算法的并行方法。

設當前迭代為 MQHOA算法的第p次迭代，第p+1次迭代運算的采樣中心點位置是第p次迭代運算更新的最優(yōu)解位置；第p+1次迭代運算的高斯采樣尺度取決于σp+1與σs的比較結(jié)果，如果，則采樣尺度減半，否則采樣尺度不變；算法是否執(zhí)行完畢取決于σp+1與的比較結(jié)果，如果則算法終止運行。因此下一次迭代運算的采樣中心位置、采樣尺度和是否繼續(xù)迭代均取決于當前迭代運算的結(jié)果，MQHOA算法的迭代運算必須串行執(zhí)行。

MQHOA算法的一次迭代運算包含k次采樣運算，在每個采樣中心點位置以當前尺度生成m個新解位置，并與當前最優(yōu)解位置進行比較，采樣運算之間互相獨立，可以在多個計算節(jié)點上并行運行。

MQHOA算法的運行過程是由迭代運算的串行運行構(gòu)成，由于迭代運算是MQHOA算法的主要運算量，其內(nèi)含的采樣運算是可并行化的，可以通過將采樣中心位置發(fā)送到多個并行計算節(jié)點，使采樣運算并行運行，實現(xiàn)MQHOA算法的并行化。根據(jù)算法結(jié)構(gòu)確定并行粒度是 MQHOA算法并行化的核心。

3.2 MQHOA算法的3種并行粒度

設MQHOA算法運行在由一個主節(jié)點和n個從節(jié)點構(gòu)成的并行計算集群上。劃分到從節(jié)點運行的任務規(guī)模是MQHOA算法的并行粒度，直接影響算法的并行性和并行開銷。根據(jù)圖1所示的MQHOA算法流程，MQHOA算法在迭代運算、尺度判斷和精度判斷時需要將上次迭代運算的結(jié)果進行匯總，因此MQHOA算法有以下3種并行粒度。

1) 粒度1

當MQHOA算法按照粒度1進行并行化時，從節(jié)點僅完成本次迭代的并行運算，其并行化框架如圖2所示。

圖2 采用并行粒度1的并行化框架

與串行程序相比，這種方法將一次迭代運算分發(fā)到多個從節(jié)點并行計算，其采樣中心點的生成方式、數(shù)量和收斂條件與串行程序完全相同。將采樣中心點位置均分并按照粒度1進行并行化后，每個從節(jié)點的運算量是相同的，當從節(jié)點的計算性能相同時，每次迭代從節(jié)點的運行時間相等。

2) 粒度2

當MQHOA算法按照粒度2進行并行化時，從節(jié)點完成當前尺度的并行運算，其并行化框架如圖3所示。與串行程序相比，這種方法在當前尺度收斂時使用的采樣中心點數(shù)量較少，導致當前尺度收斂的迭代次數(shù)增加、當前尺度正確收斂的概率降低，大幅增加算法的運行時間，降低獲取全局最優(yōu)解的概率。由于從節(jié)點獨立完成當前尺度的收斂，每個從節(jié)點的迭代運算次數(shù)不確定，導致各個從節(jié)點的運算時間存在差異，MQHOA算法的并行化時間由運算時間最長的節(jié)點決定。

3) 粒度3

當MQHOA算法按照粒度3進行并行化時，從節(jié)點完成所有尺度的并行運算，其并行化框架如圖4所示。與串行程序相比，這種方法將采樣中心點分發(fā)到多個從節(jié)點獨立運行MQHOA算法，運行完后對結(jié)果進行匯總，因此同樣會增加從節(jié)點的迭代次數(shù)并降低獲取全局最優(yōu)解的概率。從節(jié)點獨立地完成所有尺度的收斂的運算時間存在差異，MQHOA算法并行化的時間由運算時間最長的節(jié)點決定。

圖3 采用并行粒度2的并行化框架

圖4 采用并行粒度3的并行化框架

3.3 根據(jù)采樣參數(shù)選擇MQHOA算法的并行粒度

采用粒度2和粒度3將采樣中心分發(fā)到從節(jié)點獨立地進行迭代運算，與采用粒度1進行并行化相比，每個從節(jié)點上運行的采樣中心點數(shù)較少。MQHOA算法在不同采樣參數(shù)k下的性能決定了算法并行粒度的選擇方法。

將MQHOA算法的參數(shù)m依次取10、20、30、40、50、60、70、80、90、100、150、200、250、300、500，參數(shù)k依次取10、20、30、40、50、60、70、200、500、1 000，形成150個實驗組合，對3維的 Griewank函數(shù)在的解空間進行實驗，每個實驗組合分別進行 10次重復實驗，測試算法迭代次數(shù)如文獻[1]中表1所示。

可以看出，當采用粒度2、粒度3進行算法并行化時，從節(jié)點上的采樣中心數(shù)為串行程序的群體參數(shù)k較小，MQHOA算法落入局部最優(yōu)區(qū)域的概率加大，算法求解的準確性下降；與此同時，從節(jié)點上的迭代次數(shù)大幅增加，算法運行時間大幅增加。因此，本文采用粒度1對MQHOA算法進行并行化研究。

4 MQHOA-P算法的運行流程

根據(jù)MQHOA算法流程和算法并行性分析，本節(jié)使用粒度 1對 MQHOA算法進行并行化，提出MQHOA-P算法，算法的并行化框架如圖2所示，其并行化流程的詳細說明如下。

1) 初始化：在主節(jié)點完成參數(shù)k、m、S、σ0、的初始化運算，在采樣范圍內(nèi)隨機生成k個初始采樣位置，將當前的采樣位置平均分為n份，分別發(fā)送到n個從節(jié)點。

2) 迭代運算：每個從節(jié)點按照主節(jié)點發(fā)送的采樣位置和當前尺度進行迭代運算，將更新后的當前最優(yōu)解位置發(fā)送到主節(jié)點。

3) 主節(jié)點將從節(jié)點發(fā)送來的k個采樣位置進行匯總，計算其標準差σp+1，與算法當前的尺度σs進行比較。如果，則說明當前采樣中心點尚未在當前尺度收斂，返回步驟2)繼續(xù)在從節(jié)點上進行迭代運算；如果，則算法已在當前尺度收斂，進行M收斂過程。

5) 輸出結(jié)果：主節(jié)點將當前k個采樣位置中的最優(yōu)位置和目標函數(shù)值作為結(jié)果輸出。

5 MQHOA-P算法的并行化性能分析

MQHOA-P算法的初始化、尺度判斷、尺度收縮、精度判斷和輸出結(jié)果均在主節(jié)點運行，從節(jié)點僅執(zhí)行迭代運算，算法的收斂條件與串行程序完全相同。

MQHOA-P算法的主從節(jié)點間的通信包含3個部分。

1) 算法初始化后主節(jié)點向從節(jié)點發(fā)起一次通信，將初始采樣點和算法參數(shù)發(fā)送到從節(jié)點。

2) 從節(jié)點完成采樣運算后向主節(jié)點發(fā)起一次通信，將更新后的最優(yōu)解位置發(fā)送到主節(jié)點，共進行a1次通信。

3) 主節(jié)點接收到從節(jié)點發(fā)送來的最優(yōu)解位置后向從節(jié)點發(fā)起通信，將下一次迭代的尺度發(fā)送至從節(jié)點，共進行a1?1次通信。

MQHOA-P算法的運行時間為

通信時間占比為

MQHOA-P算法的加速比為

當從節(jié)點數(shù)增加時，加速度比增加，最大加速比為

由于迭代運算是 MQHOA-P算法的主要運算量，當?shù)螖?shù)a1不斷增長時，加速比不斷增加并趨于穩(wěn)定。

6 MQHOA-P算法的實驗驗證

6.1 實驗環(huán)境

本文在由同構(gòu)計算節(jié)點構(gòu)成的并行計算集群中進行實驗，所有節(jié)點的配置為 i3-3220(3.3 GHz)的CPU，4 GB內(nèi)存，操作系統(tǒng)為CentOS 6.5，將MPICH 3.1.3部署在集群中構(gòu)建并行計算環(huán)境。

6.2 測試函數(shù)

本文采用6個典型的高維測試函數(shù)對MQHOA-P算法的并行性進行實驗分析，測試函數(shù)的函數(shù)表達式、定義域、最優(yōu)解位置和全局最小值如表2所示。

表2 測試函數(shù)

為了測試MQHOA-P算法的加速比，首先使用MQHOA算法在單機環(huán)境中求解6個測試函數(shù)的全局最優(yōu)解，k=80，m=200，函數(shù)維數(shù)為6，每個測試函數(shù)重復 30次實驗計算單機平均執(zhí)行時間，實驗數(shù)據(jù)如表2的最右列所示。

6.3 MQHOA-P算法加速比實驗

1) 計算節(jié)點數(shù)對 MQHOA-P算法加速比的影響

并行算法包含可并行化和不可并行化2種成分的運算量，并行化后的MQHOA-P算法將可并行化部分分別發(fā)送到各個子節(jié)點運行，子節(jié)點仍需運行一部分不可并行化的運算量。

將計算節(jié)點數(shù)由 2個增加到 10個，使用MQHOA-P算法求解測試函數(shù)的全局最優(yōu)解，，每個測試函數(shù)重復30次實驗計算平均運算時間，與表2中的單機執(zhí)行時間進行比較，計算加速比，實驗結(jié)果如表3所示。從表3可以看出隨著計算節(jié)點數(shù)的增加，MQHOA-P算法加速比首先出現(xiàn)增加趨勢，然后逐漸趨于穩(wěn)定。這個變化趨勢與MQHOA-P算法的加速比表達式（6）相符合。由于目標函數(shù)的平均迭代次數(shù)不同，各目標函數(shù)加速比的穩(wěn)定值存在一定的差異。

2) 函數(shù)維數(shù)對MQHOA-P算法加速比的影響

隨著測試函數(shù)維數(shù)的增長，函數(shù)解空間的數(shù)量呈指數(shù)級增長，算法迭代運算的次數(shù)也不斷增長。在由1個主節(jié)點和4個計算節(jié)點構(gòu)成的并行計算集群上使用 MQHOA-P算法求解測試函數(shù)的全局最優(yōu)解，函數(shù)維數(shù)由3維逐漸增加到15維，每個測試函數(shù)重復 30次實驗計算平均運算時間，求解算法加速比，實驗數(shù)據(jù)如表4所示。從表4可以看出，隨著函數(shù)維數(shù)的增長，算法加速比逐漸增長。這是因為隨著函數(shù)維數(shù)的增長，算法迭代次數(shù)不斷增加，算法可并行化部分的運算量比例增加，使算法加速比出現(xiàn)增長。

表3 計算節(jié)點數(shù)對MQHOA-P算法加速比的影響

表4 函數(shù)維數(shù)對MQHOA-P算法加速比的影響

3) 采樣參數(shù)m對 MQHOA-P算法加速比的影響

采樣運算是算法最基本的運算單元，采樣運算單元的運算量取決于參數(shù)m。參數(shù)k依次取 80、100、150、200、250、300，參數(shù)m 依次取 200、300、400、500、600，形成30個實驗組合，在5個計算節(jié)點對6維函數(shù)f5進行實驗，測試算法加速比，每個組合重復30次實驗，實驗數(shù)據(jù)如表5所示。從表5可以看出，隨著參數(shù)m的增長，算法加速比逐步增長，這反映出隨著采樣參數(shù)m的增長，采樣運算單元的運算量相應地增長，算法可并行化部分的運算量比例增加，算法加速比增長。

表5 參數(shù)m對MQHOA-P算法加速比的影響

7 結(jié)束語

本文通過對群體參數(shù)和采樣參數(shù)進行實驗分析確定 MQHOA算法的并行粒度，提出并行化的MQHOA-P算法。通過在10個計算節(jié)點構(gòu)成的集群上對6種標準測試函數(shù)進行實驗，測試了計算節(jié)點數(shù)、函數(shù)維數(shù)和采樣參數(shù)與算法加速比的關系，實驗結(jié)果表明，MQHOA算法具有很好的加速比和可擴展性，適用于求解高維函數(shù)優(yōu)化問題。

[1] 王鵬, 黃焱, 任超, 等. 多尺度量子諧振子高維函數(shù)全局優(yōu)化算法[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.

[2] ZABARAS N, YANG G Z. A functional optimization formulation and implementation of an inverse natural convection problem[J]. Computer Methods in Applied Mechanics and Engineering, 1997, 144(3):245-274.

[3] PAPADIMITRIOU C H, STEIGLITZ K. Combinatorial optimization:algorithms and complexity[M]. Courier Corporation, 1998.

[4] LAI J Z C, HUANG T J, LIAW Y C. A fast k-means clustering algorithm using cluster center displacement[J]. Pattern Recognition, 2009,42(11): 2551-2556.

[5] 王鵬, 黃焱. 多尺度量子諧振子優(yōu)化算法物理模型[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 amp; Technology, 2015, 9(10): 1271-1280.

[6] 袁亞男,王鵬,劉峰.多尺度量子諧振子算法性能分析[J]. 計算機應用,2015,35(6):1600-1604.YUAN 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.

[7] 燕京京.基于量子諧振子模型的聚類中心選取算法[D]. 成都: 中國科學院成都計算機應用研究所, 2015.YAN J J. Clustering center selecting algorithm based on quantum harmonic oscillator model[D]. Chengdu: Chengdu Institute of Computer Application, 2015.

[8] 王鵬,黃焱.具有能級穩(wěn)定過程的 MQHOA 優(yōu)化算法[J]. 通信學報,2016,37(7):79-86.WANG P, HUANG Y. MQHOA algorithm with energy level stabilizing process[J]. Journal on Communications,2016,37(7):79-86.

[9] GRAMA A, GUPTA A, KARYPIS G. Introduction to parallel computing: design and analysis of algorithms[M]. Redwood City, CA:Benjamin/Cummings Publishing Company, 1994.

Parallelism of multi-scale quantum harmonic oscillator algorithm

HUANG Yan1, WANG Peng2, CHENG Kun3, LIU Feng4
(1. School of Computer Science and Technology, Huaiyin Normal University, Huaian 223300, China;2. School of Computer Science and Technology, Southwest University for Nationalities, Chengdu 610225, China;3. Chengdu Institute of Computer Application, Chinese Academy of Sciences, Chengdu 610041, China;4. Parallel Computing Lab, Chengdu University of Information Technology, Chengdu 610225, China)

MQHOA was a novel intelligent algorithm constructed by quantum harmonic oscillator's wave function. Sampling was the basic operation and main computational burden of MQHOA. The independence of sampling operation constructs MAHOA’s parallelism. Parallel granularity was obtained by experiments of group parameter and sampling parameter, and MQHOA-P was proposed. Experiments were done in a cluster of ten nodes on six standard test functions. By changing node number, function dimension and sampling parameter, experiments of MQHOA-P’s speed-up ratio were done. The experimental results show the good performance of MQHOA-P’s speed-up ratio and expansibility. MQHOA-P can be deployed and run on multiple nodes in a large-scale cluster.

MQHOA, algorithm parallelization, speedup, parallel granularity, functional optimization

s: The National Natural Science Foundation of China (No.60702075), Sichuan Key Laboratory Open Foundationof Pattern Recognition and Intelligent Information Processing (No.MSSB-2015-9)

TP393

A

10.11959/j.issn.1000-436x.2016179

2016-01-27；

2016-06-27

王鵬，wp002005@163.com

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

黃焱（1982-），男，江蘇泗陽人，博士，淮陰師范學院講師，主要研究方向為智能算法、最優(yōu)化理論等。

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

程琨（1987-），女，山東新泰人，中國科學院成都計算機應用研究所博士生，主要研究方向為智能算法。

劉峰（1987-），男，河南鄭州人，成都信息工程大學碩士生，主要研究方向為智能算法。