Applying the WFG algorithm to calculate incremental hypervolumes

Hypervolume is increasingly being used in-line in multi-objective evolutionary algorithms, either to promote diversity, or in an archiving mechanism, or in the selection process. The usual requirement is to determine which point in a set contributes least to the hypervolume of the set, so that that point can be discarded. We describe a new exact algorithm IWFG for performing this calculation that combines two important features from other recent algorithms: the bounding trick from WFG, that accelerates calculations by generating lots of dominated points; and the best-first queuing mechanism from IHSO, that eliminates much of the calculation for most of the points in a set. Empirical results show that IWFG is significantly faster than IHSO on much experimental data in five or more objectives.