黃焱，王鵬，程琨，劉峰

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

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

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

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

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

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

1 引言

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

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

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

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

2 MQHOA算法流程與運(yùn)行時(shí)間

2.1 MQHOA算法流程

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

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

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

圖1 MQHOA算法流程

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

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

2.2 MQHOA算法的運(yùn)行時(shí)間分析

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

每次迭代運(yùn)算A2包含k次獨(dú)立的采樣運(yùn)算B1，每次采樣運(yùn)算B1包含m次獨(dú)立的單位采樣B2，單位采樣的單位運(yùn)行時(shí)間為D2，由此可得A2的單位運(yùn)行時(shí)間為。

表1 MQHOA算法的運(yùn)行時(shí)間

MQHOA算法的總運(yùn)行時(shí)間為

迭代運(yùn)算占總運(yùn)行時(shí)間的比例為

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

3 MQHOA算法的并行化特性

3.1 MQHOA算法的并行方法

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

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

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

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

3.2 MQHOA算法的3種并行粒度

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

1) 粒度1

當(dāng)MQHOA算法按照粒度1進(jìn)行并行化時(shí)，從節(jié)點(diǎn)僅完成本次迭代的并行運(yùn)算，其并行化框架如圖2所示。

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

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

2) 粒度2

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

3) 粒度3

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

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

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

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

采用粒度2和粒度3將采樣中心分發(fā)到從節(jié)點(diǎn)獨(dú)立地進(jìn)行迭代運(yùn)算，與采用粒度1進(jìn)行并行化相比，每個(gè)從節(jié)點(diǎn)上運(yùn)行的采樣中心點(diǎn)數(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個(gè)實(shí)驗(yàn)組合，對(duì)3維的 Griewank函數(shù)在的解空間進(jìn)行實(shí)驗(yàn)，每個(gè)實(shí)驗(yàn)組合分別進(jìn)行 10次重復(fù)實(shí)驗(yàn)，測試算法迭代次數(shù)如文獻(xiàn)[1]中表1所示。

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

4 MQHOA-P算法的運(yùn)行流程

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

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

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

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

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

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

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

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

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

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

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

MQHOA-P算法的運(yùn)行時(shí)間為

通信時(shí)間占比為

MQHOA-P算法的加速比為

當(dāng)從節(jié)點(diǎn)數(shù)增加時(shí)，加速度比增加，最大加速比為

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

6 MQHOA-P算法的實(shí)驗(yàn)驗(yàn)證

6.1 實(shí)驗(yàn)環(huán)境

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

6.2 測試函數(shù)

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

表2 測試函數(shù)

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

6.3 MQHOA-P算法加速比實(shí)驗(yàn)

1) 計(jì)算節(jié)點(diǎn)數(shù)對(duì) MQHOA-P算法加速比的影響

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

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

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

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

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

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

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

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

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

7 結(jié)束語

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

[1] 王鵬, 黃焱, 任超, 等. 多尺度量子諧振子高維函數(shù)全局優(yōu)化算法[J]. 電子學(xué)報(bào),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]. 計(jì)算機(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]. 計(jì)算機(jī)應(yīng)用,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]. 成都: 中國科學(xué)院成都計(jì)算機(jī)應(yīng)用研究所, 2015.YAN J J. Clustering center selecting algorithm based on quantum harmonic oscillator model[D]. Chengdu: Chengdu Institute of Computer Application, 2015.

[8] 王鵬,黃焱.具有能級(jí)穩(wěn)定過程的 MQHOA 優(yōu)化算法[J]. 通信學(xué)報(bào),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

國家自然科學(xué)基金資助項(xiàng)目（No.60702075）；模式識(shí)別與智能信息處理四川省高校重點(diǎn)實(shí)驗(yàn)室開放基金資助項(xiàng)目（No.MSSB-2015-9）

黃焱（1982-），男，江蘇泗陽人，博士，淮陰師范學(xué)院講師，主要研究方向?yàn)橹悄芩惴ā⒆顑?yōu)化理論等。

王鵬（1975-），男，四川樂山人，西南民族大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)橹悄芩惴?、高性能?jì)算等。

程琨（1987-），女，山東新泰人，中國科學(xué)院成都計(jì)算機(jī)應(yīng)用研究所博士生，主要研究方向?yàn)橹悄芩惴ā?/p>

劉峰（1987-），男，河南鄭州人，成都信息工程大學(xué)碩士生，主要研究方向?yàn)橹悄芩惴ā?/p>