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):





BibTeX cite key*:

BringmannF12

Title, Booktitle

Title*:

Convergence of Hypervolume-Based Archiving Algorithms II: Competitiveness

Booktitle*:

GECCO'12 : Proceedings of the Fourteenth International Conference on
Genetic and Evolutionary Computation

Event, URLs

URL of the conference:

http://www.sigevo.org/gecco-2012/

URL for downloading the paper:

http://doi.acm.org/10.1145/2330163.2330229

Event Address*:

Philadelphia, USA

Language:

English

Event Date*
(no longer used):


Organization:

Association for Computing Machinery (ACM)

Event Start Date:

7 July 2012

Event End Date:

11 July 2012

Publisher

Name*:

ACM

URL:

http://www.acm.org/

Address*:

New York, NY

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

457-464

Year*:

2012

VG Wort Pages:


ISBN/ISSN:

978-1-4503-1177-9

Sequence Number:


DOI:

10.1145/2330163.2330229



Note, Abstract, ©


(LaTeX) Abstract:

We study the convergence behavior of (μ+λ)-archiving algorithms. A (μ+λ)-archiving algorithm defines how to choose in each generation μ children from μ parents and λ offspring together. Archiving algorithms have to choose individuals online without knowing future offspring. Previous studies assumed the offspring generation to be best-case. We assume the initial population and the offspring generation to be worst-case and use the competitive ratio to measure how much smaller hypervolumes an archiving algorithm finds due to not knowing the future in advance. We prove that all archiving algorithms which increase the hypervolume in each step (if they can) are only μ-competitive. We also present a new archiving algorithm which is (4 + 2/μ)-competitive. This algorithm not only achieves a constant competitive ratio, but is also efficiently computable. Both properties provably do not hold for the commonly used greedy archiving algorithms, for example those used in SIBEA, SMS-EMOA, or the generational MO-CMA-ES.



Download
Access Level:

Internal

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{BringmannF12,
AUTHOR = {Bringmann, Karl and Friedrich, Tobias},
TITLE = {Convergence of Hypervolume-Based Archiving Algorithms {II}: Competitiveness},
BOOKTITLE = {GECCO'12 : Proceedings of the Fourteenth International Conference on
Genetic and Evolutionary Computation},
PUBLISHER = {ACM},
YEAR = {2012},
ORGANIZATION = {Association for Computing Machinery (ACM)},
PAGES = {457--464},
ADDRESS = {Philadelphia, USA},
ISBN = {978-1-4503-1177-9},
DOI = {10.1145/2330163.2330229},
}


Entry last modified by Uwe Brahm, 02/04/2013
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
12/13/2012 10:28:39 AM
Revisions
3.
2.
1.
0.
Editor(s)
Uwe Brahm
Uwe Brahm
Anja Becker
Karl Bringmann
Edit Dates
04-02-2013 06:04:13 PM
01-02-2013 02:54:19 PM
29.01.2013 12:43:57
13.12.2012 10:28:39