基于Spark計算框架的多目標優化算法實現

何昱琪 李德禹

摘? 要：為了降低分解型算法求解大規模問題的運行時間成本，結合分解型多目標進化算法（MOEA/D）和Spark分布式計算框架的特點，提出了一個主從分布式分解型多目標進化算法（MODEA/D-RDD）。在新的方案中每個Map保存且進化一個子問題，從而通過多個Map分布式計算提高效率。測試例上的實驗結果表明，在求得解集質量不明顯降低的前提下，全局種群進化方案能夠有效縮短求解多目標問題的計算時間。

關鍵詞： Spark計算框架;多目標優化;MOEA/D算法

中圖法分類號： TP391? ? ? ? ?文獻標識碼：A文章編號：2096-4706（2021）22-0066-05

Abstract： In order to reduce the running time cost of decomposition algorithm for solving large-scale problems， a master-slave distributed multi-objective evolutionary algorithm （MODEA/D-RDD） is proposed based on the characteristics of the decomposition multi-objective evolutionary algorithm （MOEA/D） and Spark distributed computing framework. In the new scheme， each Map saves and evolves a sub problem， so as to improve the efficiency through multiple Map distributed computing. The Experimental results on test cases show that the global population evolution scheme can effectively shorten the computational time on solving multi-objective problems on the premise that the quality of the solution set is not significantly reduced.

Keywords： Spark computing framework; multi-objective optimization; MOEA/D algorithm

0? 引? 言

MOEAs（Multi-objective Evolutionary Algorithm Based on Decomposition， MOEA/D）算法的主要思想是將復雜的MOP進行分解，得到一組標量子問題，在每次進化迭代的過程中，同時對所有子問題進行處理，得到由各個子問題的解構成的帕累托最優解集。研究發現其分解的特性在求解效率上相對指標型和帕累托型的MOEAs有所提高，但是其求解計算密集型MOP的時間成本依然很高[1]，因此時間成本的控制也是MOP問題的一個重要研究方向。分布式計算是大數據時代的一個主流趨勢，在提升算法的運算效率方面產生了非常大的影響。為了降低求解MOP問題的時間成本，一個值得考慮的方法是將分布式計算的概念引入到多目標進化算法中。

Hadoop、Spark是目前比較流行的分布式計算框架。Hadoop是出現比較早的一個分布式計算框架，其中用來執行分布式計算的計算框架MapReduce非常適合對離線的大批量數據進行處理，但Hadoop并不適用于需要多次迭代的運算，因為其每次迭代都需要進行IO操作，磁盤IO開銷比較大。Spark是一種基于內存進行計算的分布式框架，適合于對迭代類型的算法進行分布式計算。為了減少時間成本，許多學者嘗試將分布式計算應用于多目標優化算法。2003年Deb提出了分布式島嶼模型MOEAs的分布式計算方案[2]。2008年Daniela Zaharie提出基于MPI的分層結構的分布式MOEAs[3]。2010年，Sadasivam提出基于分布式框架MapReduce 的混合GA-PSO的分布式算法[4]。2018年，Spark 分布式框架 NSGA-Ⅱ的分布式方案被提出[5]。結合分解型MOEAs的特點，選擇Spark分布式計算框架對多目標優化算法進行分布式設計是一個可行的研究方案。本文提出了一個主從分布式多目標優化算法全局優化方案。每個Map保存且進化一個完整大小的種群，從而通過多個Map分布式計算提高效率，降低分解型MOEAs求解MOP問題的時間成本。

1? 基于Spark平臺的MOEA/D 算法模型

在面對實際問題中的計算密集型優化問題，串行的分解型MOEAs的時間成本依然不夠理想。從圖1可以看出，分解型多目標進化算法每個子問題都是共同的步驟，就是對子問題的迭代計算，而這一步驟隨著問題的復雜程度的提高所需要耗費的計算時間也隨之增長，是整個算法中耗時較大的一個部分，并且此部分的處理對算法解集質量的影響也比較小。為了在得到與串行算法質量相當的解集的前提下，降低分解型MOEAs的時間成本，提出一種基于Spark的主從分布式的MOEA/D算法。

1.1 MOEA/D算法

MOEA/D利用分解的思想將復雜的多目標優化問題轉變為一系列的單目標問題。每個標量子問題分配一個鄰域，利用聚合函數計算每個子問題的聚合函數值，并在領域內通過進化計算產生新的個體，并更新各領域內的差解（不好的個體）。這樣，各個子問題之間相互協作同時優化，尋找最優的Pareto解集。MOEA/D算法流程如圖1所示。

1.2? 基于Spark框架的主從分布式計算框架

Spark是當前主流的開源分布式計算框架之一，基于內存進行計算的方式使得Spark，相比MapReduce更適合用于需要迭代執行的算法。同時，Spark的一個特殊的數據結構是彈性分布式數據集RDD對分布式內存的抽象使用。Spark的所有分布式操作都是基于RDD的，RDD是Spark最核心的部分，它的特點是可分區，各個分區的操作并行執行。作為一個記錄集合，RDD是只讀的，可以對RDD執行兩種操作算子——轉換（Transformation）算子和行動（Action）算子。基于Spark框架的主從式分布計算框架如圖2所示。

2? 基于Spark框架的分解的多目標優化算法（MOEA/D-RDD）

根據上面設計的Spark算法總流程以及MOEA/D的特點，我們為MOEA/D設計了一中基于子問題并行計算的分布式優化算法MOEA/D-RDD。算法流程為：

算法 2-1：MOEA/D-RDD 算法主框架

1：Initialization

2：? ?pop? ←? initializePopulation（） //初始化種群

3：? ?initializeDirectionVector（） //初始化方向向量

4：? ?initializeNeighborhood（） //初始化鄰居向量

5：while （進化結束條件未到達）? do

6：? ?children[] //

7：? ?for i ： 0 → N do //分布式計算每個子問題

8：? ? ?parents：parentSelection（） //選擇操作

9：? ? ?child：crossover（parents） //交叉操作

10：? ? child：mutation（child） //變異操作

11：? ? children[i] = child

12：? children：distributeEvaluateObj（children） //分布式計算

13：? for i：0? →? N do

14：? ? child = children[i]

15：? ? updateIdealPoint（child） //更新理想點

16：? ? updateNeighborhood（child） //更新鄰居向量

17：獲取最終得到的種群 pop 中不被支配的個體，構造帕累托解集 PS

18：根據 F（PS）映射得到帕累托前沿 PF

算法利用Spark 框架將第一部分產生的后代個體集合按照子問題分配到RDD的各個分區中，并對各個分區并行執行轉換算子和行動算子。在轉換算子中，各個分區并行地對分區中的個體執行目標值計算操作并產生含有目標值的后代個體集合的RDD;對轉換算子操作得到的RDD執行行動算子，觸發Spark作業并得到所有含有目標值的后代個體構成的集合。迭代計算得到的后代個體集合對原始種群執行更新操作，得到新一代種群。

3? 實驗結果分析

3.1? 測試函數

選取了四個測試問題，分別是ZDT1、ZDT2、ZDT3、ZDT4，為了能更直觀地展示實驗效果、便于在Spark上運行MOEA/D，使用的四個測試問題都為二目標測試問題，這四個測試問題的描述如表1所示。其中，曲線圖表示的是真實Pareto前沿，橫坐標是二目標問題的Function1的函數值，縱坐標是二目標問題的Function2的函數值。

3.2? 實驗結果

實驗結果均采用的是MOEA/D以本地模式運行以及MOEA/D在Spark集群上運行的結果，主要比較對象是在Spark上的以本地模式運行的串行MOEA/D，既相當于在一臺機器上以單線程模式運行的MOEA/D和在基于YARN的Spark集群上以多機器多線程模式運行的 MOEA/D。

統一多目標問題的種群大小200，鄰居大小5，迭代次數100。如圖3所示的計算結果散點圖橫坐標是二目標問題的Function1的函數值，縱坐標是二目標問題的Function2的函數值，散點圖中的多個點都是計算得出的最優解。

3.3? 結果分析

優化問題除了需要得到較優質的解之外，還有一個運行的效率這個重要的指標。因此，進行分布式優化算法的比較，加速比（Speed-up）是需要考慮的方面之一。

對多目標優化算法和分布式多目標優化算法的加速比統計比較。實驗效率分析如表2所示。

評價計算的解與Pareto前沿相近的程度，其中收斂性和多樣性為兩個主要考慮的方面。在表3實驗質量分析表中，Mean代表真實Pareto前沿面上的點集到獲取的解集的最小距離的平均值，又因為真實Pareto前沿面是分布均勻的，因此數值越小表明計算得到的解集的收斂性和多樣性越好。

實驗結果表明，在求得的解集質量沒有明顯下降的情況下，基于Spark的 MOEA/D 算法取得了非常好的優化效果，大大縮短了求解多目標問題的計算時間。

4? 結? 論

文中利用基于分解的多目標優化算法MOEA/D的分解特性，通過種群分布式存儲和處理的方式，在Spark計算框架上實現了可分布式計算的MOEA/D多目標優化算法。同時也驗證了多目標優化算法分布式運行相比非分布式運行的優勢。

在以后的研究中，可以探索用本文實現的分布式MOEA/D算法解決具體的多目標優化問題，通過具體的多目標優化問題來對算法的有效性進行更深入的驗證。

參考文獻：

[1] FONSECA C M， FLEMING P J. An overview of evolutionary algorithms in multiobjective optimization [J].Evolutionary computation， 1995，3（1）：1-16.

[2] DEB K，ZOPE P，Jain A. Distributed computing of Pareto-optimal solutions with evolutionary algorithms [C]//Proceedings of the 2nd international conference on Evolutionary multi-criterion optimization.Springer-Verlag：534-549.

[3] ZAHARIE D， PETCU D， PANICA S. A Hierarchical Approach in Distributed? Evolutionary Algorithms for Multiobjective Optimization [J].Lecture Notes in Computer Science，2008，4818：516-523.

[4] SADASIVAM G S，SELVARAJ D. A novel parallel hybrid PSO-GA using MapReduce to schedule jobs in Hadoop data grids [C]//2010 Second World Congress on Nature and Biologically Inspired Computing （NaBIC）.Kitakyushu：IEEE，2010：377-382.

[5] DONKAL G， VERMA G K. Securing Big Data Ecosystem with NSGA-II and Gradient Boosted Trees Based NIDS Using Spark [C]//2018 Second International Conference on Intelligent Computing and Control Systems （ICICCS）.Madurai：IEEE.2018：146-151.

作者簡介：何昱琪（2001—），女，漢族，浙江義烏人，本科在讀，研究方向：數據處理、數據分析統計。李德禹（2001—），男，漢族，安徽阜陽人，本科在讀，研究方向：算法設計與分析、數據處理。