论文部分内容阅读
实践证明,元启发式已经成为解决多目标问题(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的优点。