Properties of an adaptive archiving algorithm for storing nondominated vectors

By Joshua D. Knowles, David Wolfe Corne. IEEE Transactions on Evolutionary Computation, 2003

322 citations recorded by the source corpus.

Search algorithms for Pareto optimization are designed to obtain multiple solutions, each offering a different trade-off of the problem objectives. To make the different solutions available at the end of an algorithm run, procedures are needed for storing them, one by one, as they are found. In a simple case, this may be achieved by placing each point that is found into an "archive" which maintains only nondominated points and discards all others. However, even a set of mutually nondominated points is potentially very large, necessitating a bound on the archive's capacity. But with such a bound in place, it is no longer obvious which points should be maintained and which discarded; we would like the archive to maintain a representative and well-distributed subset of the points generated by the search algorithm, and also that this set converges. To achieve these objectives, we propose an adaptive archiving algorithm, suitable for use with any Pareto optimization algorithm, which has various useful properties as follows. It maintains an archive of bounded size, encourages an even distribution of points across the Pareto front, is computationally efficient, and we are able to prove a form of convergence. The method proposed here maintains evenness, efficiency, and cardinality, and provably converges under certain conditions but not all. Finally, the notions underlying our convergence proofs support a new way to rigorously define what is meant by "good spread of points" across a Pareto front, in the context of grid-based archiving schemes. This leads to proofs and conjectures applicable to archive sizing and grid sizing in any Pareto optimization algorithm maintaining a grid-based archive.

Subfields: Computational Theory and Mathematics, Management Science and Operations Research, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/5c3ab76c70a6b0591d1a3a386788f54eb7a1ffea

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Management Science and Operations Research

In Numerical Analysis

Citations in the corpus

HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization (2011, unknown): “Most hypervolume-based algorithms ﬁrst perform a nondominated sorting and then rank solutions within a particular front according to the hypervolume loss that results from the removal of a speciﬁc solution (Knowles and Corne, 2003; Emmerich et al., 2005; Igel et al., 2007; Bader et al., 2008).”
Using the Averaged Hausdorff Distance as a Performance Measure in Evolutionary Multiobjective Optimization (2012, background): “There are, for instance, fitness sharing schemes [10], [19], clustering [48], the adaptive grid [26], [27], the crowded-comparison operator [11], and entropy [6], [16], [17], among others.”
Approximating the Set of Pareto-Optimal Solutions in Both the Decision and Objective Spaces by an Estimation of Distribution Algorithm (2009, methodology): “Experimental Settings and Algorithms in Comparison The studies in [23], [27], [28] have shown that popular MOEAs, such as PAES [34], NSGA-II [26], and SPEA2 [35], cannot approximate both the PF and the PS simultaneously since these methods cannot maintain the population diversity in the decision spa”
Theory of the hypervolume indicator: optimal μ-distributions and the choice of the reference point (2009, background): “Hence, the distributions of points can diﬀer highly from a well-distributed set of points suggested in [16].”
MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition (2007, background): “Of course, other sophisticated strategies [21] for updating”
A Fast Way of Calculating Exact Hypervolumes (2012, background): “Hypervolume is also increasingly used in-line in multiobjective evolutionary algorithms, either to promote diversity [6], or as part of an archiving mechanism [7], [8], or as part of the selection process [9], [10].”
SMS-EMOA: Multiobjective selection based on dominated hypervolume (2007, methodology): “Knowles and Corne showed that the AAS strategy converges to a subset of the true Pareto front.”
Multiple Populations for Multiple Objectives: A Coevolutionary Technique for Solving Multiobjective Optimization Problems (2013, methodology): “This archive is used not only to store the nondominated solutions to be reported at the end of the evolution like in the traditional MOP algorithm [39] but also for information sharing among different swarms.”
An EMO Algorithm Using the Hypervolume Measure as Selection Criterion (2005, methodology): “Our SMS-EMOA combines ideas borrowed from other EMOA, like the well established NSGA-II [11] and archiving strategies presented by Knowles, Corne, and Fleischer [5] [6].”
A faster algorithm for calculating hypervolume (2006, background): “The most natural base case for HSO is when the points are reduced to one objective, when there can be only one nondominated point left in each slice.”
Many-Objective Evolutionary Algorithms (2015, background): “However, it should be noted that individually centered calculation of grids cannot guarantee convergence and thus will suffer from potential deterioration, which is a serious drawback in the context of many-objective optimization [Knowles and Corne 2003b].”
A Grid-Based Evolutionary Algorithm for Many-Objective Optimization (2013, methodology): “Accordingly, the originalM -dimensional objective space will be divided into divM hyperboxes.”