Paper Info
Title
Convergence of hypervolume-based archiving algorithms ii: competitiveness
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.
Year
DOI
Venue
2012
10.1145/2330163.2330229
GECCO
Keywords
Field
DocType
greedy archiving algorithm,hypervolume-based archiving algorithms ii,competitive ratio,new archiving algorithm,generational mo-cma-es,convergence behavior,archiving algorithm,individuals online,future offspring,offspring generation,constant competitive ratio,evolutionary computing,performance,theory,multiobjective optimization,selection
Convergence (routing),Population,Mathematical optimization,Computer science,Algorithm,Multi-objective optimization,Artificial intelligence,Machine learning,Competitive analysis
Conference
Citations 
PageRank 
References 
3
0.40
14
Authors
2
Name
Order
Citations
PageRank
Karl Bringmann142730.13
Tobias Friedrich221113.48