Runtime analysis of a multi-objective evolutionary algorithm for obtaining finite approximations of Pareto fronts

Previous theoretical analyses of evolutionary multi-objective optimization (EMO) mostly focus on obtaining epsilon-approximations of Pareto fronts. However, in practical applications, an appropriate value of epsilon is critical but sometimes, for a multi-objective optimization problem (MOP) with unknown attributes, difficult to determine. In this paper, we propose a new definition for the finite representation of the Pareto front the adaptive Pareto front, which can automatically accommodate the Pareto front. Accordingly, it is more practical to take the adaptive Pareto front, or its epsilon-approximation (termed the epsilon-adaptive Pareto front) as the goal of an EMO algorithm. We then perform a runtime analysis of a (mu + 1) multiobjective evolutionary algorithm ((mu + 1) MOEA) for three MOPs, including a discrete MOP with a polynomial Pareto front (denoted as a polynomial DMOP), a discrete MOP with an exponential Pareto front (denoted as an exponential DMOP) and a simple continuous two-objective optimization problem (SCTOP). By employing an estimator-based update strategy in the (mu + 1) MOEA, we show that (1) for the polynomial DMOP, the whole Pareto front can be obtained in the expected polynomial runtime by setting the population size mu equal to the number of Pareto vectors; (2) for the exponential DMOP, the expected polynomial runtime can be obtained by keeping mu increasing in the same order as that of the problem size n; and (3) the diversity mechanism guarantees that in the expected polynomial runtime the MOEA can obtain an epsilon-adaptive Pareto front of SCTOP for any given precision epsilon. Theoretical studies and numerical comparisons with NSGA-II demonstrate the efficiency of the proposed MOEA and should be viewed as an important step toward understanding the mechanisms of MOEAs. (C) 2013 Elsevier Inc. All rights reserved.