Tutorial: Use of External Archivers for Multi-objective Optimization
Date:
Presenters:
- Oliver Schütze, CINVESTAV-IPN, schuetze at cs.cinvestav.mx
- Carlos Hernández, IIMAS-UNAM, carlos.hernandez at iimas.unam.mx
Abstract
This tutorial aims to present an overview of several archiving strategies developed over the last years dealing with approximations of the solution sets of multi-objective optimization problems by evolutionary algorithms. More precisely, we will present and analyze several archiving strategies that aim for different finite size approximations either of the set of optimal solutions (Pareto set and front) as well as the set of approximate solutions of a given optimization problem. The convergence analysis will be done for a very broad framework that includes all existing evolutionary algorithms (along with other metaheuristics) and that will only use minimal assumptions on the process to generate new candidate solutions. As will be seen, already small changes in the design of the archivers can have significant effects on the respective limit archives. It is important to note that all of the archivers presented here can be coupled with any set-based multi-objective search algorithm, and that the resulting hybrid method takes over the convergence properties of the used archiver. This tutorial hence targets all algorithm designers and practitioners in the field of multi-objective optimization. We hope that the archivers can either be used to enhance their preferred search method or that they may be used as a starting point for the design of further archiving strategies that aim for different approximations of the solution set.
Topic overview
One can expect that the solution set of a continuous MOP with k objectives forms—at least locally—an object of dimension k − 1. That is, already for k = 2 objectives the Pareto set/front typically contains uncountably many solutions which represents a challenge for set based multi-objective solvers. The main task of most MOEAs is to evolve an entire finite set of elements—either only the population or the population plus an additional external archive—toward a suitable representation of the Pareto front. Unless only relatively few function calls are spent during the search it is not possible to store all or even only all promising (e.g., all non-dominated) candidate solutions that have been computed.
Instead, one has to make a selection of which points to keep and which ones to discard during the search in order to obtain a “suitable” representation of the solution set. This process is called archiving. We will give in this chapter a brief overview of the different archiving strategies in evolutionary multi-objective optimization.
Archiving strategies are used within every MOEA, but normally referred to as the process to select the elements out of the generated candidate solutions that build the new generation (or in short selection). There are three main classes of MOEAs: (i) dominance based, (ii) decomposition based, and (iii) indicator based MOEAs. For MOEAs within the classes (ii) and (iii) the selection is a rather straightforward task: for decomposition based MOEAs, the selection is simply done via considering the values of the scalarizing functions that are used for the decomposition (recall that one can expect one best value for each SOP). The population size is hence entirely determined by the number of chosen scalarizing functions. For indicator based MOEAs, one can always choose the subset P out of the candidate solutions as the next population that contains μ elements (μ being the population size) and that yields the best indicator value. By doing so, in both cases monotonicity in the sequence of archives is obtained. That is, no deterioration in the approximation quality will be observed during the run of the algorithm measured by the values of the scalarizing functions and the indicator values, respectively (assuming that neither the scalarizing functions nor the reference point/set for the performance indicator are changed). We stress that even if the selection process is straightforward for these algorithms, the use of an external archive may still be
The situation is more complicated for dominance based MOEAs due to the above described “curse of dimensionality”. Early MOEAs such as MOGA (Fonseca and Fleming 1993), NSGA (Srinivas and Deb 1994), and NPGA (Horn et al. 1994) followed the advice of Goldberg (Goldberg 1989) and have coupled non-dominated sorting together with niching techniques. None of the algorithms possesses any convergence properties due to missing elite preservation. A later generation of MOEAs, including SPEA (Zitzler and Thiele 1999), SPEA-II (Zitzler et al. 2002), PAES (Knowles and Corne 2000a), NSGA-II (Deb et al. 2002a), and most of their variants incorporated elite preservation in the selection strategy leading to a much better performance which helped to significantly increase the popularity of evolutionary multi-objective optimization.
However, still none of these methods converges in the mathematical sense which indicates that they still do not tap their full potential. In Deb (2001), a steady-state MOEA is presented that explicitly aims for uniformly spread solutions along the Pareto front. Though the numerical results that are presented are very promising, no convergence analysis is provided.
Though it is fair to say that convergence (in the mathematical sense) has played so far a rather minor role in the design of multi-objective evolutionary algorithms, there exist quite a few works that investigate archiving/selection strategies with respect to the limit behavior of the sequence of archives/populations they generate