An Evolutionary Many-Objective Algorithm Based on a Novel Tournament Selection Strategy ()
1. Introduction
It is undoubted that the multi-objective optimization technology is a research which engineers pay a lot of attention to [1]. Without loss of generality, multi-objective optimization problems (MOPs) involve two or more conflicting objectives to be optimized, which can be formulated as follows:
(1)
where
is the decision space, m is the number of objectives, and
represents the objective function. It is worth noting that optimization problems involving a high number of objectives indeed appear widely in real-world applications. Specially, if an MOP has more than three objectives, it is often known as a many-objective optimization problem (MaOP) [2]. As shown in Equation (1), we can find that MOP/MaOP involves multiple conflicting objectives to be optimized. Therefore, MOPs do not have single optimal solution that can optimize all the objectives and are usually replaced by a set of trade-off solutions. With the great success of evolutionary algorithms in recent years, a variety of promising multi-objective evolutionary algorithms (MOEAs) have been developed, such as NSGA-III [3], MOEA/D [4], and IBEA [5]. According to different computing strategies, these algorithms can be roughly classified into three categories.
The first category directly adopts Pareto dominance to distinguish and select candidate solutions. NSGA-II [6] and SPEA2 [7] are two representative MOEAs of this type, where all non-dominated solutions are first identified and then enter next generation population. Another idea belonging to this category is to combine the Pareto dominance with a new metric, and MOEAs belonging to this category include the SPEA/R [8], NSGA-II/SDR [9] and PREA [10].
The second category covers various indicator-based MOEAs. This strategy generally uses a performance indicator of solution quality measurement to select solutions from current population for the next generation. Some representative approaches of this category are indicator-based evolutionary algorithm [11], S-metric selection based evolutionary multi-objective optimization algorithm [12], and indicator-based evolutionary algorithm.
The third category is known as the decomposition-based MOEAs, which convert an MOP to a number of single-objective optimization problems (SOPs) and simultaneously solve them in a collaborative manner. MOEA/D is a representative of this class of metaheuristics. In MOEA/D, Das and Dennis’s [13] systematic approach is adopted to construct a set of weight vectors. Then, MOEA/D employs decomposition function to decompose a high-dimensional problem into a number of scalarized sub-problems to be solved collaboratively. Furthermore, the decomposition-based idea has also been exploited in some recently developed MOEAs, such as MOEA/D-CMA and ENS-MOEA/D.
Although the existing MOEAs have shown competitive performance in solving MOPs, it is difficult to tackle MaOPs. The one reason for the poor convergence performance of the existing MOEAs is that the random mating selection loses its search efficiency in solving MaOPs. This strategy of generating offspring has certain randomness, which may leads to a severe deterioration of the performance when the number of redundant objectives increases. To address this issue, we propose in this paper an evolutionary many-objective algorithm based on a novel tournament selection strategy for handling MaOPs, called NTSEA. The main contributions of this article are highlighted as in the following:
1) In NTSEA, a novel tournament selection strategy is proposed, we exploit a novel binary tournament selection strategy by grid dominance relation and density information to select individuals for variation.
2) Based on the proposed framework, a novel MOEA is proposed by adopting general MOEA as the optimizer for evolving the populations. To assess the performance of the proposed method, we compared the NTSEA with several state-of-the-art approaches on a set of benchmark problems. Case studies and experimental results demonstrate that the proposed method has good robustness for general MaOPs.
The remainder of this paper is organized as follows. Section 1 briefly reviews the previous work. In Section 2, we describe the proposed NTSEA framework. The experimental results and discussion are presented in Section 3. Finally, we conclude the project in Section 4.
2. Proposed Framework
2.1. Main Procedure of NTSEA
Algorithm 1 gives the framework of NTSEA. The basic procedure of the algorithm is similar to most generational many-objective algorithms like [14]. Firstly, N solution are randomly generated to form an initial population P and generate N uniformly distributed m dimensional unit vectors Z. Then, the grid environment for the current population P, and the fitness of solution in P is assigned according to their location in the grid. Next, select solution with a large fitness value from the population for mating selection to generate a mating pool MP and
perform cross mutation to generate offspring P'. Finally, the environmental selection procedure is used to record N best solution from the combined group Q.
2.2. Mating Selection
Mating selection usually forms a mating pool by selecting promising solutions from the current population. In this paper, a selection strategy based on grid dominance relationship and density information is used to select the solution by cross mutation. Algorithm 2 gives the detailed steps of this strategy. First, two solutions
and
are randomly selected from the population. If one Pareto dominates or the grid dominates the other, choose the former. Otherwise, it means that these two solutions are both non-dominated relations in the Pareto dominance relationship and the grid dominance relationship. In this case, we choose a solution with a lower density estimate (i.e., grid crowding distance (GCD)). Specifically, the density estimator, GCD, of x is defined as
(2)
where
represents the set of grid neighborhoods of x.
represents the grid difference between x and y. Finally, if GCD still cannot distinguish between the two solutions, one of them is randomly selected.
2.3. Environmental Selection
Algorithm 3 gives the main steps of environment selection. First adopt Pareto dominance as the selection criterion, perform non-dominated sorting on the merged population Q to obtain the Pareto front of the population. Then judge whether the population size satisfies N according to the l-th critical layer, if yes, return directly to the former l-th solution. Otherwise, first extract the first
layer solution. Then l-th level solution is associated with the nearest reference vector Z, the distance between the solution and the reference is calculated, and
closest solution are selected to maintain the population size and maintain the diversity of the population.
3. Performance Evaluation
To empirically investigate the effectiveness of the proposed NTSEA, we compare it with the following four representative algorithms: 1) MOEA/D [4]; 2) KnEA [15]; 3) RVEA [16]; and 4) RMMEDA [17].
3.1. Experimental Settings
In the experiment, the WFG test problem set whose target number can be expanded arbitrarily is used. This paper studies the cases where M is 3, 5, 8, and 10. The number of WFG decision variables is set to
, where
is the number of position-related variables, and
is the number of distance-related variables.
The genetic operator that generates offspring in the experiment uses simulated binary crossover (SBX) and polynomial mutation (PM). The termination condition of each run is the maximum algebra. For all test problems with any target number, the maximum algebra is set to 1000. In the experimental research, the inverted generational distance (IGD) is used as the evaluation index. The IGD index is defined as the average of the sum of the distances between each reference point and its nearest individual. The formula is defined as follows:
(3)
In the formula,
represents the Euclidean distance between the individual and the reference point. The population solution obtained by the algorithm are denoted as
,
is a set of reference points obtained by uniform sampling of the real Pareto front surface, and
is the size of the population distributed on the real Pareto front surface. The smaller the value of IGD is, the closer the obtained population solution are to the true Pareto front, and the more even the individual distribution is. The IGD index can evaluate both convergence and diversity.
All algorithms were run independently on each test problem 20 times, and the results obtained by the NTSEA algorithm and other comparison algorithms were compared using the Wilcoxon rank sum test method, in which the significance level of the mean analysis was set to 5%. According to the Wilcoxon rank sum test method, “+” means that the result of the comparison algorithm is better than NTSEA, “−” means that the result of the comparison algorithm is inferior to NTSEA, and “=” means that there is no significant difference between the result of the comparison algorithm and NTSEA.
3.2. Experimental Results and Analysis
In this experiment, select WFG1-WFG9 to evaluate the performance of the algorithm, and combine it with Table 1 for specific analysis. As shown in Table 1, we can find that the proposed NTSEA produced the competitive results compared with the other state-of-the-art approaches. For example, we win the best or is comparable with the best on 20 out of the 36 test instances. Since IGD is a direct indicator of population diversity and convergence, the comparison of IGD values shows that the NTSEA proposed in this paper has excellent performance in terms of convergence and diversity. WFG1 has a flat deviation and a mixed structure of Pareto front, and the performance of NTSEA is generally good. WFG2 has a disconnected Pareto front. In this test problem, NTSEA outperforms other algorithms in the 3-objective, 8-objective and 10-objective test cases. The Pareto front of WFG3 is linear and degraded, and NTSEA is not effective in dealing with the test problem of Pareto front degradation. The remaining 6 test problems have the same Pareto front in the target space, but the design in the
Table 1. Comparison algorithm run 20 times independently on the WFG test problem set to obtain a unified result (mean and standard deviation) of the IGD value.
“+” indicates that the algorithm is superior to NTSEA, “−” is inferior to NTSEA, and “=” indicates that the performance is similar to NTSEA
decision variable space has different difficulties. It can be found that NTSEA achieves the best performance in WFG4-WFG9 test questions 3-objective and 8-objective, RVEA is better at 10-objective, and NTSEA shows a certain degree of competitiveness. Figure 1 plots their output with the smallest IGD value in 20 runs on the 5-objective WFG7 in parallel coordinates. It can be seen from Figure 1 that all algorithms can converge to Pareto front, and for diversity, NTSERA is superior to other algorithms in diversity in the 5-objective WFG test problem. Therefore, based on the above analysis, it is concluded that NTSEA has significant performance in processing MaOPs, and can still maintain the performance of the algorithm in different target test cases, and has good universality.
4. Conclusion
In this paper, we have proposed a novel tournament selection strategy based on the grid dominance relation and density information. Based on this strategy, we have implemented an algorithm called NTSEA for handling MaOPs. In the proposed NTSEA, the grid dominance is introduced to compare individuals in the mating selection processes. In this way, we can ensure that the well-converged and well-distributed solutions enter the matching pool to generate promising offspring solutions. We ran our NTSEA algorithm on the WFG test problems to conduct a comprehensive comparison with several state-of-the-art approaches. The experimental results have shown that the proposed NTSEA is competitive compared with other algorithms in terms of the diversity of solutions and convergence speed, especially with the significant benefit of high-dimensional objective space handling.
In the future, we will further enhance the performance of NTSEA and apply it to some real-world problems, such as optimization of deep neural networks and path planning of robots.
Acknowledgements
The authors would like to thank the anonymous reviewers for their valuable suggestions on improving this paper. Additionally, this work is supported in part by the National Natural Science Foundation of China (61866026, 61772255, 61866025 and 62066031), the Natural Science Foundation of Jiangxi Province (20181BAB202025), the Advantage Subject Team Project of Jiangxi Province (20165BCB19007), the Aeronautical Science Foundation of China (2018ZC56008), the Outstanding Young Scientist Project of Jiangxi Province (20192BCB23011).