Distributed Design And Implementation Of Decompositionbased Multi-objective Evolutionary Algorithms

For the past few years,decomposition-based multi-objective evolutionary algorithms have shown great performance on solving multi-objective optimization problems.So more and more scholars pay more attention to the study of this kind of problems and a large number of excellent algorithms are proposed.In order to further reduce the time cost of decomposition-based algorithms when solving large scale problems,a distributed computing framework is adopted in this thesis for redesigning decomposition-based evolutionary algorithms.In detail,the multiobjective evolutionary algorithm based on decomposition(MOEA/D)and the multi-objective evolutionary algorithm based on cone decomposition(MOEA/CD)are redesigned and implemented using Spark framework.Furthermore,these two kinds of redesigned algorithms are applied to the layout problem of wireless sensor network(WSN).At first,combining the features of decomposition-based multi-objective evolutionary algorithms and the Spark framework,a general distributed scheme,named master-slave distributed scheme,is proposed in this thesis.It is very easy to implement the master-slave distributed scheme just by making a little change on the serial algorithm.But algorithms adopting this scheme can reduce the time cost obviously and obtain solutions' qualities similar to those of the serial algorithms through an analysis of experimental results on benchmark DTLZ test instances.However,the time cost of algorithms with the master-slave distributed scheme can be further improved,so a faster distributed scheme,the island distributed scheme,is proposed.And then,a partial population island distributed scheme based on spark is designed for MOEA/D according to its characteristics that subpopulations are updated locally,and an entire population distributed scheme based on spark is designed based on the characteristics of MOEA/CD that subpopulations are updated globally as well.The partial population distributed evolution scheme divides the population into several parts and all parts are evolved concurrently.So the evolution of each generation needs shorter time than the serial algorithm.The entire population distributed evolution scheme makes several copies of population to provide information about the entire population for each island,and each island just takes charge of one certain partition of the population when evolving concurrently.From the analysis of experimental results on benchmark DTLZ test instances,the algorithms with two island distributed schemes are both able to achieve the purpose of reducing the run time cost of the original algorithms without obviously losing qualities of solutions,and the acceleration effect of them is better than that of the master-slave distributed scheme.In order to further verify the performance of the island distributed scheme,this thesis applies the distributed MOEA/D with the partial population island distributed scheme and the distributed MOEA/CD with the entire population distributed scheme to the layout problem of WSN.Experimental results indicate that MOEA/D with the partial population island distributed scheme performs slightly better than MOEA/CD with the entire population distributed scheme in terms of the speedup,and the quality of solutions of MOEA/CD with the entire population distributed scheme is obviously better than MOEA/D with the partial population island distributed scheme when solving the layout problem of WSN.