基于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开销比较大。……