MPI-INF D1 Publications: Proceedings Article: Convergence of Hypervolume-Based Archiving Algorithms I: Effectiveness

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

Options:

Library locked

Goto entry point

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

URL of the conference:	http://www.sigevo.org/gecco-2011/
URL for downloading the paper:	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


(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

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

Attachment Section