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):
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
Conference URL::
http://www.sigevo.org/gecco-2012/
Downloading URL:
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
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