Research On Many-objective Dynamical Evolutionary Algorithms Based On GPU

In real world, multi-objective optimization problems are very common in science and engineering. However, in many practical multi-objective optimization problems, the number of objectives is often more than three.This kind of multi-objective optimization problem is called many-objective optimization problem.which is much more difficult than traditional multi-objective optimization problem. The reasons are as followings:On the one hand, when classic Pareto dominant strategy is used in a population of a many-objective optimization algorithm, the proportion of non-dominated objective vectors becomes very large as the number of objectives increases and there may be insufficient selective pressure to make progress in a given population, which results in convergence slowly and even stagnant. Therefore, multi-objective evolutionary algorithm degenerates into a completely random search algorithm. On the other hand. Preferences of the decision makers are not taken into account when Pareto domiant strategy is used in a population, and decision-makers can not give directions to the convergence of the algorithm. Thus decision support capabilities of non-inferior set are reduced for decision-makers, and the performance of the algorithm sharp decline. Therefore, many-objective optimization has recently become a research focus of evolutionary computation.In the traditional dynamics evolutionary algorithm, the individuals are regarded as particles of the phase space, and the population of each generation is viewed as a particle system. The traditional dynamics evolutionary algorithm mimics the mechanism of the particles of phase space in particle system to execute crossover and mutation operators, changing the mimicking particle system from non-equilibrium to equilibrium. This algorithm is effective and efficient for solving multi-objective optimization problems with2or3objectives. However, it is difficult to converge to the true Pareto front when using the traditional dynamics evolutionary algorithm to solve many-objective optimization problems, where the number of objectives is greater than3. The reasons for this are the following.(1) The Pareto front grows exponentially with the number of objectives, and thus the algorithm may converge slowly.(2) The search ability of the traditional dynamics evolutionary algorithm is limited especially for many-objective optimization problems.(3) The selection operators are either elite strategy or stochastic method, which make the algorithm premature or slow.(4) The complexity of computing the rank value of each individual in the traditional dynamics evolutionary algorithm is increasing with the size of population. In this dissertation, aiming at the weakness of the traditional dynamics evolutionary algorithm for solving many-objective optimization problems, the dominance mechanism, mutation operator and selection operator of the traditional dynamics evolutionary algorithm are analyzed and improved. Then these improved algorithms are implemented on GPU for solving many-objective optimization problems. The main research work and innovations of this dissertation are summarized as follows:(1) By analyzing the deficiency of the dominance mechanism in the traditional dynamics evolutionary algorithm for solving many-objective optimization problems, a many-objective optimization dynamics evolutionary algorithm based on Pareto-adaptive-grid E-dominance (EDAGEA) is proposed. In the proposed algorithm, it uses a slack Pareto-dominance, namely, Pareto-adaptive-grid E-dominance,which improves the selective pressure, and accelerates the convergence of the population as well as promotes the diversity of population. Experimental results indicate that the performance of EDAGEA for solving the test problems of DTLZ1. DTLZ2. DTLZ4. DTLZ6and DTLZ7is better than HN and MOPSO according to both convergence and diversity.(2) In order to improve the search ability of the traditional dynamics evolutionary algorithm for solving many-objective optimization problems, an enhanced dynamics evolutionary algorithm using an improved differential evolution mutation operator is presented. In the enhanced algorithm, global search is applied at the initial evolutionary stage, while local search is utilized at the later evolutionary stage. Thus, the proposed algorithm not only can obtain good global search capability, but also exhibits the fast convergence speed. Compared with HN and MOPSO. the proposed algorithm used for the test problems of DTLZ2. DTLZ3. DTLZ5and DTLZ7shows better performances in improving the convergence speed and maintaining the uniformity and diversity of the obtained solutions.(3) In order to enhance the selection strategy of the traditional dynamics evolutionary algorithm for solving many-objective optimization problems, an improved dynamics evolutionary algorithm with adaptive tournament selection strategy is proposed. In the proposed algorithm, the number of individuals selected by tournament selection strategy is adaptively determined by the evolutionary stage to maintain the diversity of population and to improve the search efficiency. Experiments are conducted on7test problems compared the proposed algorithm with HN and MOPSO. Experimental results indicate that the proposed algorithm for the test problems of DTLZ1,DTLZ2, DTLZ4, DTLZ5and DTLZ7obtain better performance in both the convergence and diversity of the solutions.(4) In general, the computational time of solving many-objective optimization problems is increasing as the objectives increase. In order to accelerate the convergence of the traditional the dynamics evolutionary algorithm for solving many-objective optimization problems. Three Algorithms including GPU-EDAGEA, GPU-MODDEA and GPU-CTSDEA are proposed. Experiments are conducted on7many-objective optimization test problems. The experimental results demonstrate that the proposed algorithms can drastically reduce the computational time under the premise of keeping as possible the convergence, uniformity and diversity. Under GPU hardware resource is used completely, GPU-EDAGEA obtained the speedup between14and22for DTLZ2. DTLZ4and DTLZ6. GPU-MODDEA obtained the speedup between18-27for DTLZ3and DTLZ5. GPU-CTSDEA obtained the speedup between16-24for DTLZ1and DTLZ7. The larger the number of the objectives, the greater the speedup of the algorithm.(5)Decision Map Method is used to visualize the approximate Pareto front of many-objective optimization problem. The approximate Pareto front is showed with colorful graphics and the moving slider of the scroll bar control. The performance of the algorithm is can be understood through the graphs.