English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 DetailsSummary
  Convergence of Hypervolume-based Archiving Algorithms II: Competitiveness

Bringmann, K., & Friedrich, T. (2012). Convergence of Hypervolume-based Archiving Algorithms II: Competitiveness. In GECCO'12 (pp. 457-464). New York, NY: ACM.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0014-BBD0-7 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0023-C001-7
Genre: Conference Paper

Files

show Files
hide Files
:
2012GECCO.pdf (Any fulltext), 259KB
 
File Permalink:
-
Name:
2012GECCO.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Bringmann, Karl1, Author           
Friedrich, Tobias1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2012
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1145/2330163.2330229
BibTex Citekey: BringmannF12
Other: Local-ID: 3CFCD4AF1F43FE47C1257AD300340FE6-BringmannF12
 Degree: -

Event

show
hide
Title: Fourteenth International Conference on Genetic and Evolutionary Computation
Place of Event: Philadelphia, PA
Start-/End Date: 2012-07-07 - 2012-07-12

Legal Case

show

Project information

show

Source 1

show
hide
Title: GECCO'12
  Abbreviation : GECCO 2012
  Subtitle : Proceedings of the Fourteenth International Conference on Genetic and Evolutionary Computation
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: New York, NY : ACM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 457 - 464 Identifier: ISBN: 978-1-4503-1177-9