Region Division Based Many-objective Evolutionary Algorithms And Its Application

Evolutionary algorithm is a random searching algorithm that simulates natural selection and natural evolution. It is widely used in solving highly complex nonlinear problems and has better generality. In solving the problem of complex optimization problems with few objectives, the advantages of the evolutionary algorithm are fully demonstrated. However, in real life, the optimization problem is usually related to many-objectives(more than three).In this case, the many-objective evolutionary algorithm came into being.Based on the background above, this paper proposes a many-objective evolutionary algorithm based on correlation selection and a many-objective evolutionary algorithm based on region division. In addition, a modified version of the many-objective evolutionary algorithm based on region division is used to deal with knapsack problem. The main work of this paper is as follows:1. A decomposition-based evolutionary algorithm with correlative selection mechanism for many-objective optimization is proposed. Firstly, the correlation between the reference point and the individual is given. Then, a correlation based mutation selection mechanism is proposed. The mechanism ensures the population diversity by the number of correlated individuals that each reference point owns. Finally, a correlation based population update mechanism is proposed. This mechanism ensures the population converges to true Pareto front through scalaring function while it further maintains the diversity of population. Through the test of the DTLZ1, DTLZ2, DTLZ3 and DTLZ4 problems having three to fifteen objectives, experimental results show that the new algorithm has a great competition compared with NSGA-III algorithm and MOEA/D in terms of IGD metric, and its running time is more less than that of two other algorithms.2. A region division based decomposition approach for evolutionary many-objective optimization is proposed. Firstly, the objective space is decomposed into a set of sub-regions, and two important attributes are assigned for each sub-region. Then, the selection mechanism based on attributes of regions is proposed, and this mechanism ensures population diversity by selecting individuals located in sparser regions. Finally, population updated mechanism based on attributes of regions is proposed, and this mechanism ensures population convergence through scalaring function. The new algorithm is applied to a set of many-objective optimization problems along with NSGA-III and MOEA/D. Experimental results show the new algorithm can obtain the best results in almost all test problems, while the two compared algorithms only can achieve good results in some problems.3. A many-objective evolutionary algorithm for knapsack problems is proposed. It is extended from the region division based decomposition approach for evolutionary many-objective optimization. In this improved algorithm, when the first individual to be mutated is chosen, the predetermined probability value determines the way of the other individual chosen for mutation: from the neighboring individuals of the first individual or from the overall population. In order to deal with combinatorial optimization problems, we have mapped reference points to the region near the optimal Pareto front. By testing the knapsack problems of 250, 500 and 750 elements and 2, 3 and 4 objectives, the experimental results show that the new algorithm is better than MOEA/D in all the test problems in terms of diversity while it is better than MOEA/D in most test problems in terms of convergence. In addition, the robustness of the new algorithm is better than that of MOEA/D.