An Evolutionary Algorithm Based on Minkowski Distance for Many-Objective Optimization

The existing multiobjective evolutionary algorithms (EAs) based on nondominated sorting may encounter serious difficulties in tackling many-objective optimization problems (MaOPs), because the number of nondominated solutions increases exponentially with the number of objectives, leading to a severe loss of selection pressure. To address this problem, some existing many-objective EAs (MaOEAs) adopt Euclidean or Manhattan distance to estimate the convergence of each solution during the environmental selection process. Nevertheless, either Euclidean or Manhattan distance is a special case of Minkowski distance with the order P = 2 or P = 1, respectively. Thus, it is natural to adopt Minkowski distance for convergence estimation, in order to cover various types of Pareto fronts (PFs) with different concavity-convexity degrees. In this paper, a Minkowski distance-based EA is proposed to solve MaOPs. In the proposed algorithm, first, the concavity-convexity degree of the approximate PF, denoted by the value of P, is dynamically estimated. Subsequently, the Minkowski distance of order P is used to estimate the convergence of each solution. Finally, the optimal solutions are selected by a comprehensive method, based on both convergence and diversity. In the experiments, the proposed algorithm is compared with five state-of-the-art MaOEAs on some widely used benchmark problems. Moreover, the modified versions for two compared algorithms, integrated with the proposed P-estimation method and the Minkowski distance, are also designed and analyzed. Empirical results show that the proposed algorithm is very competitive against other MaOEAs for solving MaOPs, and two modified compared algorithms are generally more effective than their predecessors.