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

In this paper, we study bounds for the

α

-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

α

-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 (

μ

 + 1)-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 + \frac{1}{2 \lambda}-\delta$

, 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.