摘要：近年来,由于分解型多目标进化算法在多目标优化问题的求解方面有着比较优秀的表现,越来越多的学者投入到了...近年来,由于分解型多目标进化算法在多目标优化问题的求解方面有着比较优秀的表现,越来越多的学者投入到了分解型多目标进化算法的研究中,并提出了大量的优秀算法来对多目标优化问题进行求解。为了进一步降低分解型算法求解大规模问题的运行时间成本,本文利用流行的Spark分布式计算框架,对两种分解型算法,基于分解的多目标进化算法(Multi-objective Evolutionary Algorithm Based on Decomposition,MOEA/D)和锥形分解多目标进化算法(Multi-objective Evolutionary Algorithm Based on Cone Decomposition,MOEA/CD)进行分布式设计与实现,并应用于无线传感器网络布局问题。本文首先结合分解型多目标进化算法的特点以及Spark分布式计算框架的特点,提出了一个通用的分布式方案——主从分布式方案。主从分布式方案的实现非常简单,对原始算法的改动较小,并且对DTLZ标准测试例的实验结果分析可知该算法不仅能降低时间成本,其所得到的解集质量也非常接近串行算法。但是由于主从分布式方案的时间成本依然存在较大的改进空间,因此又提出了一个更为快速的分布式方案——岛屿分布式方案,并根据算法MOEA/D子种群局部更新的特点设计了基于Spark框架部分种群岛屿分布式方案,以及根据MOEA/CD子种群全局更新的特点设计了基于Spark框架的整体种群岛屿分布式方案。部分种群岛屿分布式方案通过将种群个体进行分割,并对分割后的各个部分个体同时进行进化,使得每一代进化所需要的时间比串行算法时间要短;而整体种群岛屿分布式方案则将种群信息复制多份,每个分区分配一份完整的种群信息,但每个岛屿仅负责其中一个分区的一部分种群的进化,并且分布式岛屿间同时进行进化。从两个方案的DTLZ标准测试例的实验结果分析可知其均能在保证解集质量不明显下降的前提下达到减少算法运行时间的目的,且其加速效果要比主从分布式方案的效果要好。为了进一步验证岛屿分布式方案的性能,本文将部分种群岛屿分布式MOEA/D以及整体种群岛屿分布式MOEA/CD应用于无线传感器网络布局问题。实验结果表明,部分种群岛屿分布式MOEA/D的加速效果要比整体种群岛屿分布式MOEA/CD稍好,而整体种群岛屿分布式MOEA/CD得到的解集质量要明显优于部分种群岛屿分布式MOEA/D。更多还原显示全部
