A Grid-Based Inverted Generational Distance for Multi/Many-Objective Optimization
Xinye Cai, Yushun Xiao, Miqing Li, Han Hu, Hisao Ishibuchi, Xiaoping Li
Abstract
Assessing the performance of Pareto front (PF) approximations is a key issue in the field of evolutionary multi/many-objective optimization. Inverted generational distance (IGD) has been widely accepted as a performance indicator for evaluating the comprehensive quality for a PF approximation. However, IGD usually becomes infeasible when facing a real-world optimization problem as it needs to know the true PF a priori. In addition, the time complexity of IGD grows quadratically with the size of the solution/reference set. To address the aforementioned issues, a grid-based IGD (Grid-IGD) is proposed to estimate both convergence and diversity of PF approximations for multi/many-objective optimization. In Grid-IGD, a set of reference points is generated by estimating PFs of the problem in question, based on the representative nondominated solutions of all the approximations in a grid environment. To reduce the time complexity, Grid-IGD only considers the closest solution within the grid neighborhood in the approximation for every reference point. Grid-IGD also possesses other desirable properties, such as Pareto compliance, immunity to dominated/duplicate solutions, and no need of normalization. In the experimental studies, Grid-IGD is verified on both the artificial and real PF approximations obtained by five many-objective optimizers. Effects of the grid specification on the behavior of Grid-IGD are also discussed in detail theoretically and experimentally.