Paper Info
Title
Runtime analysis of a multi-objective evolutionary algorithm for obtaining finite approximations of Pareto fronts
Abstract
Previous theoretical analyses of evolutionary multi-objective optimization (EMO) mostly focus on obtaining @?-approximations of Pareto fronts. However, in practical applications, an appropriate value of @? 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 @?-approximation (termed the @?-adaptive Pareto front) as the goal of an EMO algorithm. We then perform a runtime analysis of a (@m+1) multi-objective evolutionary algorithm ((@m+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 (@m+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 @m equal to the number of Pareto vectors; (2) for the exponential DMOP, the expected polynomial runtime can be obtained by keeping @m 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 @?-adaptive Pareto front of SCTOP for any given precision @?. 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.
Year
DOI
Venue
2014
10.1016/j.ins.2013.11.023
Inf. Sci.
Keywords
Field
DocType
finite approximation,multi-objective evolutionary algorithm,exponential dmop,runtime analysis,polynomial pareto front,whole pareto front,discrete mop,adaptive pareto front,exponential pareto front,pareto front,expected polynomial runtime,pareto vector,polynomial dmop
Mathematical optimization,Exponential function,Evolutionary algorithm,Polynomial,Multi-objective optimization,Artificial intelligence,Lomax distribution,Optimization problem,Machine learning,Mathematics,Pareto principle,Estimator
Journal
Volume
ISSN
Citations 
262,
0020-0255
5
PageRank 
References 
Authors
0.41
38
2
Name
Order
Citations
PageRank
Yu Chen151749.61
Xiufen Zou227225.44