Heuristics for Optimising the Calculation of Hypervolume for Multi-objective Optimisation Problems

Abstract

The fastest known algorithm for calculating the hypervolume of a set of solutions to a multi-objective optimization problem is the HSO algorithm (hypervolume by slicing objectives). However, the performance of HSO for a given front varies a lot depending on the order in which it processes the objectives in that front. We present and evaluate two alternative heuristics that each attempt to identify a good order for processing the objectives of a given front. We show that both heuristics make a substantial difference to the performance of HSO for randomly-generated and benchmark data in 5-9 objectives, and that they both enable HSO to reliably avoid the worst-case performance for those fronts. The enhanced HSO enable the use of hypervolume with larger populations in more objectives.