# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Convergence of Hypervolume-Based Archiving Algorithms I: Effectiveness

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Bringmann, K., & Friedrich, T. (2011). Convergence of Hypervolume-Based Archiving
Algorithms I: Effectiveness. In N. Krasnogor, & P. L. Lanzim (*GECCO
2011* (pp. 745-752). New York, NY: ACM. doi:10.1145/2001576.2001678.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0010-120B-F

##### Abstract

The core of hypervolume-based multi-objective evolutionary algorithms is an
archiving algorithm which performs the environmental selection. A (μ+λ)-
archiving algorithm defines how to choose μ children from μ parents and λ
offspring together. We study theoretically (μ+λ)-archiving algorithms which
never decrease the hypervolume from one generation to the next.
Zitzler, Thiele, and Bader (IEEE Trans. Evolutionary Computation, 14:58-79,
2010) proved that all (μ+1)-archiving algorithms are ineffective, which means
there is an initial population such that independent of the used reproduction
rule, a set with maximum hypervolume cannot be reached. We extend this and
prove that for λ<μ all archiving algorithms are ineffective. On the other hand,
locally optimal algorithms, which maximize the hypervolume in each step, are
effective for λ=μ and can always find a population with hypervolume at least
half the optimum for λ<μ.
We also prove that there is no hypervolume-based archiving algorithm which can
always find a population with hypervolume greater than 1/(1+0.1338(1/λ-1/μ))
times the optimum.