Selection Indicators Based on Local Volume in Objective Space for Many-Objective Optimization

When solving Many-objective Optimization Problems (MaOPs), selection strategies are very important for Evolutionary Algorithms (EAs) and affect great influence to optimization result. The selection strategy is required to improve convergence while maintaining the diversity of the solution set or the population. This paper proposes two novel selection indicators, hyper volume difference and hyper conical volume, for Many-objective Optimization Evolutionary Algorithms (MaOEAs). NSGA, one of the MaOEAs, ranks the solutions using non-dominated sorting, which is a very powerful selection strategy to fill in a population within a predetermined number of solutions, and then selects the remaining solutions to fill the free space of the population using additional selection. However, when the number of objectives is large, the non-dominated sorting cannot determine the superiority of the solutions, and in the end, optimization is often performed by repeating only the additional selections. In such a case, the selection indicator of the additional selection greatly infuences or failure of the optimization. NSGA-II effectively solve multi-objective optimization problems (MOPs) which has less than or equal to three objectives by using crowding distance in the target front set as an indicator in the additional selection, but it does not work effectively for MaOPs which has four or more objectives. On the other hand, NSGA-III performs niche selection based on a large number of uniformly distributed reference points in the additional selection, allowing the optimization to proceed effectively while sustaining high diversity of the population, but consuming huge amount of computation cost. In order to reduce the computational cost, the proposed selection indicators are based on the hyper volume difference and the hyper conical volume of the search points of the target front set respectively. NSGA with the proposed indicators in its additional selection, NSGA-II and NSGA-III are applied to well-known many-objective test problems and verify the effectiveness.