Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

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

Action:

login to update

Options:




Library Locked Library locked




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



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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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

Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section