Bounding the Effectiveness of Hypervolume-Based (μ+λ)-Archiving Algorithms

摘要

In this paper, we study bounds for the a-approximate effectiveness of non-decreasing (μ+λ)-archiving algorithms that optimize the hypervolume. A (μ+λ)-archiving algorithm defines how μ individuals are to be selected from a population of μ, parents and λ offspring. It is non-decreasing if the μ new individuals never have a lower hypervolume than the μ original parents. An algorithm is a-approximate if for any optimization problem and for any initial population, there exists a sequence of offspring populations for which the algorithm achieves a hypervolume of at least 1/α times the maximum hypervolume. Bringmann and Friedrich (GECCO 2011, pp. 745-752) have proven that all non-decreasing, locally optimal (μ + l)-archiving algorithms are (2 + ε)-approximate for any ε > 0. We extend this work and substantially improve the approximation factor by generalizing and tightening it for any choice of λ to α = 2 - (λ - p)/μ with μ= q·λ - p and 0 ≤ p ≤ λ - 1. In addition, we show that 1 + 1/2λ - 5, for λ < μ and for any δ > 0, is a lower bound on α, i.e. there are optimization problems where one can not get closer than a factor of 1/α to the optimal hypervolume.