A new dominance-relation metric balancing convergence and diversity in multi- and many-objective optimization

• Published in: Expert systems with applications 2019-11, Vol.134, p.14-27
• Main Authors: Bao, Chunteng, Xu, Lihong, Goodman, Erik D.
• Format: Article
• Language: English
• Subjects: Clustering; Complexity; Convergence; Decomposition; Diversity; Evolutionary algorithms; Genetic algorithms; Many-objective optimization; Multiple objective analysis; Pareto dominance; Pareto optimization
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2019.05.032

•A more structured metric is proposed to promote the balance between convergence and diversity in many-objective optimization.•A distance-based diversity maintenance scheme is used to each non-dominated front to maintain population diversity.•Make full use of the neighborhood information in mating selection, which significantly improves the efficiency of the algorithm.•At most one solution in each sub-region of current Pareto front is selected in selection operation, which improves the efficiency of the algorithm. Maintaining a good balance between convergence and diversity in many-objective optimization is a key challenge for most Pareto dominance-based multi-objective evolutionary algorithms. In most existing multi-objective evolutionary algorithms, a certain fixed metric is used in the selection operation, no matter how far the solutions are from the Pareto front. Such a selection scheme directly affects the performance of the algorithm, such as its convergence, diversity or computational complexity. In this paper, we use a more structured metric, termed augmented penalty boundary intersection, which acts differently on each of the non-dominated fronts in the selection operation, to balance convergence and diversity in many-objective optimization problems. In diversity maintenance, we apply a distance-based selection scheme to each non-dominated front. The performance of our proposed algorithm is evaluated on a variety of benchmark problems with 3 to 15 objectives and compared with five state-of-the-art multi-objective evolutionary algorithms. The empirical results demonstrate that our proposed algorithm has highly competitive performance on almost all test instances considered. Furthermore, the combination of a special mate selection scheme and a clustering-based selection scheme considerably reduces the computational complexity compared to most state-of-the-art multi-objective evolutionary algorithms.