On the efficient maintenance and updating of Pareto solutions when assigned objectives values may change
Fieldsend, Jonathan E.
Everson, Richard M.
University of Exeter
Usually when undertaking a multi-objective optimisation problem it is assumed that on evaluation of a design, the assigned objectives are fixed. This allows, for instance, domination comparisons to be undertaken just once to decide on whether a design should be categorised as an elite (non-dominated) solution, with the designation only removed if a new location is found to be better at a later time step. However, there are some situations where the objective vector assigned to a design may change at a later time point. This may be due to some global change in the environment (a dynamic problem), which effects all designs proposed thus far, however it can also be a change of objectives of a single solution in isolation. This may be due to for instance due to resampling in a noisy domain updating an estimate of objective values, or via an increased resolution of the objective evaluation (e.g. a finer mesh on a finite element analysis of a design, or different data instances for a classifier being tuned). How to efficiently maintain an elite archive when the assigned objectives are susceptible to change has not been confronted until this point. Although a number of data structures exist for efficiently maintaining and querying solutions, they assume that a domination relationship between two designs at time t, will persist at all future time steps. When this no longer holds, it is necessary to track dominated as well as non-dominated solutions as the search progresses, if we want to guarantee access to the best estimate of the non-dominated subset of solutions visited by an optimiser at any time step. Here we discuss different storage and query approaches which guarantee this, and propose a novel data maintenance regime based on chaining single domination links between all solutions evaluated at any time point to rapidly discern the non-dominated subset as solutions are reevaluated, and new design locations proposed. We detail the computational complexity of this approach, and compare the empirical performance of three different link selection protocols on simulated behaviour of set updates, mimicking a converging optimiser and a optimiser performing a random search, and where locations are resampled at random, or resampling based on their estimated non-dominance.
Computer Science, University of Exeter
Copyright © 2013 University of Exeter
NOTE: Version 1.1 is the more recent version (having some additional order of complexity analysis).
Technical Report No. 2013-12, Department of Computer Science, University of Exeter