Efficient Real-Time Hypervolume Estimation with Monotonically Reducing Error
Fieldsend, JE
Date: 13 July 2019
Conference paper
Publisher
Association for Computing Machinery (ACM)
Publisher DOI
Related links
Abstract
The hypervolume (or S-metric) is a widely used quality measure
employed in the assessment of multi- and many-objective evolutionary algorithms. It is also directly integrated as a component in
the selection mechanism of some popular optimisers. Exact hypervolume calculation becomes prohibitively expensive in real-time
applications ...
The hypervolume (or S-metric) is a widely used quality measure
employed in the assessment of multi- and many-objective evolutionary algorithms. It is also directly integrated as a component in
the selection mechanism of some popular optimisers. Exact hypervolume calculation becomes prohibitively expensive in real-time
applications as the number of objectives increases and/or the approximation set grows. As such, Monte Carlo (MC) sampling is often
used to estimate its value rather than exactly calculating it. This
estimation is inevitably subject to error. As standard with Monte
Carlo approaches, the standard error decreases with the square
root of the number of MC samples. We propose a number of realtime hypervolume estimation methods for unconstrained archives
— principally for use in real-time convergence analysis. Furthermore, we show how the number of domination comparisons can be
considerably reduced by exploiting incremental properties of the
approximated Pareto front. In these methods the estimation error
monotonically decreases over time for (i) a capped budget of samples per algorithm generation and (ii) a fixed budget of dedicated
computation time per optimiser generation for new MC samples.
Results are provided using an illustrative worst-case scenario with
rapid archive growth, demonstrating the orders-of-magnitude of
speed-up possible.
Computer Science
Faculty of Environment, Science and Economy
Item views 0
Full item downloads 0