A Running Performance Metric and Termination Criterion for Evaluating Evolutionary Multi- and Many-objective Optimization Algorithms

摘要

Researchers have spent a considerable effort in evaluating the goodness of a solution set obtained by an evolutionary multi-objective algorithm. However, most performance metrics assume that the knowledge of the exact Pareto-optimal set is available. Also, most metrics evaluate an algorithm’s performance based on the final solution set, which fails to capture their performance during intermediate generations. In this paper, we investigate a running performance metric which can be applied to measure the performance at any time during the algorithm execution and no true optimum needs to be known for computing the metric. In general, multi-objective algorithms either improve the convergence based on the dominance relation or the diversity in the solution set. Our proposed running metric makes use of this fact by keeping track of the indicators regarding the extreme points and the ND solution set each generation and derives measures of convergence and diversity. Moreover, by introducing a threshold and comparing the values of indicators a set of termination criteria is also suggested. Finally, we demonstrate how our running performance metric can be used to compare multiple evolutionary multi-objective algorithms with each other. An implementation of the proposed methodology is available at pymoo, a multi-objective optimization framework: https://pymoo.org.