并行計(jì)算在MOEA/D-EGO算法中的應(yīng)用

馬永格，吳釗

?

并行計(jì)算在MOEA/D-EGO算法中的應(yīng)用

馬永格1,2，吳釗1

(1. 湖北文理學(xué)院 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，湖北 襄陽 441053；2. 中國地質(zhì)大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢 430074)

在MOEA/D-EGO算法中，當(dāng)建模樣本點(diǎn)集合元素太多和種群規(guī)模較大時(shí)，會(huì)導(dǎo)致算法運(yùn)行時(shí)間過長. 為了減少M(fèi)OEA/D-EGO算法的運(yùn)行時(shí)間，文章對(duì)MOEA/D-EGO算法的建模過程和種群優(yōu)化過程同時(shí)并行化. 在綜合考慮實(shí)驗(yàn)條件限制的情況下，使用了基于主從式的并行模型，模型在充分考慮計(jì)算機(jī)資源的使用效率與負(fù)載均衡等因素下，增加了主進(jìn)程的任務(wù)，主進(jìn)程不僅需要為子進(jìn)程分配計(jì)算任務(wù)、分發(fā)數(shù)據(jù)、進(jìn)行算法配置、收集子進(jìn)程返回的計(jì)算結(jié)果，還需要參與子進(jìn)程的任務(wù)，完成與子進(jìn)程相當(dāng)量的計(jì)算任務(wù). 實(shí)驗(yàn)結(jié)果表明文章的并行MOEA/D-EGO算法能有效求解多目標(biāo)優(yōu)化問題，且能夠大幅縮短算法運(yùn)行時(shí)間.

MOEA/D-EGO算法；并行計(jì)算；候選解；種群優(yōu)化

由于MOEA/D-EGO[1]算法本身的以建模算法評(píng)價(jià)候選解策略和種群優(yōu)化過程都是針對(duì)昂貴評(píng)價(jià)優(yōu)化問題所設(shè)計(jì)，在求解某些類別的優(yōu)化問題上已經(jīng)是目前的最優(yōu)的算法. 所以，使用并行計(jì)算[2]對(duì)MOEA/D-EGO算法并行化，以此來減少算法運(yùn)行時(shí)間是更加合理的途徑.

近年來，在使用并行演化算法來縮短算法在多目標(biāo)優(yōu)化問題上的求解時(shí)間，也被越來越多的學(xué)者所研究. 在2011年D.Logofatu和M.Gruber[3]結(jié)合MapReduce[4]與多目標(biāo)演化算法用于數(shù)據(jù)壓縮實(shí)例求解，并將算法應(yīng)用于超大規(guī)模集成電路中尋找最小測(cè)試集的問題中，該框架僅適用于含大數(shù)據(jù)處理的優(yōu)化問題. 2013年李暉教授[5]提出了一種新型的基于主從模式的并行演化算法大幅度的縮短了演化算法在繼電器參數(shù)優(yōu)化問題中的計(jì)算時(shí)間. 2013年Si-Jung Ryu, Jong-Hwan Kim[6]則針對(duì)在多目標(biāo)量子演化算法中，基于非支配排序和擁擠距離分配計(jì)算時(shí)間過長的問題，使用了GPU的分布計(jì)算能力，但是算法僅適用于基于Pareto前沿的多目標(biāo)演化算.

研究資料表明，在很多并行計(jì)算系統(tǒng)中，計(jì)算結(jié)點(diǎn)的CPU平均利用率僅達(dá)9%[7]. 通過實(shí)驗(yàn)分析，本文發(fā)現(xiàn)在MOEA/D-EGO算法的運(yùn)行過程中，計(jì)算系統(tǒng)中的資源至少有1/3 到2/3 的時(shí)間是空閑的，利用這些空閑的處理能力并行求解較大的計(jì)算問題或者并行執(zhí)行多個(gè)作業(yè)，可以大大縮短問題的求解時(shí)間.

1 MOEA/D-EGO并行性分析

在MOEA/D-EGO算法中，主要有種群初始化、候選解評(píng)價(jià)、種群優(yōu)化過程三個(gè)大的部分，種群初始化和種群優(yōu)化過程是基于MOEA/D算法[8]框架，候選解評(píng)價(jià)則是基于EGO算法[9]中的預(yù)測(cè)模型DACE模型[10](高斯隨機(jī)過程模型)來評(píng)價(jià)候選解. 所以，針對(duì)MOEA/D和EGO算法，其并行化分析如下：

1)在EGO算法中，用高斯隨機(jī)過程建立DACE模型的過程，每個(gè)目標(biāo)都需要建立一個(gè)DACE預(yù)測(cè)模型，而在建模過程中，需要涉及到大量的矩陣運(yùn)算，通過MOEA/D-EGO時(shí)間測(cè)試表4-5所示，每次建模都需要花費(fèi)大量時(shí)間. 而在建模過程中每個(gè)目標(biāo)的預(yù)測(cè)模型都是相互獨(dú)立的，不難看出，在建模這個(gè)層次上，可以將每個(gè)目標(biāo)的模型用分別在不同的進(jìn)程中創(chuàng)建，最后將待評(píng)價(jià)的候選解分別在兩個(gè)不同的進(jìn)程中評(píng)價(jià)，最后交由主進(jìn)程完成綜合評(píng)價(jià).

2)種群更新階段，在定位候選解中完成. 需要執(zhí)行種群個(gè)體雜交，變異操作，和更新鄰居子問題表. 一方面，在這個(gè)過程中，因單個(gè)個(gè)體評(píng)估時(shí)間消耗大，而且種群數(shù)規(guī)模龐大，迭代次數(shù)較多. 所以時(shí)間開銷大. 另一方面，每個(gè)個(gè)體的變異，更新都是相對(duì)獨(dú)立的，更新操作只與其鄰居個(gè)體有關(guān). 所以我們可以將種群分布為幾個(gè)子種群，每個(gè)子種群單獨(dú)優(yōu)化. 為此我們同樣設(shè)計(jì)主從式模型，由于種群中的個(gè)體優(yōu)化需要依賴其鄰居子問題，所以我們需在每個(gè)進(jìn)程上分布整個(gè)種群，每個(gè)進(jìn)程只優(yōu)化更新整個(gè)種群中自己所需演化的子種群中個(gè)體，子進(jìn)程完成自己的任務(wù)后將優(yōu)化后的種群個(gè)體發(fā)送給主進(jìn)程.

2 并行MOEA/D-EGO算法實(shí)現(xiàn)

2.1 算法基本流程

算法的框架與實(shí)現(xiàn)如圖1.

圖1 MOEA/D-EGO算法流程

算法參數(shù)：

具體步驟：

2.2 DACE建模并行化

目前，一般的單臺(tái)機(jī)器大多數(shù)機(jī)器為雙核，而同一臺(tái)機(jī)器上的并行在數(shù)據(jù)發(fā)送，接收和節(jié)點(diǎn)控制上所消耗的計(jì)算機(jī)資源很少，并且Master上的Salve并不需要發(fā)送接收數(shù)據(jù). 所以可以改進(jìn)主從式并行模型[13]，我們使Master的節(jié)點(diǎn)同時(shí)也是Salve節(jié)點(diǎn). 當(dāng)MOEA/D-EGO的目標(biāo)數(shù)比較少時(shí)，這種設(shè)置能夠得到比較優(yōu)良的結(jié)果. 模型圖如2所示：

根據(jù)第1章的DACE預(yù)測(cè)模型并行化分析和圖2的并行模型的設(shè)計(jì)，主進(jìn)程和子進(jìn)程的流程如下：

圖2 多核并行模型

2.2.1主進(jìn)程與子進(jìn)程執(zhí)行流程

上節(jié)已經(jīng)對(duì)建立DACE預(yù)測(cè)模型的并行性做了分析，該模塊基于主從式并行. 將每個(gè)目標(biāo)的DACE預(yù)測(cè)建模設(shè)置在Master節(jié)點(diǎn)和不同的Salve節(jié)點(diǎn)上，并在不同的處理器核上運(yùn)行. 由Mater將建模參數(shù)傳送到Salve節(jié)點(diǎn)，Salve節(jié)點(diǎn)完成建模后，將模型傳送給Master節(jié)點(diǎn). 主要流程如下：

主進(jìn)程：1)順序執(zhí)行到DACE建模階段；2)主進(jìn)將多個(gè)DACE建模的消息平均分布到子進(jìn)程和主進(jìn)程上；3)主進(jìn)程完成自己所獲的DACE預(yù)測(cè)模型建模；4)主進(jìn)程接收子進(jìn)程提交的建模模型信息并對(duì)信息進(jìn)行加工處理，還原為DACE預(yù)測(cè)模型；5)主進(jìn)繼續(xù)執(zhí)行，結(jié)束各個(gè)子進(jìn)程.

子進(jìn)程：1)順序執(zhí)行到DACE建模階段；等待主進(jìn)程發(fā)送建模所需參數(shù)；2)接收建模所需信息，完成DACE預(yù)測(cè)模型建模；3)將完成的DACE預(yù)測(cè)模型參數(shù)發(fā)送給主進(jìn)程；4)子進(jìn)程結(jié)束.

2.2.2并行DACE建模實(shí)現(xiàn)

1)將已評(píng)價(jià)的樣本點(diǎn)變量值與適應(yīng)值，進(jìn)行封裝；2)判斷每個(gè)進(jìn)程上所需建立的模型；3)主進(jìn)程將1中封裝的信息按照2的判斷發(fā)送到相應(yīng)的子進(jìn)程；4)子進(jìn)程利用3中的信息建模；5)子進(jìn)程將4中得到的DACE預(yù)測(cè)模型的參數(shù)封裝，發(fā)送給主進(jìn)程；6)主進(jìn)程將5子進(jìn)程得到的信息還原為DACE預(yù)測(cè)模型；7)子進(jìn)程結(jié)束，主進(jìn)程繼續(xù)執(zhí)行.

2.3 種群優(yōu)化并行化

在單機(jī)多核環(huán)境中，設(shè)置主進(jìn)程運(yùn)行在Mater節(jié)點(diǎn)上，主進(jìn)程除了需要負(fù)責(zé)對(duì)各個(gè)Salve節(jié)點(diǎn)的控制，信息收發(fā)，信息收集和信息整合外，同時(shí)也需要演化分布在Mater節(jié)點(diǎn)上的子種群個(gè)體. Salve節(jié)點(diǎn)運(yùn)行子進(jìn)程，子進(jìn)程完成子種群個(gè)體雜交變異，和更新個(gè)體鄰居子問題表操作.

在第1章節(jié)中，已經(jīng)對(duì)種群優(yōu)化的并行性做了分析，該模塊的并行基于主從式并行. 本論文中，由于實(shí)驗(yàn)條件限制，同樣采用第二種方式. 即單機(jī)多核環(huán)境，將需要演化的子種群平均分配到CPU的每個(gè)核上，Master節(jié)點(diǎn)運(yùn)行的主進(jìn)程負(fù)責(zé)對(duì)節(jié)點(diǎn)的信息收發(fā)，控制，并且需要演化分布在自己節(jié)點(diǎn)上的子種群. Salve節(jié)點(diǎn)上的子進(jìn)程負(fù)責(zé)演化分布其上的子種群，主要流程如圖3.

圖3 并行種群優(yōu)化流程示意圖

3 并行MOEA/D-EGO結(jié)果分析

3.1 測(cè)試環(huán)境與參數(shù)設(shè)置

采取C++語言進(jìn)行編寫，開發(fā)軟件為eclipse CDT，編譯環(huán)境gcc version 4.4.0，并行環(huán)境是MPI，采用的并行庫是MPICH，硬件上使用8核CPU的機(jī)器測(cè)試算法的并行.

表1(a) 算法性能測(cè)試硬件環(huán)境

硬件CPU內(nèi)存硬盤 型號(hào)Inter (R) Core(TM)i7930@2.80GHz6 GB DDR2 800MHz500GB 7200RPM

表1(b) 算法性能測(cè)試軟件環(huán)境

表2 測(cè)試函數(shù)集

3.2 算法運(yùn)行結(jié)果記錄與分析

為了驗(yàn)證并行MOEA/D-EGO算法的正確性，下面以2個(gè)目標(biāo)函數(shù)的多目標(biāo)問題ZDT1、ZDT3、ZDT6運(yùn)行結(jié)果圖和3個(gè)目標(biāo)函數(shù)的的DTLZ2[11]運(yùn)行結(jié)果圖來說明. 圖4至圖7為算法在8核CPU的計(jì)算機(jī)環(huán)境中，種群大小為300個(gè)個(gè)體，評(píng)價(jià)次數(shù)為200的條件下，2個(gè)進(jìn)程運(yùn)行，取10次結(jié)果中的最優(yōu)值. 圖7為算法在8核CPU計(jì)算機(jī)環(huán)境中，種群大小為595個(gè)個(gè)體，評(píng)價(jià)次數(shù)為300的條件下，3個(gè)進(jìn)程運(yùn)行，取10次結(jié)果中的最優(yōu)值.

圖4 ZDT1 8核2進(jìn)程運(yùn)行結(jié)果

圖5 ZDT3 8核2進(jìn)程運(yùn)行結(jié)果

圖6 ZDT6 8核2進(jìn)程運(yùn)行結(jié)果

圖7 DTLZ2 8核3進(jìn)程運(yùn)行結(jié)果

如圖4至圖7所示，算法在運(yùn)行2個(gè)目標(biāo)和3個(gè)目標(biāo)的的經(jīng)典測(cè)試函數(shù)時(shí)，能夠得到較優(yōu)的結(jié)果. 該結(jié)果驗(yàn)證了并行MOEA/D-EGO算法在有限評(píng)價(jià)次數(shù)之內(nèi)能夠得到測(cè)試問題的非支配收斂解，盡管收斂精度不能達(dá)到一般算法理論研究時(shí)的苛刻精度，但種群的非支配收斂趨勢(shì)表明了算法在解決昂貴評(píng)價(jià)多目標(biāo)問題上的正確性，以及算法具備實(shí)際應(yīng)用能力.

為了研究并行MOEA/D-EGO算法在DACE建模過程中時(shí)間的節(jié)省，用1到8個(gè)進(jìn)程執(zhí)行了測(cè)試函數(shù)ZDT1. 如表3所示，測(cè)試函數(shù)40次運(yùn)行過程中DACE建模時(shí)間對(duì)比，1-8個(gè)進(jìn)程平均每次測(cè)試運(yùn)行5次，建模時(shí)間為5次建模的平均值.

表3 8核環(huán)境多進(jìn)程并行DACE建模時(shí)間對(duì)比(ZDT1測(cè)試) 單位: s

并行計(jì)算在建立DACE預(yù)測(cè)模型的過程中，因程序在建模級(jí)上作得并行即將每個(gè)模型的建立分配到不同的進(jìn)程中，程序沒有做粒度更小的并行，故在進(jìn)程數(shù)超過目標(biāo)數(shù)時(shí)，建模時(shí)間不會(huì)繼續(xù)縮短，反而會(huì)因?yàn)檫M(jìn)程的增多，計(jì)算機(jī)資源消耗增大而導(dǎo)致建模的時(shí)間相對(duì)增加.

為了研究并行MOEA/D-EGO算法在種群過程節(jié)省時(shí)間，采用1~8個(gè)進(jìn)程執(zhí)行了測(cè)試函數(shù)ZDT1. 表4所示，測(cè)試函數(shù)40次運(yùn)行過程中種群優(yōu)化過程花費(fèi)的時(shí)間對(duì)比，1~8個(gè)進(jìn)程平均每次測(cè)試運(yùn)行5次，種群優(yōu)化時(shí)間為程序5次運(yùn)行的平均值.

表4 8核環(huán)境多進(jìn)程并行定位候選解時(shí)間對(duì)比 單位: s

并行計(jì)算在種群優(yōu)化過程中，將種群的優(yōu)化分布到多個(gè)進(jìn)程中需要消耗一定的時(shí)間，所以在進(jìn)程數(shù)繼續(xù)增加過程中，種群優(yōu)化過程時(shí)間的減少量的相對(duì)值變化會(huì)慢慢的減小，在實(shí)際應(yīng)用中運(yùn)行并行程序需要具體考慮進(jìn)程數(shù)的安排個(gè)數(shù).

為了進(jìn)一步研究并行MOEA/D-EGO算法，如表5所示，算法在8核環(huán)境下，平均每次測(cè)試結(jié)果為3次程序的運(yùn)行得出時(shí)間的平均值. 測(cè)試函數(shù)為2個(gè)目標(biāo)的多目標(biāo)函數(shù)種群大小為300，評(píng)價(jià)次數(shù)為200次；測(cè)試函數(shù)為3個(gè)目標(biāo)的多目標(biāo)函數(shù)種群大小為595，評(píng)價(jià)次數(shù)為300次. 為了更加清晰的現(xiàn)實(shí)算法的效率，本文給出了多進(jìn)程運(yùn)行的加速比，如表6所示.

表5 8核環(huán)境算法運(yùn)行總時(shí)間對(duì)比 時(shí)間：s

表6 加速比對(duì)

通過表5所示程序運(yùn)行時(shí)間對(duì)比與表6所示的加速比分析，很容易的看出當(dāng)測(cè)試函數(shù)目標(biāo)數(shù)為2，種群數(shù)為300，評(píng)價(jià)次數(shù)為200次的情況下，并行MOEA/D-EGO算法在進(jìn)程數(shù)為3或4的時(shí)候效率最高，當(dāng)進(jìn)程數(shù)增加到8時(shí)候能夠很明顯的看出程序運(yùn)行時(shí)間反而增大；當(dāng)測(cè)試函數(shù)目標(biāo)數(shù)為3，種群數(shù)為595，評(píng)價(jià)次數(shù)為300次的情況下，并行MOEA/D-EGO算法隨著進(jìn)程數(shù)的增加而運(yùn)行時(shí)間減少，在進(jìn)程數(shù)為8的情況下算法效率最高.

4 結(jié)語

本文圍繞并行MOEA/D-EGO算法，對(duì)MOEA/D-EGO算法中的DACE建模過程和種群優(yōu)化過程進(jìn)行了并行性分析，采用基于主從式模型模型，實(shí)現(xiàn)了DACE建模的并行化和種群優(yōu)化過程的并行化. 通過多個(gè)經(jīng)典的測(cè)試函數(shù)的測(cè)試，實(shí)驗(yàn)結(jié)果不僅證明了算法能夠有效解決昂貴評(píng)價(jià)多目標(biāo)優(yōu)化問題，而且驗(yàn)證了并行計(jì)算的利用能夠使得MOEA/D-EGO算法在運(yùn)行時(shí)間上獲得較大負(fù)幅度的加速，對(duì)計(jì)算機(jī)資源的利用率有著顯著的提高.

[1] ZHANG QINGFU, LIU WUDONG, TSANG E, et al. Expensive multiobjective optimization by MOEA/D with Gaussian process model[J]. IEEE Transactions on Evolutionary Computation, 2010, 14(3): 456-474.

[2] 陳國良. 并行算法的設(shè)計(jì)與分析[M]. 2版. 北京: 高等教育出版社, 2002.

[3] LOGOF?TU DONIA, GRUBER MANFRED, DUMITRESCU D D. Distributed Evolutionary Algorithm Using the MapReduce Paradigm–A Case Study for Data Compaction Problem[M]. Berlin: Springer Berlin Heidelberg, 2011: 279-291.

[4] 李建江, 崔 健, 王 聃, 等. MapReduce并行編程模型研究綜述[J]. 電子學(xué)報(bào), 2012, 39(11): 2635-2642.

[5] 劉小明, 李 暉, 熊慕舟. 并行演化算法在MEMS繼電器參數(shù)優(yōu)化中的應(yīng)用[J]. 計(jì)算機(jī)工程與應(yīng)用, 2014, 50(6): 200-204.

[6] RYU SI-JUNG, KIM JONG-HWAN. Distributed Multiobjective Quantum-Inspired Evolutionary Algorithm[J]. Robot Intelligence Technology and Applications, 2013, 208: 663-670.

[7] JIN Y. A comprehensive survey of fitness approximation in evolutionary computation[J]. Soft Computing, 2005, 9(1): 3-12.

[8] ZHANG QINGFU, LI HUI. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712–731.

[9] JEONG SHINKYU, OBAYASHI SHIGERU. Efficient Global Optimization (EGO) for Multi-objective Problem and Data Mining[C]// IEEE. Proceedings of the 2005 IEEE Congress on Evolutionary Computation. Chicago: IEEE, 2005: 2138-2145.

[10] ULMER H, STREICHERT F, ZELL A. Evolution strategies assisted by Gaussian processes with improved pre-selection criterion[C]// IEEE. Proceedings of the 2005 IEEE Congress on Evolutionary Computation. IEEE, 2003: 692-699.

[11] DEB K, THIELE L, LAUMANNS M, et al. Scalable multi-objective optimization test problems[C]// IEEE. Proceedings of the 2002 IEEE Congress on Evolutionary Computation. Honolulu: IEEE, 2002: 825-830.

Parallel Computing in MOEA/D-EGO Algorithm

MA Yongge1,2, WU Zhao1

(1. College of Mathematical and Computer Sciences, Hubei University of Arts and Sciences, Xiangyang 441053, China; 2.School of Computer Science and Technology, China University of Geosciences, Wuhan 430074, China)

In MOEA/D-EGO algorithm, when there are too many modeling sample set elements or the population scale is large , it will lead to a long computation time. In order to reduce the run time of the MOEA/D-EGO algorithm, this paper parallelizes both the modeling process and the population optimization process. considering the experimental conditions, this paper uses the master-slave parallel model which adds the task to the main process in the condition of fully considering the efficiency of computer resources and load balance. The main process not only assigns computation task, distributes data, configures algorithm, collects the computation results, but also participates in the task of child process and complete the same amount of computation task as child process. The experimental result shows that the paralleled MOEA/D-EGO algorithm can effectively solve the multi-objective optimization problem, and can significantly shorten the running time of the algorithm.

MOEA/D-EGO algorithm; Parallel computing; Candidate solution; Population optimization

TP301.6

A

2095-4476(2014)05-0009-06

2014-03-03;

2014-04-01

國家自然科學(xué)基金重點(diǎn)項(xiàng)目(31130055); 國家自然科學(xué)基金面上項(xiàng)目(31372573, 61172084); 湖北省自然科學(xué)基金項(xiàng)目(2013CFC026); 湖北省科技支撐計(jì)劃項(xiàng)目(2013BHE022)

馬永格(1987— ), 女, 河北藁城人, 湖北文理學(xué)院與中國地質(zhì)大學(xué)(武漢)聯(lián)合培養(yǎng)碩士研究生;

吳 釗(1973— ), 男, 湖北武漢人, 湖北文理學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院副教授, 博士, 中國地質(zhì)大學(xué)(武漢)兼職碩士生導(dǎo)師，主要研究方向: 智能算法, 云計(jì)算.

(責(zé)任編輯：饒 超)