馬永格，吳釗

?

并行計(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í)，會導(dǎo)致算法運(yùn)行時(shí)間過長. 為了減少M(fèi)OEA/D-EGO算法的運(yùn)行時(shí)間，文章對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]算法本身的以建模算法評價(jià)候選解策略和種群優(yōu)化過程都是針對昂貴評價(jià)優(yōu)化問題所設(shè)計(jì)，在求解某些類別的優(yōu)化問題上已經(jīng)是目前的最優(yōu)的算法. 所以，使用并行計(jì)算[2]對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ī)模集成電路中尋找最小測試集的問題中，該框架僅適用于含大數(shù)據(jù)處理的優(yōu)化問題. 2013年李暉教授[5]提出了一種新型的基于主從模式的并行演化算法大幅度的縮短了演化算法在繼電器參數(shù)優(yōu)化問題中的計(jì)算時(shí)間. 2013年Si-Jung Ryu, Jong-Hwan Kim[6]則針對在多目標(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í)行多個作業(yè)，可以大大縮短問題的求解時(shí)間.

1 MOEA/D-EGO并行性分析

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

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

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

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

2.1 算法基本流程

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

圖1 MOEA/D-EGO算法流程

算法參數(shù)：

具體步驟：

2.2 DACE建模并行化

目前，一般的單臺機(jī)器大多數(shù)機(jī)器為雙核，而同一臺機(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ù)測模型并行化分析和圖2的并行模型的設(shè)計(jì)，主進(jìn)程和子進(jìn)程的流程如下：

圖2 多核并行模型

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

上節(jié)已經(jīng)對建立DACE預(yù)測模型的并行性做了分析，該模塊基于主從式并行. 將每個目標(biāo)的DACE預(yù)測建模設(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)將多個DACE建模的消息平均分布到子進(jìn)程和主進(jìn)程上；3)主進(jìn)程完成自己所獲的DACE預(yù)測模型建模；4)主進(jìn)程接收子進(jìn)程提交的建模模型信息并對信息進(jìn)行加工處理，還原為DACE預(yù)測模型；5)主進(jìn)繼續(xù)執(zhí)行，結(jié)束各個子進(jìn)程.

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

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

1)將已評價(jià)的樣本點(diǎn)變量值與適應(yīng)值，進(jìn)行封裝；2)判斷每個進(jìn)程上所需建立的模型；3)主進(jìn)程將1中封裝的信息按照2的判斷發(fā)送到相應(yīng)的子進(jìn)程；4)子進(jìn)程利用3中的信息建模；5)子進(jìn)程將4中得到的DACE預(yù)測模型的參數(shù)封裝，發(fā)送給主進(jìn)程；6)主進(jìn)程將5子進(jìn)程得到的信息還原為DACE預(yù)測模型；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é)對各個Salve節(jié)點(diǎn)的控制，信息收發(fā)，信息收集和信息整合外，同時(shí)也需要演化分布在Mater節(jié)點(diǎn)上的子種群個體. Salve節(jié)點(diǎn)運(yùn)行子進(jìn)程，子進(jìn)程完成子種群個體雜交變異，和更新個體鄰居子問題表操作.

在第1章節(jié)中，已經(jīng)對種群優(yōu)化的并行性做了分析，該模塊的并行基于主從式并行. 本論文中，由于實(shí)驗(yàn)條件限制，同樣采用第二種方式. 即單機(jī)多核環(huán)境，將需要演化的子種群平均分配到CPU的每個核上，Master節(jié)點(diǎn)運(yùn)行的主進(jìn)程負(fù)責(zé)對節(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 測試環(huán)境與參數(shù)設(shè)置

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

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

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

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

表2 測試函數(shù)集

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

為了驗(yàn)證并行MOEA/D-EGO算法的正確性，下面以2個目標(biāo)函數(shù)的多目標(biāo)問題ZDT1、ZDT3、ZDT6運(yùn)行結(jié)果圖和3個目標(biāo)函數(shù)的的DTLZ2[11]運(yùn)行結(jié)果圖來說明. 圖4至圖7為算法在8核CPU的計(jì)算機(jī)環(huán)境中，種群大小為300個個體，評價(jià)次數(shù)為200的條件下，2個進(jìn)程運(yùn)行，取10次結(jié)果中的最優(yōu)值. 圖7為算法在8核CPU計(jì)算機(jī)環(huán)境中，種群大小為595個個體，評價(jià)次數(shù)為300的條件下，3個進(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個目標(biāo)和3個目標(biāo)的的經(jīng)典測試函數(shù)時(shí)，能夠得到較優(yōu)的結(jié)果. 該結(jié)果驗(yàn)證了并行MOEA/D-EGO算法在有限評價(jià)次數(shù)之內(nèi)能夠得到測試問題的非支配收斂解，盡管收斂精度不能達(dá)到一般算法理論研究時(shí)的苛刻精度，但種群的非支配收斂趨勢表明了算法在解決昂貴評價(jià)多目標(biāo)問題上的正確性，以及算法具備實(shí)際應(yīng)用能力.

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

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

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

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

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

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

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

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

表6 加速比對

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

4 結(jié)語

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