English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Convergence of Hypervolume-Based Archiving Algorithms I: Effectiveness

Bringmann, K., & Friedrich, T. (2011). Convergence of Hypervolume-Based Archiving Algorithms I: Effectiveness. In N. Krasnogor, & P. L. Lanzim (Eds.), GECCO 2011 (pp. 745-752). New York, NY: ACM. doi:10.1145/2001576.2001678.

Item is

Files

show Files

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

Details

show
hide
Language(s): eng - English
 Dates: 20112011
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 618721
DOI: 10.1145/2001576.2001678
URI: http://doi.acm.org/10.1145/2001576.2001678
Other: Local-ID: C1256428004B93B8-3DED5E5BC5A335DEC1257984004D9BA0-BringmannF2011
 Degree: -

Event

show
hide
Title: 2011 Genetic and Evolutionary Computation Conference
Place of Event: Dublin, Ireland
Start-/End Date: 2011-07-12 - 2011-07-16

Legal Case

show

Project information

show

Source 1

show
hide
Title: GECCO 2011
  Subtitle : Genetic and Evolutionary Computation Conference
Source Genre: Proceedings
 Creator(s):
Krasnogor, Natalio1, Editor
Lanzim, Pier Luca1, Editor
Affiliations:
1 External Organizations, ou_persistent22            
Publ. Info: New York, NY : ACM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 745 - 752 Identifier: ISBN: 978-1-4503-0557-0