The Distributed Design And Implement Of Multi-objective Evolutionary Algorithm Based On Map Reduce And Spark

Multi-objective optimization problems usually have multiple solutions, which can be solved by using the evolutionary algorithm based on population search to search a series of optimal solutions in single time. Most of Multi-objective evolution algorithms are Pareto optimum algorithms. The multi-objective evolution algorithms based on decomposition appear in recent years, like the Multi-Objective Evolution Algorithm based on Decomposition(MOEA/D) and Conical Hypervolume Evolutionary Algorithm(CHEA), which have higher operational efficiencies because of the decomposition thought drawing the traditional mathematical programming method. However, when solving the time-consuming objective function, algorithms of decomposition still need a long running time. Therefore, considering the MapReduce and Spark have been regarded as the general computing framework in industry, it'll be an effective method by using this framework to reduce the algorithm running time, which combines the multi-objective evolution algorithm and the distributed parallel design.In this article, we design and implement the global and local population evolution schemes with MOEA/D and CHEA by using the decomposition model algorithm decomposition characteristics of MOEA/D and CHEA. In the global population evolution scheme, each Map keeps the whole population and runs one or more time evolution process with all individuals. There is a little difference in the local population evolution scheme, showing that even though the local plan Map has the whole population, it won't evolve all individuals; instead, it simply evolves one partition of the whole population. The result from the three target optimization case shows that on the premise that the quality of solution set is not less than the serial condition, the global population evolution scheme can provide greater acceleration ratio, while the local population evolution scheme can provide faster convergence speed in the process of population evolution, in the meanwhile, MOEA based on the Spark computation framework can obviously gain higher acceleration ratio than that based on the MapReduce computation framework. At the end, the global design schemes of Spark is applied to solve the problem of wireless sensor networks(WSN) deployment. The experimental results show that the global population evolution scheme of MOEA/D has a decent effect of acceleration ratio in the condition that the quality of solution set can be guaranteed, which greatly reduces the running time of WSN layout.