Research And Implementation Of Parallel Decomposition-based On Multiobjective Evolutionary Algorithms Using MPI+Open MP

There widely exist multi-objective optimization problems(MOPs) which involve simultaneous optimization of two or more objectives in the real world. Since the set of Pareto optimal solutions of a MOP includes many solutions and evolutionary algorithms(EAs) can simultaneously search many solutions, EAs are well suited for solving MOPs in essence. Nowadays, a multiobjective evolutionary algorithm based decomposition(MOEA/D) combines the decompose idea from traditional mathematical programming and EAs in a better way. In MOEA/D, a MOP is composed into a series of scalar optimization subproblems and each individual in the population is responsible for optimizing only one subproblem. Therefore, MOEA/D performs much better than the EAs based on Pareto dominance in both the running efficiency and the solution quality. However, when a MOP involes objective functions with high computational costs, the standard MOEA/D algorithm can not obtain the Pareto set with high quality within a reasonable time. Furthermore, a significant way of reducing its running time is to parallelize MOEA/D.In this paper, multi-objective evolutionary algorithm decomposition MOEA/D in solving complex multi-objective optimization problem running high time cost, the main research and design of two-goal as well as high-dimensional target space MOEA/D algorithm two asynchronous parallel versions of MOEA/D, which are respectively based on local populations in the bi-objective space and global populations in higher dimensional objective spaces, are research and designed in order to reduce the running time of MOEA/D. Besides, the performances of the two parallel versions are evaluated on some benchmark test problems as well as a wireless sensor network layout problem. The main research contents of this paper can be summarized as follows:1. A parallel MOEA/D version with overlapping local populations and asynchronous migration under MPI parallel environment is designed by utilizing the simple linear neighbor structure of scalar sub-problems in the bi-objective space. First, the global population is divided into non-overlapping sub-populations is calculated according to the number of nodes and each node is responsible for the evolution of only its sub-population. Then some overlapping neighbor individuals are appended to the margins of each sub-population in order to complete individual updating operations. Finally, the updated reference points of each sub-population emigrate to its adjacent sub-populations to avoid the frontier breakage resulted by the narrow search space. Experimental results on benchmark test problems including ZDT and DTLZ show that this parallel MOEA/D version with local populations achieves high speedup ratios without any significant decline of solution quality in the biobjective space.2. The above parallel MOEA/D version with overlapping local populations and asynchronous migration is not suitable for the more complex nonlinear neighbor structure in higher dimensional objective spaces. Therefore, a universal parallel MOEA/D version with global populations, partial evolution and asynchronous migration in both the biobjective space and higher dimensional objective spaces under the MPI parallel environment is further designed. In this version, a global population on each node is maintained in order to handle the complex nonlinear neighbor structure in higher dimensional objective spaces. Each node is responsible for the evolution of only the partial population and the search of only the partial front, which increases the diversity between populations. Finally, the updated reference points of each node also emigrate to its adjacent nodes. Experimental results on benchmark test problems including ZDT and DTLZ show that this parallel MOEA/D version with global populations achieves high speedup ratios without any significant decline of solution quality not only in the biobjective space but also in higher dimensional objective spaces. Moreover, it achieves the significantly better front quality than the serial version on some test instances.3. The above parallel MOEA/D parallel versions based on local populations and global populations are implemented under the MPI+Open MP parallel environment where the process-level parallelism between nodes is done by the use of MPI while the internal thread-level parallelism within a multicore node is done by the use of Open MP. Only the loop parts with high complexities are handled by the Open MP thread-level parallelism. Experimental results on a cluster with quad-core nodes show that the speedup ratios of the parallel versions under the MPI+Open MP environment are as about twice high as those under only the MPI environment with nearly the same solution quality.4. The layout of wireless sensor network is a typical MOP which involves the objectives such as the number of sensors and energy consumption with very high computational costs. In this paper, the parallel MOEA/D version with global populations under the MPI+Open MP environment is applied to the layout problem of wireless sensor network. Experimental results show that the parallel MOEA/D version with global populations achieves high speedup ratios and effectively reduces the running time of the serial MOEA/D version without any significant decline of solution quality on this problem.