Tight bounds for the approximation ratio of the hypervolume indicator

摘要: The hypervolume indicator is widely used to guide the search and evaluate performance of evolutionary multi-objective optimization algorithms. It measures volume dominated portion objective space which considered give a good approximation Pareto front. There surprisingly little theoretically known about quality this approximation. We examine multiplicative ratio achieved by two-dimensional sets maximizing prove that it deviates significantly from optimal ratio. This provable gap even exponential in between largest smallest value also additive achieves apart small factor ≤ n/(n - 2), where n size population. Hence can be achieve very but not