MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Bringmann, Karl
Friedrich, Tobias		dblp
dblp
Editor(s):
Krasnogor, Natalio
Lanzim, Pier Luca		dblp
dblp
Not MPII Editor(s):
Krasnogor, Natalio
Lanzim, Pier Luca
BibTeX cite key*:
BringmannF2011
Title, Booktitle
Title*:
Convergence of Hypervolume-Based Archiving Algorithms I: Effectiveness
Booktitle*:
GECCO 2011 : Genetic and Evolutionary Computation Conference
Event, URLs
Conference URL::
http://www.sigevo.org/gecco-2011/
Downloading URL:
http://doi.acm.org/10.1145/2001576.2001678
Event Address*:
Dublin, Ireland
Language:
English
Event Date*
(no longer used):
Organization:
 SIGEVO ACM Special Interest Group on Genetic and Evolutionary Computation
Event Start Date:
12 July 2011
Event End Date:
16 July 2011
Publisher
Name*:
ACM
URL:
http://www.acm.org
Address*:
New York, NY
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
Pages:
745-752
Year*:
2011
VG Wort Pages:
8
ISBN/ISSN:
978-1-4503-0557-0
Sequence Number:
DOI:
10.1145/2001576.2001678
Note, Abstract, ©
(LaTeX) 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.
Keywords:
Archiving Algorithms, Hypervolume Indicator, Multiobjective Optimization
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{BringmannF2011,
AUTHOR = {Bringmann, Karl and Friedrich, Tobias},
 EDITOR = {Krasnogor, Natalio and Lanzim, Pier Luca},
 TITLE = {Convergence of Hypervolume-Based Archiving Algorithms {I}: {Effectiveness}},
 BOOKTITLE = {GECCO 2011 : Genetic and Evolutionary Computation Conference},
 PUBLISHER = {ACM},
 YEAR = {2011},
 ORGANIZATION = { SIGEVO ACM Special Interest Group on Genetic and Evolutionary Computation},
 PAGES = {745--752},
 ADDRESS = {Dublin, Ireland},
 ISBN = {978-1-4503-0557-0},
 DOI = {10.1145/2001576.2001678},
}

Entry last modified by Anja Becker, 03/19/2012
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
01/13/2012 03:07:41 PM
Revisions
2.
1.
0.

Editor(s)
Anja Becker
Anja Becker
Karl Bringmann

Edit Dates
19.03.2012 08:54:39
01.02.2012 14:45:49
13.01.2012 15:07:41