基于Spark计算框架的MOEA/D算法研究

摘要

实践证明，元启发式已经成为解决多目标问题(Multiobjective OptimizationProblems, MOPs)的有效手段。特别是进化算法的广泛使用，使得大量的优秀算法被设计出来，如NSGA-Ⅱ，SPEA2，PAES等等。多数多目标进化算法是基于帕累托占优的概念。然而在MOP领域，另一行之有效的策略是基于分解的方法。基于分解的多目标进化算法(Multi-Objective Evolutionary Algorithm based on Decomposition，MOEA/D)就是典型之一。通过分解，MOEA/D可以利用现有的单目标优化算法，使得单目标优化的优秀算法也能被充分利用。经过改进，MOEA/D获得了CEC2009多目标进化算法竞赛冠军，展示了它的优越性。
　　大数据时代的来临，对计算机的处理速度又提出了新的要求。为了针对海量数据提出的挑战，多核芯片、多CPU、分布式系统已经是当下的研究热点。其中Spark在新一代大数据处理平台中，得到最广泛的认可和支持。
　　Spark平台现在已经集成了机器学习领域的众多算法，但是在优化算法领域，特别是多目标进化算法还未集成。本文着重对MOEA/D进行研究，并提出其在Spark计算框架下的实现方案，通过对比实验，验证各种实现方案的优劣。在MOEA/D中，权向量是定义子问题的必要部件。本文针对权向量的设置，提供权向量分区的方案，并以此定义算法的分布式模式。对于分区方法，本文提出两种方法，一种是以相近的权向量作为一个分区，该方案能充分利用分区内的邻居信息，但是由于多样性不足，各个分区容易提前进入收敛;另一种方案是将相近的权向量分配到不同的分区，与前一方案相比，它能够提供更好的多样性，但是，邻居的信息质量不如方案一中的高。存分布式框架中的实验表明，在大多数测试函数中，方案二能得到较好的结果。在扩展性方面，本文将权向量划分为多个分区作为算法的扩展方式。实验表明，单纯依靠权向量的划分，算法的扩展性受到了限制，因为越多分区，每个分区得到的权向量以及邻居的质量越少，不能完全利用MOEA/D的优点。

目录

声明

摘要

第一章 绪论

1．1 课置背景

1．2 国内外研究现状和研究意义

1．2．1 多目标优化算法的并行化研究

1．2．2 Spark计算框架的优点

1．3 本论文研究工作

1．4 本论文章节安排

第二章 基本理论

2．1 多目标优化问题

2．2 基于分解的多目标进化算法(MOEA／D)

2．3 多目标优化的分解

2．4 MOEA／D算法流程

2．5 MOEA／D算法发展

2．6 多目标进化算法的评价指标

2．7 本章小结

第三章 基于Spark的MOEA／D算法

3．1 基本模型

3．2 分区方案一：连续选择

3．2．1 分区方案一流程

3．2．2 性能测试

3．3 分区方案二：间隔选择

3．3．1 分区方案二流程

3．3．2 性能测试

3．4 分区方案二扩展：间隔选择，沟通参考点

3．3．1 分区方案二流程

3．3．2 性能测试

3．5 扩展性研究

3．6 加速比研究

3．7 与其他并行算法的比较

3．8 本章小结

第四章 结论和进一步工作

4．1 论文的创新点

4．2 存在的问题和进一步工作

参考文献

攻读硕士学位期间发表的论文

参与科研项目

致谢